Fibonacci Hashing: The Optimization That the World Forgot
probablydance.com
Fibonacci Hashing: The Optimization That the World Forgot
1–10 of 79 posts
Re: Fibonacci Hashing: The Optimization That the World Forgot
#2Great article, really blow my mind
Re: Fibonacci Hashing: The Optimization That the World Forgot
#3This sounds quite similar to the fastrange [0] method. I’ve used it for random sampling but not a hash table. It’d be great for non-power-of-two tables while avoiding integer modulus.
Re: Fibonacci Hashing: The Optimization That the World Forgot
#4This sounds quite similar to the fastrange [0] method. I’ve used it for random sampling but not a hash table. It’d be great for non-power-of-two tables while avoiding integer modulus. [0] https://github.com/lemire/fastrange
fastrange is discussed in the article.
Re: Fibonacci Hashing: The Optimization That the World Forgot
#5Summary: 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 might be.
But later it mentions, in passing, a simpler approach: just shift the high bits down and xor! The author only tries doing this as a preprocessing step in front of Fibonacci hashing to avoid "bad patterns". So I'm left wondering: might shift-down-and-xor be good enough on its own?
Re: Fibonacci Hashing: The Optimization That the World Forgot
#6I think the search part is implementing the Fibonacci Search Technique[0]. It’s related to Golden ratio search[1].
[0] https://en.wikipedia.org/wiki/Fibonacci_search_technique
Re: Fibonacci Hashing: The Optimization That the World Forgot
#7It'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 information from low bits (examples below). Fibonacci hashing amounts to running a second multiplicative hash over your input, which is only worthwhile if you're paranoid about your input distribution.
Java SDK: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/s...
Android (C++): https://android.googlesource.com/platform/system/core/+/mast...
Re: Fibonacci Hashing: The Optimization That the World Forgot
#8It'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 uses some non-standard one anyway.
Re: Fibonacci Hashing: The Optimization That the World Forgot
#9It'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
#10Light travels around a foot in a nanosecond.
Makes thinking about processing times a bit easier when you can visualise it as a distance.