Martin Stjernholm, Roxen IS @ Pike developers forum wrote:
In my quest for a good design for multi-cpu pike I ran across this rather interesting design for a lock free hash table:
Very impressive.
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.
This is rather cache-friendly, so it seems like a Good Thing to me.
o Keys are never deleted (a "resize" to the same size is necessary).
Keys can actually be deleted, that's what the Tombstone key is for.
o It never shrinks.
The algorithm allows for shrinking the same way it allows for growth, it's just that he hasn't implemented it. The reason why (as he states it) is that you'd need to be careful that you don't get one thread shrinking and another growing and another then shrinking again, and so forth. Other than that, the method for growing and shrinking basically is the same.
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.
It looks like a superior hash-table design overall, is there a reason why you wouldn't want to use it to replace any of the existing hash-tables?