Re: [gnugo-devel] DFA should be "best" NFA

[Dave Denholm]

Tanguy URVOY <address@hidden> writes:

> Hi,
> 
> I still not finished to write my phd :(
> But soon I will be free to help you again :)
> I have (too?) many ideas to speedup pattern matching.
> 
> 
> > Yes this is bad, and the problem will increase as processor speeds go up
> > (as scan_for_patterns is mostly memory latency bound, whereas the rest
> > of the code is mostly CPU bound). On what processor/RAM is this?
> > 
> 
> The best we can do is to touch memory
> one time for each test of the board.


I'd have thought that it is really only the first touch of
each line that matters. Once it's in the cache, it's fast.

Localising memory accesses is a good thing. Matching in rows
would be better than spiralling, though of course that doesn't
work for the rotations.

Would it be useful to revisit the approach of generating
a transform of the whole board, and then doing the matching
on the transformed board, rather than doing the transform
in the spiral order array ?


I've been wondering on and off about how to arrange things
to prefetch cache-lines to ensure that they are in memory
when we come to use them.

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