[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] DFA compile speedup (trevor_3_3.2)
From: |
Trevor Morris |
Subject: |
[gnugo-devel] DFA compile speedup (trevor_3_3.2) |
Date: |
Wed, 29 May 2002 09:44:09 -0400 |
http://www.public32.com/games/go/trevor_3_3.2
- improves DFA compile time by doing fewest possible large syncs
Two motivations for this patch:
* owl tuning became noticeably slower when DFA became standard, due
to fairly slow DFA compiles.
* I'd like to try out pre-rotating patterns to see how it affects performance
and DFA size. Faster DFA compiles will make this much easier.
Briefly, the old DFA builds would do a sync_prodcut on the entire DFA for
every string. This new code stores a number of smaller intermediate DFAs
into intermediate buckets (32 seemed to work best), by adding the strings
serially to each buckets. Finally, these buckets are merged in a binary
fashion (i.e. 32 -> 16 -> 8 -> 4 -> 2 -> 1), thus minimizing the number of
sync_products on large DFAs.
Note that all of the DFA functions used to take a dfa_t * parameter - this
is no longer used in dfa_add_string(..). The upshot is that it's only
possible to build one DFA at a time (without calls to init_dfa() ). I'm
not sure this wasn't the case before, and it's currently never attempted
anyway. Not sure it this is considered a problem.
I'm not certain that this patch is 100% correct, but the group's been so
quiet, and I'd like to get feedback. I lost my cable modem connection
to a thunderstorm a couple of days ago, so it's tough to update my
sandbox, which I last did on May 22. I've not yet determined if these
regression differences are due to this patch or were there prior:
owl:262: PASSED: correct: 0 answer: 0
trevora:290: FAILED: correct: !C8 answer: C8
nngs1:30: FAILED: correct: P17|O18 answer: N18
strategy:29: PASSED: correct: R4 answer: R4
viking:7: FAILED: correct: !T7 answer: T7
trevorb:660: PASSED: correct: D3 answer: D3
trevorc:1440: FAILED: correct: E12|F11 answer: E10
global:8: PASSED: correct: H9 answer: H9
global:9: PASSED: correct: F4 answer: F4
global:34: FAILED: correct: N6 answer: L6
arend:29: FAILED: correct: B14|C14 answer: F15
13x13:15: PASSED: correct: C7|B7|C6|B6|B5|C5 answer: C7
13x13:39: FAILED: correct: H4|J4 answer: E2
strategy4:181: FAILED: correct: F3 answer: O8
Cheers,
Trevor
- [gnugo-devel] DFA compile speedup (trevor_3_3.2),
Trevor Morris <=