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

[Tanguy URVOY]

Trevor Morris wrote:
>
> 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.

Good idea!!
this "divide to conquer" strategy should speedup
the compilation process.

Another speedup could be to
use incremental DFA compilation:

(1) Store precompiled bucket-DFAs for sets of patterns in a a file.
(2) Test before compiling which patterns have been modified or added.
(3) Rebuild each modified bucket-DFA
(4) Mix old non-modified bucket-DFA's with the new ones.

> 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 do not exactly understand this problem,
i will understand after a look to the code.

> 
> 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 will read it cerfully :)

-- 
-------------------------------------
Tanguy Urvoy http://www.turvoy.fr.st
-------------------------------------