Computer Chess Club Archives


Search

Terms

Messages

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

Author: Omid David Tabibi

Date: 02:48:41 03/29/03

Go up one level in this thread


On March 29, 2003 at 03:49:21, Tom Kerrigan wrote:

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

Could you please mention which 7 ECM positions were you using? I will try to
conduct your tests using Genesis, as it provides very detailed statistics
regarding the hash table.

Omid.



>-Tom



This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

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