MetroHash: Faster, Better Hash Functions
jandrewrogers.com
MetroHash: Faster, Better Hash Functions
1–10 of 23 posts
Re: MetroHash: Faster, Better Hash Functions
#2How does it compare to xxHash? https://github.com/Cyan4973/xxHash
Comparing MetroHash to CityHash is not really fair. Why would anyone use CityHash in 2015?
Re: MetroHash: Faster, Better Hash Functions
#3How does it compare to xxHash? https://github.com/Cyan4973/xxHash Comparing MetroHash to CityHash is not really fair. Why would anyone use CityHash in 2015?
It looks like 'FarmHash' is the successor from the CityHash authors. Does xxHash have 128/256-bit variants?
Re: MetroHash: Faster, Better Hash Functions
#4I would be interested to see what the x64 versions were like.
Re: MetroHash: Faster, Better Hash Functions
#5How does it compare to xxHash? https://github.com/Cyan4973/xxHash Comparing MetroHash to CityHash is not really fair. Why would anyone use CityHash in 2015?
With respect to xxHash64, the closest (and slowest) algorithm is Metro64. I just ran it on my laptop using SMHasher for comparison purposes.
- Metro64 is about 10-15% faster for bulk hashing
- Metro64 is about 2x faster for small keys
- Metro64 has better statistical quality
These days, most people should be using 128-bit hash functions. Not only are they more collision resistant, they also run faster on modern microarchitectures.
Measuring CityHash at 32-bits is not a realistic measurement of its performance. Its structure is optimized for 64-128 bit hashes, which it actually does quite well for some types of keys.
Re: MetroHash: Faster, Better Hash Functions
#6Is 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?
Re: MetroHash: Faster, Better Hash Functions
#7Is 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…
The 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.
Re: MetroHash: Faster, Better Hash Functions
#8Possibly stupid question... Why there's _1 and _2 variants for each hash size?
Re: MetroHash: Faster, Better Hash Functions
#9Possibly stupid question... Why there's _1 and _2 variants for each hash size?
Mostly because I could. There are use cases for statistically independent hashes, such as Bloom filters, though these can sometimes be satisfied by other means. Having two independent functions for each gives people flexibility and also serves as a (trivial) proof of capability.
It would be a small thing to generate a dozen statistically independent versions of each hash algorithm, primarily because the generation process is so straightforward. This by itself is unique for popular hash functions. One possible use case for random generation of these functions is security through obscurity by having every hash table implementation using a different function to make them more difficult to attack.
Re: MetroHash: Faster, Better Hash Functions
#10How does it compare to xxHash? https://github.com/Cyan4973/xxHash Comparing MetroHash to CityHash is not really fair. Why would anyone use CityHash in 2015?
I do it all the time. CityHash has been around long enough that it is broadly included in most hash suites on most platforms, but is new enough that it doesn't suck as bad as its predecessors.