[gnugo-devel] DFA compile speedup (trevor_3_3.2)

[Trevor Morris]

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