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

31–40 of 42 posts

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

#31

Post by rurban »

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…

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!

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

#32

Post by CodesInChaos »

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…

> “we don’t store the keys and just rely on the hash to be really good”

I think that's fine if you actually use a really good hash (e.g. a 128-bit cryptographic PRF). But I wouldn't be comfortable with hashes shorter than that or which aren't crypto quality.

People already make such assumptions when assuming uniqueness v4 UUIDs.

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

#33

Post by herbstein »

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…

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

You can get this guarantee by using a random hash function if you don't support insertion and are fine with using a relatively larger amounts of memory.

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

#34

Post by [deleted] »

herbstein wrote: post #33
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…

> 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. You can get this guarantee by using a random hash function if you don't support insertion and are fine with using a relatively larger amounts of memory.

[deleted]

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

#35

Post by rurban »

rurban wrote: post #31
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…

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!

Added it to smhasher https://github.com/rurban/smhasher/#smhasher

It may be the fastest rust hash, but certainly not faster than other fast hashes. More like 2x slower.

xxh3, t1ha0, wyhash are all much faster on the 2 machines I tested it on, an old 7 years old Intel i5-2300, and a new Ryzen 3200U.

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

#36

Post by kouteiheika »

rurban wrote: post #35
rurban wrote: post #31

Earlier quoted context omitted.

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!

Added it to smhasher https://github.com/rurban/smhasher/#smhasher It may be the fastest rust hash, but certainly not faster than other fast hashes. More like 2x slower. xxh3, t1ha0, wyhash are all much faster on the 2 machines I tested it on, an old 7 years old Intel i5-2300, and a new Ryzen 3200U.

> It may be the fastest rust hash, but certainly not faster than other fast hashes. More like 2x slower.

If it's so much slower then most likely something is wrong.

1) Did you enable the AES instruction when compiling? (IIRC it's disabled by default) 2) When compiling the benchmark did you have cross-language inlining enabled? (IIRC you need to compile your C++ code with a specific version of Clang to get it to inline between Rust and C++)

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

#38

Post by rurban »

kouteiheika wrote: post #36
rurban wrote: post #35

Earlier quoted context omitted.

Added it to smhasher https://github.com/rurban/smhasher/#smhasher It may be the fastest rust hash, but certainly not faster than other fast hashes. More like 2x slower. xxh3, t1ha0, wyhash are all much faster on the 2 machines I tested it on, an old 7 years old Intel i5-2300, and a new Ryzen 3200U.

> It may be the fastest rust hash, but certainly not faster than other fast hashes. More like 2x slower. If it's so much slower then most likely something is wrong. 1) Did you enable the AES instruction when compiling? (IIRC it's disabled by default) 2) When compiling the benchmark did you have cross-language inlining enabled? (IIRC you need to compile your C++ code with a specific version of Clang to get it to inlin…

That might be it. gcc 10 with lto only, not clang. I also saw a lot if weird rust exception like functions brought into it.

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

#39

Post by zeroonetwothree »

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 :)

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

#40

Post by icsa »

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.
Post reply on HN