5 ms·

So - what's the motivation to use "open addressing" vs chaining, which I thought was the more common approach to solving this. I assume there must be a substan

So - what's the motivation to use "open addressing" vs chaining, which I thought was the more common approach to solving this. I assume there must be a substantial performance gain for this to be used as it seems significantly more complicated, any information on how much better it is?

gopher_protocol 8y ago
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.
jeanmichelx 8y ago
Pointer chasing is very expensive if your chains end up in different cache lines. The bottleneck on a lot of application isn't how fast your instructions run, but how fast you can get data to them.
blattimwind 8y ago
All* high performance hashtables use open addressing, because chaining tends to mean (multiple) indirection to addresses outside the table. * not sure if that's literally true, but I've never seen anyone do chaining in performance-sensitive applications, and all the papers on fast hash tables use some way of open addressing.
- shittyadmin 8y ago
  Interesting, both the Qt and Java ones seem to use chaining, but I guess they're not designed with these sorts of extremely demanding applications in mind.
  - dbt00 8y ago
    The java.util.HashMap implementation uses chaining, but for example the google guava libraries that are frequently used are open addressing based.
  - amalcon 8y ago
    One thing to note is that this performance tradeoff is actually the reverse of what it was ~20 years ago. This is because CPU speeds have improved dramatically more than RAM speeds over a similar period. Open addressing does do more comparisons than chaining. It used to save time to traverse the linked list rather than to spend CPU cycles on those additional comparisons. Now, because CPU cycles are relatively cheaper, the opposite is true. The reason the Qt and Java hashtables use chaining is simply that the code in question was initially written back when the tradeoff ran the other way.
    - barrkel 8y ago
      If hash codes are stored inline alongside keys, code comparisons can be made without an indirection while key comparison (often strings, seldom anything without an indirection) usually needs an indirection. Hash codes are very cheap to compare. These indirections have always been costly on any machine with virtual memory. TLB misses aren't free. I'd have put any estimate on the tradeoff being the other way around to more than 25 years.
simias 8y ago
AFAIK an important factor to get good performance out of a hash table is to dimension the table so that collisions are rare. In this scenario it's not too surprising that the additional cost of sometimes having to iterate through the table beats chasing pointers. Furthermore as the article explains they can use SIMD to search several buckets at once, something that wouldn't really be possible if they didn't exist in contiguous memory.

gopher_protocol 8y ago

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.

jeanmichelx 8y ago

Pointer chasing is very expensive if your chains end up in different cache lines. The bottleneck on a lot of application isn't how fast your instructions run, but how fast you can get data to them.

blattimwind 8y ago

All* high performance hashtables use open addressing, because chaining tends to mean (multiple) indirection to addresses outside the table. * not sure if that's literally true, but I've never seen anyone do chaining in performance-sensitive applications, and all the papers on fast hash tables use some way of open addressing.

shittyadmin 8y ago
Interesting, both the Qt and Java ones seem to use chaining, but I guess they're not designed with these sorts of extremely demanding applications in mind.
- dbt00 8y ago
  The java.util.HashMap implementation uses chaining, but for example the google guava libraries that are frequently used are open addressing based.
- amalcon 8y ago
  One thing to note is that this performance tradeoff is actually the reverse of what it was ~20 years ago. This is because CPU speeds have improved dramatically more than RAM speeds over a similar period. Open addressing does do more comparisons than chaining. It used to save time to traverse the linked list rather than to spend CPU cycles on those additional comparisons. Now, because CPU cycles are relatively cheaper, the opposite is true. The reason the Qt and Java hashtables use chaining is simply that the code in question was initially written back when the tradeoff ran the other way.
  - barrkel 8y ago
    If hash codes are stored inline alongside keys, code comparisons can be made without an indirection while key comparison (often strings, seldom anything without an indirection) usually needs an indirection. Hash codes are very cheap to compare. These indirections have always been costly on any machine with virtual memory. TLB misses aren't free. I'd have put any estimate on the tradeoff being the other way around to more than 25 years.

simias 8y ago

AFAIK an important factor to get good performance out of a hash table is to dimension the table so that collisions are rare. In this scenario it's not too surprising that the additional cost of sometimes having to iterate through the table beats chasing pointers. Furthermore as the article explains they can use SIMD to search several buckets at once, something that wouldn't really be possible if they didn't exist in contiguous memory.