5 ms·

Are there any cases where the abseil maps are slower? And: how often does this even matter? I'd guess very rarely.

• tialaramex 4y ago
  The 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 ago
    I 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 ago
      Why do you think it isn't?
      • themulticaster 4y ago
        Well, 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 ago
          Hmm, 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 ago
            As 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 ago
    Luckily absl also provides absl::Hash, which doesn't have this problem.