Hacker News Reader

Comment by tialaramex | Hacker News Reader

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.

View on HN

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-...

   $ python
  >>> [hash(x) for x in range(4)]
  [0, 1, 2, 3]

Why do you think it isn't?

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).

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

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/#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.

> 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 ?

Then it's the good choice - I'm pretty confident the only reason std::hash is explicitly in the standard library is because it's the only way they could find to enable people to specialize hash functions for their own custom types - checking when it was introduced (C++ TR1: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n18...), std::hash is in a subsection of the "unordered containers" section and is really shown as an implementation detail of those (that has to be user-customizable).

If you use another hash table implementation, likely you're also going to choose a hash function that works well with it - I use Ankerl's in my own code for instance which 1/ comes with a modern hash implementation, wyhash, and 2/ obviously I specialize for the really specific cases I need performance for with the known statistical properties of my inputs. But I wouldn't want to pay for this cost for std::unordered_map

Luckily absl also provides absl::Hash, which doesn't have this problem.

Reply on news.ycombinator.com