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