[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [gnugo-devel] DFA shuffle.

From: Trevor Morris
Subject: Re: [gnugo-devel] DFA shuffle.
Date: Sun, 01 Dec 2002 20:43:23 -0500

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

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


reply via email to

[Prev in Thread] Current Thread [Next in Thread]