Re: [gnugo-devel] DFA shuffle.

[Trevor Morris]

At 10:31 AM 12/1/2002 +0100, you wrote:

>> http://www.public32.com/games/go/trevor_3_13.1
>>
>> - dfa_rt_t.next now stores offset to next state.
>> - shuffles DFA states to minimize jump size.
>> - shorten generated pattern files to avoid too many lines warning.
>>....
>I got a small performance increase. However, after reading the patch
>this suprised me a little: Browsing a little through e.g. the old
>owl_defendpat.c seemed to indicate good locality, i.e. there were many
>states with all arrows leading to the state right next in the table,
>which should of course be optimal cache-wise.
>
>After your patch, instead most arrows have similar "length" of 500-800
>instead.
>
>Maybe the good locality in the CVS version is only at places far down
>in the spiral, where we hardly ever get. Still it might be worth
>experimenting with dfa_shuffle() such that there are more frequent small
>jumps in the DFA.

Actually, I believe the old behavior was to have a jump for EMPTY always
be 1.  It certainly seems like that would be optimal.  I think the current
implementation of dfa_shuffle should go in, though.  The advantage
of being able to use "-a" is worth it.  If next[0] and next[1] can be made
to be <256 and next[2] and next[3] < 32k, the DFA size could shrink
again such that each state would be exactly 64 bits.  So, a more clever
shuffle algorithm would be useful.

It's not obvious that dfa_shuffle would do poorly cache-wise, when you
consider pipelining effects and successive iterations.

-Trevor