Concurrent Hash Tables: Fast and General? (2019)

https://dl.acm.org/doi/pdf/10.1145/3309206

by todsacerdoti • 6 years ago

131 34 6 years ago

dl.acm.org

te• 6 years ago

I'd probably look at this one as well: https://arxiv.org/abs/1809.04339

senderista2• 6 years ago

See also https://www.semanticscholar.org/paper/A-Concurrent-Bidirecti.... I used the insert algorithm from this paper in my evaluation of linear probing algorithms, where it outperformed Robin Hood: https://github.com/senderista/hashtable-benchmarks.

nayuki• 6 years ago

The ACM website's online PDF viewer is terrible. The zoom buttons need to be pressed so many times to make any meaningful change, the document pages load lazily, there are many unnecessary animations, the scrollbar position keeps jumping around, etc. Good thing there is a download link so that I can use my browser's built-in PDF viewer or an external reader.

hinkley2• 6 years ago

Infinite scroll is great when you're trying to kill time. When you're actually trying to get shit done it's a walking nightmare.

Scroll to the end before you can do a text search. Aaaargh!

pests• 6 years ago

Remember the era when people couldn't figure out how to make footers work with infinite scroll? Even Facebook messed it up. Try to click something and the next page would load and off the footer went half way down the window.

bubblethink• 6 years ago

May have something to do with drm. When you download a pdf, you get some watermarked version with a rightslink banner. However, when you view it, it doesn't show you the banner. They didn't want to ruin your viewing pleasure with the banner. So they ruined it with the shitty pdf viewer.

albertzeyer• 6 years ago

There was this simple GPU hash table a while ago: https://news.ycombinator.com/item?id=22541925

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.

hinkley2• 6 years ago

I always wondered why when it comes time to create data structures we rarely if ever use a doubling of the constant factor to fix or at least reduce some of these issues.

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.

foota• 6 years ago

This sounds somewhat similar to log structured merge trees.

constantine42• 6 years ago

Good ole double buffering. I've used this pattern for many custom concurrency designs.

senderista2• 6 years ago

Me too. I find the pattern especially powerful with Redis's atomic RENAME command. Here's an application to aging bloom filters: https://ieeexplore.ieee.org/abstract/document/5066970

rurban• 6 years ago

It doesn't test the IMHO currently best. https://greg7mdp.github.io/parallel-hashmap/

And I don't see the TSX benefits, which is Intel only.

jbapple• 6 years ago

The benefits are visible if you search for the word "TSX". It says:

"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%"

rrss• 6 years ago

... but if you just ctrl-F for TSX, you probably won't find it, because of this unique web viewer.

jeffbee2• 6 years ago

Has there ever been an Intel CPU with working TSX that didn't get disabled by a microcode update?

addled• 6 years ago

I was once asked what career I'd pursue other than programming.

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".

kabdib• 6 years ago

"I'm afraid we're all out of hash buckets at the moment. Would you like a seat at our open addressing table?"

craz8• 6 years ago

If you could fill every seat, with no wait, that would be perfect!

sriram_malhar• 6 years ago

Make sure you don't implement cuckoo hashing!

neonate• 6 years ago

https://archive.md/VirvR

throwaway7281• 6 years ago

Uh, I have to yet find an "enhanced" "view PDF" page, which does not make things worse.

Here's a direct link to a PDF: https://arxiv.org/pdf/1601.04017.pdf

saagarjha• 6 years ago

I would have agreed with you until about a year ago, which was when my browser somehow broke crucial PDF features like search in their already plainly-legacy PDF renderer…

rtheunissen• 6 years ago

There is also https://www.arxiv-vanity.com/papers/1601.04017/

sbahra• 6 years ago

Thanks for sharing!

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).

raphaelj2• 6 years ago

I always preferred immutable sorted trees (such as found in Haskell or Scala) to concurrent hash tables when dealing with concurrent sets or maps.

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.

AshamedCaptain2• 6 years ago

With a concurrent hash table, you have to hold a lock on the whole datastructure

I would suspect that the entire point of a concurrent hash table is to avoid exactly that. Not much point otherwise.

raphaelj2• 6 years ago

Not if you don't want the hash table to change while doing some read only processing on it. Immutability ensures that the reference you get always point towards a object that is in a consistent state.

heavenlyblue• 6 years ago

I don’t understand: are Haskell or Scalia trees cache-friendly at all?

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.

a1369209993• 6 years ago

The actual article is here: https://dl.acm.org/doi/pdf/10.1145/3309206?download=true [PDF].

Avi-D-coder• 6 years ago

If you have a GC HAMTs are ideal for a lock free transactional semantics. In fact all pure data structures can be generalized to give lock free optimistic transactions with a single CAS. HAMTs just have the nicest properties for minimizing conflicts.

Concurrent Hash Tables: Fast and General? (2019)

Related Stories