4 ms·

Can you share more about the quality tests XXH3 fails? I don't know this space deeply, so I'm having trouble reconciling why XXH3 is popular if it fails tests.

neonsunset 1y ago
Same here. And I’m not aware of quality issues with GxHash either. For large(r) inputs I’d expect it to be easily competitive. And it’s better than XXH3 on my M4.
jandrewrogers 1y ago
The quality measure for a hash function is the probability that it is a random oracle for any given set of hash keys. Test suites will test tens of thousands of key sets (and billions of keys) with different properties. The distribution of probabilities across those tests can then be compared to the same distribution from a random oracle instead of a hash function. The best cryptographic hash functions, like SHA-256, are very close to a random oracle. Weaker cryptographic hash functions, like MD5, are significantly further away and stronger non-cryptographic hash functions, like rapidhash, are further yet. Most non-cryptographic hash functions are so far away from a random oracle in some of the tests as to be effectively broken. XXH3 is an example of this, anyone can try it for themselves using e.g. SMHasher3. For these “broken” cases, the hashes quite obviously don’t have a random distribution. There are a couple important points to take away from this: Hash quality is a function of the key set. If you know the properties of the key set ahead of time, which is often the case, then you can construct a hash function with narrowly optimal quality and performance even though it is totally broken for many other key sets that are out of scope. These almost always perform better than a general purpose hash function. This is a good performance engineering trick. For a hash function to claim suitability for “general purpose”, it needs to be consistently close to a random oracle across all key sizes and key distributions. If it breaks for one key set, it is broken for many others that you didn’t test. Being closer to a random oracle across tens of thousands of tests does not imply that the hash function is not broken (even SHA-256 may be broken) but it greatly improves the probability that you will never accidentally generate a key set that creates a severely biased hash distribution. Most non-cryptographic hash functions sacrifice quality to improve latency. Low latency and small I-cache footprint is very important for small-key hashing performance in real systems. The Pareto frontier of quality+latency is still quite an active area of research. Any hash function that was designed 10 years ago will be very far from that frontier, the state-of-the-art is fast-moving. There is a similar Pareto frontier for quality+throughput e.g. hashes used as block storage checksums. As for why XXH3 is popular, it is incessant self-promotion and marketing. I recently went down a rabbit hole of analyzing quality measures for many hash functions to see how far the state-of-the-art is from the cryptographic hash functions, so the data is pretty fresh. The great news is that non-cryptographic hash quality is now qualitatively far beyond what it was even a few years ago while at the same time improving performance.
- spiffytech 1y ago
  I'd love to read your findings if you've written them up.
  - camgunz 1y ago
    I'm also naive in this space, but I rely on rurban's smhasher for this: https://github.com/rurban/smhasher https://github.com/rurban/smhasher. There's also smhasher3: https://github.com/fwojcik/smhasher3/tree/main/results https://github.com/fwojcik/smhasher3/tree/main/results

neonsunset 1y ago

Same here. And I’m not aware of quality issues with GxHash either. For large(r) inputs I’d expect it to be easily competitive. And it’s better than XXH3 on my M4.

jandrewrogers 1y ago

The quality measure for a hash function is the probability that it is a random oracle for any given set of hash keys. Test suites will test tens of thousands of key sets (and billions of keys) with different properties. The distribution of probabilities across those tests can then be compared to the same distribution from a random oracle instead of a hash function. The best cryptographic hash functions, like SHA-256, are very close to a random oracle. Weaker cryptographic hash functions, like MD5, are significantly further away and stronger non-cryptographic hash functions, like rapidhash, are further yet. Most non-cryptographic hash functions are so far away from a random oracle in some of the tests as to be effectively broken. XXH3 is an example of this, anyone can try it for themselves using e.g. SMHasher3. For these “broken” cases, the hashes quite obviously don’t have a random distribution. There are a couple important points to take away from this: Hash quality is a function of the key set. If you know the properties of the key set ahead of time, which is often the case, then you can construct a hash function with narrowly optimal quality and performance even though it is totally broken for many other key sets that are out of scope. These almost always perform better than a general purpose hash function. This is a good performance engineering trick. For a hash function to claim suitability for “general purpose”, it needs to be consistently close to a random oracle across all key sizes and key distributions. If it breaks for one key set, it is broken for many others that you didn’t test. Being closer to a random oracle across tens of thousands of tests does not imply that the hash function is not broken (even SHA-256 may be broken) but it greatly improves the probability that you will never accidentally generate a key set that creates a severely biased hash distribution. Most non-cryptographic hash functions sacrifice quality to improve latency. Low latency and small I-cache footprint is very important for small-key hashing performance in real systems. The Pareto frontier of quality+latency is still quite an active area of research. Any hash function that was designed 10 years ago will be very far from that frontier, the state-of-the-art is fast-moving. There is a similar Pareto frontier for quality+throughput e.g. hashes used as block storage checksums. As for why XXH3 is popular, it is incessant self-promotion and marketing. I recently went down a rabbit hole of analyzing quality measures for many hash functions to see how far the state-of-the-art is from the cryptographic hash functions, so the data is pretty fresh. The great news is that non-cryptographic hash quality is now qualitatively far beyond what it was even a few years ago while at the same time improving performance.

spiffytech 1y ago
I'd love to read your findings if you've written them up.
- camgunz 1y ago
  I'm also naive in this space, but I rely on rurban's smhasher for this: https://github.com/rurban/smhasher https://github.com/rurban/smhasher. There's also smhasher3: https://github.com/fwojcik/smhasher3/tree/main/results https://github.com/fwojcik/smhasher3/tree/main/results