Re: [gnugo-devel] Improvement of the hash table in GNU go

[Heikki Levanto]

On Wed, Feb 05, 2003 at 09:27:27PM +0100, Arend Bayer wrote:
> single array
>        cache[N].
> Each array entry consists of two entries that store
>  * the 64bit hash value,
>  * the other date we store now (komaster, routine, position)
>  * the result (of course :-) ),
>  * a cost function.

If I understood the idea right, the N will be the hashvalue modulus
cache-size. And the hash will already contain the position, komaster, and
routine. So we do not have to store the hash value - or if we trust it to be
good enough, we could skip the (position, komaster, routine).

I suggest that we add counters to check the frequency of hash collisions,
both collisions where two totally separate hashes give the same N, and where
different (p,k,r) give the same hash. With that data in hand we should be
able to increase N and possibly the number of bits in the hash, until
collisions are so rare that we can ignore them. Byt that time we can reclaim
the extra memory by dropping almost everything in the cache nodes. But we
had better leave the code in, so that we can debug the case where the cache
does play a trick on us...

Just my thoughts early morning, before the first coffee. If I am totally
off, I will welcome a correction.

-H

-- 
Heikki Levanto  LSD - Levanto Software Development   <address@hidden>