Author: Robert Hyatt
Date: 20:08:38 09/15/99
Go up one level in this thread
On September 15, 1999 at 17:52:22, Heiner Marxen wrote: >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 Note that if false hits are not at all acceptable, hashing can not be used at all... because there is _definitely_ a non-zero probability of collisions. But Tim's scheme does solve the issue by basically destroying entries where a race to store occurs... which is ok. And the performance improvement is non-trivial to boot...
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.