Lukasz, My performance test suite did 7 ways of tracking liberties: * dense linked lists, (where 4 * number of positions are allocated) * sparse linked lists, (where 256 * number of positions are allocated) * arrays of liberties, (256 * number of positions are allocated) * trivial pseudo-liberties * boesch computation for pseudo-liberties * bitsets * bitsets, with each bit in a separate word.
I tested all of them using 2 techniques: * simple mc, (which never asked for the list of liberties for a group) Note that it also tests reseting the board in 3 ways. * ladder reading exercises, which asked for the liberties of a group and used undo. Results are were pretty striking. Below is raw data. Tests were on a 3 year old Core2. * for pure mc: simple pseudo liberties was by far the fastest. * for ladder reading: arrays of liberties was by far the fastest. * as noted in other emails, linked lists have horrible cache behavior. * So, as far as I can see the only question is whether you will do any classic reading or not, which will determine the best implementation. Michael Wing ------------------- DENSE LINKS normal 324 moves: total 3000 ms, each game 0.300000 ms, 3333.333333 games/sec undo 324 moves: total 3860 ms, each game 0.386000 ms, 2590.673575 games/sec reset 324 moves: total 3062 ms, each game 0.306200 ms, 3265.839321 games/sec ladder: total 3469 ms, each ladder 0.346900 ms, 2882.675123 ladders/sec SPARSE LINKS normal 324 moves: total 7109 ms, each game 0.710900 ms, 1406.667604 games/sec undo 324 moves: total 7703 ms, each game 0.770300 ms, 1298.195508 games/sec reset 324 moves: total 10890 ms, each game 1.089000 ms, 918.273646 games/sec ladder: total 8062 ms, each ladder 0.806200 ms, 1240.387001 ladders/sec BOESCH PSEUDO LIBERTIES normal 324 moves: total 2281 ms, each game 0.228100 ms, 4384.042087 games/sec undo 324 moves: total 3422 ms, each game 0.342200 ms, 2922.267680 games/sec reset 324 moves: total 2532 ms, each game 0.253200 ms, 3949.447077 games/sec ladder: total 5797 ms, each ladder 0.579700 ms, 1725.030188 ladders/sec SIMPLE PSEUDO LIBERTIES normal 324 moves: total 1985 ms, each game 0.198500 ms, 5037.783375 games/sec undo 324 moves: total 2328 ms, each game 0.232800 ms, 4295.532646 games/sec reset 324 moves: total 1922 ms, each game 0.192200 ms, 5202.913632 games/sec ladder: total 4890 ms, each ladder 0.489000 ms, 2044.989775 ladders/sec ARRAYS normal 324 moves: total 2578 ms, each game 0.257800 ms, 3878.975950 games/sec undo 324 moves: total 3313 ms, each game 0.331300 ms, 3018.412315 games/sec reset 324 moves: total 2703 ms, each game 0.270300 ms, 3699.593045 games/sec ladder: total 2703 ms, each ladder 0.270300 ms, 3699.593045 ladders/sec BITSET normal 324 moves: total 3453 ms, each game 0.345300 ms, 2896.032436 games/sec undo 324 moves: total 4203 ms, each game 0.420300 ms, 2379.252915 games/sec reset 324 moves: total 3828 ms, each game 0.382800 ms, 2612.330199 games/sec ladder: total 6735 ms, each ladder 0.673500 ms, 1484.780995 ladders/sec BITSET IN WORDS normal 324 moves: total 6172 ms, each game 0.617200 ms, 1620.220350 games/sec undo 324 moves: total 7203 ms, each game 0.720300 ms, 1388.310426 games/sec reset 324 moves: total 10157 ms, each game 1.015700 ms, 984.542680 games/sec ladder: total 7172 ms, each ladder 0.717200 ms, 1394.311210 ladders/sec > What other methods have you tried? > > Lukasz > > On Thu, Apr 2, 2009 at 17:14, <[email protected]> wrote: > > Isaac, > > > > I implemented about 6 way to track liberties, > > a couple years ago, and measured the running > > performance, and by far the best is also the > > simplest: keep an array of liberties for each > > chain, and do a simple linear search. > > > > This may seem slow, but it has a couple real > > advantages. First, it works with the cache > > to maximize locality. Second it is very simple. > > > > Michael Wing > > > >> > Many Faces also counts real liberties, and is quite fast enough. > >> > > >> > >> > > I can confirm, with a bit of optimization, counting real liberties is > >> > > only marginally slower than counting pseudo-liberties. So there's > >> > > really no benefit that I can see from using pseudo liberties. > >> > > > >> > > Mark > >> > > > >> > >> > > > When John Tromp and I were thinking about these things in 2007 we > >> > > > decided to switch to counting real liberties instead of > >> > > > pseudo-liberties. Someone (Rémi?) told us that in the end the > >> > > > performance difference wasn't very large, and we verified this. > >> > > > > >> > > > Álvaro. > >> > > > > >> > >> Thanks. What is a fast way to track liberties? > >> > >> I thought about bit arrays. Merging to groups would take O(1), counting > >> takes O(1)-ish, and memory required would be small. > >> > >> Of course I could also use STL's "set" structure, but I found it to be > >> quite slow - it implements a set using a RB-tree. This was actually the > >> reason I switched to pseudo libs. > >> > >> -ibd. > >> -- > >> Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: > > http://www.gmx.net/de/go/multimessenger01 > >> _______________________________________________ > >> computer-go mailing list > >> [email protected] > >> http://www.computer-go.org/mailman/listinfo/computer-go/ > >> > > > > > > > > -- > > > > > > > > _______________________________________________ > > computer-go mailing list > > [email protected] > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > _______________________________________________ > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ > -- _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
