11 ms·
I Wrote My Fastest Hashtable
- jlrubin 10y agoAuthor may be interested in http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-m... as a way of avoiding modulo altogether.
- TorKlingberg 10y agoThis is fine if you are working with 32-bit numbers on a CPU with fast 64-but multiplication. What if you have 64-bit numbers?
- jbapple 10y agox86-64 has single instruction (MUL) that produces a 128-bit unsigned result by multiplying two unsigned 64-bit operands.
- gpderetta 10y agoIn addition to what jbapple said, if your hash map has more than 2^32 buckets, the latency of the division is the last of your problem.
- TorKlingberg 10y agoSure N (number of buckets) shouldn't be too big, but x (the input value) could be.
- 79d697i6fdif 10y agorealistically any hash table bigger than the 32 bit boundary will be well outside any CPU caches and possibly even ram. At these sizes the memory latency will dwarf CPU speed
- 79d697i6fdif 10y agoThe author seems mistaken about a couple things relating to hash tables. He doesn't seem aware that, by far, the main reason for using power-of-two hash table sizes is so you can use a simple bitshift to eliminate modulo entirely. He is also going to run into modulo bias since using the remainder to calculate a slot position is biased toward certain positions for every table size that isn't a power of two. (see https://ericlippert.com/2013/12/16/how-much-bias-is-introduced-by-the-remainder-technique/ https://ericlippert.com/2013/12/16/how-much-bias-is-introduc... for cool graphs) Prime number table sizes do nothing to fix these issue. The power-of-two size with a bitshift is not just faster, it gets rid of the modulo bias. Fastrange is much faster than modulo but if his goal is to build the fastest hashtable it's stupid to use a table size of anything except a power of two. Source: I also wrote a hashtable :)
- pacoverdi 10y ago> He doesn't seem aware that, by far, the main reason for using power-of-two hash table sizes is so you can use a simple bitshift to eliminate modulo entirely. [...] using a power of two to size the table so that a hash can be mapped to a slot just by looking at the lower bits. He seems to know this bit :)
- mark-r 10y agoHe appears to know about bit masking but not bit shifting, which seems odd.
- krajzeg 10y agoThere is a lot of material in the article on power-of-two vs non-power-of-two sizes and it definitely includes a discussion of how POT is convenient due to modulo becoming a bitmask (not a bitshift, which would be division).
- anon1385 10y ago>The author seems mistaken about a couple things relating to hash tables. He doesn't seem aware that, by far, the main reason for using power-of-two hash table sizes is so you can use a simple bitshift to eliminate modulo entirely. From the article: >This is the main reason why really fast hash tables usually use powers of two for the size of the array. Then all you have to do is mask off the upper bits, which you can do in one cycle.
- EGreg 10y agoSpeaking of avoiding non-binary logic, what do you all think of using the same simplification for doing SYNC: http://magarshak.com/blog http://magarshak.com/blog
- dgacmu 10y agoThey may, but it's worth noting that if you're going to use Lemire's trick, you must have a good hash function -- which this post avoids. The trick you referenced (i use "trick" in a good sense) relies on the high-order bits of the multiplication changing substantially, which means that items that hash to 1, 2, 3, ... end up in the same bin. This is perfectly fine if your hash function maps uniformly to [0, max_int32_t] (or max_int64_t if you use the umul_hi variant), but it's not fine if you use the horrible default identity function std::hash. (Speaking from experience: I used his trick to accelerate one of the TensorFlow hash tables a while ago -- https://github.com/tensorflow/tensorflow/commit/a47a300185026fe7829990def9113bf3a5109fed https://github.com/tensorflow/tensorflow/commit/a47a30018502... )
- deleted 10y ago[deleted]
- gpderetta 10y agoHum, the nice thing with Robin Hood hashing is that you get close to 90% load factor without pathological performance degradation. If you have a fixed probe count, wouldn't you be better just grouping your buckets in fixed size sub buckets and doing (trivially parallelizable) linear searches for lookups and to find empty insert positions? On a related note, I have in general concerns about latency spikes due to rehashing. Is there a good, general, incremental rehashing scheme?
- throwawayish 10y ago> Is there a good, general, incremental rehashing scheme? Trees.
- gpderetta 10y agoAs a C++ programmer, my default dictionary is usually an std::map (which is just an RB-tree), so, yes agree 100%. But the amortized O(1) lookup of hash tables is hard to beat. edit: s/bass/beat/
- throwawayish 10y ago> But the amortized O(1) lookup of hash tables is hard to beat. On the other hand: the performance characteristics of trees are much easier to predict. And in many cases a HT lookup isn't distinguishable from a tree lookup, at least if it's a dedicated application data structure, like some index or so. I feel like HTs are very good for smaller structures (excellent example: dictionary/hashtable-based interpreters), but for larger data structures (e.g.: indices) ... not so much.
- leventov 10y agoThere is a good general segmented hashtable algorithm with ~100 times smaller rehash spikes than in classic hash tables: https://github.com/OpenHFT/SmoothieMap/blob/master/src/main/java/net/openhft/smoothie/SmoothieMap.java#L94 https://github.com/OpenHFT/SmoothieMap/blob/master/src/main/... The idea is not super clever so I'm sure many people found & implemented it in papers and other languages, but I didn't find them. Will be grateful if someone points me to prior work.
- _benedict 10y agoThis is great, and I don't want to take away from it, but the idea that limiting the number of probes before a rehash is a new contribution is mistaken. I've certainly done this in hash tables I've implemented at times, and I've seen this in library hash tables too. One public well-known example that springs to mind is Cliff Click's NonBlockingHashMap in Java.
- cat199 10y agoAnd with one fell swoop, the thesis went pop
- 3pt14159 10y agoWhy is it mistaken?
- PeterisP 10y agoI wouldn't ever have thought that replacing the generic integer modulo operation with a switch statement and a modulo operation with a particular hardcoded denominator could possibly cause a performance improvement. Especially for primes. I can imagine that various power-of-two related values could have some bit-twiddling ways to make them much faster, but assuming that the compiler will be able to improve x mod 711 to something better than using the CPU modulo operation seems weird... but it somehow works.
- MaulingMonkey 10y agoIf you want to see what the magic looks like for yourself: https://godbolt.org/g/5LZy2t https://godbolt.org/g/5LZy2t
- Sharlin 10y agoYep, there's pretty much a trick for every reasonably small divisor. For instance GCC 4.9 translates division by 711 as follows (dividend in edi): mov eax, edi mov edx, -1202107583 imul edx mov eax, edi sar eax, 31 add edx, edi sar edx, 9 sub edx, eax mov eax, edi imul edx, edx, 711 sub eax, edx This is, uh, pretty deep magic. Apparently this sequence of ops, including those two imuls, is still faster than a single idiv.
- flamedoge 10y agoIs this from r=n-x*711; x=n/711 done via long binary division?
- pwdisswordfish 10y agoNot quite. See https://zneak.github.io/fcd/2017/02/19/divisions.html https://zneak.github.io/fcd/2017/02/19/divisions.html — it was posted here some time ago.
- tehwalrus 10y agoIs this the trick where you multiply by the two's-compliment inverse instead of dividing? That was the coolest thing I learned when I spent a few days coding assembly. I can't see the shift that you normally need after pulling the result out of the overflow register though. My asm is a little rusty though.
- charisma_stupid 10y agoThis is good work. I wish it was extended to work under multiple threads so it could be used in databases.
- jlrubin 10y agoI'd be interested to see a comparison of cuckoo hashing v.s. robin hood on these benchmarks. I chose to use Cuckoo in my implementation of a high performance fixed-size cache for bitcoin signature validation (see https://github.com/bitcoin/bitcoin/blob/master/src/cuckoocache.h https://github.com/bitcoin/bitcoin/blob/master/src/cuckoocac...). Cuckoo is great in my experience if you want to use memory fully and can afford > 3 high quality hashes per entry. I also like cuckoo because you're able to use it pretty well for lockfree/high concurrency use cases (can make concurrent erases and reads lock free for example), which made it a good fit for the bitcoin workload. It seems that this hashtable's approach isn't quite amenable to concurrent operations, but perhaps there are some tricks that could work for that.
- exDM69 10y agoJust to clear up a common point of confusion: the "Robin Hood" scheme that is commonly used these days is not a multiple hashing solution like the original research paper from the 1980s (and Cuckoo hash table). What's used these days should be called "Robin Hood linear probing" or something else. It's just a variant of linear probing where an entry occupying a "better" slot than the one being inserted gets pushed back. It might still be an interesting comparison but I'm under the impression that Robin Hood is a very good solution for a general purpose hash table.
- rurban 10y agoCuckoo uses 2x memory, with constant cache trashing. It can be made fast with concurrent maps, but there Cliff Click's or Preshing's Leapfrog approaches are better.
- jlrubin 10y agoWhat makes you say that cuckoo uses 2x memory?
- rurban 10y agoThe most commonly used variant uses 2 arrays, indexed by the two hash functions. Or one array twice the size. While the current trend is to reduce the size of this array by using size-compressed indirect indices, e.g. the new ruby/python hashes.
- amelius 10y agoWhat objects were actually stored in the hash table for these tests? Are they fixed size, non-heap-allocated? And would the performance improvement still be relevant if this is not the case, e.g. for variable size strings?
- ZoFreX 10y agoSome of the hash tables were heap allocating others were in place. They tested a variety of sizes.
- Ono-Sendai 10y agoWell I think my hashtable is probably faster. It's also faster than dense_hash_map. The author claiming their hash table is the fastest ever is kind of ridiculous.
- elmigranto 10y agoIt's fastest of all author's implementations, which is stated in first paragraph.
- Ono-Sendai 10y agoYes but the title make a claim that it's the fastest.
- elmigranto 10y agoAnd it is, though, not among a set of hashtable implementations you assumed. It is quite similar with how you wrote "fastest" instead "fastest among all existing publicly available implementations". Nothing wrong with that, since it is obvious from context, very much the same way it is obvious from article what author means.
- Ono-Sendai 10y agoit's a bullshit clickbait title.
- saalweachter 10y agoAs the author explains right off the bat, it's a logical clickbait title. He wrote three blog posts: "I wrote a fast hashtable", "I wrote a faster hashtable", "I wrote the fastest hashtable". I mean, I'd still call it clickbait, but it's hardly bullshit clickbait.
- cat199 10y ago
- nialv7 10y agoGrowing hashtable based on number of unsuccessful probes is essentially the same as grow based on load ratio (α). Because the expected number of probes can be calculated from it, which is 1 + 1/(1 − α).
- _benedict 10y agoWell, you're assuming a perfect uniform distribution of your values. Skew in data is common, since cryptographic hash functions are uncommon (since they're expensive), and any way we generally store collections vanishingly smaller than infinity, in which case even a perfect distribution will produce clusters with varying frequency; and each will degrade differently under these situations. At the extreme, if every item produces the same hash code, growing on reprobes will result in exponential insert complexity (since every insert will trigger a grow). Growing on load factor will just maintain O(n) insert/lookup complexity (or the complexity of the hash bucket, if not open-addressing). With less extreme skew, growing on load factor will simply use less memory than growing on reprobes, while reprobes will have a slightly lower median (and possibly mean) insert/lookup costs.
- ot 10y agoThe author seems to ignore that GCC's implementation of std::hash is the identity on integral types: https://github.com/gcc-mirror/gcc/blob/cf8c140a8b8131b3ab4f500346dc4c004c899163/libstdc%2B%2B-v3/include/bits/functional_hash.h#L113 https://github.com/gcc-mirror/gcc/blob/cf8c140a8b8131b3ab4f5... This is an incredibly poor design choice (at Facebook we'd say "clowntown") as it makes it unusable with any sophisticated hashtable data structure that assumes reasonable randomness. That's what causes the quadratic growth in the sequential example with dense_hash_map. The solution is to use better hash functions, not prime hash table sizes. Prime modulus will only make the problems harder to notice, but if you have a poor hash function, you're giving up every complexity guarantee. Note that even if you reduce modulo a prime > n, you'll still have the identity over the first n numbers. Personally I just use folly::Hash (https://github.com/facebook/folly/blob/da08e63ce3bac9196b18db82e64db8ecbb44d0ed/folly/Hash.h#L352 https://github.com/facebook/folly/blob/da08e63ce3bac9196b18d...) as it uses sane defaults for hash functions, and contrary to std::hash it's a polymorphic functor so you can just drop it as template argument without having to specify the key type: dense_hash_map<int, int, folly::Hash>. The other reason dense_hash_map uses power-of-2 sizes (other than to avoid the modulo) is that it is sufficient to guarantee that the quadratic probing schedule is transitive, that is, it can reach all the slots of the table. Quadratic probing is used because it's very effective for unsuccessful lookups. You can find a table of expected probe counts at different load factors here: https://github.com/sparsehash/sparsehash/blob/4cb924025b8c622d1a1e11f4c1e9db15410c75fb/src/sparsehash/internal/densehashtable.h#L77 https://github.com/sparsehash/sparsehash/blob/4cb924025b8c62... Hash tables are a fine craft. While it's interesting to gain these experiences first-hand, this is an amateurish post and it should be taken with a grain of salt.
- 79d697i6fdif 10y agoOuch, this is much more thorough than my attempt to debunk the post.
- Trundle 10y agoHey, this really belongs on one of your older comments about you starting a blog but the comment was too aged to reply. Can you add me to the list of people to contact when you get it off the ground? Cheers. prostorm.blue@gmail.com
- throwaway206801 10y ago> at Facebook we'd say "clowntown" Aren't you the same people who produced that monstrosity of an iPhone app and then publicly boasted, in defense of it, that iOS can't "handle our scale?" Considering that Facebook's reputation as an engineering company isn't exactly stellar, tossing in an "at Facebook" only serves to undermine your post rather than bolster it.
- ksk 10y agoFB can have brilliant world-class engineers working on task A producing quality output, while others working on task B can over-engineer and over-abstract, producing crapola. Replace FB with Google, Apple, Microsoft, Oracle, Sun, IBM, Adobe, etc, etc.
- cgag 10y agoI hear they've got a clowntown mobile app (I don't use it) but react, flow, graphql, relay, and their Haskell spam filtering / ghc work all seems pretty great.
- deleted 10y ago[deleted]
- rudolf0 10y agoTheir non-mobile quality seems to be pretty high as far as I can tell, but, yeah, I feel like he'd have to agree their iOS app is the definition of clowntown.
- ot 10y agoThat word is more often than not directed at our own work. Maintaining a self-mocking attitude can help in being more receptive to valid criticism.
- dang 10y agoWe've banned this account for trolling. Please don't create accounts to break HN's guidelines with. We detached this subthread from https://news.ycombinator.com/item?id=13745383 https://news.ycombinator.com/item?id=13745383 and marked it off-topic.
- markcerqueira 10y agoA lesson in "Tone is everything" perhaps? You make excellent points and taught me a bunch (thanks!), but just because the author admits he doesn't understand hash tables inside and out does not make calling his work "amateurish" or "clowntown" okay.
- ot 10y agoIf you read carefully you'll see that "clowntown" referred to GCC's implementation of std::hash, not the post. I think it's natural to have high standards for GCC. I don't think my tone was too aggressive, maybe made exception for the word "amateurish"? I explained above what I meant, if you replace that word with a better one does it change the tone of the post?
- astine 10y ago"if you replace that word with a better one does it change the tone of the post?" Yes, it does. 'Amateurish' is often used as an insult to imply that someone needn't have tried at all. If you replaced it with 'novice,' I think people would have understood your meaning without taking offense.
- ot 10y agoI see. I didn't know "amateurish" had such negative connotations. Unfortunately HN doesn't let me edit the post anymore.
- q3r3qr3q 10y agoYour tone was fine. Don't pander to these people, please.
- mamp 10y agoFor a post on HN the tone was ok but not great, if one of my team spoke like that in a meeting I would commend them on their technical knowledge but remind them that their effectiveness and influence depends more on tone than technical skill, because people.
- titzer 10y agoInteger modulus is one of the slowest CPU operations, especially on modern CPUs (since most other operations have been heavily optimized, and there are many execution units available for them). IDIV on Nehalem can literally take up to 100 cycles (http://www.agner.org/optimize/instruction_tables.pdf http://www.agner.org/optimize/instruction_tables.pdf), and it varies _a lot_. Power of 2 hashtables are so much faster because indexing uses a mask. The problem is that, as others have mentioned, powers of 2 suffer a lot with bad hash functions, and people tend to write pretty bad ones, so it's generally a good idea to salt or rehash hashcodes before dropping the upper bits with a mask. In fact it looks like the results from the author's bear that out, as the flat_hashmap_powers_of_two is almost always the fastest.
- deleted 10y ago[deleted]
- silok 10y agoHave you compared it to this implementation? http://www.ilikebigbits.com/blog/2016/8/28/designing-a-fast-hash-table http://www.ilikebigbits.com/blog/2016/8/28/designing-a-fast-...
- Dowwie 10y agoRaymond Hettinger made an interesting talk about Python's dict (hash table) and how Python's core development team evolved it over time. He's giving the polished version of talk at PyCon this May but if you can't wait for it, here's a rough version: https://www.youtube.com/watch?v=p33CVV29OG8 https://www.youtube.com/watch?v=p33CVV29OG8