kbhearn wrote:bob wrote:kbhearn wrote:
That makes no sense. A fixed-size hash table has the same number of entries whether single or multi. They should fill up at exactly the same rate.
Indeed they do fill at the same rate, but while there are empty spots it's more likely that a random node will find one if it hits a multientry bucket in a 50% used HT than if it hits a single entry bucket in a 50% used HT.
the single entry has 2 states per bucket: used/unused - if you hit used you're pushing something out. Hence 50% filled is exactly 50% chance to have to push something out.
the 4-entry has 5 states: 0/4, 1/4, 2/4, 3/4, 4/4 - only 4/4 forces you to replace something. but if half the buckets are at 4/4 in a 50% full table that'd mean the other half the buckets were at 0/4. very unlikely unless you have an error in your code. Hence at 50% filled, there is < 50% chance of having to push something out with a multientry bucket.
edit: to extend this to something truly useful, you could replace 'filled' with 'would prefer not to replace' in the above arguments provided you have some method to detect the things that you don't mind being gone (such as age, depth)
You are overlooking one key. There are 1/4 as many buckets as there are entries. So you are just as likely to find a full bucket as you are a single used entry. The advantage is that with the bucket, you get a choice of what to replace, saving better entries.
No, i'm not overlooking that...
single entry: 1024 buckets of 1 entry, 512 used
4-entry: 256 buckets of 4 entries, total 1024 entries. if 128 of those buckets are 4/4 filled, then 128 of them are 0/4 at 512 used. very statistically unlikely.
When the table is 1/2 full, there is not a lot of overwriting going on. Or do you believe that your Zobrist numbers are poor enough that you don't evenly distribute hash signatures across the table?
You can easily test this. And yes, this bucket approach should result in a table with fewer unused entries. But it won't be a lot better. The issue is not just overwriting, but having a choice in what you overwrite.
You could (I will try to do this myself and post results) run with a table size of 1M entries. After doing 1M stores (with all different keys, so don't count the stores where the signatures match) loop over the table to see how many unused entries there are...
For my first run, I used 1M entries (16mbytes) with the normal 4 bucket approach. I'm giving two numbers on each line. First is number of actual stores done for different signatures, second is percent full for the table:
stores_done=1048576 used=80
stores_done=2097152 used=98
stores_done=3145728 used=99
stores_done=4194304 used=99
stores_done=5242880 used=99
stores_done=6291456 used=100
stores_done=7340032 used=100
stores_done=8388608 used=100
stores_done=9437184 used=100
stores_done=10485760 used=100
stores_done=11534336 used=100
stores_done=12582912 used=100
stores_done=13631488 used=100
stores_done=14680064 used=100
stores_done=15728640 used=100
stores_done=16777216 used=100
stores_done=17825792 used=100
stores_done=18874368 used=100
stores_done=19922944 used=100
stores_done=20971520 used=100
To make it simple, the next set of data uses 4M entries (1M buckets) but only the first entry of a bucket is used or checked, so still 1M usable entries but now no buckets to help spread the data over the table.
stores_done=1048576 used=62
stores_done=2097152 used=84
stores_done=3145728 used=94
stores_done=4194304 used=97
stores_done=5242880 used=99
stores_done=6291456 used=99
stores_done=7340032 used=99
stores_done=8388608 used=99
stores_done=9437184 used=99
stores_done=10485760 used=99
stores_done=11534336 used=99
stores_done=12582912 used=99
stores_done=13631488 used=99
stores_done=14680064 used=99
stores_done=15728640 used=99
stores_done=16777216 used=99
stores_done=17825792 used=100
stores_done=18874368 used=100
stores_done=19922944 used=100
stores_done=20971520 used=100
Observations. with 4 entry buckets, after 3M stores done the hash table is 99% used. With 1 entry buckets, it takes 5M stores to reach that point. This is not so significant. Both fill the hash table within 5M nodes, less than a factor of two difference between them. Beyond that point, there is no difference.
For a quick comparison in search efficiency with these, same position, searched to same depth, but with the second using 4x the memory to make the hash tables equal in entries.
time=5.35(100%) nodes=24458569(24.5M) fh1=92% nps=4.6M
time=15.25(100%) nodes=69474405(69.5M) fh1=92% nps=4.6M
So, both use 1M entries, one with 4 entry buckets, one with 1 entry buckets. Both get hash to 99%+ full, but notice the speed difference. A factor of 3x slower for the one-probe hash algorithm, because it has no choice in what it overwrites.
That's where the gain comes from, having a choice and making a wise one, rather than filling the table better...