Looks to me like an "RCU grace period" (not sure what this is, sleep maybe?) is introduced to allow concurrent threads time to "finish reads" in between pointer changes.
The grace period is only necessary to ensure that no readers could possibly still be using a block before it's moved or freed. For example, when enlarging a table, if an object gets moved from a big bucket into a smaller one, there's a chance that readers on that object would suddenly find themselves in the wrong bucket. Waiting for the grace period ensures that there are no readers anymore and it's safe to move the object.
Very similar to RCU. Paul McKenny has had some great RCU articles on LWN in the past.
2010: http://lwn.net/Articles/418853/ 2014: http://lwn.net/Articles/609904/
Non-chaining hash tables make the most sense when you can fit the entire hash nodes directly into the array of buckets; that way, you never dereference a pointer at all. However, when storing larger structures, you typically need to put a pointer into the bucket rather than the structure itself. Once you've done that, you've already introduced an indirection and an extra memory read (or cacheline fetch). With open chaining, if you've sized the hash table to have on average 1 node per bucket, you have that same single indirection going from the bucket to the node, and then the node has all the data, so you don't need another.
Yes, for an efficient closed hash of a larger structure, you'd need to store both a pointer to structure and a means of disambiguation so that that you don't have to follow the pointer to (probabilistically) test if you have a matching entry. For a cuckoo, this might be the hash of the other slot, so it's not entirely wasted space, but it would add 8B or so to each entry. On the other hand, we're presuming a large struct anyway, this might not be too much extra burden.
The model that I'm mentally comparing to is an 2-way cuckoo hash with 8 slots per bucket, with a single SIMD compare to test for a match. It's an approach that makes a lot of sense to me. It's not quite what they describe, but if you haven't seen it, you might check out this paper: https://www.cs.princeton.edu/~mfreed/docs/cuckoo-eurosys14.p...
In any case, neat stuff to think about. Thanks for answering questions throughout the thread.
Or do you mean maintaining a reference to the value stored?
It seems to me that, even with a layer of indirection with a coocoo hashtable (i.e. your hash table is an array of pointers to elements), you still come out ahead with coocoo hashing as opposed to this method. If nothing else, your lookups are worst-case constant time.
In other words: what am I missing here?
> Or do you mean maintaining a reference to the value stored?
The hash node is the value stored; many hash tables are maps from keys to objects, and the objects get linked directly into the hash chain without further indirection.
The Linux kernel hash tables have a structure hlist_node which contains a next and previous pointer, and objects linkable into a hash table will contain an hlist_node as a field. This avoids having an extra level of indirection to get from a hash node to the hashed object.