13 ms·
Why Hashbrown Does a Double Lookup
- prudhvis 8y agoThis is pretty amazing, i really like the fact that a fastest hash table implementation is going to be part of the Rust's stdlib.
- haggy 8y agoWhere does it say that this is the fastest hash table implementation?
- rurban 8y agoIt's accepted knowledge that the Google Swisstable is currently the fastest hashtable around. (The C++ implementation) But there are three variants, and this looks like the slowest of the three, but the best for dynamic languages.
- asveikau 8y agoIt should depend a lot on what you put into it and the access pattern, no? You can talk about averages, about complexity, about benchmarks, but I feel like "fastest hashtable around" is a very odd expression, as if to desire the world to be a lot less complex than it is and for there to be exactly one best.
- rurban 8y agoAs I said there are two best, plus the worse third variant. Not implemented by google, only described, but now apparently implemented in Rust. Haven't checked closely, because Rust is kinda unreadable compared to C what exactly is going on. Need to see the SIMD assembly also. You cannot really trust much what's going on with Rust, as there's too much hype and lies, but it undeniably got better recently.
- laughinghan 8y agoIs there anywhere we can read more about who says Google Swisstable is the fastest and why?
- ChrisSD 8y agoAnswer: SIMD. What looks like "two loops" is really "do two simple SIMD operations".
- scotty79 8y agoI 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.
- shittyadmin 8y agoSo - 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 agoOpen 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 agoHow 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 agoThis is actually described quite well in the OP.
- mehrdadn 8y agoOh 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.
- 8y ago
- deleted 8y ago[deleted]
- aswanson 8y agoI wonder if there is any research into hardware architectures optimized for Rust.
- ars 8y agoThere is nothing rust specific about this algorithmic.
- mlindner 8y agoThe Rust ABI isn't fixed and it uses LLVM. That's like asking if there's hardware architectures optimized for LLVM.
- devit 8y agoThe 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.
- 0815test 8y agoActually, 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.
- hyperman1 8y agox86 seems reasonable to me: Fast array bounds checking is, handling the lower bound by unsigned integer math : cmp index,bound ja crash_handler Overflow handling is mostly jo crash_handler That's 1 or 2 instructions and the jump has perfect prediction. I'd assume the cost is negligible compared with jump mispredicts and cache misses. I read somewhere the main problem is LLVM not being quite capable of optimizing these decently: It has to handle all these extra jumps which causes lots of extra basic blocks.
- jeanmichelx 8y agoSo how does this degrade for bigger hash tables? Surely the two loops implementation is less efficient since your cache is trashed by the time you do the second look up
- mbrubeck 8y agoThis varies not with the size of the whole hash table, but with the distance from any given index to the first empty bucket. By keeping the load factor constant, you can grow the hash table as much as you want without degrading the expected performance.
- jeanmichelx 8y agoGood point, thanks!
- simcop2387 8y agoNot necessarily, as the sibling mentioned load of the table matters, but also the fact that the single loop has to do other housekeeping may also mean that it could ruin any cache prefetching that could be happening because of the less predicable pattern. Ideally the housekeeping variables are going to be in registers but that's not always going to be possible. In this case, two loops that look at the data sequentially are going to predict very very nicely and probably load more of the cache as it's searching than anything that could be random.
- kibwen 8y agoThe author is also in the thread on /r/rust if you have any questions for them: https://www.reddit.com/r/rust/comments/b38cwz/why_hashbrown_rusts_new_hashmap_implementation/ https://www.reddit.com/r/rust/comments/b38cwz/why_hashbrown_...
- mabbo 8y agoI went to university with him. Really nice guy. Every time we talk, I say something like "any day now dude, I'm going to really get into Rust" and then I never do because I'm awful.
- linsomniac 8y agoTL;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 http://www.youtube.com/watch?v=npw4s1QTmPg
- the8472 8y agoWhat's the memory efficiency compared to the previous implementation? AIUI robin hood hashing with backwards shift deletion could achieve rather high load ratios, and thus keep memory footprint small. What I read about tombstone based open addressing suggests that it requires a lower load factor and thus more memory.
- cbhl 8y agoIf memory overhead (load factor) isn't a big issue, readers may also find cuckoo hashing rather interesting. (Theoretically, it has a worst-case constant lookup time. Learned about it in one of my university algorithms classes, but have yet to see an implementation in practice.) https://en.wikipedia.org/wiki/Cuckoo_hashing https://en.wikipedia.org/wiki/Cuckoo_hashing
- posnet 8y agohttps://blog.acolyer.org/2016/11/03/algorithmic-improvements-for-fast-concurrent-cuckoo-hashing/ https://blog.acolyer.org/2016/11/03/algorithmic-improvements... https://github.com/efficient/libcuckoo https://github.com/efficient/libcuckoo
- blattimwind 8y agohttps://github.com/efficient/libcuckoo https://github.com/efficient/libcuckoo There's the related cuckoo filter as well: https://github.com/efficient/cuckoofilter https://github.com/efficient/cuckoofilter
- mikeash 8y agoI assume that’s constant lookup time assuming well distributed hash values? The absolute worst case for a hash table is when every key has the same hash, and then you must fall back to something that’s at best log-n time.
- 19870213 8y agoThe standard Java java.util.HashMap currently falls back to a Tree(Map) if a bucket gets too full (more than 5? Not sure, a LinkedList if not too full). But I wonder, couldn't you not use a different hash and have use a HashMap as a bucket?
- mikeash 8y agoYou could, but it’s theoretically possible to have keys whose hashes always collide, even with different hash functions. This is not a purely theoretical concern, I should note. There are practical DoS attacks that can be carried out by deliberately crafting colliding keys. The current state of the art seems to be to make it impractical for attackers to accomplish this by incorporating secret data into the hash function, rather than by ensuring the theoretical worst case is acceptable. Which is probably the right approach.
- norswap 8y agoAnother alternative: Robind Hood Hashing http://norswap.com/robin-hood-hashing-jvm/ http://norswap.com/robin-hood-hashing-jvm/ (Might actually be the same technique, it's not quite clear!)
- erichdongubler 8y agoUh...this is what Rust uses currently. ;)
- zamalek 8y agoAll good points in the article. > it was doing something that was so offensive to people who care about collection performance Hmm. It also helps here to go back to academia. Big O notation doesn't usually express coefficients/constants, it usually only deals with exponents.[1] The Wikipedia page has a good explanation as to why. Opinion: coefficients/constants are, however, useful if you're running over a network or some other latency-bound operation. [1]: https://en.wikipedia.org/wiki/Big_O_notation#Properties https://en.wikipedia.org/wiki/Big_O_notation#Properties
- dbaupp 8y agoThe whole point of the article is that constant factors work in Hashbrown's favour.
- wyldfire 8y ago> . For instance, when compiled with sse2 support it can search 16 buckets at once. Does Neon get similar order of magnitude benefit?
- btym 8y ago>And so our "two loops" are usually just "do two simple SIMD operations". Not quite so offensive when you say it like that! No, it's not quite so offensive, but this doesn't explain why it's the best option. Is there no equally-fast way to write the first-tombstone implementation with SIMD instructions? The answer seems to be in the sketch of the implementation, which I'm having trouble understanding. EDIT: I'm watching the original SwissTable talk now... would it really have been worse to use 2 bits for empty/tombstone/full/sentinel, and 6 bits for hash prefix? EDIT 2: More implementation info. Tombstones are actually rare, because if any element in your 16-wide chunk is empty, you don't have to create a tombstone. In the very best case (a perfectly distributed hash function), your hashmap has to be ~94% full before it's even possible to fail this. Because tombstones are so rare, it's better to save the single bit for extra confidence in the hash prefix. So, here is my understanding of the implementation and its rationale: * Every bucket in the backing array has a corresponding byte in a metadata array * 1 bit of this byte stores whether the bucket is empty, the other 7 bits are for a hash prefix * SIMD instructions search 16 bytes at a time, checking: this bucket is not empty, this bucket's key matches the first 7 bits of my key * Since 16 buckets are checked for emptiness at the same time, you can avoid creating a tombstone for a bucket if any of the other 15 buckets are empty (just set it to empty, i.e. set the first bit to 0) * This means that tombstones are very unlikely- you'll probably rehash before you get to the load factor where you start seeing tombstones * Since tombstones are so unlikely, it's more valuable to add an extra bit to the hash prefix than it is to quickly find tombstones My question remains: why can't the first search return the offset of the first empty bucket? In this loop, why is there not an else that saves the offset?: https://github.com/abseil/abseil-cpp/blob/256be563447a315f2a7993ec669460ba475fa86a/absl/container/internal/raw_hash_set.h#L1652 https://github.com/abseil/abseil-cpp/blob/256be563447a315f2a...
- btym 8y agoOk, I got it. They're exactly the same. Either way you'd need to do a second search, because you're trying to differentiate between 3 states: "probably a match", "empty", or "deleted". A much better way than stealing a bit from the hash prefix is using a special value that represents "empty or deleted", and that's exactly what SwissTable does: https://github.com/abseil/abseil-cpp/blob/256be563447a315f2a7993ec669460ba475fa86a/absl/container/internal/raw_hash_set.h#L253-L278 https://github.com/abseil/abseil-cpp/blob/256be563447a315f2a...