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

61–70 of 79 posts

Re: Fibonacci Hashing: The Optimization That the World Forgot

#61

Post by acqq »

attractivechaos wrote: post #55
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…

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+(h With "h * k>>(64-b)", the result has a cycle of 2^b. Suppose b=3 and you have input 1 At the end of d…

> Although it involves more steps, it only involves plus and bit operations and probably can be computed faster than generic multiplication.

It the most recent popular CPUs the multiplication is exactly "one step" long, that's how wonderfully fast they got to be. See e.g. Agner Fog instruction tables. And where not, the number of "steps" is typically not more than 2 or 3. The multiplication is implemented very efficiently today, unless the CPU has to be with a very low transistor count (linke in some embedded systems). The more exotic CPUs can, of course, be different.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#62

Post by ot »

If you need to map a uniform b-bit integer x into the [0, n) range, using ((x * n) >> b) will work just as well as the modulo in terms of (quasi-)even distribution, and it avoids integer division.

The idea is just to imagine x as a b-bit fixed-point uniformly random number in [0, 1), and rescaling it by multiplication.

This works great for hash tables whose size is not a power of 2, provided that you start from a good hash function.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#63

Post by carapace »

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.

Start with Knuth, don't end with him. ;-)

Re: Fibonacci Hashing: The Optimization That the World Forgot

#64

Post by allenz »

flurrything wrote: post #41
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).

It's the same API, but I highly doubt that his implementation is fully compliant with the C++ standard.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#65

Post by rurban »

acqq wrote: post #56
rurban wrote: post #36

Earlier quoted context omitted.

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?

See the relevant smhasher discussions.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#66

Post by rurban »

acqq wrote: post #46
rurban wrote: post #35

Earlier quoted context omitted.

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…

I haven't found a usecase yet where a better hash function leads to a faster hash table. Theoretically this would happen with CPUs with extremely slow or small cache.

It's also confirmed with the recent trend to add slower hash functions everywhere, leading to dramatic performance regressions.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#67

Post by rurban »

nhaehnle wrote: post #59
rurban wrote: post #36

Earlier quoted context omitted.

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?

Yes, because almost nobody knows. But when you see it it's super trivial. Knuth would be ashamed.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#68

Post by acqq »

rurban wrote: post #65
acqq wrote: post #56

Earlier quoted context omitted.

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

See the relevant smhasher discussions.

"smhasher discussions" where? This is not an answer.

Especially regarding "4 min" re siphash, about which kind of attack do you talk about at all, under which conditions?

The writings of those who try to protect from flooding attacks are more specific, e.g.:

https://github.com/google/highwayhash

"The author of SipHash has published C++ programs to generate" "'universal (key-independent) multicollisions' for CityHash and Murmur. Similar 'differential' attacks are likely possible for any hash function consisting only of reversible operations"

"attackers are only looking for multiple m mapping to the same bin rather than identical hash values."

"a strong hash function is not, by itself, sufficient to protect a chained hash table from flooding attacks. However, strong hash functions are important parts of two schemes for preventing denial of service. Using weak hash functions can slightly accelerate the best-case and average-case performance of a service, but at the risk of greatly reduced attack costs and worst-case performance."

Also, please also be specific about the "regressions" you mention in another post. Your statements, in the form they are, aren't of much use.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#69

Post by ghusbands »

junctioniv wrote: post #60
ghusbands wrote: post #54

Earlier quoted context omitted.

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 f…

When someone else pointed out that you need another hash function on the front:

Author: "Why [would] Fibonacci hashing not work as a hash function alone? It should, unless you have a use case that results in lots of Fibonacci numbers being inserted. You can use the identity function as the hash when you use Fibonacci hashing to assign a hash to an index."

Re: Fibonacci Hashing: The Optimization That the World Forgot

#70

Post by flurrything »

allenz wrote: post #64
flurrything wrote: post #41

Earlier quoted context omitted.

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

It's the same API, but I highly doubt that his implementation is fully compliant with the C++ standard.

It is, and so is boost::unordered_map, that's the whole point of the comparison. Just check the implementation out.
Post reply on HN