Computer Chess Club Archives




Subject: How important is a big hash table? Measurements...

Author: Tom Kerrigan

Date: 00:49:21 03/29/03

I just finished a mess of tests, running my engine for 60 seconds/pos on a set
of 7 ECM positions that it solves in 30 to 60 seconds.

I used the hash table sizes 1, 2, 4, 8, 16, 32, 64, 128, 256.

The average depth being searched at 60 seconds was:
11.42, 11.71, 11.71, 11.71, 11.71, 11.71, 11.71, 11.71, 11.71
So increasing hash table size beyond a couple of MB won't make you search
significantly deeper.

The sum of times to solutions was:
361 (4/7 right), 342 (5/7), 329 (6/7), 321 (6/7), 310, 309, 309, 309, 313
In other words, increasing the size up to 16MB makes a huge difference, but
there's no benefit to going bigger.

The nodes/second times were:
1074k, 1074k, 1076k, 1077k, 1083k, 1084k, 1084k, 1079k, 1073k
So the biggest swing is 1%, so hash table size basically doesn't affect NPS. For
some reason speed seems to rise, peak at ~32MB, and fall. I can't explain that;
maybe it's just random.

I was curious about how full the hash table was getting, so I wrote some code to
count empty entries after the search and also to count the number of overwrites,
i.e., when data for one position is overwritten by data for another position.
For reasons that should be pretty clear, I only calculated these numbers for the
depth-replace hash table and not the always-replace hash table. I only got
statistics for (IMO) the most significant hash table sizes.

This is the hash table "fullness":
NA, NA, NA, 100%, 100%, NA, NA, NA, 44%

This is the percentage of writes that were overwrites:
NA, NA, NA, 30%, 27%, NA, NA, NA, 4%

It's interesting to note that the 16MB table is getting completely filled and 1
in 4 writes are overwrites, i.e., a lot of information is being lost, but it
performs as well as the 256MB table which gets less than half full and hardly
any information is lost.

In other words, it doesn't hurt to have a huge hash table, but anything more
than a surprisingly small table (~16MB = ~30% overwrites) likely isn't helping.
Contrary to Hyatt's assertion, it apparently doesn't matter if the hash table
fills up, or if it can hold the entire search tree.


This page took 0.08 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.