Concurrent Hash Tables: Fast and General? (2019)
dl.acm.org
dl.acm.org
I suppose you could call it a generational hash table, but really it's a Hash Table interface wrapped around 2, occasionally 3 hash tables.
Create a read-write hash table A. When A hits capacity, create a second read-write hash table B (a constant factor 1.0 < n < 1.5), and stop writing to A. Create a read-only hash table R, dump A into it. During this time, all reads look at [B, A, R] in sequence. Once R is created, swap the list to [B, R]. When B fills, create another RW hash C (again resized) and dump R and B into a new read-only table S and swap the list to [C, S].
During resizes you only ever have 3 places to look. The Read-Write hash has to handle tombstones (and keep a count of them to keep resizing costs O(1)). I believe the main thing not handled here is if concurrent mutation traffic is faster than the copy constructor for the read-only heap. As near as I can tell the cited paper here has no solution for this.
I need to re-read Cliff Click's description of his lock-free hash table. If memory serves it has flavors of this and also answers the back-pressure problem (amortization across writers). But I suspect you can do something rather pedestrian and get similar results.
Here's a direct link to a PDF: https://arxiv.org/pdf/1601.04017.pdf
Scroll to the end before you can do a text search. Aaaargh!
I replied that I would open a restaurant that focused on stir fries created from a limited number of finely chopped ingredients simmering in predefined locations of a large grill. Not only tasty, this arrangement would allow serving customers quickly with little overhead.
I'd name the restaurant "Hash Table".
You can add or remove a node from such trees without modifying the original trees, by only creating O(log(n)) nodes (tree branches that don't change don't have to be copied). So "modifying" a tree does not invalidate the previous versions of the tree, that can still be processed by concurrent threads if they still hold a reference to the root node. No longer referenced tree branches will then be discarded by the GC.
With a concurrent hash table, you have to hold a lock on the whole datastructure if you don't want it to be modified while processing it, and this makes the whole thing is harder to think about overall.
I also find it easier to implement a correct and fast comparison function (required by tree structures) than an equivalent hash function. Trees can also give you range search, and keep your items sorted, which are useful in some cases.
Trees are now my go to datastructures for map and sets unless maximum speed and minimal memory use are absolutely required. These might not be as efficient, but they make more reliable software.
I would suspect that the entire point of a concurrent hash table is to avoid exactly that. Not much point otherwise.
The reason people don’t use trees is because it’s hard to make them memory-local. Otherwise it’s obviously easier to conceptually understand.
Is this covered in the article? I don't see this linked, but it was just a blog post, so maybe not relevant here, and they describe the same algorithms anyway.
And I don't see the TSX benefits, which is Intel only.
"Replacing the insert and update functions of our specialized growing hash table with Intel TSX variants increases the throughput of our hash table by up to 7%"
If you only run trusted code, Zombieload V2 seems irrelevant (on first glance. I didn't look deeper to see if there are ways to exploit it from a bytecode interpreter or such.)
For single-writer multi-reader scenario this requires no atomic fences or operations on TSO: http://concurrencykit.org/presentations/lpc2015.pdf
Works on any open-addressed scheme (there is also a robin hood implementation).