Re: [gnugo-devel] more on dfa

[Dave Denholm]

Dave Denholm <address@hidden> writes:

> 
> 
> Well, anyway, what I have so far is that while building the dfa, each state
> has two attributes. One which lists the patterns matched at that node, and
> one which lists all the patterns matched up to and including that node.
> (The former is probably useless in the long term, but in the short term I
>  would ideally like to be able to run the engine in the old mode, asserting
>  that the pattern list accumulated is the same as the one stored in the dfa)
> 
> 
> 
> 
> I'm also trying to add a pattern to a dfa in situ, rather than making a new 
> dfa out
> of two input dfas. I'm hoping this will offset the performance problems
> of not using the pool of smaller dfas (since I am still assuming I add
> patterns one at a time, in order of increasing length).
> 
> The algorithm is then that product of (L,0) is just L itself. It does leave
> unreachable states in the dfa, but they can easily be pruned once at the end.
> (Does mean that the code for measuring the incremental size increases in the
> dfa is useless...)
> 
> Unfortunately, I've got a problem with my state cache for (0,R), which means 
> I end
> up appending the new pattern to each existing terminal state which can match
> it :-(
> 

I've got that fixed, and I now believe that I am generating correct DFA's.

Unfortunately, I see no significant performance benefit :-(

I'm now assuming that the problem is all the memory cache misses. Should be
possible to confirm this using the cpu performance counters.

So while the current code has extra stuff in the main loop, it all works
from cache and is cheap. Taking it out doesn't fix the main problem,
which is that all the scattered reads are expensive.

I think I saw somewhere that the latest pentiums have an instruction
which can read memory without forcing the whole line to be read into
cache. That might be useful, since in the new scheme, there is only
one memory read from each dfa state, so we don't want the cpu to stall
while it loads the whole line, when we usually won't want it.



dd
-- 
address@hidden          http://www.insignia.com