RE: [computer-go] Chains and liberties - performance

["Mark Boon" <tesuji@xxxxxxxxx>]

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of Arend Bayer
> Sent: Sunday, November 14, 2004 22:12
> To: computer-go
> Subject: [computer-go] Chains and liberties - performance
>
>
>
>
> On Sun, 14 Nov 2004, Mark Boon wrote:
>
> > I've done a quick implementation along the lines I described. I
> found that
> > along with the marking of the merged chain in the chain array,
> all I need to
> > do is adding those same points to an array of integers.
> Although it has to
> > do this for all stones in the chain, I don't see how keeping
> cyclic lists is
> > going to beat that. I may be wrong of course. (And I have
> somehow gotten to
> > hate making linked-lists, so I suppose I'm a bit biased here.)
>
> > I'm not too enthousiastic about the speed. A quick test seemed
> to point to a
> > little over 0.5 million moves per second, including taking back
> those same
> > moves. 2 uSec per move doesn't compare too well with my
> ladder-module, which
> > is more than twice the speed and does a whole lot more. So using it for
> > ladders is not an option. But maybe for the other tactial readers and
> > life-and-death it is, provided I can optimize the current implementation
> > still.
>
> Just as a data point:
> For a life and death test set (owl.tst) of GNU Go, I get 296000 moves
> per second. According to a profile run, gnugo spends 14.2 % of that time
> updating the board data, and 3.3% in the undo function. So that would be
> 1.7 Million moves per second for the board library alone.
> This is on a Pentium M 1.4GHz (appr. as fast as a Pentium 2.4GHz on
> usual benchmarks, but I dont know about gnugo).
>
> Here is the data it keeps track of in this time:
>
> /* Incremental string data. */
> (Only one copy for each string.)
> struct string_data {
>   int color;                       /* Color of string, BLACK or WHITE */
>   int size;                        /* Number of stones in string. */
>   int origin;                      /* Coordinates of "origin", i.e. */
>                                    /* "upper left" stone. */
>   int liberties;                   /* Number of liberties. */
>   int libs[MAX_LIBERTIES];         /* Coordinates of liberties. */
>   int neighbors;                   /* Number of neighbor strings */
>   int neighborlist[MAXCHAIN];      /* List of neighbor string numbers.  */
> };
>
> static int string_number[BOARDMAX];
> (The id of each string for each board positioin to refer to the data
> above.)
>
> static int next_stone[BOARDMAX];
> (The circular list to traverse a string that Gunnar talked about.)
>
> Plus of course some (cheap) global data (ko position, "komaster" state,
> 64bit hash value, # of captured stones).
>

Thanks, that gives me an idea.

Still, it's hard to compare numbers like this. (Vincent would probably say:
see, Java is three times slower!) I run on a 900Mhz AMD, so how to compare?
Only possible when running on the same hardware I suppose. Do you have a
simple app I can run? (I don't have Linux by the way, nor a C compiler)

Some simple optimization (of which removing the Stack synchronization was
the biggest by far) gives me now 0.8 million per sec. My guess is 1 million
is kind of the limit of the algorithm on my hardware.

Seems your module does a little more than mine does, as I don't keep the
neighbours. I think both are going to be in the same ball-park.

So far I run the default Sun JRE that comes with Eclipse. I don't know if
choosing another JVM is going to make a lot of difference. It used to make a
lot of difference some years ago, but I'd expect them to converge over time.


_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/