[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Inge Wallin
Subject: Re: [gnugo-devel] Improvement of the hash table in GNU go
Date: Fri, 7 Feb 2003 09:47:50 +0100

> 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.

I am afraid that you are totally off.  :-)

First, this check is impossible to do, unless we store the whole
position and the rest of the information in the hash table.  Granted,
this is possible to do, but it lowers the number of nodes in the table
significally.  We could, of course, do it for checking purposes, but 
 a) the program will be much, much slower and
 b) we will still not know the exact probability of collisions remove
    the extra information from the hash table and therefore can
    increase the number of nodes again.

Second, the calculations already show that given a 64 bit hash value,
and the number of nodes per second that we search, the risk is still
very small.  If you are interested, I can look up the exact
calculations in Breuker and present them to you.  I did it maybe a
year ago, and that mail is probably still in the mailing list archive


reply via email to

[Prev in Thread] Current Thread [Next in Thread]