3 ms·
To preempt the inevitable comment: in some cases (make sure to check!) you can use a third-party hash table such as the one Abseil provides, which may be faster
by saagarjha 4y ago
To preempt the inevitable comment: in some cases (make sure to check!) you can use a third-party hash table such as the one Abseil provides, which may be faster for your usecase if you can use it. Of course, profile first before switching and make sure that std::unordered_map is your bottleneck, understand why it is slow, then determine whether it would be possible to switch.
- lrem 4y agoAre there any cases where the abseil maps are slower? And: how often does this even matter? I'd guess very rarely.
- tialaramex 4y agoThe Abseil maps assume you are using a good quality hash for your hash map. If you are using one that's particularly bad, e.g. your standard library typically provides hashes which are a complete joke, Google's Swiss Tables have catastrophically bad performance. In contrast your typical std::unordered_map has indifferent performance with a good hash versus a terrible hash, anything vaguely resembling a working hash will perform similarly (not very well). Remember "all the defaults are wrong" in C++. That's not literally true, but more often than not, if there's a clownishly obvious mistake possible, C++ made it and you will need to explicitly work around it in your C++ program. In this case, there's no avalanche behaviour in most out-of-box hashes for C++. So the hash for 1, 2, 3 and 4 are extremely similar, and indeed in many cases they turn out to be 1, 2, 3 and 4 respectively. Not a good hash.
- themulticaster 4y agoI was genuinely surprised when I stumbled upon this Stack Overflow question [1] where someone asked why std::hash is the identity function for int, and some commenters argue that it is a perfectly sensible choice for a hash function. [1] https://stackoverflow.com/questions/38304877/why-stdhashint-seems-to-be-identity-function https://stackoverflow.com/questions/38304877/why-stdhashint-...
- syrrim 4y ago$ python >>> [hash(x) for x in range(4)] [0, 1, 2, 3]
- jcelerier 4y agoWhy do you think it isn't?
- themulticaster 4y agoWell, using the identity function as a hash does not provide any avalanche effect at all. And as parent comments point out, certain hash map implementations require a strong hash function. I'm guessing that the identity function probably isn't a "good" hash function as required by abseil's swiss tables and similar hash maps, but to be honest I haven't looked into this any further. Put another way, I'd have expected std::hash to be at least a very basic hash function (like FNV-1 for example).
- jcelerier 4y agoHmm, I know that at least some hash map implementations look for hash functions with an is_avalanching trait and otherwise add an explicit combination step; I'd assume that std::unordered_map implementations do the explicit combination all the time as std::hash was pretty much introduced just to work with such containers
- tialaramex 4y agoAs you presumably know std::unordered_map is essentially obliged to be a particular flavour of hash map which I'd say values simplicity of implementation over any performance metrics but which also provides certain iterator invalidation semantics which C++ programs could in principle come to rely on (and hence it cannot be swapped for a new structure). Turns out for this structure hash quality just doesn't matter very much. The identity function is all you need for mediocre results, and a really great hash produces only slightly improved results with this data structure, yet running the hash costs performance so why bother ? But a modern hash map structure actually relies on that quality for reasonable performance. https://martin.ankerl.com/2022/08/27/hashmap-bench-01/#benchmark-results-table https://martin.ankerl.com/2022/08/27/hashmap-bench-01/#bench... Ask that table about std::unordered_map - notice the fancier hashes make it worse (bigger numbers are worse, relative to 100 is the best) but not that much worse. It's always poor, it just varies as to whether it's very poor. Now, ask it about absl::flat_hash_map - for Abseil's own hashes the results range from very good to mediocre, and likewise other modern high quality hashes, but for std::hash it's so awful most benchmarks don't finish, shown as - instead of a number. You can try to detect this, but this is a fundamentally a QoI problem. Why even provide this rubbish hash function in the standard library? This is a lesson the C++ standard library refuses to learn, if you can't do it well then don't become an attractive nuisance by doing it badly. People are actually less unhappy with Microsoft's stdlib which gives you a poor FNV hash instead of the identity function. Like, OK, this isn't a great hash, but it does basically work (under non-adversarial conditions, FNV has big problems for tailored input) something like Swiss Tables will be substantially slower than it ought to be, but not crazy benchmark failed due to timeout slower. Nobody is cheering, but it doesn't cause open weeping.
- sagarm 4y agoLuckily absl also provides absl::Hash, which doesn't have this problem.
- usefulcat 4y agoIf you don't need all the guarantees provided by std::unordered_map (pointer stability is usually the big one), you can go a /lot/ faster with a map that uses open addressing. Some of my favorite alternative hash map implementations are ska::flat_hash_map and ska::bytell_hash_map from https://github.com/skarupke/flat_hash_map https://github.com/skarupke/flat_hash_map. They're fast, and the single header implementation makes them easy to add to a project. For my use cases they generally offer similar performance to abseil and folly F14. Don't be fooled by the fact that they haven't been updated in ~5 years. I've been using them for nearly that long and have yet to find any bugs.
- jcelerier 4y agohttps://github.com/martinus/unordered_dense https://github.com/martinus/unordered_dense Check this one out, it's a successor to this idea. Boost also introduced a very performant flat_hash_map in 1.81