Re: [gnugo-devel] more on dfa

[Arend Bayer]

> There are many ways to optimize the DFA:
>
> 1- use a reverse spiral and a stack to
> implement an incremental scanner
> as explained in the texinfo file.

I've tried to understand how you would implement this, and I think
there is one point missing in your explanation in the texinfo:

If there is, compared to the last DFA run, one additional stone placed,
you want to directly jump to that state (for each starting point and each
spiral orientation) in which the DFA was right before it visited the
intersection where this stone was placed.

However, in the current implementation, this would forget all patterns
that have been matched already before the respective DFA spiral reached this
position.

There is a clean way to solve this problem: Instead of having attributes
for all states, we could only have attributes for those states that have
a transition into the error state. I.e., only at the very end of the DFA
spiral we generate a list of all patterns that got matched.

These attributes could be handled by a separate list, that would be much
smaller because most states do _not_ have a transition to the error
state.

I am writing this because:
1. This could be implemented independently of the incremental matcher
(and would be a step towards it).
2. It would immediately have two benefits: Save some memory, make the
inner-most loop of the DFA simpler (because there is no longer a need to
check for the attribute), and it should have good cache benefits (there will
be four instead of five (short-)ints per dfa state, so more dfa states
fit into a cache line, and we get good alignment for free).

Now there's been a lot of DFA discussion, if we could only get s.th.
done, too... :-)

Arend