10 ms·

Open addressing has better cache performance, and for most workloads is much faster than chaining implementations. Hashbrown's implementation is based on Google

Open addressing has better cache performance, and for most workloads is much faster than chaining implementations. Hashbrown's implementation is based on Google's SwissTable, and they explained the reasoning behind their choices in this CppCon talk: https://www.youtube.com/watch?v=ncHmEUmJZf4 https://www.youtube.com/watch?v=ncHmEUmJZf4

mehrdadn 8y ago
How does open addressing handle deletions? I never figured this out. Update: So I just read the article (I didn't have the chance earlier) and I see it explains tombstones, which seem like a pretty clever solution I wasn't thinking about. What I had been confused about, though was the other more-obvious attempt at a solution, which is backshifting. I think I had gotten stuck is what you do with the spot that opens up after the backshift... it might have been part of another probe chain (or multiple, for that matter) that had jumped over it before, so how do you find one of these chains to move back an item into this slot (which you would have to do)?
- shittyadmin 8y ago
  This is actually described quite well in the OP.
  - mehrdadn 8y ago
    Oh I see, thanks. I'm on my phone about to go to a meeting and haven't had a chance to read the article yet.
- blattimwind 8y ago
  The easiest one is tombstones (i.e. "this item is deleted") to keep the chain alive, or backshifting (i.e. moving all items in the chain forward one slot).
  - 0815test 8y ago
    I'm not sure that backshifting is as easy as "moving all items in the chain forward by one slot". Consider the hashtable [A, B1, B2, _, _], where one element is subsequently added after B2, giving [A, B1, B2, X, _]. Now when we remove B1 and shift B2 forward one slot ([A, B2, _, X, _]), we have to shift X forward if it hashes to the second or the third slot in the table, but not the fourth. So there might be multiple chains involved; if it was one contiguous chain only, we could simply arrange for the "hole" in it to be filled with no need for shifting all the items in it, and it would be quite efficient. However, it seems that it's not so simple.
    - barrkel 8y ago
      Yup, the chains can be interleaved. Often it's best to save the hash of each key as well as the key itself. Comparing the full hash (rather than the modulus of the hash) will eliminate many keys faster than doing a full key comparison, and having the full hash available means recreation on expansion is cheap, as all the keys don't need rehashing. The full hashes can then be used to distinguish between different chains if you decide to do backfilling, again cheaper than recalculating key hashes. Of course, having the hashes available also speeds up recreation, should the tombstone approach be used. Basically, keep the full hashes around :)
      - rurban 8y ago
        Certainly not with open addressing as it will destroy all the cache-line advantages. with seperate chaining it's very common, esp. for resizing.
        barrkel 8y ago
        The key is usually indirected, which means a pointer, which is usually bigger than the hash code. (And of course you could use parallel arrays if you're super concerned about cache lines, though the tradeoffs would very much depend on whether hash misses or hits are the expected mode.)
- Jernik 8y ago
  Reading the article reveals that you can either use tombstones or move the elements back into the slot they "would have been in" if the deleted element was never added
- usefulcat 8y ago
  The article mentions a couple of options, one of which is tombstones. In a chaining implementation, the load factor is straightforward: num_items / table_size. Adding items increases the load factor and deleting items reduces it. With open addressing, deletions do not decrease the load factor (at least not immediately, in general), because a deleted item becomes a tombstone. So for open addressing, load factor is (num_items + num_tombstones) / table_size. The upshot is that in a scenario where items are being repeatedly added and removed, over time the load factor will gradually increase until eventually the table has be recreated. This is true even if the average number of items remains relatively constant over time, and is unlike a chaining implementation. In this scenario, the average insertion time might be lower with open addressing, but the worst case will be much worse than for chaining.
  - deleted 8y ago
    [deleted]
  - a1369209993 8y ago
    You can eliminate tombstones over time by: # any time a tombstone immediately preceeds a empty, it can be marked empty [ $ _ ] -> [ _ _ ] # any time you lookup a key, it can be swapped with a tombstone immediately preceeding it [ $ A ] -> [ A $ ] # (moving the tombstone closer to a empty that will destroy it) # if you don't have iterators, you can also jump over other keys [ $ B A ] -> [ A B $ ] [ $ B C A ] -> [ A B C $ ] # etc # (this will cause a iterator at A to yield B again, or at B to skip A) How well this keeps the load factor down depends on how aggressively you look for tombstone disposal opportunities, but it does keep it down.
    - tptacek 8y ago
      Mutating the table on lookup seems pretty gross, though.
      - dhash 8y ago
        Eh, it’s the classic amortized approach. Whoever you ca “touch” the data and you’re right there already due to a lookup, it makes sense to amortize your data structure housekeeping IMO. TBH, the right answer is always due to the users use case (Amortization and housekeeping really help with purely functional data structures), and benchmark data.
- munificent 8y ago
  If you want more material, the "Hash Tables" chapter in my book walks through it: http://www.craftinginterpreters.com/hash-tables.html http://www.craftinginterpreters.com/hash-tables.html
hinkley 8y ago
Cliff Click (of JVM fame) did a presentation once on an open addressing hash table implementation that he believed was lock free (it used CAS and possibly some memory barriers). I wouldn't want to argue with Cliff Click on concurrency but everybody makes mistakes. I haven't checked back if anyone found any bugs yet. I'm also curious if or how that implementation would translate to other languages. What he did might not be declarable in the Rust ownership model.

mehrdadn 8y ago

How does open addressing handle deletions? I never figured this out. Update: So I just read the article (I didn't have the chance earlier) and I see it explains tombstones, which seem like a pretty clever solution I wasn't thinking about. What I had been confused about, though was the other more-obvious attempt at a solution, which is backshifting. I think I had gotten stuck is what you do with the spot that opens up after the backshift... it might have been part of another probe chain (or multiple, for that matter) that had jumped over it before, so how do you find one of these chains to move back an item into this slot (which you would have to do)?

shittyadmin 8y ago
This is actually described quite well in the OP.
- mehrdadn 8y ago
  Oh I see, thanks. I'm on my phone about to go to a meeting and haven't had a chance to read the article yet.
blattimwind 8y ago
The easiest one is tombstones (i.e. "this item is deleted") to keep the chain alive, or backshifting (i.e. moving all items in the chain forward one slot).
- 0815test 8y ago
  I'm not sure that backshifting is as easy as "moving all items in the chain forward by one slot". Consider the hashtable [A, B1, B2, _, _], where one element is subsequently added after B2, giving [A, B1, B2, X, _]. Now when we remove B1 and shift B2 forward one slot ([A, B2, _, X, _]), we have to shift X forward if it hashes to the second or the third slot in the table, but not the fourth. So there might be multiple chains involved; if it was one contiguous chain only, we could simply arrange for the "hole" in it to be filled with no need for shifting all the items in it, and it would be quite efficient. However, it seems that it's not so simple.
  - barrkel 8y ago
    Yup, the chains can be interleaved. Often it's best to save the hash of each key as well as the key itself. Comparing the full hash (rather than the modulus of the hash) will eliminate many keys faster than doing a full key comparison, and having the full hash available means recreation on expansion is cheap, as all the keys don't need rehashing. The full hashes can then be used to distinguish between different chains if you decide to do backfilling, again cheaper than recalculating key hashes. Of course, having the hashes available also speeds up recreation, should the tombstone approach be used. Basically, keep the full hashes around :)
    - rurban 8y ago
      Certainly not with open addressing as it will destroy all the cache-line advantages. with seperate chaining it's very common, esp. for resizing.
      - barrkel 8y ago
        The key is usually indirected, which means a pointer, which is usually bigger than the hash code. (And of course you could use parallel arrays if you're super concerned about cache lines, though the tradeoffs would very much depend on whether hash misses or hits are the expected mode.)
Jernik 8y ago
Reading the article reveals that you can either use tombstones or move the elements back into the slot they "would have been in" if the deleted element was never added
usefulcat 8y ago
The article mentions a couple of options, one of which is tombstones. In a chaining implementation, the load factor is straightforward: num_items / table_size. Adding items increases the load factor and deleting items reduces it. With open addressing, deletions do not decrease the load factor (at least not immediately, in general), because a deleted item becomes a tombstone. So for open addressing, load factor is (num_items + num_tombstones) / table_size. The upshot is that in a scenario where items are being repeatedly added and removed, over time the load factor will gradually increase until eventually the table has be recreated. This is true even if the average number of items remains relatively constant over time, and is unlike a chaining implementation. In this scenario, the average insertion time might be lower with open addressing, but the worst case will be much worse than for chaining.
- deleted 8y ago
  [deleted]
- a1369209993 8y ago
  You can eliminate tombstones over time by: # any time a tombstone immediately preceeds a empty, it can be marked empty [ $ _ ] -> [ _ _ ] # any time you lookup a key, it can be swapped with a tombstone immediately preceeding it [ $ A ] -> [ A $ ] # (moving the tombstone closer to a empty that will destroy it) # if you don't have iterators, you can also jump over other keys [ $ B A ] -> [ A B $ ] [ $ B C A ] -> [ A B C $ ] # etc # (this will cause a iterator at A to yield B again, or at B to skip A) How well this keeps the load factor down depends on how aggressively you look for tombstone disposal opportunities, but it does keep it down.
  - tptacek 8y ago
    Mutating the table on lookup seems pretty gross, though.
    - dhash 8y ago
      Eh, it’s the classic amortized approach. Whoever you ca “touch” the data and you’re right there already due to a lookup, it makes sense to amortize your data structure housekeeping IMO. TBH, the right answer is always due to the users use case (Amortization and housekeeping really help with purely functional data structures), and benchmark data.
munificent 8y ago
If you want more material, the "Hash Tables" chapter in my book walks through it: http://www.craftinginterpreters.com/hash-tables.html http://www.craftinginterpreters.com/hash-tables.html

hinkley 8y ago

Cliff Click (of JVM fame) did a presentation once on an open addressing hash table implementation that he believed was lock free (it used CAS and possibly some memory barriers). I wouldn't want to argue with Cliff Click on concurrency but everybody makes mistakes. I haven't checked back if anyone found any bugs yet. I'm also curious if or how that implementation would translate to other languages. What he did might not be declarable in the Rust ownership model.