Author: Dan Newman
Date: 12:18:06 09/23/98
Go up one level in this thread
On September 23, 1998 at 08:14:16, Pat King wrote:
>
>On September 22, 1998 at 14:54:11, Dan Newman wrote:
>
>[snip]
>>I once measured the hashing error rate for an old program of
>>mine (I think it was doing on the order of 100 knps). For
>>a 29 bit hash code I was getting between 600 and 900 errors
>>per second. At 33 bits I was getting 0-8 errors per second.
>>(By errors I mean undetected collisions in which two different
>>positions hash to the same code.) So, 32 bits isn't nearly
>>enough. I made a guesstimate that 64 bits give me about
>>1 error in 1.5 years of runtime--that is perhaps overkill,
>>but if we go down just a few bits, then we get a few errors
>>per day or hour... (At 41 bits I was getting maybe one
>>error per minute.)
>>
>>The trick I used to measure error rate is to mask off
>>some bits of the hash code and use those that are left
>>for the index and key. The bits that were masked off were
>>used to check for an error. Maybe I could put that more
>>clearly... When comparing the key stored in the hash table
>>entry with the key for the position, do it twice. Once
>>ignoring some bits and once again with all the bits:
>>
>> if( (entry.key & 0x1fffffff) == (key & 0x1fffffff) ) {
>> if( entry.key != key ) nerrors++;
>> //etc.
>> }
>>
>>With 3 bits masked off we have a 29-bit hash code (assuming
>>we start with 32 bits). This trick fails to detect about 1/8
>>of the errors you would get with a 29-bit hash code because we
>>have only the 3 masked off bits to do the check. If we
>>mask down a 64 bit hashcode to 32 bits we catch virtually all
>>the errors this way.
>>
>>-Dan.
>Aha! If everyone does it this way, I understand my confusion. I routinely use
>half my key to detect collisions as you do above in your test; it didn't occur
>to me that anyone would try "flying blind".
>
>Pat
Well, I do this too. Perhaps our terminology is different. I typically
use the lower 19 or 20 bits of my "hash code" as an index into the table,
and I store the upper 48 bits in my hash table entry as a "key". Some
people call this the "lock"; I used to call it the "signature". The
business above was just my attempt at an expanation of the way I measured
the hashing error rate--not the way I ordinarily probe my hash table.
(Actually I wasn't flying blind above because I still retained a portion
of my key/lock.)
-Dan.
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.