Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

ChibiHash: Small, Fast 64 bit hash function

nrk.neocities.org

Post reply on HN
Print view View original

11–20 of 33 posts

Re: ChibiHash: Small, Fast 64 bit hash function

#11

Post by xxs »

teo_zero wrote: post #4

While 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…

like mentioned x86/64 is quite generous with non-aligned access, yet on architectures that require aligned loads, they will be aligned (all lowest bits being zero at the start), so it will continue being aligned with each 8 byte load.

Re: ChibiHash: Small, Fast 64 bit hash function

#12

Post by palsecam »

Sesse__ wrote: post #10
palsecam wrote: post #7

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…

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.

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.

Re: ChibiHash: Small, Fast 64 bit hash function

#13

Post by gliptic »

vanderZwan wrote: post #9
gliptic wrote: post #8

Earlier quoted context omitted.

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 someon…

Maybe, but from what I've seen you run out of what theory can say about your non-crypto hash function pretty quickly.

Re: ChibiHash: Small, Fast 64 bit hash function

#15

Post by HelloNurse »

gliptic wrote: post #13
vanderZwan wrote: post #9

Earlier quoted context omitted.

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 someon…

Maybe, but from what I've seen you run out of what theory can say about your non-crypto hash function pretty quickly.

If this is the case, improvements come from tuning constants and calculation and tests are more valuable.

Re: ChibiHash: Small, Fast 64 bit hash function

#16

Post by Sesse__ »

palsecam wrote: post #12
Sesse__ wrote: post #10

Earlier quoted context omitted.

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.

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.

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?

Re: ChibiHash: Small, Fast 64 bit hash function

#18

Post by zamalek »

palsecam wrote: post #7

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…

From the archive link (blog post published 2018):

> To our surprise, we found a lack of published, well-optimized, large-data hash functions.

Murmur was released in 2008. Murmur3 in 2011. Release dates on higher quality functions are not easy to find, but I am sure that there were more around.

This type of thing is why I take Casey's claims with a huge dose of salt.

Re: ChibiHash: Small, Fast 64 bit hash function

#19

Post by GTP »

snvzz wrote: post #3

How does it compare to CRC64, for the purpose of detecting errors?

With CRC, you have algebraic guarantees on which kind of errors it detects (and which kind doesn't), while with hash functions collisions are essetially random (unless you have some clever insight on how it works internally). Which one is best, depends on the context.

Re: ChibiHash: Small, Fast 64 bit hash function

#20

Post by ur-whale »

palsecam wrote: post #7

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…

> See also: “Meow hash”

Meow hash may very well be fast on large data, but it completely fails the "small code" criteria, which is one of the clearly stated design goal of Chibi.

Generally speaking, the "code as small as possible" is IMO a design constraint that is very often under-estimated or even ignored for these type of algorithms, including the crypto hard ones.

I personally find the "code fits on half a page" metric very important: beyond satisfying some very personal sense of aesthetics, it buys you quite a lot of nice properties:

   - fits in head
   - inlines like a dream
   - easy to integrate
   - easy to do header only
   - easy to security audit
   - pretty hard to introduce bugs
   - nothing up my sleeve numbers pretty much obvious
For these reasons, I used to love the TEA (tiny encryption algorithm) [1] before cryptanalysis unfortunately showed it to be weak. Its successors (XXTEA, etc...) are already almost too big for my taste.

The speck cipher [2] is quite nice in that regard, in spite of its rather untrustworthy provenance.

[1] https://en.wikipedia.org/wiki/Tiny_Encryption_Algorithm

[2] https://en.wikipedia.org/wiki/Speck_(cipher)

Post reply on HN