In my quest for a good design for multi-cpu pike I ran across this
rather interesting design for a lock free hash table:
http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.html
The most complete description of it is a taped talk:
http://video.google.com/videoplay?docid=2139967204534450862
The way it can be resized without locking is pretty cool. Several
threads can even share the work to carry out the copying.
His design parameters for the hash table are a bit unorthodox though:
o Size is always power of two (not prime).
o It's closed.
o Reprobing is linear.
o Keys are never deleted (a "resize" to the same size is necessary).
o It never shrinks.
The first three together are a bit scary if the hash function is bad,
but maybe it's just me..
This could put to good use for the shared string table, but probably
more places too. I think it'd be good to implement shrinking, though.
