Author: h.g.muller
Date: 04:01:14 02/07/06
Go up one level in this thread
I plead 'guilty' about the 8-fold rehash. I think I can add a lot to my defense, though: discarding hash entries by overwriting them should not be done too lightly. Entries are supposed to be valuable, if a hash-table miss due to this occurs later, the research will cost you dearly, probably a hundredfold or more compared to the time of a re-hash. A rehash can be extremely cheap. Modern CPUs have a cache-line of 64 bytes. If your hash-table entry is 16 bytes, every hash-table retrieval will bring 4 entries in the L1 cache. These entries can be searched almost for free, because the L1 access time is 20-50 times faster than DRAM access, and hash tables are usually so big that they fit in none of the caches and have to come from DRAM. Finally, if you make up to 8 tries to find an empty hash-table slot, this does not mean that you have to make 8 tries on every retrieval to find it back. The number of tries you have to do to find an empty slot is the inverse of the fraction of the table that is empty. So the first half of the table you enter in 1-2 tries, the next quarter in 2-4, the next 1/8 in 4-8 tries. On average only ~2.25 tries (ln 8 to be exact) for a table that is 7/8 full. And compared to the first try the next tries are 20 times cheaper... But of course one should not make thousands of retries.
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.