Re: [gnugo-devel] more on dfa

[Tanguy URVOY]

Arend Bayer wrote:
> 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.

Yes, this is the main principle.

> 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.


> 
> 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.

This is a good optimization of the DFA
to put the attributes only in the states with
an output transition to the error state.

> 
> 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.
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 ?


> I am writing this because:
> 1. This could be implemented independently of the incremental matcher
> (and would be a step towards it).

agreed.

> 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.

Still i dont know how we will seek for the attributes.

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

As soon as i have written my phd i will work on the incremental scheme.
But these are both long and difficult tasks ;^)
Maybe if someone else has time...


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