4 ms·

Maybe I'm daft, but the growing and shrinking explained looks like how you'd do it for any hash table, is that not how a normal one works? Do normal hash tables

by howeyc 12y ago

Maybe I'm daft, but the growing and shrinking explained looks like how you'd do it for any hash table, is that not how a normal one works? Do normal hash tables "freeze the world" to change tables or something? 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.

JoshTriplett 12y ago
With a normal hash table, you'd acquire either a table-wide lock or every per-bucket lock before resizing the table. With this algorithm, readers can continue to run concurrently with the resize, and the concurrent resize will never cause a reader to incorrectly fail to find a hash element.
- howeyc 12y ago
  It looks to me like the major thing here is the grace period right? Otherwise you could get "pointer-changing" happy and mess up readers traversing bucket lists right?
  - bronson 12y ago
    If I understand correctly, readers never need to wait for the grace period. Careful ordering of operations ensures they can charge at full steam and yet always have a consistent view of the hash table. 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.
- kazinator 12y ago
  This issue arises even in completely single-threaded programs that have hash tables. Suppose you're iterating over a hash, hitting a callback function for each element which has access to the hash and inserts new elements. During the callback, new elements could be inserted which trigger a growth. If you allow the hash table reorganization, then it has to be reconciled with the in-progress traversal, so that it doesn't miss some elements, or visit some elements more than once.
  - im3w1l 12y ago
    I think if you insert an element during iteration, it is unpredictable whether said element will be visited during the iteration or not, so it is probably a bad idea even if you wont have a resize.
    - seabee 12y ago
      It's a bad idea if you don't have a well-defined mode of operation; for example, you're fine if the hash table uses copy-on-write semantics.
- bmm6o 12y ago
  How does the "grace period" work in practice? Is it really a set amount of wall time?
  - JoshTriplett 12y ago
    No, it's a construct from RCU. There's an rcu_read_lock() and rcu_read_unlock(), which despite the name is a lightweight cpu-local operation that doesn't take any locks. synchronize_rcu() waits for all currently active readers, but does not wait for any new readers.
riking 12y ago
For an explanation of "RCU grace periods", read "The RCU Api, 2010/2014 Edition": 2010: http://lwn.net/Articles/418853/ http://lwn.net/Articles/418853/ 2014: http://lwn.net/Articles/609904/ http://lwn.net/Articles/609904/
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.

by howeyc 12y ago

JoshTriplett 12y ago

With a normal hash table, you'd acquire either a table-wide lock or every per-bucket lock before resizing the table. With this algorithm, readers can continue to run concurrently with the resize, and the concurrent resize will never cause a reader to incorrectly fail to find a hash element.

howeyc 12y ago
It looks to me like the major thing here is the grace period right? Otherwise you could get "pointer-changing" happy and mess up readers traversing bucket lists right?
- bronson 12y ago
  If I understand correctly, readers never need to wait for the grace period. Careful ordering of operations ensures they can charge at full steam and yet always have a consistent view of the hash table. 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.
kazinator 12y ago
This issue arises even in completely single-threaded programs that have hash tables. Suppose you're iterating over a hash, hitting a callback function for each element which has access to the hash and inserts new elements. During the callback, new elements could be inserted which trigger a growth. If you allow the hash table reorganization, then it has to be reconciled with the in-progress traversal, so that it doesn't miss some elements, or visit some elements more than once.
- im3w1l 12y ago
  I think if you insert an element during iteration, it is unpredictable whether said element will be visited during the iteration or not, so it is probably a bad idea even if you wont have a resize.
  - seabee 12y ago
    It's a bad idea if you don't have a well-defined mode of operation; for example, you're fine if the hash table uses copy-on-write semantics.
bmm6o 12y ago
How does the "grace period" work in practice? Is it really a set amount of wall time?
- JoshTriplett 12y ago
  No, it's a construct from RCU. There's an rcu_read_lock() and rcu_read_unlock(), which despite the name is a lightweight cpu-local operation that doesn't take any locks. synchronize_rcu() waits for all currently active readers, but does not wait for any new readers.

riking 12y ago

For an explanation of "RCU grace periods", read "The RCU Api, 2010/2014 Edition": 2010: http://lwn.net/Articles/418853/ http://lwn.net/Articles/418853/ 2014: http://lwn.net/Articles/609904/ http://lwn.net/Articles/609904/

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.