Ticket #148 (new defect)

Opened 1 year ago

Last modified 7 months ago

Some upgrades

Reported by: draqo Assigned to: gnugo
Priority: normal Milestone: 3.8
Component: source Version:
Severity: minor Keywords:
Cc: patch: 1

Description

Ok. I'm creating a new ticket which holds changes from two of my previous tickets (nr 144 and 145). They should be closed.

There is a final relase upgrade, cache, board.c optimization and some small changes which I've done during code overlooking. Now I'll systematically go through all other engine files and optimize them and look for errors.

As for now I've found 2 of them:

1). One is in extended_chainlinks function, which was counting the string as neighbor itself (we didn't mark ourselves when both_colors were true). This caused one more regression test passed.

2). Second was in build_worms, where an origin was set for every vertex. Now it is set only for vertexes with stone on them. This change gives us two more regressions passed.

Passed regressions are (I don't remember which change gives which regression test passed): strategy2-55, arend-9, ninestones-280.

All other changes don't change a logic of the GnuGo? and gives us only a very little performance upgrade. Except one more: in komaster_trymove in scheme 2b and 4 komaster is reset only, when the owner of komaster plays at kom_pos - not when opponent plays them (I don't think that it changes anything, but it should be like that). I've done all regressions for these changes and it gives us 3 more passes as mentioned above. Other works the same as old version. I've also played about 100 games between old and new version and the result is near 50% won games.

There are no changes in performance for non-final release version, because I've added some more asserts and not optimized too much. When final release version is turned on it gives about 1,2% better performance.

Please accept these changes, because soon there will be much more :-) I've finished project in my job and now again will have some time for GnuGo?. My Master's Degree is late already... :)

Attachments

changes.diff (142.0 kB) - added by draqo on 11/28/06 23:50:20.
changes2.diff (97.1 kB) - added by draqo on 11/28/06 23:53:16.
doc.diff (40.2 kB) - added by draqo on 11/29/06 00:01:35.
code.diff (224.1 kB) - added by draqo on 12/30/06 22:07:52.
unnecessary inlines removed
worm1.diff (6.2 kB) - added by draqo on 12/31/06 19:04:39.
worm cleanup patch nr 1 (no logic changes) - apply after code.diff
unconditional.diff (13.8 kB) - added by draqo on 01/02/07 20:16:00.
cleanup patch nr 2 (apply after patch nr 1)
cleanup.diff (12.4 kB) - added by draqo on 01/22/07 21:46:46.
cleanup patch nr 3 (apply after patch nr 2)
vcproj.diff (176.3 kB) - added by draqo on 01/22/07 22:41:17.
Visual Studio patch (apply after cleanup patch nr 3)
reg_tests.diff (0.8 kB) - added by draqo on 01/23/07 01:05:54.
Regression tests changes after tickets 162-164
worm2.diff (14.0 kB) - added by draqo on 02/05/07 15:56:10.
worm cleanup patch nr 2 (no logic changes, added discarded moves) - apply to 3.7.11 ver and after all mine previous patches and tickets 162-164
matchpat.diff (21.8 kB) - added by draqo on 02/05/07 16:04:32.
matchpat.c cleanup patch (includes also minimal change in attack.db and defense.db) - apply after worm2 patch
vcproj-opt.diff (5.5 kB) - added by draqo on 02/06/07 15:42:12.
VisualC projects optimization enable patch
dfa.patch (65.9 kB) - added by draqo on 02/19/07 10:50:36.
Usage of DFA in all patterns and few errors corrected + small upgrade in owl_test_cuts
all-in-one.zip (121.0 kB) - added by draqo on 02/19/07 17:08:53.
All my patches in one file (from this ticket and 162, 163 and 164) - easier to apply and diffed with actual version of GnuGo?, which changed since my early patches
loops.patch (34.8 kB) - added by draqo on 02/24/07 15:10:34.
Loops optimization - and small cleanup in worm.c
worm3.patch (21.1 kB) - added by draqo on 03/07/07 14:19:36.
some cleanups - most in worm.c
worm4.patch (10.5 kB) - added by draqo on 03/07/07 23:38:27.
upgraded threat finding (+ small cleanup) - fix2.patch from ticket #163 is needed to don't change regression
worm5.patch (7.7 kB) - added by draqo on 03/08/07 17:56:19.
upgraded: attack_threats when liberties==1 and find_lunch - no changes in regression
cleanup2.patch (63.4 kB) - added by draqo on 03/15/07 10:55:38.
big cleanup
board-mem.patch (2.7 kB) - added by draqo on 03/15/07 11:06:26.
small cleanup in tables memory handling in board.c
all-in-one2.zip (144.5 kB) - added by draqo on 03/20/07 11:26:06.
all my patches in one file - end of my work

Change History

11/28/06 23:50:20 changed by draqo

  • attachment changes.diff added.

11/28/06 23:53:16 changed by draqo

  • attachment changes2.diff added.

11/29/06 00:01:35 changed by draqo

  • attachment doc.diff added.

(in reply to: ↑ description ) 11/29/06 00:04:24 changed by draqo

I splitted changes in 3 files, because looking through them in Trac worked really slow. Now it works only slow :-) I don't split it further because you want to have all changes in even one file.

(follow-up: ↓ 5 ) 12/09/06 01:48:18 changed by arend

Some comments on changes2.diff:

- I don't like the changes str->str_pos, and I am sure others don't like them either, otherwise it would have been done long ago. - Your "inline"s don't do anything mostly, as GCC can't inline functions when they are used in another file as the definition; OTOH, when they are in the same file, GCC probably does a better job at deciding whether to inline them or not than we do (as GCC has much more information). Also please don't inline not performance-critical functions, they only make code size bigger. - Please don't keep your changes consistent with the existing coding style. - To me, your changes from "deepest" to "most reliable" in the hashing code make no sense to me, but maybe I am misunderstanding s.th. "more reliable" to me implies the two entries refer to the same position, which they don't. - Please don't make logic changes in cleanup patches (adjust_level_offset). - Please don't clutter essential, but not at all time-critical functions as examine_position() with asserts to save time. - Please dont mix logic changes into a cleanup patch. Please don't.

I will stop here, at about half-way through the file.

(follow-up: ↓ 6 ) 12/09/06 01:49:47 changed by arend

Could you make two separate patches for the bugs (1) and (2) you listed above? Preferably in separate tickets.

(in reply to: ↑ description ; follow-up: ↓ 7 ) 12/09/06 01:52:25 changed by arend

Replying to draqo:

There are no changes in performance for non-final release version, because I've added some more asserts and not optimized too much. When final release version is turned on it gives about 1,2% better performance.

This is a trade-off. I prefer having 1.2% worse performance in released version and finding more bug this way by reports from users. This will be much better for GNU Go's strength and performance in the long run.

(in reply to: ↑ 2 ; follow-up: ↓ 9 ) 12/12/06 21:03:07 changed by draqo

- I don't like the changes str->str_pos, and I am sure others don't like them either, otherwise it would have been done long ago.

I think that this change is helpful, because you immediately know if variable is string number or string position (in board.c both are used).

- Your "inline"s don't do anything mostly, as GCC can't inline functions when they are used in another file as the definition; OTOH, when they are in the same file, GCC probably does a better job at deciding whether to inline them or not than we do (as GCC has much more information). Also please don't inline not performance-critical functions, they only make code size bigger.

I inlined only really small functions, where parameters passing is quite costly in comparison with function code. But yes, it doesn't give us nearly anything, because most of these funcions are called once for a move. I'll change it soon.

- Please don't keep your changes consistent with the existing coding style.

?

- To me, your changes from "deepest" to "most reliable" in the hashing code make no sense to me, but maybe I am misunderstanding s.th. "more reliable" to me implies the two entries refer to the same position, which they don't.

Most reliable is for one entry only (so for one position - exactly for positions with the same hashing code). Caching code stores in the entry the shallowest node (not the deepest) and if a depth is the same, it stores results from function with bigger cost (which analyze better) - that's why I changed variable name to "most_reliable".

- Please don't make logic changes in cleanup patches (adjust_level_offset). - Please dont mix logic changes into a cleanup patch. Please don't.

I'm looking through GnuGo? file by file, so it will be really difficult to split patch into logic and other changes patches. And I'm always writing, what logic changes I've made in ticket description.

(in reply to: ↑ 3 ) 12/12/06 21:04:50 changed by draqo

Replying to arend:

Could you make two separate patches for the bugs (1) and (2) you listed above? Preferably in separate tickets.

Ok. I could do this. I will made 3 tickets - one for bug (1), second for bug (2) and third for the rest of the changes. But I'll do it later.

(in reply to: ↑ 4 ) 12/12/06 21:07:54 changed by draqo

Replying to arend:

Replying to draqo:

There are no changes in performance for non-final release version, because I've added some more asserts and not optimized too much. When final release version is turned on it gives about 1,2% better performance.

This is a trade-off. I prefer having 1.2% worse performance in released version and finding more bug this way by reports from users. This will be much better for GNU Go's strength and performance in the long run.

That's why FINAL_RELEASE should be used only in important tournaments - once in the year or something. I wrote better descriptions of this in previous tickets (nr 144 and 145) - look there.

(in reply to: ↑ description ) 12/13/06 23:23:02 changed by gunnar

1). One is in extended_chainlinks function, which was counting the string as neighbor itself (we didn't mark ourselves when both_colors were true). This caused one more regression test passed.

That's clearly a bug.

2). Second was in build_worms, where an origin was set for every vertex. Now it is set only for vertexes with stone on them. This change gives us two more regressions passed.

Historically worms could also be built from empty points (aka caverns), but that was removed when it turned out not be of any use any longer. Nowadays it shouldn't make any difference at all and therefore the regressions point to bugs elsewhere in the code, at least some of which are addressed by ticket #155. Thanks for providing the hint. :-)

(in reply to: ↑ 5 ) 12/14/06 00:09:02 changed by arend

Replying to draqo:

- I don't like the changes str->str_pos, and I am sure others don't like them either, otherwise it would have been done long ago.

I think that this change is helpful, because you immediately know if variable is string number or string position (in board.c both are used).

Ah I see your point. However, in the rest of GNU Go, "str" always is a string position, so it would make more sense to me to always use "s" as a string number.

- Your "inline"s don't do anything mostly, as GCC can't inline functions when they are used in another file as the definition; OTOH, when they are in the same file, GCC probably does a better job at deciding whether to inline them or not than we do (as GCC has much more information). Also please don't inline not performance-critical functions, they only make code size bigger.

I inlined only really small functions, where parameters passing is quite costly in comparison with function code. But yes, it doesn't give us nearly anything, because most of these funcions are called once for a move. I'll change it soon.

But GCC knows that, too. Generally speaking, unless you really know what you are doing (as in knowing that the compiler does the wrong decision on a common platform), it is much better to leave inline decisions to the compiler these days.

12/30/06 22:07:52 changed by draqo

  • attachment code.diff added.

unnecessary inlines removed

12/30/06 22:16:31 changed by draqo

I've added new patch, in which I removed unnecessary inlines. In everything else it's identical to changes.diff and changes2.diff (it's just in one file now).

12/31/06 19:04:39 changed by draqo

  • attachment worm1.diff added.

worm cleanup patch nr 1 (no logic changes) - apply after code.diff

01/02/07 20:16:00 changed by draqo

  • attachment unconditional.diff added.

cleanup patch nr 2 (apply after patch nr 1)

01/22/07 21:43:04 changed by draqo

I realized, that regression tests can differ, depending on how much memory we assign for cache. And when I changed it to standard value (-1) I got one more regression passed (due to extended_chainlinks or build_worms change) - trevorb:140.

01/22/07 21:46:46 changed by draqo

  • attachment cleanup.diff added.

cleanup patch nr 3 (apply after patch nr 2)

01/22/07 22:41:17 changed by draqo

  • attachment vcproj.diff added.

Visual Studio patch (apply after cleanup patch nr 3)

01/22/07 22:45:20 changed by draqo

I've just added Visual Studio 2005 patch. It includes new solution and project files. But also it removes memory leaks - with exception when exit is called. And it adds to sgfnode.c isascii function to avoid asserts in isspace.

(follow-up: ↓ 14 ) 01/23/07 00:19:53 changed by draqo

After previous patches, tickets 162, 163 and 164 should be applied now. After adding these 3 tickets, regression tests changes to: filllib.tst:35 PASSED semeai.tst:47 PASSED trevord.tst:680 FAILED nngs4.tst:270 PASSED 9x9.tst:650 PASSED

After applying changes from one of these tickets there are possibly more passes or failures, but combination of all of them gives the above results. When I made changes from ticket 162 I got some unexpected failures and I was working them out, because I REALLY don't want any of them (which I couldn't achieve because of trevord.tst:680 - it gives failure because of different semeai move valuation - a result of semeai is the same). After repairing some failures I got another and this iterating process leads finally to all 3 tickets - that's why these tickets should be treated as 1 really (they are splitted for easier reading).

01/23/07 01:05:54 changed by draqo

  • attachment reg_tests.diff added.

Regression tests changes after tickets 162-164

(in reply to: ↑ 13 ; follow-up: ↓ 15 ) 01/23/07 01:51:01 changed by draqo

Replying to draqo:

After previous patches, tickets 162, 163 and 164 should be applied now. After adding these 3 tickets, regression tests changes to: filllib.tst:35 PASSED semeai.tst:47 PASSED trevord.tst:680 FAILED nngs4.tst:270 PASSED 9x9.tst:650 PASSED

I forgot to add regression tests changes. Now they are in reg_tests.diff patch. For 13x13c:43 K12 gives same results as G13. As for strategy2:55, B13 is good move too, maybe even better than C12, because it gives white better shape, black D15 group can't make 2 eyes anyway (the fight is really complicated but I couldn't make 2 eyes - my level is about 3 or 4 kyu - GnuGo? can't make them too) and B15 dragon wins semeai with C18. Anyway, GnuGo? generates C12 now, so it should be one more unexpected PASS, if you don't agree with me on B13 move.

(in reply to: ↑ 14 ) 01/23/07 01:55:57 changed by draqo

Replying to draqo:

Anyway, GnuGo? generates C12 now, so it should be one more unexpected PASS, if you don't agree with me on B13 move.

I made a mistake - it generates B13, so it should be expected fail, if you don't agree.

(follow-up: ↓ 17 ) 01/23/07 19:23:23 changed by draqo

Hmm... I've seen a second ago, that some patches were applied to GnuGo? recently. And what I'm asking is when my patches would be applied? The longer the time will be the bigger probability that these patches won't match actual files in GnuGo?. I know that they are big, but most of this code doesn't change any logic. Beside of that I tested all of them very good - make regression tests, play several games and everything is working ok. As for me you can choose to not apply any of them at all, because this work is for Masters Degree, but I want to give something from me more than straight work to school and it would be nice, when it will be used by you in GnuGo?. I am interested in AI and I'm doing this because I really want GnuGo? to play better and it gives me some satisfaction :-) You can cut, what you don't like, but apply at least logic changes, please...

(in reply to: ↑ 16 ; follow-ups: ↓ 18 ↓ 19 ) 01/24/07 00:08:30 changed by gunnar

Replying to draqo:

Hmm... I've seen a second ago, that some patches were applied to GnuGo? recently. And what I'm asking is when my patches would be applied? The longer the time will be the bigger probability that these patches won't match actual files in GnuGo?. I know that they are big, but most of this code doesn't change any logic. Beside of that I tested all of them very good - make regression tests, play several games and everything is working ok. As for me you can choose to not apply any of them at all, because this work is for Masters Degree, but I want to give something from me more than straight work to school and it would be nice, when it will be used by you in GnuGo?. I am interested in AI and I'm doing this because I really want GnuGo? to play better and it gives me some satisfaction :-) You can cut, what you don't like, but apply at least logic changes, please...

As I said in a comment to ticket #145 a prerequisite for accepting non-trivial patches is a copyright assignment to the Free Software Foundation for the changes, see http://lists.gnu.org/archive/html/gnugo-devel/2006-09/msg00011.html.

When it comes to the patches I'm generally not enthusiastic about the non-functional code changes. On the other hand the doc improvements look useful, as do the functional code changes. More specifically on the latter #162 is a step in the right direction although I probably don't agree with all details, #163 looks very interesting, and #164 is probably a good idea.

(in reply to: ↑ 17 ) 01/24/07 11:12:12 changed by draqo

Replying to gunnar:

As I said in a comment to ticket #145 a prerequisite for accepting non-trivial patches is a copyright assignment to the Free Software Foundation for the changes, see http://lists.gnu.org/archive/html/gnugo-devel/2006-09/msg00011.html.

It isn't a problem. Just tell me what I should send to you.

When it comes to the patches I'm generally not enthusiastic about the non-functional code changes. On the other hand the doc improvements look useful, as do the functional code changes.

I know that not all are valuable. Eg. like assigning to some temporary variables values which are accessed more than once or twice (values like table[xx].field1 - to which access means 3 reads from memory) - but it gives us at least one less read from memory and the code often looks easier to read for human. But some changes gives us more, eg. using memcpy instead of for loop. And there are some new comments, where not everything was easy to understand and took me a time to analyze. I think all of them gives us at least a very little enhancement in speed, code organization or readability of the code - sometimes very little indeed, but when I'm analyzing the code line by line, such ideas comes to the head, so why not apply them :-)

(in reply to: ↑ 17 ) 01/24/07 11:20:27 changed by draqo

Replying to gunnar:

More specifically on the latter #162 is a step in the right direction although I probably don't agree with all details, #163 looks very interesting, and #164 is probably a good idea.

As for 162 tell with what you don't agree (write it in #162).

And about #164: Look on the new pattern CC505, defend_both is used there. If the old version of the function would be used, this pattern would make dragons for worms, which you could connect only, when you would win a ko - and this situation definitely shouldn't be treated as one dragon. Changes in all other places, where the defend_both is used, should make this change even more valuable.

(follow-up: ↓ 21 ) 01/24/07 15:58:49 changed by nando

Hi draqo,

I see that you haven't logged on KGS in a long time, so that's probably the reason why you didn't get my message: there's a room under 'Social' named 'GNU Go Hackers'. Gunnar, Arend, Alain and I are relatively often there and you are cordially invited to join us there.

Other than that, I also have many comments about your proposed patches, but I think it's useless to discuss about those, as long as you haven't done the necessary paperwork (did you get in touch with Daniel Bump about this procedure?)

(in reply to: ↑ 20 ) 01/24/07 17:40:30 changed by draqo

Replying to nando:

I see that you haven't logged on KGS in a long time, so that's probably the reason why you didn't get my message: there's a room under 'Social' named 'GNU Go Hackers'. Gunnar, Arend, Alain and I are relatively often there and you are cordially invited to join us there.

I'll log there soon :-)

Other than that, I also have many comments about your proposed patches, but I think it's useless to discuss about those, as long as you haven't done the necessary paperwork (did you get in touch with Daniel Bump about this procedure?)

I don't know the procedure and I want to contact him. By mail or how?

02/05/07 15:56:10 changed by draqo

  • attachment worm2.diff added.

worm cleanup patch nr 2 (no logic changes, added discarded moves) - apply to 3.7.11 ver and after all mine previous patches and tickets 162-164

02/05/07 16:04:32 changed by draqo

  • attachment matchpat.diff added.

matchpat.c cleanup patch (includes also minimal change in attack.db and defense.db) - apply after worm2 patch

(follow-up: ↓ 23 ) 02/05/07 16:12:46 changed by draqo

After examining matchpat I am curious, why DFA pattern matching isn't always used? Is sometimes it takes longer than a normal matching with a grid optimization?

(in reply to: ↑ 22 ) 02/05/07 20:16:50 changed by gunnar

Replying to draqo:

After examining matchpat I am curious, why DFA pattern matching isn't always used? Is sometimes it takes longer than a normal matching with a grid optimization?

If I remember correctly it can require a significant amount of memory, which isn't always justified when doing non time critical pattern matching.

02/06/07 15:42:12 changed by draqo

  • attachment vcproj-opt.diff added.

VisualC projects optimization enable patch

02/19/07 10:50:36 changed by draqo

  • attachment dfa.patch added.

Usage of DFA in all patterns and few errors corrected + small upgrade in owl_test_cuts

02/19/07 10:53:23 changed by draqo

Ok. I've changed all patterns to use DFA. It uses about 800 kB memory more and in these times it is a small amount - the time is much more important. Due to this I've changed some things in dfa and mkpat and corrected some errors, too. Also I had to change throw_in_atari_helper and cutstone2_helper from helper to autohelper because of constant offsets inside these functions (pattern ED40 didn't work anyway because it was rotated and didn't match these offsets).

I've optimized DFA too, which hasn't been done for a really long time and added a note in the documentation about optimizing to remind it :-) After the optimization some patterns becomes rotated differently and an order of matching them changed. Due to this some regression results changed too. I've corrected this by adding counting of liberties in owl_test_cuts, but it also gives one unexpected fail (anyway, some other patterns' rotation could give this fail too) - but 2 unexpected passes are bigger than the fail (passes are: strategy4:205, ninestones:700 and the fail is: handtalk:15).

Also my signed copyright assignments arrived in Boston and finally my patches could be applied :-)

02/19/07 17:08:53 changed by draqo

  • attachment all-in-one.zip added.

All my patches in one file (from this ticket and 162, 163 and 164) - easier to apply and diffed with actual version of GnuGo?, which changed since my early patches

02/19/07 20:21:54 changed by draqo

Regression changes after all-in-one patch are (these were written in patches descriptions, but I want to gather them in one place): - filllib:35 PASS - semeai:47 PASS - strategy4:205 PASS - nngs4:270 PASS - ninestones:280 PASS - ninestones:700 PASS - 9x9:650 PASS - trevord:680 FAIL - handtalk:15 FAIL

The program is working faster, too. After some rough tests I got 8% faster result (enabling FINAL_RELEASE gives even better result) - but this must be analyzed more precisely.

02/24/07 15:10:34 changed by draqo

  • attachment loops.patch added.

Loops optimization - and small cleanup in worm.c

03/07/07 14:15:46 changed by draqo

After previous patches, tickets #168, #169, #170, #171 and #172 should be applied now (upgrade.patch from ticket #163 have to be applied too). After adding these tickets, regression tests changes to: nngs2.tst:600 PASSED 9x9.tst:120 PASSED global:44 PASSED nicklas3:1403 PASSED ninestones:260 PASSED 13x13:64 FAILED nngs2.tst:150 FAILED 9x9.tst:197 FAILED. So we have 5 new passes and 3 new failures - but passes are in majority and best 3 of them are bigger than failures.

After applying changes from one of these tickets there are possibly more passes or failures, but combination of all of them gives the above results - it's like in comment from 01/23/07 00:19:53.

03/07/07 14:19:36 changed by draqo

  • attachment worm3.patch added.

some cleanups - most in worm.c

03/07/07 23:38:27 changed by draqo

  • attachment worm4.patch added.

upgraded threat finding (+ small cleanup) - fix2.patch from ticket #163 is needed to don't change regression

03/08/07 17:56:19 changed by draqo

  • attachment worm5.patch added.

upgraded: attack_threats when liberties==1 and find_lunch - no changes in regression

03/15/07 10:55:38 changed by draqo

  • attachment cleanup2.patch added.

big cleanup

03/15/07 11:03:47 changed by draqo

I added ticket 173.

03/15/07 11:06:26 changed by draqo

  • attachment board-mem.patch added.

small cleanup in tables memory handling in board.c

03/20/07 11:26:06 changed by draqo

  • attachment all-in-one2.zip added.

all my patches in one file - end of my work

03/20/07 11:42:48 changed by draqo

Ok. My work finally comes to the end. I've attached a file, where all my patches are - these from tickets: 148, 162, 163, 164, 168, 169, 170, 171, 172 and 173.

Results are:

- 2% slower work, but enabling FINAL_RELEASE gives about 1,5% faster work and then the speed is almost the same

- unexpected PASSES (19): filllib:35, viking:1, nicklas3:1403, trevorc:410, global:44, semeai:47, strategy4:205, nngs2:600, nngs4:270, strategy5:295, ninestones:260, ninestones:280, ninestones:340, ninestones:700, thrash:26, 9x9:120, 9x9:300, 9x9:640, 9x9:650

- unexpected FAILURES (5): nngs:700, trevord:680, handtalk:15, nngs2:150, 9x9:197

- after playing 200 games between a recent version (in CVS) and my new version the result is 102:98 to my version (both players played 100 games as black and 100 as white)

So a result of the regression is significantly better, but unfortunately it doesn't have influence on overall level of GnuGo?. I think, that with more aggresive player strength of the new version would be bigger, but it must be tested in real life :)

Last thing is copyright assignments from my University. I have a meeting in next week, on which I should get this assignment and after another few days it should get to Boston. I'll write, when all this bureaucracy comes to the end.

04/19/07 13:55:46 changed by draqo

Finally I managed to meet with somebody on my University to get copyright assignments. I sent them today, so in few days (maybe more) they should arrive in Boston. I'll write, when this happens.

(follow-up: ↓ 36 ) 04/19/07 20:37:19 changed by arend

Have you measured whether using DFA for all the pattern databases actually speeds up the program? I doubt it, actually.

(follow-up: ↓ 37 ) 04/19/07 20:40:33 changed by arend

Why are you changing DEFAULT_MEMORY to -1?

(follow-up: ↓ 38 ) 04/19/07 20:42:42 changed by arend

What are you trying to do with SIZEOF_INT? I don't think we want to add code to take care of machines with int size smaller than 4, if that's what you are trying to do.

(follow-up: ↓ 39 ) 04/19/07 20:44:00 changed by arend

As I said earlier: let's keep str for string positions in board.c/board.h, that's what str is used for in the rest of GNU Go. If somewhere str is used for a string number, that should be fixed.

(follow-up: ↓ 40 ) 04/19/07 20:52:44 changed by arend

Can you explain why the new VC project files are needed? I know nothing about VC, but we used to have one/two developers using VC, my understanding was it used to work.

(follow-up: ↓ 41 ) 04/19/07 21:26:18 changed by arend

I think board-mem.patch is wrong, it reduces data locality and my bet is it is more likely to cause a slowdown than a speedup.

(in reply to: ↑ 30 ) 04/23/07 13:12:15 changed by draqo

Replying to arend:

Have you measured whether using DFA for all the pattern databases actually speeds up the program? I doubt it, actually.

I measured a time only after using DFA in all pattern databases. And it speeds it up quite a lot. But I don't remember now how much exactly.

(in reply to: ↑ 31 ) 04/23/07 13:22:06 changed by draqo

Replying to arend:

Why are you changing DEFAULT_MEMORY to -1?

Because it uses then a default value saved in a program. It's nearly 8 MB used when DEFAULT_MEMORY==8. But only nearly - not the same - and this could lead to different regression results, when cache is different sized. I decided to unify this, because in Visual config.h it was -1 and in Linux config.h it was 8 (if I remember correctly).

(in reply to: ↑ 32 ) 04/23/07 13:23:25 changed by draqo

Replying to arend:

What are you trying to do with SIZEOF_INT? I don't think we want to add code to take care of machines with int size smaller than 4, if that's what you are trying to do.

It is used for machines with int bigger than 4 bytes, too.

(in reply to: ↑ 33 ) 04/23/07 13:26:52 changed by draqo

Replying to arend:

As I said earlier: let's keep str for string positions in board.c/board.h, that's what str is used for in the rest of GNU Go. If somewhere str is used for a string number, that should be fixed.

When somebody new is looking on the board code it is really confusing. And now both You and new GnuGo? programmers won't have this problem. It will be clear if it is a number or not. But it's up to You to leave it as it was...

(in reply to: ↑ 34 ) 04/23/07 13:28:31 changed by draqo

Replying to arend:

Can you explain why the new VC project files are needed? I know nothing about VC, but we used to have one/two developers using VC, my understanding was it used to work.

Because there is new VC version and it uses different format for projects. I couldn't work on old version.

(in reply to: ↑ 35 ; follow-up: ↓ 42 ) 04/23/07 13:46:27 changed by draqo

Replying to arend:

I think board-mem.patch is wrong, it reduces data locality and my bet is it is more likely to cause a slowdown than a speedup.

It reduces locality but speeds up a program, because memory doesn't need to be allocated at each call to functions. It could be better cached, too. I tested using static and local tables in a small program and results was... no difference :-) Or in error margin. But I think if it would change something (on other compilers, systems, etc.), it change it on plus.

(in reply to: ↑ 41 ; follow-up: ↓ 44 ) 04/23/07 16:57:23 changed by arend

Replying to draqo:

Replying to arend:

I think board-mem.patch is wrong, it reduces data locality and my bet is it is more likely to cause a slowdown than a speedup.

It reduces locality but speeds up a program, because memory doesn't need to be allocated at each call to functions. It could be better cached, too. I tested using static and local tables in a small program and results was... no difference :-) Or in error margin. But I think if it would change something (on other compilers, systems, etc.), it change it on plus.

The memory doesn't need to be allocated, the array is just put on the stack. Anyway, in case it is unclear whether this is a speedup, then always the more maintainable code wins, which is the current version.

(follow-up: ↓ 45 ) 04/23/07 17:19:10 changed by arend

loops.patch is definitely wrong. This kind of optimization is done by every modern compiler (if it isn't, file a bug with your compiler), AND your change makes the code less readable.

(in reply to: ↑ 42 ) 04/23/07 19:54:36 changed by draqo

Replying to arend:

Replying to draqo:

Replying to arend:

I think board-mem.patch is wrong, it reduces data locality and my bet is it is more likely to cause a slowdown than a speedup.

It reduces locality but speeds up a program, because memory doesn't need to be allocated at each call to functions. It could be better cached, too. I tested using static and local tables in a small program and results was... no difference :-) Or in error margin. But I think if it would change something (on other compilers, systems, etc.), it change it on plus.

The memory doesn't need to be allocated, the array is just put on the stack. Anyway, in case it is unclear whether this is a speedup, then always the more maintainable code wins, which is the current version.

Array is put on the stack, so it is allocated - not by an user but by a program. If you don't want just don't apply this patch :)

(in reply to: ↑ 43 ; follow-up: ↓ 46 ) 04/23/07 19:57:11 changed by draqo

Replying to arend:

loops.patch is definitely wrong. This kind of optimization is done by every modern compiler (if it isn't, file a bug with your compiler), AND your change makes the code less readable.

I don't think so. But... just don't apply. You could make some tests by yourself, too.

(in reply to: ↑ 45 ; follow-up: ↓ 47 ) 04/24/07 01:41:20 changed by arend

Replying to draqo:

Replying to arend:

loops.patch is definitely wrong. This kind of optimization is done by every modern compiler (if it isn't, file a bug with your compiler), AND your change makes the code less readable.

I don't think so. But... just don't apply. You could make some tests by yourself, too.

I thought it might be nicer to explain why I don't think it is worth applying...

See, I am not an expert in low-level optimization at all, but over the years working on GNU Go I have learned a bit here and there. For example, I know that a loop variable k that is only used to index an array never actually appears in the compiler output. Try looking at the (optimized) assembler output of a compiler that has that option, and you will see. This is such a common optimization that every compiler that wasn't able to do that would be completely horrible at SPEC etc.

As a general rule, low-level optimization of C code is pretty much not worth it anymore, and not for GNU Go in particular:

  • Unlike us coders, often the compiler knows which processor it is compiling the code for, and knows a lot more about that than we have ever heard. (Try learning what the scheduler of a compiler does if you don't believe me.)
  • Even if you are lucky with one particular optimization and trick the compiler into generating more efficient code (which is essentially what you are trying to do), then there is no guarantee that the same will happen with a different compiler, or a new version of the same compiler.
  • A lot of code in GNU Go is hardly performance critical, but will have to be maintained for a long time, and get changed many times during that period. So maintainability is more important than miniscule performance improvements.

Also, we are not asking you to do anything that we wouldn't do for our own patches. When I try a performance optimization, I will test this as a single patch changing only one thing (not throwing several possible improvements together), and post detailed numbers showing the performance improvements, all measured on an otherwise idle computer.

(in reply to: ↑ 46 ; follow-up: ↓ 48 ) 04/24/07 15:23:09 changed by draqo

Replying to arend:

Replying to draqo:

Replying to arend:

loops.patch is definitely wrong. This kind of optimization is done by every modern compiler (if it isn't, file a bug with your compiler), AND your change makes the code less readable.

I don't think so. But... just don't apply. You could make some tests by yourself, too.

I thought it might be nicer to explain why I don't think it is worth applying...

Ok, it's not a problem :-)

See, I am not an expert in low-level optimization at all, but over the years working on GNU Go I have learned a bit here and there. For example, I know that a loop variable k that is only used to index an array never actually appears in the compiler output. Try looking at the (optimized) assembler output of a compiler that has that option, and you will see. This is such a common optimization that every compiler that wasn't able to do that would be completely horrible at SPEC etc.

I read a book on it, but it was many years ago and it gave just a general rule, that pointers are faster than indexing by a variable. I have a little knowledge about compilers, but my upgrade can only give better results or make no difference in time. And readability is, I think, similar - it depends rather on style of coding. So I'm leaving decision to apply this patch to you. I thought that this could make GnuGo? working faster, but if you are sure that all standard compilers do this optimization, it doesn't need to be applied.

(in reply to: ↑ 47 ) 04/24/07 22:28:28 changed by gunnar

Replying to draqo:

I read a book on it, but it was many years ago and it gave just a general rule, that pointers are faster than indexing by a variable. I have a little knowledge about compilers, but my upgrade can only give better results or make no difference in time. And readability is, I think, similar - it depends rather on style of coding. So I'm leaving decision to apply this patch to you. I thought that this could make GnuGo? working faster, but if you are sure that all standard compilers do this optimization, it doesn't need to be applied.

Pointers were faster than indexing in the past. 8 years or so ago I gained quite a bit of performance by optimizing some convolver code that way. But it has changed. Today the recommendation is to use indexing rather than pointers because it allows the compiler the optimize more aggressively; with pointers it's much harder to e.g. determine whether they may overlap. For simple cases like here it's unlikely to make a difference either way though.

For readability I see no question about indexing being far more obvious. My convolver code, by the way, became completely unreadable from the optimizations.

(follow-up: ↓ 50 ) 04/25/07 01:06:36 changed by arend

draqo added infrastructure to free all malloc()'d memory before exiting. I think it's perfectly fine to just exit and let the OS do the clean-up, but I have no strong opinions on that. Any other opinions?

(in reply to: ↑ 49 ; follow-up: ↓ 51 ) 04/25/07 10:07:27 changed by draqo

Replying to arend:

draqo added infrastructure to free all malloc()'d memory before exiting. I think it's perfectly fine to just exit and let the OS do the clean-up, but I have no strong opinions on that. Any other opinions?

I added this, because it allows checking if there are any memory leaks somewhere. Visual C writes information about it, when the program is exiting. But there was many intended memory leaks now and it makes check impossible. So I repaired it and now, when somebody writes a new code with malloc, he can check if he is freeing memory properly (in function, which allocates memory in each move, it must be freed properly).

(in reply to: ↑ 50 ; follow-up: ↓ 52 ) 04/27/07 01:26:28 changed by arend

Replying to draqo:

Replying to arend:

draqo added infrastructure to free all malloc()'d memory before exiting. I think it's perfectly fine to just exit and let the OS do the clean-up, but I have no strong opinions on that. Any other opinions?

I added this, because it allows checking if there are any memory leaks somewhere. Visual C writes information about it, when the program is exiting. But there was many intended memory leaks now and it makes check impossible. So I repaired it and now, when somebody writes a new code with malloc, he can check if he is freeing memory properly (in function, which allocates memory in each move, it must be freed properly).

I understand that, but this kind of checking is special to Visual C, and there are better memory leak tests available on other platforms (e.g. valgrind can check whether there is unreferenced unfreed memory at program exit). So I don't think the memory leak checking by itself is worth the extras complication in the code.

(in reply to: ↑ 51 ; follow-up: ↓ 54 ) 04/27/07 10:42:44 changed by draqo

Replying to arend:

Replying to draqo:

Replying to arend:

draqo added infrastructure to free all malloc()'d memory before exiting. I think it's perfectly fine to just exit and let the OS do the clean-up, but I have no strong opinions on that. Any other opinions?

I added this, because it allows checking if there are any memory leaks somewhere. Visual C writes information about it, when the program is exiting. But there was many intended memory leaks now and it makes check impossible. So I repaired it and now, when somebody writes a new code with malloc, he can check if he is freeing memory properly (in function, which allocates memory in each move, it must be freed properly).

I understand that, but this kind of checking is special to Visual C, and there are better memory leak tests available on other platforms (e.g. valgrind can check whether there is unreferenced unfreed memory at program exit). So I don't think the memory leak checking by itself is worth the extras complication in the code.

How much extra compilation is this comparing to the whole program? Few lines to many thousands. I don't think that this is any argument... And on other platforms are other tools, but they will show actual unfreed memory, too.

(follow-up: ↓ 55 ) 04/28/07 12:21:18 changed by draqo

Ok.My assignment arrived finally in Boston,so now patches could be applied :-)

(in reply to: ↑ 52 ) 05/03/07 23:47:12 changed by arend

Replying to draqo:

How much extra compilation is this comparing to the whole program? Few lines to many thousands. I don't think that this is any argument... And on other platforms are other tools, but they will show actual unfreed memory, too.

It is not about extra code in the compiled program, it is about making the source code a tad more complicated, which should never be done without a good reason.

(in reply to: ↑ 53 ; follow-up: ↓ 56 ) 05/03/07 23:49:12 changed by arend

Replying to draqo:

Ok.My assignment arrived finally in Boston,so now patches could be applied :-)

It would REALLY help for that if you could post single-issue patches as separate tickets, as I have done for various stuff.

We really don't want to apply patches that do various unrelated things, there are many reasons not to do so.

(in reply to: ↑ 55 ) 05/05/07 00:33:06 changed by draqo

Replying to arend:

Replying to draqo:

Ok.My assignment arrived finally in Boston,so now patches could be applied :-)

It would REALLY help for that if you could post single-issue patches as separate tickets, as I have done for various stuff. We really don't want to apply patches that do various unrelated things, there are many reasons not to do so.

I can't do that, because I don't have time. Sorry. I posted most of upgrades in different files and for all important changes created new tickets. All that I can do now is apply all changes manually (by writing in the code)... But I'll leave it for you, because I don't know, which changes you like and which you don't like. Really, I think that all this changes should be applied (without loops patch and eventually board-mem patch), but you have sometimes strange (for me) arguments. But this is your project and you are deciding. Choose what you like - all changes are throughoutly tested.

(follow-up: ↓ 58 ) 05/09/07 10:00:19 changed by draqo

I saw that you add one of my patches :-) But there is a lot more. If you don't want, don't add any that doesn't change any regression (but at least some of them are helpful, some repairs errors - especially in DFA matcher, and there are new Visual Studio files). It would be nice if my work doesn't come to nothing. Anyway, there are few that change regression: nr #162, #163, #164, #168, #169, #170, #171, #172 and #173 - and I think that 19 PASSES and 5 FAILS are good result. But these patches works best combined together, because some of them repairs failures that some others generate. As for now I don't see any activity on these patches. Does somebody overlooked them?

(in reply to: ↑ 57 ) 05/09/07 22:24:30 changed by gunnar

Replying to draqo:

Anyway, there are few that change regression: nr #162, #163, #164, #168, #169, #170, #171, #172 and #173 - and I think that 19 PASSES and 5 FAILS are good result.

Yes, that's good results.

But these patches works best combined together, because some of them repairs failures that some others generate.

Been there, done that. When you've combined a series of modifications iteratively to fix failures the end result is not very predictable. E.g. suppose patch A fixes something but introduces new failures, patch B fixes those failures and introduces some of its own, and patch C finally fixes the latter without bad side effects. Then it may well happen that patch C is great on its own, A and C together does everything that all three patches do, and B in fact is no good. So we will cherrypick and test out things first separately and then in combination if needed.

As for now I don't see any activity on these patches. Does somebody overlooked them?

There's more going on than meets the eye but our time is limited too so things are moving slowly. Most of the current action is to be found in the regressiontest tab (see the upper right of the navigation bar) where regression results for patches are reported. Many of the patches still need to be rediffed so that they apply cleanly for (semi-)automated testing.

05/09/07 22:32:07 changed by gunnar

For the record, all-in-one2.zip applies cleanly on top of r2379. It doesn't build cleanly on Linux due to init_sockets() being #defined to emptiness but that's easily fixed. The regression delta agrees with the previously stated 19 PASS / 5 FAIL, more precisely

filllib:35      PASS A8 [A8|B8]
viking:1        PASS O15 [O15]
nicklas3:1403   PASS H9 [J6|H9]
nngs:700        FAIL K18 [K17]
trevorc:410     PASS G12 [G12]
global:44       PASS D5 [D5]
semeai:47       PASS 1 0 R9 [1 0 (PASS|T11|T9|R9|T10|R10|R11)]
trevord:680     FAIL R15 [S16]
strategy4:205   PASS P11 [P11]
handtalk:15     FAIL M19 [J3]
nngs2:150       FAIL J18 [M3|L3]
nngs2:600       PASS B5 [B5]
nngs4:270       PASS M1 [!P5]
strategy5:295   PASS J2 [J2]
ninestones:260  PASS B16 [B16]
ninestones:280  PASS S2 [R1|S1|S2]
ninestones:340  PASS H4 [H4]
ninestones:700  PASS K15 [K15]
thrash:26       PASS A1 [E1|A1]
9x9:120         PASS F1 [F1]
9x9:197         FAIL D8 [E8|H5]
9x9:300         PASS D2 [D2]
9x9:640         PASS A8 [A8|G6|J6]
9x9:650         PASS E1 [E1]
19 PASS
5 FAIL
Total nodes: 1735615389 3337766 12649478 (+2.3% +0.043% +2.7%)

10/24/07 21:14:10 changed by gunnar

  • milestone changed from 3.7.11 to 3.8.