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

11–20 of 79 posts

Re: Fibonacci Hashing: The Optimization That the World Forgot

#11

Post by adrianratnapala »

rntz wrote: post #5

Summary: The article is looking for an efficient way to map a hash code into a smaller power-of-two-sized range, for use as a hashtable index. It dismisses the common solution, masking off the high bits, because it discards information, and proposes Fibonacci hashing: multiply by the golden ratio and shift down. It gives measurements suggesting this gives better performance in practice, and some theory as to why this…

Yep. The high-bits thing puzzled me as well because I thought shift-and-xor folding was standard practice. Also multiply-and-shift-down still tends to favour certain bits over others.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#13

Post by twic »

rntz wrote: post #5

Summary: The article is looking for an efficient way to map a hash code into a smaller power-of-two-sized range, for use as a hashtable index. It dismisses the common solution, masking off the high bits, because it discards information, and proposes Fibonacci hashing: multiply by the golden ratio and shift down. It gives measurements suggesting this gives better performance in practice, and some theory as to why this…

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 well-distributed, then this is pointless. But if they aren't, it's useful. So, it seems to me that rather than applying Fibonacci hashing to all hash codes, it would be better to use it as the original hash function for types which currently have bad hash functions. This is something a C++ standard library could easily do.

For example, LLVM's libc++ implements string hashing using MurmurHash2 on 32-bit machines, and CityHash on 64-bit machines:

https://github.com/llvm-mirror/libcxx/blob/master/include/__...

https://github.com/llvm-mirror/libcxx/blob/master/include/ut...

But hashes all sizes of integers to themselves:

https://github.com/llvm-mirror/libcxx/blob/master/include/ex...

Changing that to a Fibonacci hash, or a simpler shift-and-xor, could be a quick win.

Provided that libc++'s unordered_map uses power-of-two table sizes, that is. The code is labyrinthine, but i think, rather gloriously, sometimes it does, and sometimes it doesn't:

https://github.com/llvm-mirror/libcxx/blob/master/include/__...

https://github.com/llvm-mirror/libcxx/blob/master/include/__...

__constrain_hash is a simple but entertaining bit of bit-dickery (reformatted slightly):

    size_t __constrain_hash(size_t __h, size_t __bc) {
        return !(__bc & (__bc - 1))
            ? __h & (__bc - 1)
            : (__h
The x & (x - 1) tests whether a number is a power of two, because for any number that is not a power of two, subtracting one leaves the top bit set, so the bitwise and will contain at least one set bit. If the bucket count (number of slots) is a power of two, use a mask to extract the bottom bits of the hash. If it's not, do a modulus - but spend a branch to avoid that if the hash is already in the right range, which i'm surprised is a win.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#15

Post by wrs »

It's a strangely distinct memory that when I needed to implement a hash table in 1992, I read Knuth--in 1992 I guess there wasn't much else to do--and apparently read it correctly. The beauty of the golden ratio technique made it memorable and I've been doing "multiply by 2^n/phi" ever since! In fact just last week I launched Ruby to calculate it again...

Re: Fibonacci Hashing: The Optimization That the World Forgot

#16

Post by no_identd »

I wonder if, under some circumstances, one ought to use this instead for optimality of this or something similar:

https://en.wikipedia.org/wiki/Plastic_number for a similar use. It shares a property with phi which no other irrational shares with it (They are known as the only two Morphic numbers, which one must avoid confabulating with a similarly named concept whose name I can't recall right now.). And Knuth liked it (well, the reciprocal of it's square anyway, albeit the cubed version seems more interesting to me.), but never found any application for it. (He even made a special TeX symbol for the square of it, 'High Phi', see Wikipedia for details.)

Re: Fibonacci Hashing: The Optimization That the World Forgot

#17

Post by [deleted] »

twic wrote: post #8
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…

std::unordered_map is a bit of a red-headed stepchild in the C++ world. I'm not surprised that it hasn't had nearly the amount of tuning that hashmaps have had in other languages. When i asked some C++ers about it, they warned me off using it, for reasons i didn't fully understand, but i got the impression that there are structural reasons why it can never be really fast, so anyone who needs a really fast hashmap use…

[deleted]

Re: Fibonacci Hashing: The Optimization That the World Forgot

#18

Post by HippoBaro »

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…

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 insert operation might break all references.

So, in a sense, it's a bit unfair because std::unordered_map, in a real-world scenario, will potentially require you to perform less lookup because you can cache the references. With the others, you can't.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#19

Post by allenz »

HippoBaro wrote: post #18
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…

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