Author: Heiner Marxen
Date: 14:52:22 09/15/99
Go up one level in this thread
On September 15, 1999 at 16:18:05, Tim Mann wrote: >On September 15, 1999 at 14:02:49, Heiner Marxen wrote: > >>On September 15, 1999 at 09:00:08, Robert Hyatt wrote: >> >>>Tim Mann suggested a new hashing scheme that >>>is cute for SMP users, as it effectively eliminates the Lock()/UnLock() calls >>>without the danger of incorrect hash results. >> >>Would you please explain briefly, how this can be done (i.e. maintaining >>atomicity of shared multi word hash entries without lock/unlock) ? >>Sounds really interesting. > >Sure, glad to explain. Background: A hash table entry consists of some amount >of data about the position, plus a hash key. The hash key is a hash of the >position. To look up a position in the hash table, you compute the hash key, >compute an entry's address from the hash key, then look to see if the expected >key is stored in that entry slot. Because the hash is not a full >representation of the position, there is a small risk of a hash collision >(two different positions hashing to exactly the same key) causing a false hit >and a wrong value being returned from the table, but that's rare enough that >we're willing to live with it. [good explanation snipped] Great! >There is of course some chance of a false hit if you're extremely unlucky about >the value that gets produced by xoring a garbage entry. However, the >probability of this kind of false hit should be no greater than a hash >collision false hit, which we're already willing to accept. Aha. While we are willing to accept very rare false hits, this technique will work. If false hits are not at all acceptable, this will not work. Thanks for your great explanation. Heiner
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.