Re: [gnugo-devel] DFA shuffle.

[Arend Bayer]

> 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.
>
> The main reason to change the DFA code to use incremental offsets
> is that it allows for bigger DFAs.  The current code breaks when
> compiling owl_attackpat with "-a".  This patch solves that problem.
>
> Performance-wise there is almost no difference - someone else should
> probably re-test that there is no performance penalty under GNU/Linux.

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.

Arend