Platform Independent Lockless Hashing

[Pradu]

The lockless hashing technique described here assumed 64-bit atomic operations:

Code: Select all

typedef struct _hashEntry
{
   U64 hashkey;
   U64 data;
}hashEntry;

void storeEntry(hashEntry* h)
{
   hashEntry* volatile bucket = hashtable + ((h->hashkey)%HT_SIZE);
   bucket->hashkey = h->hashkey^h->data;
   bucket->data = h->data;
}

Does the compiler translate the 64-bit xor into two 32-bit xors and the 64-bit store into two 32-bit stores for 32-bits exe? If so, this will still work assuming 32-bit or 16-bit or 8-bit atomic operations right?

[H.G.Muller]

Tricky! In a 32-bit environment the stores will be translated as 32-bit stores. But the CPU will apply write-combining to the stores.

The truly atomic operation from the hardware point of view is a 64-bit store, as the FSB is 64-bit wide. But I don't think there are any memory controllers that actually allow interruption of a burst cycle, which stores 8 consecutive 64-bit words (one cache line).

I guess to be absolutely safe in a 32-bit environment, you would have to use an FPU store. The best way to force a compiler to use one is

Code: Select all

void AtomicStore(double *source, double *destination)
{ *destination = *source; }


and then call it with the source a pointer to the u64 you want to store, casted to (doouble *) to avoid compiler complaints.

Btw, another way to do lockless hashing is simply make sure the lock is distributed over the two (or more) atomic stores. With a 32-bit signature, you could put 16 bits of it in each of the two words, and there would only be a 1 in 64K probability of a corrupted entry to bhave a valid signature.

[Pradu]

Tricky! In a 32-bit environment the stores will be translated as 32-bit stores. But the CPU will apply write-combining to the stores.

The truly atomic operation from the hardware point of view is a 64-bit store, as the FSB is 64-bit wide. But I don't think there are any memory controllers that actually allow interruption of a burst cycle, which stores 8 consecutive 64-bit words (one cache line).

I guess to be absolutely safe in a 32-bit environment, you would have to use an FPU store. The best way to force a compiler to use one is

Code: Select all

void AtomicStore(double *source, double *destination)
{ *destination = *source; }


and then call it with the source a pointer to the u64 you want to store, casted to (doouble *) to avoid compiler complaints.

Btw, another way to do lockless hashing is simply make sure the lock is distributed over the two (or more) atomic stores. With a 32-bit signature, you could put 16 bits of it in each of the two words, and there would only be a 1 in 64K probability of a corrupted entry to bhave a valid signature.

I think I mis-phrased what I wanted to say. What I meant was that perhaps you don't need to worry about how may bits the atmoic operations deal with at all. Lets say it's 32-bit code and hashEntries h1 and h2 are being stored at the same time into the same bucket. lets say this happens:

Code: Select all

hashtable_hashKey_low32 = h1_hashkey_low32;
hashtable_hashKey_low32 = h2_hashkey_low32;
hashtable_hashKey_high32 = h2_hashkey_high32;
hashtable_hashKey_high32 = h1_hashkey_high32;

So when you are probing the hashEntry, the lock key won't match up if stores happen out of order. I think the lockless hashing works regardless of how many bits are messed around with in the atmoic operations. Nevertheless, I'm not quite sure if my assumptions on how the processor/compiler works this out is correct...

Your suggestion of using cast to double is quite interesting. I'll try it out.

[Tony van Roon-Werten]

The lockless hashing technique described here assumed 64-bit atomic operations:

...

No, it doesn't. It basicly depends on detroying the hashtable entry when the store wasn't atomic.


Tony

[H.G.Muller]

Lockless hashing is basically a check-sum technique (CRC redundancy check), that invalidates entries that are chimeras made up from different interfering stores. This can be done without extra bits for the checksum, as it will in practice be sufficient to change the signature into another valid signature for mixed entries, as the chances that such a valid signature will satisfy a request is next to zero. (In addition, if you sore a 64-bit signature, there are already a lot of redundant bits in this, namely the ones from which you derived the index.)

As long as every individual atomic store contributes to the checksum, it cannot be replaced by data from an interfering store without affecting the checksum. E.g. withatomic byte stores, you could XOR (or add) all bytes of the entry, and store that XOR (or sum) in stead of any of the original signature bytes.

Of course a sufficiently composite entry would still have a 1:256 chance of accidentaly regenerating the original signature. So it would be beter if the atomic stores were longer. In modern CPUs they fortunately are always at least 32 bits, and you could use that in combination with even a 32-bit signature to have only a 1:4G chance accepting corrupted entries.