A Lock-Free Hash Table (google video)

[Dan]

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.

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