[HN Gopher] Concurrent Hash Tables: Fast and General? (2019) ___________________________________________________________________ Concurrent Hash Tables: Fast and General? (2019) Author : todsacerdoti Score : 77 points Date : 2020-05-02 15:31 UTC (7 hours ago) (HTM) web link (dl.acm.org) (TXT) w3m dump (dl.acm.org) | addled wrote: | 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 wrote: | "I'm afraid we're all out of hash buckets at the moment. Would | you like a seat at our open addressing table?" | neonate wrote: | https://archive.md/VirvR | throwaway7281 wrote: | 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 | hinkley wrote: | 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. | te wrote: | I'd probably look at this one as well: | https://arxiv.org/abs/1809.04339 | albertzeyer wrote: | 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. | [deleted] | nayuki wrote: | 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. | hinkley wrote: | 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 wrote: | 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. | rurban wrote: | 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 wrote: | 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 wrote: | ... but if you just ctrl-F for TSX, you probably won't find | it, because of this unique web viewer. ___________________________________________________________________ (page generated 2020-05-02 23:00 UTC)