Author: Tim Mann
Date: 13:18:05 09/15/99
Go up one level in this thread
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.
The trick for atomicity without locking is to xor all the other data into the
hash key and store the modified value in the table instead of the original key.
The entry's address is still computed from the original key. When you are
checking for a hit on a lookup, you read the entire entry and xor the modified
key with the other data to recover the original key, then compare that with the
hash of the position you are looking for.
To do this in Crafty required changing only a few lines of code. The main hash
tables consist of two 64-bit words, with word1 containing the data and word2 the
hash key. Basically the code changes from:
store(data, key)
{
Entry* entry = &table[key & MASK];
Lock();
entry->word1 = data;
entry->word2 = key;
Unlock();
}
lookup(key)
{
Entry* entry = &table[key & MASK];
Word word1, word2;
Lock()
word1 = entry->word1;
word2 = entry->word2;
Unlock();
if (word2 == key)
return word1
else
return NOT_FOUND;
}
}
To:
store(data, key)
{
Entry* entry = &table[key & MASK];
entry->word1 = data;
entry->word2 = data^key;
}
lookup(key)
{
Entry* entry = &table[key & MASK];
Word word1, word2;
word1 = entry->word1;
word2 = entry->word2;
if (word1^word2 == key)
return word1;
else
return NOT_FOUND;
}
Why does this technique let you access the table without a lock? Most of the
time, there will be no race and you'll read/write the table correctly.
Occasionally, there will be a race, and you'll read a garbage entry, consisting
of some data from one entry and some from (one or more) others. With high
probability, xoring these words together will not recover the key you were
looking for, so you will get a miss. There's also a possibility of *writing* a
garbage entry, if two writers race; again with high probability no one will ever
get a hit on such an entry. It will eventually be displaced by a good entry
that hashes to the same address.
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. (In fact, the probability of
a false hit on a garbage entry will be less, because the bits of the hash key
that determine the address get xor'ed with data too, so if you xor a garbage
entry, there is a strong chance that it will not even appear to be at the right
address, so no lookup could ever match it.)
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.