2009/4/7 Adriaan van Kessel <adriaan.van.kes...@rivm.nl>: > > > computer-go-boun...@computer-go.org wrote on 07-04-2009 18:33:34: > >> Thanks. What about linked lists? >> They seem to be both compact and fast to merge and detect duplicates. >> Why have you abandoned them? > > Linked lists have a terrible cache behaviour: every pointer (or index) > dereference has a nearly 100% chance of causing a cache miss. > > Lists as arrays and bitmaps have the smallest cache footprint. > Not storing them at all, but recomputing them as David Fotland does > (only in the playouts) has no memory footprint at all.
It's quite easy and efficient to put all lists (cyclic, linked in one direction) of liberties (on one 19x19 board) into 4*19*19*sizeof (vertex) array. If vertex is int32 then it is about 1.5 kB. Is it too much for cache? Which cache we are talking about? Lukasz > > AvK > > > Disclaimer RIVM > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
