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

41–50 of 79 posts

Re: Fibonacci Hashing: The Optimization That the World Forgot

#41

Post by flurrything »

allenz wrote: post #7

It's not really fair to compare a custom implementation against the standard unordered_map implementations, which need to be fully general. See https://news.ycombinator.com/item?id=9675608 Still, I'm shocked that GCC, LLVM, and boost all assign buckets using modulus, which is very slow. I would love to know the reasoning. I assumed that they mask the high bit (or & with the table size). Fast hashmaps use xor to mix i…

> It's not really fair to compare a custom implementation against the standard unordered_map implementations, which

But he is comparing the standard unordered_map implementation to his own implementation of the standard unordered_map (same API).

Re: Fibonacci Hashing: The Optimization That the World Forgot

#42

Post by mickronome »

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 of the entire table is perfectly acceptable, and the additional performance the other 99.999% of the time is a welcome bonus.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#43

Post by pubby »

The comments here have given me an idea for my own hash tables.

Rather than accounting for poor hash functions using phi or fmix, I'm going to measure the hash function's distribution at run time and throw an error if its bad. For release builds I'll disable these checks.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#44

Post by danbruc »

On a related note, growing a hash table by a factor of two might not be optimal due to interactions with the memory allocator, more specifically the new allocation will be larger than all previous allocations combined so that you can not reuse previously allocated memory. Starting with m buckets one will allocate m * 2^t buckets after t growing operation, in total m * (2^(t + 1) - 1), but that is one bucket less than the m * 2^(t + 1) buckets required for growing again [1]. Whether this might be an issue obviously depends on the memory allocator used and other factors like the usage of a compacting garbage collector, phi appears again when looking for a better growth factor, and I will just leave this link to a Stack Overflow question [2] as a starting point because I am unable to find the article I had initially in mind.

[1] Assuming you can somehow incorporate the current allocation, previously freed were only m * (2^t - 1) buckets.

[2] https://stackoverflow.com/questions/2369467/why-are-hash-tab...

Re: Fibonacci Hashing: The Optimization That the World Forgot

#46

Post by acqq »

rurban wrote: post #35
fis wrote: post #26

Earlier quoted context omitted.

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…

The best is currently Leonid Yuriev's t1ha. See https://github.com/rurban/smhasher/ Note that in contrast with what Andy or DJB say, the collision safety is not a problem of the hash function per se, as you cannot fix collision attacks with any "safer" hash function. You can easily brute-force even the worst of all siphash in under 4min. Safety begins with 256 bits, in a hash table you got typically 10-14, max 32 to…

Thanks. Also, from smhasher text:

"See e.g. A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing

https://infosys.cs.uni-saarland.de/publications/p249-richter...

for a concise overview of the best hash table strategies, confirming that the simpliest Mult hashing (bernstein, FNV*, x17, sdbm) always beat "better" hash functions (Tabulation, Murmur, Farm, ...) when used in a hash table."

The conclusion is not properly stated, it's surely not "always" but there are enough use cases where the simple multiplications (or, even more probably, the "rotate, multiply, xor" and variants) are the fastest in practice.

From the paper:

"We could observe that Mult produces indeed more collisions than the expected amount on uniformly distributed keys. However, this larger amount of collisions does not get highly reflected in the observed performance. Thus, we consider Mult as the best candidate to be used in practice when quality results on high throughputs is desired, but at the cost of a high variance across data distributions."

It’s still a trade-off, but a good choice in some use cases.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#47

Post by tankenmate »

flurrything wrote: post #39
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

The whole point of fibonacci hashing is making hash tables more resistant to bad hash functions. Expecting everybody to be using the perfect hash function for each case is extremely naive, and even then, it just takes somebody else refactoring some code and adding a new member to a struct somewhere without updating the hash function to break that completely.

Doubly so if you are making a library where de facto you don't know what the input data might be and hence you don't know in advance what the perfect hash function is.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#48

Post by bradleyjg »

aappleby wrote: post #27
fis wrote: post #26

Earlier quoted context omitted.

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…

Murmur3 has good distribution properties and is much less code than City/Highway/Spooky. There are also some hashes based on hardware AES instructions (not crypto, just taking advantage of the mixing properties) that are near perfect but I don't recall their names and haven't benchmarked them.

This one? https://github.com/stg7/haesni

Re: Fibonacci Hashing: The Optimization That the World Forgot

#50

Post by barrkel »

allenz wrote: post #7

It's not really fair to compare a custom implementation against the standard unordered_map implementations, which need to be fully general. See https://news.ycombinator.com/item?id=9675608 Still, I'm shocked that GCC, LLVM, and boost all assign buckets using modulus, which is very slow. I would love to know the reasoning. I assumed that they mask the high bit (or & with the table size). Fast hashmaps use xor to mix i…

Hash table design in libraries is an exercise in minimizing the costs of the worst case, and it's made harder by typically only being able to control one side of the equation - the table and not the hash function.

Thus general purpose hash table implementations need to choose whether they will help naive programmers by doing modulus with a prime number of buckets, or if they will leave a potential performance bomb for people who e.g. hash integers to themselves. The article argues for a third way which is somewhere in the middle: faster than prime modulus, but not as dangerous as bit masking.

It's usually easy to beat any general purpose hash table for these reasons, as long as you control the hash function you can tweak your implementation to suit.

Post reply on HN