{"id":12012,"date":"2024-11-06T00:13:28","date_gmt":"2024-11-05T23:13:28","guid":{"rendered":"https:\/\/monodes.com\/predaelli\/?p=12012"},"modified":"2024-11-06T00:13:28","modified_gmt":"2024-11-05T23:13:28","slug":"fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo","status":"publish","type":"post","link":"https:\/\/monodes.com\/predaelli\/2024\/11\/06\/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo\/","title":{"rendered":"Fibonacci Hashing: The Optimization that the World Forgot (or: a Better Alternative to Integer Modulo)"},"content":{"rendered":"

Fibonacci Hashing: The Optimization that the World Forgot (or: a Better Alternative to Integer Modulo)<\/a><\/em><\/p>\n

<\/p>\n

\n
\n
\n

Fibonacci Hashing: The Optimization that the World Forgot (or: a Better Alternative to Integer\u00a0Modulo)<\/h3>\n

by Malte Skarupke<\/span><\/h4>\n
\n

I recently posted a blog post about a new hash table, and whenever I do something like that, I learn at least one new thing from my comments. In my last comment section Rich Geldreich talks about his hash table which uses \u201cFibonacci Hashing\u201d, which I hadn\u2019t heard of before. I have worked a lot on hash tables, so I thought I have at least heard of all the big important tricks and techniques, but I also know that there are so many small tweaks and improvements that you can\u2019t possibly know them all. I thought this might be another neat small trick to add to the collection.<\/p>\n

Turns out I was wrong. This is a big one. And everyone should be using it. Hash tables should not be prime number sized and they should not use an integer modulo to map hashes into slots. Fibonacci hashing is just better. Yet somehow nobody is using it and lots of big hash tables (including all the big implementations of std::unordered_map) are much slower than they should be because they don\u2019t use Fibonacci Hashing. So let\u2019s figure this out.<\/p>\n

 <\/p>\n

First of all how do we find out what this Fibonacci Hashing is? Rich Geldreich called it \u201cKnuth\u2019s multiplicative method,\u201d but before looking it up in The Art of Computer Programming, I tried googling for it. The top result right now is this page<\/a> which is old, with a copyright from 1997. Fibonacci Hashing is not mentioned on Wikipedia. You will find a few more pages mentioning it, mostly from universities who present this in their \u201cintroduction to hash tables\u201d material.<\/p>\n

From that I thought it\u2019s one of those techniques that they teach in university, but that nobody ends up using because it\u2019s actually more expensive for some reason. There are plenty of those in hash tables: Things that get taught because they\u2019re good in theory, but they\u2019re bad in practice so nobody uses them.<\/p>\n

Except somehow, on this one, the wires got crossed. Everyone uses the algorithm that\u2019s unnecessarily slow and leads to more problems, and nobody is using the algorithm that\u2019s faster while at the same time being more robust to problematic patterns. Knuth talked about Integer Modulo and about Fibonacci Hashing, and everybody should have taken away from that that they should use Fibonacci Hashing, but they didn\u2019t and everybody uses integer modulo.<\/p>\n

Before diving into this, let me just show you the results of a simple benchmark: Looking up items in a hash table:<\/p>\n

\"unordered_map_comparison_larger_font\"<\/p>\n

In this benchmark I\u2019m comparing various unordered_map implementations. I\u2019m measuring their lookup speed when the key is just an integer. On the X-axis is the size of the container, the Y-axis is the time to find one item. To measure that, the benchmark is just spinning in a loop calling find() on this container, and at the end I divide the time that the loop took by the number of iterations in the loop. So on the left hand side, when the table is small enough to fit in cache, lookups are fast. On the right hand side the table is too big to fit in cache and lookups become much slower because we\u2019re getting cache misses for most lookups.<\/p>\n

But the main thing I want to draw attention to is the speed of ska::unordered_map, which uses Fibonacci hashing. Otherwise it\u2019s a totally normal implementation of unordered_map: It\u2019s just a vector of linked lists, with every element being stored in a separate heap allocation. On the left hand side, where the table fits in cache, ska::unordered_map can be more than twice as fast as the Dinkumware implementation of std::unordered_map, which is the next fastest implementation. (this is what you get when you use Visual Studio)<\/p>\n

So if you use std::unordered_map and look things up in a loop, that loop could be twice as fast if the hash table used Fibonacci hashing instead of integer modulo.<\/p>\n

How it works<\/h3>\n

So let me explain how Fibonacci Hashing works. It\u2019s related to the golden ratio \"\\phi=1.6180339...\" which is related to the Fibonacci numbers, hence the name. One property of the Golden Ratio is that you can use it to subdivide any range roughly evenly without ever looping back to the starting position. What do I mean by subdividing? For example if you want to divide a circle into 8 sections, you can just make each step around the circle be an angle of \"360^\\circ\/8\" degrees. And after eight steps you\u2019ll be back at the start. And for any \"n\" number of steps you want to take, you can just change the angle to be \"360^\\circ\/n\". But what if you don\u2019t know ahead of time how many steps you\u2019re going to take? What if the \"n\" value is determined by something you don\u2019t control? Like maybe you have a picture of a flower, and you want to implement \u201cevery time the user clicks the mouse, add a petal to the flower.\u201d In that case you want to use the golden ratio: Make the angle from one petal to the next \"360^\\circ\/\\phi\" and you can loop around the circle forever, adding petals, and the next petal will always fit neatly into the biggest gap and you\u2019ll never loop back to your starting position. Vi Hart has a good video about the topic:<\/p>\n