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

11–20 of 42 posts

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

#11

Post by boulos »

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/d2a305811972f391...

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

#13

Post by [deleted] »

zucker42 wrote: post #10

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]

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

#15

Post by [deleted] »

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…

[deleted]

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

#16

Post by wangyi_fudan »

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

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

#17

Post by graderjs »

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 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.

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

#18

Post by wangyi_fudan »

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.

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

#20

Post by stingraycharles »

graderjs wrote: post #17
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 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.
Post reply on HN