3 ms·
Is there a quality benchmark for hashes? In general, how does one test the overall good uniqueness of a hash-function - e.g. less hash collisions on overall?
by malkia 11y ago
Is there a quality benchmark for hashes?
In general, how does one test the overall good uniqueness of a hash-function - e.g. less hash collisions on overall?
Is it done with some corpuses, like words in a dictionary, sentences from books, randomly generated strings, etc?
I'm just interrested how one goes to show that X has better quality than Y and it's still faster.
For example how a language runtime would choose it's hash function for built-in types?
- jandrewrogers 11y agoThe best single quality benchmark is the SMHasher test suite. For most purposes it is very thorough at finding defects in non-cryptographic hash function designs. A strong design has good statistical properties regardless of the types of key sets and SMHasher tests many kinds of key sets, including several that are designed to be pathological. There are two caveats with using SMHasher to be aware of. First, it does not thoroughly exercise the internals of some hash function constructions that you sometimes see in larger hashes. You can modify the source to add this coverage but it is not there by default. Second, the speed test implementation is broken. It is good enough to give you a rough idea of what is going on for bulk hashing relative to other algorithms, but the absolute performance measurement deviate from proper testing by a significant amount (up to 20-25% anecdotally). Also really fast small key algorithms can be significantly off. Basically, performance is measured using a method that Intel's performance measurement documentation strongly advises to not do. This can give inconsistent results even across CPUs that are based on the same microarchitecture.
- aappleby 11y agoYeah, some hashes (City) change behavior for small keys and I'm not bothering to exercise every possible key size thoroughly. The perf test was pretty quick and dirty - if you have better ways of benchmarking things I'd gladly accept a patch. :)
- gpakosz 11y agoWell at least what's awesome with SMHasher is that it's easy to integrate all hash functions into it and compare them even though the speed test is supposedly flawed.