3 ms·
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
by 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 agoIt 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 agoIf 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 agoThis 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 agoI 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 agoIt'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 agoHow does the "grace period" work in practice? Is it really a set amount of wall time?
- JoshTriplett 12y agoNo, 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.