Operations of the form "v[0] ^= rotate_right((v[0] * k2) + v[1], 17) * k1;" aren't reversible, so your intermediate states are leaking a few bits of entropy. Probably not enough to matter since the internal state is 256 bits - if it passes SMHasher, I'd use it. :)
MetroHash: Faster, Better Hash Functions
11–20 of 23 posts
Re: MetroHash: Faster, Better Hash Functions
#12Is 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 n…
Yeah, 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. :)
Re: MetroHash: Faster, Better Hash Functions
#13A few recommendations from the peanut gallery:
1. The files have .cpp extensions, but they seem like plain C other than static_cast/reinterpret_cast? For integrating with other software just using C would be better. Use 'export "C"' in the header file, though
2. It's reasonable to optimize for intel CPUs, but the current implementations of read_u64() and friends would crash if used on CPUs that don't allow unaligned reads. It would be nice if that was #ifdef'ed so that it was portable.
3. Similarly, it seems that the result of the hash functions are endian-dependent. Optimizing for little-endian makes sense, but it would be nice if they produced consistent answers on big-endian CPUs. This is often a requirement for uses like on-disk bloomfilters. Probably all that is required is doing endian swaps in read_u64()/etc on big-endian.
Re: MetroHash: Faster, Better Hash Functions
#14How 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?
My smhasher fork has both:
https://github.com/rurban/smhasher/
Comparable results for xxHash and the new metrohash will be uploaded soon. These things take time.
But I'm more interested in comparing it to HW CRC32-C, the fastest and best hash so far, 2x faster than metro.
Re: MetroHash: Faster, Better Hash Functions
#15How 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 micro…
Most is true, but:
128-bit hash functions for hash table makes no sense, unless you have 1TB tables in external memory. And for security 128 is peanuts, you start with 256 there.
First you need 4x more space, when you store the hash also for faster collision checks. 32bit is normal. cache size is more important than cpu mostly.
Second, collision resistancy on normal sized hash tables take only the first 7-15 bits, so calculating the other 113 bits makes not much sense. 32 bit is usually enough unless you need huge tables, where 64bit is enough.
Re: MetroHash: Faster, Better Hash Functions
#16I would be interested to see what the x64 versions were like.
These versions only work on 64bit machines, optimized for x64 and arm64.
The crc variant only on those.
Re: MetroHash: Faster, Better Hash Functions
#17Possibly 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 pr…
Well, we don't call that "security by obscurity", we call that "universal hashing", which is provable secure.
The rules to create the constants would nice to have to actually create good universal hashing. 2 variants are not enough yet, but the quality of _1 and _2 are already much better than the typical universal hash function variant.
Re: MetroHash: Faster, Better Hash Functions
#18Earlier quoted context omitted.
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 n…
Yeah, 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. :)
Well 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.
Re: MetroHash: Faster, Better Hash Functions
#19I've updated now my smhasher results at https://github.com/rurban/smhasher including metrohash and xxHash but not FarmHash yet.
From the good enough hash functions, metrohash are by far the fastest, so they should be the new default on 64bit machines. On x86_64 and arm8 the crc variants are the best.
For 32bit we are stuck with Murmur still.
Re: MetroHash: Faster, Better Hash Functions
#20How 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?
My smhasher fork has both: https://github.com/rurban/smhasher/ Comparable results for xxHash and the new metrohash will be uploaded soon. These things take time. But I'm more interested in comparing it to HW CRC32-C, the fastest and best hash so far, 2x faster than metro.
For the record, CRC32-C doesn't appear in your summary table