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

New fastest portable hash: wyhash

github.com

Post reply on HN
Print view View original

31–40 of 52 posts

Re: New fastest portable hash: wyhash

#31

Post by mises »

winnin_the_game wrote: post #28

To me, the most interesting part: >> Even if [...] worse hash functions will lead to more collisions, the overall speed advantage beats the slightly worse quality.

I'm not sure if that part is correct. If I use something like SHA1 or MD5 (yes, I know they're no longer considered secure), know with essentially 100% certainty that I will not get a collision. This means I don't have to implement chaining, quadratic probing, or another method of collision avoidance. Though it might cost some speed on the end use of the app, it's often easier for initial development because I simply have to write less code.

Maybe a more experienced dev can comment on this? Still learning here, and haven't spent time in a lot of large codebases.

Re: New fastest portable hash: wyhash

#32

Post by throwawaymath »

WallWextra wrote: post #5
panic wrote: post #4

Here's a link to wyhash itself: https://github.com/wangyi-fudan/wyhash

Maybe the link could be updated to point to this instead?

Yeah the submitter didn't link to wyhash, they linked to their own project...without the title there'd be no context here. SMHasher is well known (at least the original Google project is, maybe not this fork), but why not just submit wyhash directly? There's no explanation of how wyhash works here, and I can't find a paper.

Re: New fastest portable hash: wyhash

#33

Post by winnin_the_game »

mises wrote: post #31
winnin_the_game wrote: post #28

To me, the most interesting part: >> Even if [...] worse hash functions will lead to more collisions, the overall speed advantage beats the slightly worse quality.

I'm not sure if that part is correct. If I use something like SHA1 or MD5 (yes, I know they're no longer considered secure), know with essentially 100% certainty that I will not get a collision. This means I don't have to implement chaining, quadratic probing, or another method of collision avoidance. Though it might cost some speed on the end use of the app, it's often easier for initial development because I simply…

The strong collision avoidance guarantee is mostly a result of the large space of hashes those functions generate. So, yes, if you have a hashmap with 2^128 slots, you're technically right. But you don't have a hashmap with 2^128 slots. So you have to smash that output space into a smaller space somehow. And then you're back to considering what to do when you have collisions.

Re: New fastest portable hash: wyhash

#34

Post by bradleyjg »

orasis wrote: post #23

I’d really like to see progress on hashes that fit into a few lines of code. It seems FNV-1a is still the best option in that regard.

If this is all there is to it: https://github.com/wangyi-fudan/wyhash/blob/master/wyhash.h

That doesn’t seem like much.

Re: New fastest portable hash: wyhash

#35

Post by dagss »

asdkhadsj wrote: post #18
rurban wrote: post #16

Earlier quoted context omitted.

Not in hash tables. There the smaller, the faster. The selection criteria is: not bad (not failing any test), small and fast. Esp. it needs to be inlinable. There will always be collisions on dynamic workloads. Otherwise you would choose perfect hashes. In the usual programming language case SPOOKY32 has the least collisions, and is pretty fast too. But it has no chance against the small hash functions. The smhasher…

> Not in hash tables. There the smaller, the faster. The selection criteria is: not bad (not failing any test), small and fast. Esp. it needs to be inlinable. Can you explain why? Like what use cases are there where you don't actually care how likely something is to collide, you just want it to be fast? I've always thought being able to predict the chance of collision to be the most important factor on a hasher. When…

First off, for small tables, you always take the hash value modulo some small number like 10000. Who cares how good the hash function is, if you end up with 1/10000 chance of collision in the end anyway? Speed is obviously more important in this setting.

Second, assume very large hash tables...assume that with noncollision using the data structure takes time T1(H) and with collission it takes T2(H) for hash function H, and that the probability of collision is P(H).

So your total cost is then

P(H) T2(H) + (1 - P(H)) T1(H)

Which is approximately

P(H) T2(H) + T1(H)

Easy to play with numbers so that a worse but cheaper hash has a lower total cost. In fact this will usually be the case I would expect... T2 is multiplied with P and disappears for all but the very worst hashes/extremely expensive T2

Re: New fastest portable hash: wyhash

#37

Post by haberman »

bradleyjg wrote: post #34
orasis wrote: post #23

I’d really like to see progress on hashes that fit into a few lines of code. It seems FNV-1a is still the best option in that regard.

If this is all there is to it: https://github.com/wangyi-fudan/wyhash/blob/master/wyhash.h That doesn’t seem like much.

Agreed, if that's the whole hash function I think small code size is a selling point of this hash compared with other modern fast hashes.

This hash function looks like it will do unaligned reads if you're hashing an unaligned string. This doesn't matter on x86, but portable code should avoid this. It would be helpful to have a wrapper function that could handle unaligned strings by special-casing the begin and end of buffer.

Re: New fastest portable hash: wyhash

#38

Post by haberman »

I would love for this to be solid, but something here seems too good to be true. Modern hashing is well-studied, with lots of smart people attacking the problem. Modern hashes like Google's FarmHash are thousands of lines of code with platform-specific intrinsics for acceleration. This hash claims to beat other modern hashes in speed, without using platform-specific intrinsics, and without quality problems, and in a mere 100 lines of code to boot.

I would love for this to be true, but I'd love to see a more thorough explanation of how it manages to be both smaller and faster than other competing hashes.

Re: New fastest portable hash: wyhash

#39

Post by CodesInChaos »

jchw wrote: post #14
rurban wrote: post #8

Earlier quoted context omitted.

> misinformed rant Only siphash fans would say that, and they are very misinformed about the false recommendations from their paper. Prove me wrong.

I didn't know much about this argument so I looked it up and funny enough it's you arguing here too: https://github.com/google/highwayhash/issues/28 Still trying to wrap my head around exactly what is being argued... but it's starting to feel like there's something personal going on here, not gonna lie. It's a bit quaint. (Also a bit curious why Rust is looped into this. It seems like Rust was insecure because the sa…

I think the claim isn't "SipHash is not a secure keyed hash function (PRF)" but rather "secure keyed hash functions are insufficient mitigation for hash DoS".

For long lived hash-tables even per-table keys don't prevent finding bucket-collisions via side-channels. So you either have to either rekey when a large number of bucket-collisions are detected. Or you fall back to a balanced tree based data structure for those buckets. If you prefer the latter mitigation, there is little reason to pay the performance hit of SipHash.

So the OP has a point, but is terrible at communicating it.

Re: New fastest portable hash: wyhash

#40

Post by jchw »

CodesInChaos wrote: post #39
jchw wrote: post #14

Earlier quoted context omitted.

I didn't know much about this argument so I looked it up and funny enough it's you arguing here too: https://github.com/google/highwayhash/issues/28 Still trying to wrap my head around exactly what is being argued... but it's starting to feel like there's something personal going on here, not gonna lie. It's a bit quaint. (Also a bit curious why Rust is looped into this. It seems like Rust was insecure because the sa…

I think the claim isn't "SipHash is not a secure keyed hash function (PRF)" but rather "secure keyed hash functions are insufficient mitigation for hash DoS". For long lived hash-tables even per-table keys don't prevent finding bucket-collisions via side-channels. So you either have to either rekey when a large number of bucket-collisions are detected. Or you fall back to a balanced tree based data structure for thos…

Well, I am not a cryptographer, so I can't really make much attestations myself, but here's what I read:

- OP claims that the security claims of SipHash are incorrect or misleading.

- SipHash paper author defends claims made in SipHash paper.

- OP responds, claims that the security properties are misleading because most people would just assume it meant it was a "secure hash" and not a secure PRF. To prove this, he alludes to a Rust bug that as far as I can tell would work exactly the same with any hash function.

So I'm curious. Can you recover the seed in SipHash with side channel attacks? The response can be summed up as "PoC||GTFO," and I tend to agree; it seems to contradict at least some of the security claims they are making, after all.

All in all, if they have a point, it's missed in the flurry of unrelated points that were brought up there, and I definitely am not sure what to take away from it.

Post reply on HN