4 ms·

It depends on the hash table. Cuckoo hashing is a lot easier since you can resize and reorder the buckets concurrently in a new array, exposing it to new reader

by seabee 12y ago

It depends on the hash table. Cuckoo hashing is a lot easier since you can resize and reorder the buckets concurrently in a new array, exposing it to new readers is a single pointer swap. When you have a linked list of buckets you have a lot more work to do!

JoshTriplett 12y ago
Cuckoo hashing, and other closed-hashing (non-chaining) approaches, don't allow other portions of the system to maintain references to hash nodes. Nodes within hash tables in the Linux kernel often consist of some other data structure with an embedded hlist_node, allowing the data structure to be dropped into a hash bucket. 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.
- nkurz 12y ago
  I was presuming that you'd want more nodes per bucket, but I suppose once you have a hash that can expand and contract efficiently that becomes less of an problem. The issue though with having an average of 1 node is that about 1/3 of the buckets will have no nodes (wasted space), and about 1/3 will have 2 or more (longer lookups). 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.pdf 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.
- TheLoneWolfling 12y ago
  Why do you need to maintain a reference to a hash node? 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?
  - JoshTriplett 12y ago
    > Why do you need to maintain a reference to a hash node? > 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.

by seabee 12y ago

JoshTriplett 12y ago

Cuckoo hashing, and other closed-hashing (non-chaining) approaches, don't allow other portions of the system to maintain references to hash nodes. Nodes within hash tables in the Linux kernel often consist of some other data structure with an embedded hlist_node, allowing the data structure to be dropped into a hash bucket. 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.

nkurz 12y ago
I was presuming that you'd want more nodes per bucket, but I suppose once you have a hash that can expand and contract efficiently that becomes less of an problem. The issue though with having an average of 1 node is that about 1/3 of the buckets will have no nodes (wasted space), and about 1/3 will have 2 or more (longer lookups). 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.pdf 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.
TheLoneWolfling 12y ago
Why do you need to maintain a reference to a hash node? 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?
- JoshTriplett 12y ago
  > Why do you need to maintain a reference to a hash node? > 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.