A Lock-Free Hash Table (google video)

[Sean Kelly]

Dan wrote:
> Craig Black Wrote:
> 
>>> Very interesting, thanks for that. Maybe now we can convince Walter to 
>>> include the patch I made about a year ago to make D's AA power-of-2/AND 
>>> instead of prime/MOD?
> 
> oh my!  I thought this was obvious; as was the powers of two, and using atomic asm operators to complete whole transactions or not at all.  I assumed this was already well known and implemented.
> 
> Actually, another way to implement the atomic transaction is to use any SSE/SSE2 move instruction to move a key/value pair into place with a:
> 
> struct KeyVal {
>    char* key;
>    union {
>       long l_value;
>       void* ptr_value;
>      double d_value;
>    }
> }
> assert(KeyVal.sizeof == 16);
> 
> into a ^2 sized array.  It's either there, or it's not; so it's concurrent if you follow the rest of the principles, and requires absolutely no preparation for a CAS or locking.

Yup.  It's rehashing that gets a bit messy.

> I'm going to hope that moving a 16-byte uses SSE2...

Nope.  It's all plain old D code at the moment IIRC.


Sean