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

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

github.com

Post reply on HN
Print view View original

21–30 of 42 posts

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

#21

Post by kouteiheika »

wangyi_fudan wrote: post #18
kouteiheika wrote: post #7

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

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.

Apparently there is a patch for the SMHasher here which adds support for ahash:

https://github.com/tkaitchuck/aHash/tree/master/smhasher

There are also ahash's own benchmarks here:

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.

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

#22

Post by Bootvis »

stingraycharles wrote: post #20
graderjs wrote: post #17

Earlier quoted context omitted.

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…

To be fair 2^64 keys is a lot , to the point that it cannot possibly fit into memory with today’s hardware.

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.

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

#23

Post by hansvm »

stingraycharles wrote: post #20
graderjs wrote: post #17

Earlier quoted context omitted.

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…

To be fair 2^64 keys is a lot , to the point that it cannot possibly fit into memory with today’s hardware.

We're getting close. There's way more RAM than that in the world, and a quick search turned up a single machine from a few years ago that was only off by 160x or so.

Even without relying on the pigeonhole principle though you still have the birthday paradox. As a ballpark estimate, if you have N keys then you'd expect a 50/50 chance of at least one collision with sqrt(N) hashes -- 2^32 for this problem.

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

#24

Post by wangyi_fudan »

kouteiheika wrote: post #21
wangyi_fudan wrote: post #18

Earlier quoted context omitted.

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.

Apparently there is a patch for the SMHasher here which adds support for ahash: https://github.com/tkaitchuck/aHash/tree/master/smhasher There are also ahash's own benchmarks here: 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 su…

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.

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

#25

Post by laserbeam »

wangyi_fudan wrote: post #16
laserbeam wrote: post #14

Meow hash claims 3-4x faster hashing over this, still passes smhasher, and is a few years old. 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

moew is not good at short keys. portability is also a concern

Indeed, regarding portability moew was definitely made with gamedev in mind, without concern for portability.

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

#26

Post by kouteiheika »

wangyi_fudan wrote: post #24
kouteiheika wrote: post #21

Earlier quoted context omitted.

Apparently there is a patch for the SMHasher here which adds support for ahash: https://github.com/tkaitchuck/aHash/tree/master/smhasher There are also ahash's own benchmarks here: 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 su…

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.

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.

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

#27

Post by injinj »

wangyi_fudan wrote: post #16
laserbeam wrote: post #14

Meow hash claims 3-4x faster hashing over this, still passes smhasher, and is a few years old. 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

moew is not good at short keys. portability is also a concern

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/

[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/3ce2b23e0d9853fe...

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

#28

Post by [deleted] »

stingraycharles wrote: post #20
graderjs wrote: post #17

Earlier quoted context omitted.

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…

To be fair 2^64 keys is a lot , to the point that it cannot possibly fit into memory with today’s hardware.

[deleted]

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

#29

Post by kaoD »

Bootvis wrote: post #22
stingraycharles wrote: post #20

Earlier quoted context omitted.

To be fair 2^64 keys is a lot , to the point that it cannot possibly fit into memory with today’s hardware.

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.

But even after only one item is inserted the probability of collision is >0. Yes, it is very very very (very) small, but it's still there!

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

#30

Post by rurban »

boulos wrote: post #11

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

I do a similar thing with constant keys. Check the result with a simple memcmp/strcmp of the key for false positives. But only usable for constant perfect hashes.

64 bit is not good enough for that claim. 128 would be good, 256 perfect for production use. Regardless of the hash function quality. wyhash is a very good hash, the best and fastest portable one.

Post reply on HN