Re: [gnugo-devel] DFA rewrite

[Evan Berggren Daniel]

> > OK, so this may or may not be a great idea.  My knowledge of DFAs is
> > mostly from hand tuned small ones in assembly class.  They were fast
> > though ;)
> >
> > OK, so my thinking is that folding together has the disadvantage for large
> > state machines that you have, at least temporarily, memory usage
> > proportional to the product of the number of states in each of the two
> > machines, which could be unacceptably large during compilation.
> >
>
> The synchronized product is a brutal algorithm,
> we implented a hash table to reduce memory usage
> when combining big automata.
> This may not be optimal but it works well.

I'll probably use this at first then.  If it gets to be a problem, I'll
have to do something interesting.  Having a hashtable already available
would be decidedly useful...

>
>
> > So, we instead build the entire state machine, one state at a time.  Start
> > with state 1, the empty state.  Create 3 states corresponding to whether
> > the next position is black, white, or empty.  Check for each of those (and
> > store temporarily) what partial matches it corresponds to.  Store as part
> > of the machine any final matches it corresponds to.  Check the hash table
> > of partial matches for anything that is the same partial state; if there
> > is such, we just duplicated a state, throw the new one away.  You've now
> > created 3 new states; stick them at the end of the state machine and move
> > to the next state (state 2, which you just created, create 5, 6, 7, and
> > then do state 3).
> >
> > Of course, this mechanism precludes incremental compiles, which is not
> > particularly helpful.
>
>
> For me the main problem is not the construction of the DFA but the DFA
> itself.
> A lot of intersting approach may be considered to control memory usage
> with partially determinisitic machines.
>
> What will be your compression scheme ?

Two parts:

First, store minimal information.  Each state can be stored as 4 32bit
integers: where to go for each of black, white, and empty, and an output
code that gets translated in a separate table (could also do a state
machine here... hmm...) to produce a list of matches.

Second, don't compress that at all.  In fact, 16 bytes is a very
convenient number -- it lines up easily on cacheline boundaries, can be
shuffled about with SSE instructions if we decide to hand optimize, etc.

As for the output codes...  Instead of doing a list of codes, each with an
associated list of varying length of matches to report, Do a state table
-- each code has a single match to output, and a code for the ones left.
That might even be smaller, and is probably simpler.

Thoughts?

Thanks

Evan Daniel