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.
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.
The java.util.HashMap implementation uses chaining, but for example the google guava libraries that are frequently used are open addressing based.
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…
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).
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.
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.
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.
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.
Answer: SIMD. What looks like "two loops" is really "do two simple SIMD operations".
I think rather the answer is:
Tombstones in place of deleted elements mean that finding out that key is not in the table requires going to a different place than finding the right place to finally put it. Hence two lookups. SIMD just makes keeping two lookups separate economical.
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
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…
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.
I wonder if there is any research into hardware architectures optimized for Rust.
The things Rust wants more than other languages are support for fast array bounds checks and fast integer overflow checks. Unfortunately none of the current popular architectures seem to have either.
Actually, I'd say that support for fast range checks is less important in Rust than in some other languages, because the Rust compiler is quite good at removing the checks when a value can be proven to be in the right range. In general, Rust seems to cope quite well with current CPU architectures, although I do think that there's an open question as to how to support viable parallelism that not quite as fine-grained as current ILP approaches (pipelining, superscalar), nor quite as coarse as to be effectively exploited via multiple threads. ISTM that this is one portion of the design space that Rust might address quite nicely.
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?
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.
The main case that I know of where you really don't want to use open addressing (using tombstones) is when you have both of the following requirements: a) need to repeatedly insert and delete items, and b) can't tolerate (relatively) really bad worst case insertion performance.
I can't speak directly to the performance of non-tombstone based open addressing implementations, but it definitely seems like the need to move things around after deletions would be significantly more work than the fastest chaining implementation I've come up with.
TL;DR: You first need to look for the hash "tombstone", then you need to find the actual insertion which may be very far away.
Raymond Hettinger (HN commenter and all around Smart Dude (tm)) has a good talk from PyCon 2017 about the evolution of Python dictionaries that goes into tombstones and so much more: http://www.youtube.com/watch?v=npw4s1QTmPg