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

[Arend Bayer]

Gunnar wrote:
> Arend wrote:
> > I can see advantages in your approach. One thing you should look out for
> > is that hash collisions get more likely, so maybe we should then switch
> > to 96 or 128 bit hashing (of course you need to check whether we still
> > save memory then).
>
> My intuition is that this scheme wouldn't significantly increase the
> risk for collisions, but I wouldn't mind being convinced by some
> actual calculations.

My assumption was that Inge's scheme uses a 64-bit hash value to
identify board position, the routine, and the attacked/defended objects
(whereas now it's used to identify the board position).
But that's pretty much non-sense, as Inge can still store that
information in the actual entry.

> > (The replacement algorithm in persistent.c is clearly O(cache size).
> > Of course the same is true for the lookup.)
>
> We should improve those algorithms some day.

Yes.  Lookup is simple to improve, with a hash table. As for replacement,
I was so far not able to think of a non-messy solution that is not
O(cache size). But yes, it's certainly possible.

> > I think we should just store owl results in a separate hash table (which

> Splitting them up is reasonable, but not necessarily simpler in the
> end.

> > (To avoid the problem of "open nodes" we can do this _before_ we start
> > a new tactical reading tree, once the cache is 95% full.)
>
> I don't believe in this idea. For some cache size and some reading
> complexity (think high levels) the cache will overflow anyway and if
> we can't clear it on the fly the performance hit will be severe. The
> partial clearing scheme for the current cache was a major improvement,
> practically eliminating all cache related problems we were seeing at
> the time.

We can still have hashtable_partially_clear() as a fall-back.

I worry that this function might need too much time if we want to
increase the cache size. After all, it has to traverse all the 8MB of
the cache. (And leaves the processor cache behind in a state full of
uninteresting data -- so it's costs are higher than what you see in
profiles.)
Also, having the cache table cleared inmidst of an expensive computation
doesn't look clever to me.

Arend