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

Fibonacci Hashing: The Optimization That the World Forgot

probablydance.com

Post reply on HN
Print view View original

51–60 of 79 posts

Re: Fibonacci Hashing: The Optimization That the World Forgot

#51

Post by stochastic_monk »

allenz wrote: post #19
HippoBaro wrote: post #18

Earlier quoted context omitted.

Yes, but it's also important to understand what you lose when using these better-performing hashtables. First thing that comes to mind is that when performing a successful lookup on a std::unordered_map, the reference is guarrantied to be valid until either (a) you erase that element or (b) the table itself is destroyed. Almost all faster hashtables around give up that properties for better lookup performance. Any in…

Yes, I agree with you that unordered_map should be slower. For context, the author shows off a graph where his custom Fibonacci implementation is the fastest, which proves nothing about Fibonacci hashing.

I had an application several years ago in which the executable was 10x as fast when using khash instead of std::unordered_map.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#52

Post by jrochkind1 »

CephalopodMD wrote: post #30
aappleby wrote: post #22

Don't do this. Use a real hash function that guarantees a highly random distribution, make your hash tables power-of-two sized, and map from hash value to table index using (hash & (size-1)). The fibonacci constant thing will help clean up the distribution of a bad hash function, but it does nothing for collision resistance if the underlying hash function is weak. -Austin, author of Murmurhash and SMHasher

Wait, I thought the author was saying to use this _after_ using a more secure hash function, not instead of it. Why wouldn't you do that?

It's about "hash tables" (ie associative arrays, HashMap), right?

Is security even an issue in hash functions for this purpose? I honestly don't know, it's not obvious to me that it is.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#53

Post by baking »

fis wrote: post #26
aappleby wrote: post #23

Earlier quoted context omitted.

Also, there is nothing magic about his fibonacci constant. Any large odd constant with roughly half the bits set at random will do the same thing.

I also did not follow what is special about 2^n/phi. I found this more concise justification: http://mathforum.org/kb/message.jspa?messageID=431065 "Knuth's finding was that the dispersion of indexes for a sequence of consecutive keys is maximized when M is chosen this way, thus a multiplicative hash table with a dense set of keys will have the fewest possible collisions when M approx= 2^N * R." Although, if the keys…

Phi is the most irrational of the irrational numbers, meaning that successive rational approximations are just slightly better: 1/1, 1/2, 2/3, 3/5, 5/8, 8/13, etc. There are no rational approximations that "jump out" as being much better, so you won't find any unexpected patterns when using it.

The Golden Ratio (why it is so irrational) - Numberphile https://www.youtube.com/watch?v=sj8Sg8qnjOg

Re: Fibonacci Hashing: The Optimization That the World Forgot

#54

Post by ghusbands »

mickronome wrote: post #42
aappleby wrote: post #22

Don't do this. Use a real hash function that guarantees a highly random distribution, make your hash tables power-of-two sized, and map from hash value to table index using (hash & (size-1)). The fibonacci constant thing will help clean up the distribution of a bad hash function, but it does nothing for collision resistance if the underlying hash function is weak. -Austin, author of Murmurhash and SMHasher

He's clearly, and obviously not talking about using it as a hash, or even to consider it as a secondary hash as someone mentioned. The use case according to the article is strictly to replace integer modulo to map into buckets for cases where that operation is the limiting factor. In his case that's when 9ns per key is too much, and roughly 1ns is good. For small hash tables sometimes the worst case of a linear scan…

He is talking about using it as a hash function and clearly states so. To quote:

> 1. Hash the key > 2. Map the hash value to a slot

> Knuth [Fibonacci Hash] uses the term “hash function” to refer to something that does both step 1 and step 2.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#55

Post by attractivechaos »

mickronome wrote: post #42
aappleby wrote: post #22

Don't do this. Use a real hash function that guarantees a highly random distribution, make your hash tables power-of-two sized, and map from hash value to table index using (hash & (size-1)). The fibonacci constant thing will help clean up the distribution of a bad hash function, but it does nothing for collision resistance if the underlying hash function is weak. -Austin, author of Murmurhash and SMHasher

He's clearly, and obviously not talking about using it as a hash, or even to consider it as a secondary hash as someone mentioned. The use case according to the article is strictly to replace integer modulo to map into buckets for cases where that operation is the limiting factor. In his case that's when 9ns per key is too much, and roughly 1ns is good. For small hash tables sometimes the worst case of a linear scan…

Fibonacci hashing takes the form of "h * k>>(64-b)", where k is determined by golden ratio and b is the bit size of the table. This involves one generic multiplication, which is the bottleneck. This multiplication is not strictly necessary. You can replace it with k=1033 for example, which can be implemented as "h+(hWith "h * k>>(64-b)", the result has a cycle of 2^b. Suppose b=3 and you have input 1At the end of day, however, Fibonacci hashing or similar ideas only helps when you hash keys to similar integers but has no effect when you hash different keys to the same integer. You have to use a reasonable hash function anyway.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#56

Post by acqq »

rurban wrote: post #36
carapace wrote: post #14

Moral of the story: Always always consult Knuth.

Unless Knuth is outdated. With hash tables Knuth is seriously outdated. With hash functions you can consult his test functions, but he is also outdated. E.g. the CRC scheme is the fastest by far (one even exists in HW), but too easily attackable. Trivial really, any 10 year old can do that, due to some unfortunate CRC properties.

> too easily attackable. Trivial really, any 10 year old can do that

In another comment you write:

> You can easily brute-force even the worst of all siphash in under 4min.

Can you please write what you mean by those statements? Is it about the "hash-flooding DoS" attacks or something else? Can you share a little more of your insights?

Re: Fibonacci Hashing: The Optimization That the World Forgot

#57

Post by twic »

acqq wrote: post #31
twic wrote: post #13

Earlier quoted context omitted.

The article presents Fibonacci hashing as an operation to map a hash code into a smaller range, but it isn't that, really. The operation that does that is still just taking some bits from the hash code. What Fibonacci hashing actually is is a way of stirring a hash code before use, to spread its entropy out more, so that the bits you end up taking a more likely to be well-distributed. If your hash codes are already w…

> LLVM's libc++ Great find! So the library solutions are still often suboptimal, and it's even more easy to hide bad decisions in the C++ sources, so whoever has the approach "just use the default library" should be aware of that once the performance is important. Yes, even the simple multiplicative constants can significantly improve the hash if it by default doesn't do anything with the input! The libraries definit…

> "SipHash was designed as a mitigation to hash-flooding DoS attacks. It is now used in the hash tables implementation of Python, Ruby, Perl 5, etc."

It's also the default hasher in Rust.

Rust's hashing is interesting. Types that want to be hashable implement the Hash trait. What the Hash trait requires is that a type knows how to feed its fields to a Hasher, as a sequence of primitives - it doesn't require that it actually computes a hash itself. It's the Hasher which computes the hash. This is nice, because it's very easy to implement Hash; indeed, so easy that it can be done automatically using a derive macro. The downside is that it's not possible for a type to implement a custom hash that takes particular advantage of its own structure, and so to get a particularly good tradeoff of distribution against performance. The only place to make that tradeoff is in the choice of Hasher, where it has to be made generically across all types.

That said, you can choose the hasher used for individual HashMaps, so if you have a HashMap where you know the keys are integers, you can use a Hasher which just does a Fibonacci hash.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#58

Post by IshKebab »

aappleby wrote: post #23
aappleby wrote: post #22

Don't do this. Use a real hash function that guarantees a highly random distribution, make your hash tables power-of-two sized, and map from hash value to table index using (hash & (size-1)). The fibonacci constant thing will help clean up the distribution of a bad hash function, but it does nothing for collision resistance if the underlying hash function is weak. -Austin, author of Murmurhash and SMHasher

Also, there is nothing magic about his fibonacci constant. Any large odd constant with roughly half the bits set at random will do the same thing.

Actually there is something special about the using the golden ratio. By some measure it is "the most irrational" number, and that property makes it really good at distributing numbers evenly along an interval.

You can use it to generate a nice sequence of different colours - set the hue to (n * the golden ratio) mod 1.

But I don't know if that property is really necessary for a hash table. I guess only if you are using a terrible key hash.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#59

Post by nhaehnle »

rurban wrote: post #36
carapace wrote: post #14

Moral of the story: Always always consult Knuth.

Unless Knuth is outdated. With hash tables Knuth is seriously outdated. With hash functions you can consult his test functions, but he is also outdated. E.g. the CRC scheme is the fastest by far (one even exists in HW), but too easily attackable. Trivial really, any 10 year old can do that, due to some unfortunate CRC properties.

> any 10 year old can do that

Is this kind of hyperbole really necessary?

Re: Fibonacci Hashing: The Optimization That the World Forgot

#60

Post by junctioniv »

ghusbands wrote: post #54
mickronome wrote: post #42

Earlier quoted context omitted.

He's clearly, and obviously not talking about using it as a hash, or even to consider it as a secondary hash as someone mentioned. The use case according to the article is strictly to replace integer modulo to map into buckets for cases where that operation is the limiting factor. In his case that's when 9ns per key is too much, and roughly 1ns is good. For small hash tables sometimes the worst case of a linear scan…

He is talking about using it as a hash function and clearly states so. To quote: > 1. Hash the key > 2. Map the hash value to a slot > Knuth [Fibonacci Hash] uses the term “hash function” to refer to something that does both step 1 and step 2.

Actually that quote is in the article for the opposite reason. He is referencing that because historically Fibonochi hashing was coupled with a hashing function and that is why it’s overlooked as a mapping function. His article is specifically advocating using the Fibonacci method only for mapping.

He is writing from the context of writing a hash table library where the user is expected to provide their own hashing function.

Post reply on HN