←back to thread

ChibiHash: Small, Fast 64 bit hash function

(nrk.neocities.org)
104 points thunderbong | 5 comments | 18 Nov 24 00:23 UTC | HN request time: 0.616s | source
Show context
palsecam ◴[18 Nov 24 10:52 UTC] No.42171316[source]▶
See 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

replies(3): >>42171727 #>>42172847 #>>42173408 #
1. Sesse__ ◴[18 Nov 24 12:15 UTC] No.42171727[source]▶
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.

replies(2): >>42171802 #>>42183422 #
2. palsecam ◴[18 Nov 24 12:30 UTC] No.42171802[source]▶
Right, Meow is not the best when it comes to small inputs.

It shines for large inputs (it’s far up the SMHasher list you linked in this case).

It offers a good compromise; it’s not bad (good, even) for both large and small inputs.

Granted, rapidhash is quite good on both fronts, too.

replies(1): >>42172274 #
3. Sesse__ ◴[18 Nov 24 13:52 UTC] No.42172274[source]▶
Well, it's not even the best AES-NI hash on the list (for large nor small inputs), and it's not passing the quality tests, so why bother?
4. nwellnhof ◴[19 Nov 24 13:52 UTC] No.42183422[source]▶
I wouldn't consider a hash function that relies on 64-bit multiplication truly portable. Its performance will suffer considerably on a 32-bit system. Note that this applies to both Rapidhash and ChibiHash.
replies(1): >>42184161 #
5. Sesse__ ◴[19 Nov 24 15:04 UTC] No.42184161[source]▶
Well, even without taking into account that 32-bit systems are increasingly becoming extinct, it's less catastrophic than one might think. You get four muls instead of one and then a little carry propagation; I guess less if you have 32x32 -> 64 muls available? (I haven't thought deeply about it.) Certainly anything that relies on AES-NI would be much worse. But I guess your best shot in Murmur3, then.