Can you give some more info about experimental setup and the algorithms you used?
On Thu, Apr 9, 2009 at 01:42, <w...@swcp.com> wrote: > Lukasz, > > My performance test suite did 7 ways of tracking liberties: > * dense linked lists, (where 4 * number of positions are allocated) I guess this is what gnugo-montecarlo implemented? > * sparse linked lists, (where 256 * number of positions are allocated) ? > * arrays of liberties, (256 * number of positions are allocated) Is it like regular gnugo board implementation. > * trivial pseudo-liberties like libego I guess. > * boesch computation for pseudo-liberties an link? > * bitsets one bit per board location per string? > * 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. one playout over and over again, or many randomized playouts? (you mention 324 moves) > * 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. can you elaborate on that? Does it apply to dense lists? In general I'm about to implement dense lists. What is slow about them in your implementation? (in playouts) > * 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, <w...@swcp.com> 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 >> >> 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/ >> > >> _______________________________________________ >> 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/ > _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
