ChibiHash: Small, Fast 64 bit hash function
nrk.neocities.org
ChibiHash: Small, Fast 64 bit hash function
1–10 of 33 posts
Re: ChibiHash: Small, Fast 64 bit hash function
#2SMHasher/Murmurhash author here - I don't see anything fundamentally wrong with this hash function, it uses basically the same operations as the Murmur family (and a lot of other hashes at this point).
The handling of the "tail" of the key (the last < 32 bytes) is slightly odd (the "if (l & 1) { mix 1 byte of key }" happens before 8-byte chunks and 2-byte chunks), but if it passes SMHasher it should be fine for general use.
Re: ChibiHash: Small, Fast 64 bit hash function
#3How does it compare to CRC64, for the purpose of detecting errors?
Re: ChibiHash: Small, Fast 64 bit hash function
#4While the benefit of processing chunks of 8 bytes is obvious, what's the purpose of grouping those into macrogroups of 4? Does it trigger any implicit parallelism I failed to spot? Or is it just to end this phase with the 4 h[] having had the same amount of entropy, and thus starting the next one with h[0]?
> The way it loads the 8 bytes is also important. The correct way is to load via shift+or > This is free of any UB, works on any alignment and on any machine regardless of it's endianness. It's also fast, gcc and clang recognize this pattern and optimize it into a single mov instruction on x86 targets.
Is a single MOV instruction still fast when the 8 bytes begin on an odd address?
Re: ChibiHash: Small, Fast 64 bit hash function
#5SMHasher/Murmurhash author here - I don't see anything fundamentally wrong with this hash function, it uses basically the same operations as the Murmur family (and a lot of other hashes at this point). The handling of the "tail" of the key (the last < 32 bytes) is slightly odd (the "if (l & 1) { mix 1 byte of key }" happens before 8-byte chunks and 2-byte chunks), but if it passes SMHasher it should be fine for gener…
> if it passes SMHasher it should be fine for general use.
Author of the post writes:
> I kept making changes until the tests passed.
If SMHasher has become a target, shouldn't it be considered a bad measure now? [1]
Re: ChibiHash: Small, Fast 64 bit hash function
#6While the benefit of processing chunks of 8 bytes is obvious, what's the purpose of grouping those into macrogroups of 4? Does it trigger any implicit parallelism I failed to spot? Or is it just to end this phase with the 4 h[] having had the same amount of entropy, and thus starting the next one with h[0]? > The way it loads the 8 bytes is also important. The correct way is to load via shift+or > This is free of any…
> Is a single MOV instruction still fast when the 8 bytes begin on an odd address?
On x86, yes. There is no performance penalty for misaligned loads, except when the misaligned load also happens to straddle a cache line boundary, in which case it is slower, but only marginally so.
Re: ChibiHash: Small, Fast 64 bit hash function
#7See also: “Meow hash” by the legendary Casey Muratori, a fast non-cryptographic hash function: https://github.com/cmuratori/meow_hash
> It’s the fastest hash function we know of, and we have benchmarked all the ones we could find. On modern Intel x64 CPUs, it hashes 16 bytes per cycle single-threaded. This means in cache it can hash at a rate of 64 gigabytes per second on a 4.2gHz machine. Out of cache, it hashes at whatever speed your main memory bus can provide to a single core, since that is usually the limiting factor on modern x64 CPUs.
> It has also now been tuned to be the fastest hash on small inputs, too. Despite the fact that it is a full 128-bit hash, it still outperforms “fast” 64-bit hashes across all input sizes.
— https://archive.is/CQOVm (originally https://mollyrocket.com/meowhash)
Discussion on HN: https://news.ycombinator.com/item?id=29038813 & https://news.ycombinator.com/item?id=18262627
Re: ChibiHash: Small, Fast 64 bit hash function
#8SMHasher/Murmurhash author here - I don't see anything fundamentally wrong with this hash function, it uses basically the same operations as the Murmur family (and a lot of other hashes at this point). The handling of the "tail" of the key (the last < 32 bytes) is slightly odd (the "if (l & 1) { mix 1 byte of key }" happens before 8-byte chunks and 2-byte chunks), but if it passes SMHasher it should be fine for gener…
> if it passes SMHasher it should be fine for general use. Author of the post writes: > I kept making changes until the tests passed. If SMHasher has become a target, shouldn't it be considered a bad measure now? [1] [1]: https://en.wikipedia.org/wiki/Goodhart%27s_law
Hash tests have always been targets. What else are you supposed to do for non-cryptographic hashes?
Re: ChibiHash: Small, Fast 64 bit hash function
#9Earlier quoted context omitted.
> if it passes SMHasher it should be fine for general use. Author of the post writes: > I kept making changes until the tests passed. If SMHasher has become a target, shouldn't it be considered a bad measure now? [1] [1]: https://en.wikipedia.org/wiki/Goodhart%27s_law
Hash tests have always been targets. What else are you supposed to do for non-cryptographic hashes?
Not OP, but I suppose there might be a difference between blindly trying to pass a test by tweaking numbers, or a more principled approach to figuring out how to introduce better randomness.
OTOH, I would expect that tests for hashing and random number generation in particular would be naturally resistant to overfitting, due to the nature of the problem. But I'm not an expert at this topic, so I'd love to hear someone else's take on that
Re: ChibiHash: Small, Fast 64 bit hash function
#10See also: “Meow hash” by the legendary Casey Muratori, a fast non-cryptographic hash function: https://github.com/cmuratori/meow_hash > It’s the fastest hash function we know of, and we have benchmarked all the ones we could find. On modern Intel x64 CPUs, it hashes 16 bytes per cycle single-threaded. This means in cache it can hash at a rate of 64 gigabytes per second on a 4.2gHz machine. Out of cache, it hashes at…
Not sure why people keep claiming it's the “fastest” when it's far down the list on the SMHasher benchmark list:
https://rurban.github.io/smhasher/doc/table.html
In particular, rapidhash is three times as fast for small inputs and is portable (unlike meow_hash). Plus meow fails one of the SMHasher quality tests.