Re: [gnugo-devel] more on dfa

[Arend Bayer]

Tanguy wrote:

> Arend Bayer wrote:
> > However, in the current implementation, this would forget all patterns
> > that have been matched already before the respective DFA spiral reached this
> > position.
>
> The idea was to maintain for each intersection
> the list of matched patterns ids in memory
> (we must suppress the quicksort).

> We also keep a 2 integers stack for each intersection:
> the first entry of the stack gives the reached state at a given
> deepness, the
> second entry gives the position in pattern's ids list.
> With this system, we do not forget anything:
> we restart the scan from the last move and we update (if needed)
> the end of the list of mached patterns.

Maybe I misunderstand a little. Either you have to copy the list of
patterns matched-so-far at every single step in the DFA, which sounds
like a lot of overhead. Or you have to re-run the spiral to collect all
patterns that had previously been 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 would be happy to know the amount of states without
> out-transitions.
In owldefendpat.c, there are ~33000 states, and ~4600 of them have a
transition into the error state.

> If you are right this may be a good compression of the DFA.
> Can you explain how this list works ?
> Will you use a hash table ?
Yes, either that. Or the error state becomes "a very high number"
instead of 0, where this high number also encodes a pointer where to
look for the attribute list.

> > 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).
>
> huu ?
> We would need to check 4 integers at each step to see
> if there is an edge to the error state.
> Four tests instead of one,this is not what
> i call a simplification!
> However this is not so important, modern processors
> should be as fast with 1 or 4 tests.

Now this time you misunderstood me a little. The idea would be that
_all_ matched pattern can be extracted from the last state we were in
before we actually enter the error state.

Hmm, maybe this would however increase the size of the DFA. It is
practically the same as having multiple error states, with each carrying
the information which patterns got matched.

Arend