Re: [gnugo-devel] Persistent cache sizes

[Arend Bayer]

> 
> I don't know if this has already been discussed, my apologies in that case.
> 
> I made a couple experiments yesterday night by :
> - making GG replay its own color for something like a half-dozen of its
>   KGS and NNGS games
> - varying persistent reading and connection cache sizes
> 
> It was late and neglected to take notices, but I obtained the best timing
> results (--showtime) with both reading and connection cache sizes increased
> to 300, which speeded up the engine by up to 10%. Increasing the sizes
> further only gained a few 1/10 secs over a game, so it didn't seem worth
> the size overhead.

I don't think this has been discussed much, but it has been on my to-do-
(or rather to-try)-list for some time. I suppose increasing the cache
sizes to the sizes you suggest could be done immediately. But I guess
more could be gained by increasing them to, say, 1000, and rewriting all
the O(cache size) algorithms in the persistent caches.

This would involve:
1. Organizing them in a heap so that throwing the most worthless entry
out and inserting a new one is a O(log(n)) operation. 
[Don't we have someone on this list who likes to implement heaps? Hint,
hint...]
2. Computing a hash value (from the part of the board that is
guarantueed to be in the stored board, no matter how the surrounding of
the involved strings look like) to make cache lookup pretty much a
O(1) operation.

Testing whether this gives an additional speedup could be tested easily
by looking at the node counts for higher cache sizes.

Arend