6 ms·

New Bare Hash Map: 2X-3X Speedup over SOTA

74 points by wangyi_fudan 6y ago

adamnemecek 6y ago
#ifndef WYHASH_CONDOM A what now? https://github.com/wangyi-fudan/wyhash/blob/master/wyhash.h#L14 https://github.com/wangyi-fudan/wyhash/blob/master/wyhash.h#...
- bfung 6y ago
  Protection, right? extra protection against entropy loss A little brogramming and some google translate and here we are.
- rurban 6y ago
  Against valgrind and asan. And the very rare cases when the key is at the end of a page, and the next page belongs to someone else.
fakename11 6y ago
They should throw the "Simple Example" through a code formatter. Would look more professional. Other than that, this is a nice project, congrats to the author.
deleted 6y ago
[deleted]
jandrewrogers 6y ago
A change in the last ten years is that it now makes a lot of sense, due to the development of nuanced algorithms, to optimize your hash infrastructure for the details of the specific application. This has been a positive development generally when it comes to efficient software.
kouteiheika 6y ago
According to this ahash is faster: https://github.com/tkaitchuck/aHash/blob/master/compare/readme.md https://github.com/tkaitchuck/aHash/blob/master/compare/read... Did anything change?
- wangyi_fudan 6y ago
  I am also wondering whether ahash is faster. ahash is developed with rust. We need a head to head comparsion. However, it is not available in SMHasher package.
  - kouteiheika 6y ago
    Apparently there is a patch for the SMHasher here which adds support for ahash: https://github.com/tkaitchuck/aHash/tree/master/smhasher https://github.com/tkaitchuck/aHash/tree/master/smhasher There are also ahash's own benchmarks here: https://github.com/tkaitchuck/aHash/blob/master/compare/tests/compare.rs https://github.com/tkaitchuck/aHash/blob/master/compare/test... They use the wyhash Rust crate, so if wyhash itself was updated doing a head to head comparison would boil down to updating the wyhash crate and rerunning ahash's benchmark suite.
    - wangyi_fudan 6y ago
      wyhash crate is not wyhash itself. It depends on the skill of the translator and the wyhash version. wyhash has been improved significantly version by version. Also ahash should submit a PR to smhasher and play with ~100 other hash functions there.
      - kouteiheika 6y ago
        Okay, I've quickly added the new wyhash to ahash's benchmark suite (the original C version converted to Rust with c2rust so that it can be inlined by the compiler) and reran the benchmarks; here are the results on my machine: 1kb string: - ahash: 23.0ns - wyhash (rust crate): 54.2ns - wyhash (new): 34.8ns u64: - ahash: 0.69ns - wyhash (rust crate): 1.6ns - wyhash (new): 0.97ns So the new version is faster, but it looks like ahash is still state-of-the-art when it comes to speed.
    - rurban 6y ago
      Interestingly this patch never was submitted to me. Just saw it now. Will add it asap. Very interesting is his claim to create wyhash collisions at will. Even with bad keys, not bad seeds!
dietrichepp 6y ago
I see my name in the "thanks" section, it's nice, but I don't know why I'm there.
- soedirgo 6y ago
  Probably for your PR from way back when: https://news.ycombinator.com/item?id=19359870 https://news.ycombinator.com/item?id=19359870
pansa2 6y ago
See also “New fastest portable hash: wyhash” from 2019: https://news.ycombinator.com/item?id=19357895 https://news.ycombinator.com/item?id=19357895
zucker42 6y ago
Based on the comment in the source, the hash table doesn't handle hash collisions. And furthermore, I don't see the code which benchmarks this versus other hash tables, just the claim that it is 2-3x faster. Specifically, comparisons for different tables sizes using the same hash function would be good. The API this presents is not really inspiring either.
- deleted 6y ago
  [deleted]
boulos 6y ago
I feel like you’d want something a bit safer than “we don’t store the keys and just rely on the hash to be really good” [1], putting “please do not use this for serious tasks” in a comment embedded in the header file isn’t a clear enough warning. It’s not clear to me that that probability of collision assumptions hold. It’s basically assuming that the hashing is perfect and distributes any inputs to the full 64-bit space with uniform probability. That’s the usual hash map / randomized algorithm hope, but does BigCrush or similar avalanche testing really prove that? (Presumably not, otherwise there wouldn’t be image attacks for things like md5). [1] https://github.com/wangyi-fudan/wyhash/blob/d2a305811972f391d472cd57c9d542411773ead1/wyhash.h#L204 https://github.com/wangyi-fudan/wyhash/blob/d2a305811972f391...
- deleted 6y ago
  [deleted]
- graderjs 6y ago
  I agree that not storing keys is riskier, and it's not a risk that's mitigated even if it is a perfect uniform distribution because you can still have collisions. Maybe I don't understand the reasons for that design but personally I don't think it's a good design for a hash table. But even so the hash underlying it is a very good hash. Big crush and smhasher give a good indication of uniform distribution, but nothing can guarantee no collisions because you're always going to have collisions it's always a possibility. Even if you have a perfect permutation of the 64 bit space, the minute you go beyond 64 bits of keys you're going to collide within 64 bits of hash. By all the tests they run md5 is a much poorer hash than many others. But it's a or it was a cryptographic hash. It's different.
  - stingraycharles 6y ago
    To be fair 2^64 keys is a lot, to the point that it cannot possibly fit into memory with today’s hardware.
    - Bootvis 6y ago
      According to the Birthday paradox you can expect a collision after approx 2^32 keys. Whether this is small or big probably depends on your use case.
laserbeam 6y ago
Meow hash claims 3-4x faster hashing over this, still passes smhasher, and is a few years old. https://mollyrocket.com/meowhash https://mollyrocket.com/meowhash And there are a bunch of other good suggestions here in the comments looking at around the same 50-60gb/sec speed
- wangyi_fudan 6y ago
  moew is not good at short keys. portability is also a concern
  - laserbeam 6y ago
    Indeed, regarding portability moew was definitely made with gamedev in mind, without concern for portability.
  - injinj 6y ago
    The meow 0.4 was faster at short keys, but failed at the smhasher "LongNeighborTest" [1]. However, doubling the AES rounds makes it pass that test. Two rounds is enough for full diffusion in AES [2]. I recently looked at computing 4 Meow keys per hash function [3], and found the speedup to be almost 2x in a microbench. That puts it in rare territory for hash speed. [1] https://github.com/injinj/smhasher/ https://github.com/injinj/smhasher/ [2] Section 5.4 of Introduction to Cryptography by Trappe and Washington -- It can be shown that two rounds are sufficient to obtain full diffusion, namely, each of the 128 output bits depends on each of the 128 input bits. [3] https://github.com/raitechnology/raikv/blob/3ce2b23e0d9853fe4babcd9127d81faa1ebdfe86/src/key_hash.c#L1690 https://github.com/raitechnology/raikv/blob/3ce2b23e0d9853fe...
ddtaylor 6y ago
https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function
zeroonetwothree 6y ago
I had an assignment in college many years ago that was partially graded on performance. It amounted to basically a hash table with a bunch of lookups. To optimize mine I had it not store the keys, fortunately I was lucky and the test data they used didn’t cause any collisions. As a result mine was the fastest in the class :)
icsa 6y ago
With respect to wyrand, it seems that all prime numbers are not created equal. I implemented wyrand() using the two primes just below 2^64. The upper 53 bits of each 64-bit random deviate was used to generate a uniform [0,1) floating point deviate. The expected value of the sum of the uniform floating point deviates is 0.5 * #deviates. When using the two primes numbers above, the resulting value was 0.6430236 * #deviates - indicating significant bias in the random deviates generated by wyhash for those particular prime numbers.
- wangyi_fudan 6y ago
  you sure make popcount(prime)==32
  - icsa 6y ago
    Thanks! Is that requirement in the documentation?

74 points by wangyi_fudan 6y ago

#ifndef WYHASH_CONDOM A what now? https://github.com/wangyi-fudan/wyhash/blob/master/wyhash.h#L14 https://github.com/wangyi-fudan/wyhash/blob/master/wyhash.h#...

bfung 6y ago
Protection, right? extra protection against entropy loss A little brogramming and some google translate and here we are.
rurban 6y ago
Against valgrind and asan. And the very rare cases when the key is at the end of a page, and the next page belongs to someone else.

fakename11 6y ago

They should throw the "Simple Example" through a code formatter. Would look more professional. Other than that, this is a nice project, congrats to the author.

deleted 6y ago

[deleted]

jandrewrogers 6y ago

A change in the last ten years is that it now makes a lot of sense, due to the development of nuanced algorithms, to optimize your hash infrastructure for the details of the specific application. This has been a positive development generally when it comes to efficient software.

kouteiheika 6y ago

According to this ahash is faster: https://github.com/tkaitchuck/aHash/blob/master/compare/readme.md https://github.com/tkaitchuck/aHash/blob/master/compare/read... Did anything change?

wangyi_fudan 6y ago
I am also wondering whether ahash is faster. ahash is developed with rust. We need a head to head comparsion. However, it is not available in SMHasher package.
- kouteiheika 6y ago
  Apparently there is a patch for the SMHasher here which adds support for ahash: https://github.com/tkaitchuck/aHash/tree/master/smhasher https://github.com/tkaitchuck/aHash/tree/master/smhasher There are also ahash's own benchmarks here: https://github.com/tkaitchuck/aHash/blob/master/compare/tests/compare.rs https://github.com/tkaitchuck/aHash/blob/master/compare/test... They use the wyhash Rust crate, so if wyhash itself was updated doing a head to head comparison would boil down to updating the wyhash crate and rerunning ahash's benchmark suite.
  - wangyi_fudan 6y ago
    wyhash crate is not wyhash itself. It depends on the skill of the translator and the wyhash version. wyhash has been improved significantly version by version. Also ahash should submit a PR to smhasher and play with ~100 other hash functions there.
    - kouteiheika 6y ago
      Okay, I've quickly added the new wyhash to ahash's benchmark suite (the original C version converted to Rust with c2rust so that it can be inlined by the compiler) and reran the benchmarks; here are the results on my machine: 1kb string: - ahash: 23.0ns - wyhash (rust crate): 54.2ns - wyhash (new): 34.8ns u64: - ahash: 0.69ns - wyhash (rust crate): 1.6ns - wyhash (new): 0.97ns So the new version is faster, but it looks like ahash is still state-of-the-art when it comes to speed.
  - rurban 6y ago
    Interestingly this patch never was submitted to me. Just saw it now. Will add it asap. Very interesting is his claim to create wyhash collisions at will. Even with bad keys, not bad seeds!

dietrichepp 6y ago

I see my name in the "thanks" section, it's nice, but I don't know why I'm there.

soedirgo 6y ago
Probably for your PR from way back when: https://news.ycombinator.com/item?id=19359870 https://news.ycombinator.com/item?id=19359870

pansa2 6y ago

See also “New fastest portable hash: wyhash” from 2019: https://news.ycombinator.com/item?id=19357895 https://news.ycombinator.com/item?id=19357895

zucker42 6y ago

Based on the comment in the source, the hash table doesn't handle hash collisions. And furthermore, I don't see the code which benchmarks this versus other hash tables, just the claim that it is 2-3x faster. Specifically, comparisons for different tables sizes using the same hash function would be good. The API this presents is not really inspiring either.

deleted 6y ago
[deleted]

boulos 6y ago

I feel like you’d want something a bit safer than “we don’t store the keys and just rely on the hash to be really good” [1], putting “please do not use this for serious tasks” in a comment embedded in the header file isn’t a clear enough warning. It’s not clear to me that that probability of collision assumptions hold. It’s basically assuming that the hashing is perfect and distributes any inputs to the full 64-bit space with uniform probability. That’s the usual hash map / randomized algorithm hope, but does BigCrush or similar avalanche testing really prove that? (Presumably not, otherwise there wouldn’t be image attacks for things like md5). [1] https://github.com/wangyi-fudan/wyhash/blob/d2a305811972f391d472cd57c9d542411773ead1/wyhash.h#L204 https://github.com/wangyi-fudan/wyhash/blob/d2a305811972f391...

deleted 6y ago
[deleted]
graderjs 6y ago
I agree that not storing keys is riskier, and it's not a risk that's mitigated even if it is a perfect uniform distribution because you can still have collisions. Maybe I don't understand the reasons for that design but personally I don't think it's a good design for a hash table. But even so the hash underlying it is a very good hash. Big crush and smhasher give a good indication of uniform distribution, but nothing can guarantee no collisions because you're always going to have collisions it's always a possibility. Even if you have a perfect permutation of the 64 bit space, the minute you go beyond 64 bits of keys you're going to collide within 64 bits of hash. By all the tests they run md5 is a much poorer hash than many others. But it's a or it was a cryptographic hash. It's different.
- stingraycharles 6y ago
  To be fair 2^64 keys is a lot, to the point that it cannot possibly fit into memory with today’s hardware.
  - Bootvis 6y ago
    According to the Birthday paradox you can expect a collision after approx 2^32 keys. Whether this is small or big probably depends on your use case.

laserbeam 6y ago

Meow hash claims 3-4x faster hashing over this, still passes smhasher, and is a few years old. https://mollyrocket.com/meowhash https://mollyrocket.com/meowhash And there are a bunch of other good suggestions here in the comments looking at around the same 50-60gb/sec speed

wangyi_fudan 6y ago
moew is not good at short keys. portability is also a concern
- laserbeam 6y ago
  Indeed, regarding portability moew was definitely made with gamedev in mind, without concern for portability.
- injinj 6y ago
  The meow 0.4 was faster at short keys, but failed at the smhasher "LongNeighborTest" [1]. However, doubling the AES rounds makes it pass that test. Two rounds is enough for full diffusion in AES [2]. I recently looked at computing 4 Meow keys per hash function [3], and found the speedup to be almost 2x in a microbench. That puts it in rare territory for hash speed. [1] https://github.com/injinj/smhasher/ https://github.com/injinj/smhasher/ [2] Section 5.4 of Introduction to Cryptography by Trappe and Washington -- It can be shown that two rounds are sufficient to obtain full diffusion, namely, each of the 128 output bits depends on each of the 128 input bits. [3] https://github.com/raitechnology/raikv/blob/3ce2b23e0d9853fe4babcd9127d81faa1ebdfe86/src/key_hash.c#L1690 https://github.com/raitechnology/raikv/blob/3ce2b23e0d9853fe...

ddtaylor 6y ago

https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function

zeroonetwothree 6y ago

I had an assignment in college many years ago that was partially graded on performance. It amounted to basically a hash table with a bunch of lookups. To optimize mine I had it not store the keys, fortunately I was lucky and the test data they used didn’t cause any collisions. As a result mine was the fastest in the class :)

icsa 6y ago

With respect to wyrand, it seems that all prime numbers are not created equal. I implemented wyrand() using the two primes just below 2^64. The upper 53 bits of each 64-bit random deviate was used to generate a uniform [0,1) floating point deviate. The expected value of the sum of the uniform floating point deviates is 0.5 * #deviates. When using the two primes numbers above, the resulting value was 0.6430236 * #deviates - indicating significant bias in the random deviates generated by wyhash for those particular prime numbers.

wangyi_fudan 6y ago
you sure make popcount(prime)==32
- icsa 6y ago
  Thanks! Is that requirement in the documentation?