Hashing and caching upgrade + scan_board + lot of small changes

[draqo]

I upgraded files cache.c/h and hash.c/h. The main change is that tt_update replaced the newest node even when that node was stored in the most_reliable (I changed names too) node or the added node total_cost was lower. After that I counted stats for 10 games of the old and new version of the program and average hits per move got better - old version had 110420 hits (89785 trusted) and new 128846 (104325).

Beside that there is lot of small changes that don't change mechanics of the program. Sometimes they are really small like change from x++ to ++x :-) But when I read the code line by line and saw something I made changes (I'm sometimes perfectionist :)

One change that have some impact is a new macro named scan_board. It scans each vertex of the board and run some code for them. It is faster than old for loop and testing if a field is GRAY - on 19x19 the difference is minimal but on 9x9 is bigger.

Also I have 2 questions: 1). When new patches are applied? Only when new version is released or earlier - when somebody accepts it? 2). When I post a patch and later change something in the same file and want to post second patch these 2 patches will have a lot in common and checking them and applying would cause some problems. What should I do - wait for the first patch to be accepted, delete the first patch and post only second (maybe in both places) or something else?

[gunnar]

I upgraded files cache.c/h and hash.c/h. The main change is that tt_update replaced the newest node even when that node was stored in the most_reliable (I changed names too) node or the added node total_cost was lower. After that I counted stats for 10 games of the old and new version of the program and average hits per move got better - old version had 110420 hits (89785 trusted) and new 128846 (104325).

More importantly, what does it do to the overall speed?

Beside that there is lot of small changes that don't change mechanics of the program. Sometimes they are really small like change from x++ to ++x :-) But when I read the code line by line and saw something I made changes (I'm sometimes perfectionist :)

Please don't. You're not the only perfectionist here and changes to a different style won't be accepted, only slow reviewing down.

One change that have some impact is a new macro named scan_board. It scans each vertex of the board and run some code for them. It is faster than old for loop and testing if a field is GRAY - on 19x19 the difference is minimal but on 9x9 is bigger.

It is also fits badly with idiomatic C constructs and looks like it might be nightmarish to step through in a debugger. See http://lists.gnu.org/archive/html/gnugo-devel/2004-12/msg00126.html and comments for an earlier proposal on the same theme.

Also I have 2 questions: 1). When new patches are applied? Only when new version is released or earlier - when somebody accepts it?

When one of the maintainers accepts it. Exactly when that happens is not so easy to predict though. Some factors that are involved:

• Complexity of the patch.
• Whether the patch is controversial in some way.
• Impact of the patch.
• Available time. Unfortunately it tends to be quite limited for all maintainers.

Additionally there's a strict requirement on completed paperwork for new contributors (also mentioned in http://lists.gnu.org/archive/html/gnugo-devel/2006-09/msg00011.html) unless the patches can be considered trivial.

2). When I post a patch and later change something in the same file and want to post second patch these 2 patches will have a lot in common and checking them and applying would cause some problems. What should I do - wait for the first patch to be accepted, delete the first patch and post only second (maybe in both places) or something else?

The first and most difficult trick is to try to make small and isolated changes. :-)

When that's not possible the best solution is to post an updated patch, leaving the previous one behind. This is much simplified by grouping the patches by functionality, not by file. See #132 for an example.

[draqo]

Replying to gunnar:

I upgraded files cache.c/h and hash.c/h. The main change is that tt_update replaced the newest node even when that node was stored in the most_reliable (I changed names too) node or the added node total_cost was lower. After that I counted stats for 10 games of the old and new version of the program and average hits per move got better - old version had 110420 hits (89785 trusted) and new 128846 (104325).

More importantly, what does it do to the overall speed?

When we get more hits, the whole program works faster. It needn't to compute again the same position.

Beside that there is lot of small changes that don't change mechanics of the program. Sometimes they are really small like change from x++ to ++x :-) But when I read the code line by line and saw something I made changes (I'm sometimes perfectionist :)

Please don't. You're not the only perfectionist here and changes to a different style won't be accepted, only slow reviewing down.

Hmm. ++x is faster than x++, so it isn't only style - but it works only for objects with operator++ and here it doesn't apply because it's only C code. I'm a professional programist in C++ and when I see things like that I have desire to change it :-) But OK, I'll leave it as it is. But isn't good idea to remain sticked to this style - better change it to ++C style :) Beside of that, I don't change anything in style - the indentation is awful (I think, because of narrow console in Linux) and there lacks many clear lines between some part of the code and reading of this code is sometimes really painful...but I won't change anything. I'm not a masochist to change 1.5 MB of indentations ;-)

One change that have some impact is a new macro named scan_board. It scans each vertex of the board and run some code for them. It is faster than old for loop and testing if a field is GRAY - on 19x19 the difference is minimal but on 9x9 is bigger.

It is also fits badly with idiomatic C constructs and looks like it might be nightmarish to step through in a debugger. See http://lists.gnu.org/archive/html/gnugo-devel/2004-12/msg00126.html and comments for an earlier proposal on the same theme.

I look in these comments. I checked this macro and old for loop and macro works faster (at least on Visual C++) - on 19x19 it's about 2% difference but on 9x9 it works 3 times faster. Also it doesn't use memory like the idea with an array. But the argument about debugging is good. One can preprocess this code to resolve defines and then debug, but... I think I could change it to an inline iterator which works with the same idea as this macro, but I have to check it for speed first. And a good argument for defining macro or function is that when something changes in the board implementation one would have to change something only in one place, not in dozens.

The first and most difficult trick is to try to make small and isolated changes. :-) When that's not possible the best solution is to post an updated patch, leaving the previous one behind. This is much simplified by grouping the patches by functionality, not by file. See #132 for an example.

As for me it isn't so simple because I'm going through whole code line by line and maybe I will change some things in more than one place in a file and these changes won't be connected too much. But it will turn out later...

[gunnar]

Replying to draqo:

Replying to gunnar:

More importantly, what does it do to the overall speed?

When we get more hits, the whole program works faster. It needn't to compute again the same position.

Yes, sure, I agree that it should be a win, but it would be nice to have hard numbers and see that nothing unexpected breaks. Have you found out yet how best to run the regression tests?

the indentation is awful (I think, because of narrow console in Linux)

It shouldn't be. It's written with indentation depth 2 and traditional tab stop settings every 8th space. Does your editor by any chance have a tab width of 4?

One change that have some impact is a new macro named scan_board. It scans each vertex of the board and run some code for them. It is faster than old for loop and testing if a field is GRAY - on 19x19 the difference is minimal but on 9x9 is bigger.

It is also fits badly with idiomatic C constructs and looks like it might be nightmarish to step through in a debugger. See http://lists.gnu.org/archive/html/gnugo-devel/2004-12/msg00126.html and comments for an earlier proposal on the same theme.

I look in these comments. I checked this macro and old for loop and macro works faster (at least on Visual C++) - on 19x19 it's about 2% difference but on 9x9 it works 3 times faster.

Measured how? The time to run empty loops is not very interesting and as far as I'm aware there are no time-critical board loops in the code. Unless there's a measurable overall speed difference the relevant aspects are readability, debugability, and error-proneness.

Also it doesn't use memory like the idea with an array. But the argument about debugging is good. One can preprocess this code to resolve defines and then debug, but...

Indeed. Possible in theory but a pain in practice.

I think I could change it to an inline iterator which works with the same idea as this macro, but I have to check it for speed first. And a good argument for defining macro or function is that when something changes in the board implementation one would have to change something only in one place, not in dozens.

We've been through that when changing from 2D arrays to 1D arrays a long time ago now. The conversion could have been faster with aggressive use of macros but I'm not so sure it would really have made the code better in the long run. In my opinion they should be used carefully.

The first and most difficult trick is to try to make small and isolated changes. :-) When that's not possible the best solution is to post an updated patch, leaving the previous one behind. This is much simplified by grouping the patches by functionality, not by file. See #132 for an example.

As for me it isn't so simple because I'm going through whole code line by line and maybe I will change some things in more than one place in a file and these changes won't be connected too much. But it will turn out later...

To speed up review it's helpful to have logically grouped patches. I tend to have a working copy of the code with a lot of small unrelated experimental changes, some of which turn out to be ineffective, some bad, and some good. When I've determined that some change is of the latter kind I make a diff of the whole tree and manually pick out the relevant parts (which may span several files and exclude other changes in those files). The edited diff I apply to a clean working copy, verify that it does work as expected on its own, and then generate a new diff (the edited one is usually off on line numbers and doesn't always apply cleanly).

[draqo]

I had a lot of work in my job recently. I don't have too much time for GnuGo?. But I've done something and now I'm moving this and previous ticket to a new ticket. This should be closed.

And some replies to this ticket:

the indentation is awful (I think, because of narrow console in Linux)

It shouldn't be. It's written with indentation depth 2 and traditional tab stop settings every 8th space. Does your editor by any chance have a tab width of 4?

I worked in Visual Studio and it had different tab width. That's why I was seeing that as awful indentation :-)

One change that have some impact is a new macro named scan_board. It scans each vertex of the board and run some code for them. It is faster than old for loop and testing if a field is GRAY - on 19x19 the difference is minimal but on 9x9 is bigger.

It is also fits badly with idiomatic C constructs and looks like it might be nightmarish to step through in a debugger. See http://lists.gnu.org/archive/html/gnugo-devel/2004-12/msg00126.html and comments for an earlier proposal on the same theme.

I look in these comments. I checked this macro and old for loop and macro works faster (at least on Visual C++) - on 19x19 it's about 2% difference but on 9x9 it works 3 times faster.

Measured how? The time to run empty loops is not very interesting and as far as I'm aware there are no time-critical board loops in the code. Unless there's a measurable overall speed difference the relevant aspects are readability, debugability, and error-proneness.

I run it with xor command inside, which is really fast.

[gunnar]

Ok, closing this ticket as a duplicate of #148.