8 ms·

Fibonacci Hashing: An optimization that the world forgot (2018)

204 points by djoldman 4y ago

dang 4y ago
Discussed at the time: Fibonacci Hashing: The Optimization That the World Forgot - https://news.ycombinator.com/item?id=17328756 https://news.ycombinator.com/item?id=17328756 - June 2018 (75 comments)
User23 4y ago
Along the same lines there’s Dijkstra’s use of the Leonardo numbers in smoothsort. I doubt that one in a hundred working computer programmers have heard of them.
- goy 4y ago
  Can you share a link?
  - tmtvl 4y ago
    The first source quoted in the Wikipedia article* for Smoothsort is a link to a transcript of Dijstra's discussion/presentation of it. * https://en.wikipedia.org/wiki/Smoothsort#cite_note-EWD-796a-1 https://en.wikipedia.org/wiki/Smoothsort#cite_note-EWD-796a-...
PcChip 4y ago
How does this compare to tsl::robin_map?
- vidarh 4y ago
  Skimming the code, it seems to use bitwise and with a mask if the hash size is a power of two, which has the same caveats as described for Dinkumware (it's fast, but if your hash is poor it can have awful results), and uses modulo if not which has all the issues the article describes. This is encapsulated in a single file [1] so it looks like it'd be easy to improve. [1] https://github.com/Tessil/robin-map/blob/master/include/tsl/robin_growth_policy.h https://github.com/Tessil/robin-map/blob/master/include/tsl/...
leed25d 4y ago
Knuth has a great few pages on Fibonacci Hashing TAOCP Vol3 pp 510 - 512
thomasahle 4y ago
They hardly forgot it. It's just that today we prefer hash functions that are seeded, so we use a random number instead of the "magical" fibonacci constant. See for example multiply shift hashing in https://arxiv.org/abs/1504.06804 https://arxiv.org/abs/1504.06804
- vidarh 4y ago
  The article is not about using Fibonacci hash to replace the hash function, but to replace integer modulo when remapping the hash value to smaller space.
  - xxs 4y ago
    Yet, no one in their sane mind uses module on hashing, it's always power of 2 table, so the operation is just: hash & (len -1) which is absolutely trivial. It has been this way for decades.
    - vidarh 4y ago
      And yet just here in this article someone asked how it compares to a recent hash implementation that offers non-power of two tables and uses modulo if you let it do that, and I have seen many other recent hash table implementations do so. But that is also not the only issue: If you use powers of two and resort to bitwise and to pick the bucket, you're even more dependent on a good hash function, which may be impossible to guarantee if implementinf APIs that let the user choose hash function as in the article. Unless you follow the suggestion in this article and uses this method to pick buckets.
      - xxs 4y ago
        Personally I do murmur smear that involves a RoL, an add and two muls on all input hashes.
    - rurban 4y ago
      To the contrary almost everybody who knows a bit about DDOS security uses primes, not power's of two. This has been this way for decades, see the relevant hash tables for glibc, gcc, binutils, ...
ReactiveJelly 4y ago
I first learned this trick for generating hues for colors when you don't know how many you'll need. I think LibreOffice might do this. It always picks blue and orange for the first 2 series in a chart. But you can keep picking and it always has more colors that are just slightly different than all the previous ones.
mungoman2 4y ago
Interesting article, but I'm not convinced about this idea. This is just fixing up the hash function, which should have a good enough distribution from the start. And if it did this remapping wouldn't be necessary. The proper place to add this is in your hash function, to "fix up" the distribution. But then, if your hash function doesn't generate a good enough distribution without this trick you should probably redesign it.
- vidarh 4y ago
  This misses the point which is two-part: 1) A lot of hash tables uses modulo to map a large range to a small range, and this is slow. 2) Fibonacci hashing is according to the author both faster and as a side effect happens to improve on bad inputs. Yes, you should improve your hash function, but assuming the author is right you should still prefer this over integer modulo to reduce the size of the input hash value to the size of the hash table if you can as a default because it's faster, and the extra mixing is just a bonus. Also, for library implementations where the implementer has no control over which hash function the user provides, being resistant to pathological inputs is good. Especially if you get it as a free side effect of a performance improvement.
  - judofyr 4y ago
    > Yes, you should improve your hash function, but assuming the author is right you should still prefer this over integer modulo to reduce the size of the input hash value to the size of the hash table if you can as a default because it's faster, and the extra mixing is just a bonus. What we're comparing here are these two: // We're only dealing with sizes of num_slots = 2^b int key_to_slot1(key) { return hash(key) & (num_slots - 1); } int key_to_slot2(key) { return (hash(key) * k) >> (64 - b); } The only difference is: (1) we're doing an extra multiplication, and (2) we're using the high bits instead of the low bits. This should _only_ help if you use a terrible hash function. I'm also not sure why they claim that integer modulo is slow when the* show how to make it fast by using bitwise AND. > Also, for library implementations where the implementer has no control over which hash function the user provides, being resistant to pathological inputs is good. Especially if you get it as a free side effect of a performance improvement. But we're designing the hash table! There's no reason for us to make it possible for the user to provide a custom hash function. We've learnt this before: Instead of letting the user provide `int hashCode(Key key)` (as in Java), we use `void hash(Hash state, Key key)` (as in Rust). The user will tell us which sources of data needs to be hashed, but we can provide the hash function and mixing functionality.
ultrablack 4y ago
Multiplication is bad. Knuth actually also describes a hash function using random numbers and XOR. Its 10x faster than the modulo, and I belive Mikkel Thorup proved it optimal. The idea is roughly: Say you have a hashtable of size 1024. You then create x uint arrays of size size 256. These arrays you fill up with random numbers 0-1023. To get your hash value, you take your input and for i=0..x-1 determine byte k=input[i] you lookup the value in array[i][k]. These lookup values are then XORed giving a final random value between 0-1023 ready for inserting into the hash array. No modulos. No multiplications. You only have to redo the random tables when the size changes from say 1024 to 2048. Easy peacy. Superfast.
- karmakurtisaani 4y ago
  How do you fill the array though? Wouldn't filling it with random numbers give you a different hash each time you rebuild the hash function? I can see it being useful for a short-lived data structure, but you wouldn't be able to use it as a shared deterministic hash function?
  - RhodesianHunter 4y ago
    Why couldn't you fill it deterministically?
    - karmakurtisaani 4y ago
      I guess that was my question indeed. In the sense of how do you do it in practice? I suppose there are pseudorandom algorithms that can be easily applied.
      - cycomanic 4y ago
        Pseudorandom bit sequences PRBS are deterministic and very easy to implement (just linear feedback shift registers). Something similar is actually done in communication systems, with scrambling, to prevent long strings of transmitted ones or zeros (which cause issues for some of the hardware components). Essentially you just add or multiply the data with the PRBS sequence. At the receiver you just do the reverse operation.
nopurpose 4y ago
TLDR; hash the hash with fast function, like fibonacci hash which is just single multiplication by a constant, then take lower bits as your bucket index.
- Findecanor 4y ago
  No, you take the highest bits. The product is a fixed-point real fraction. The integer part has overflowed out of the machine word. 0..(2**64-1) represents 0.0<=x<1.0 Picking the n highest bits is like multiplying with 2**n and using the integer result.
Findecanor 4y ago
One property I find interesting about this scheme is that resizing the table (doubling or halving) could be done without recomputing any index — and therefore be superfast compared to the mod-prime method. Each bucket in the smaller table maps to precisely two buckets in the larger table. The differences are in the lowest bit in the larger table's indices. If you'd store the product in each entry then you wouldn't need to redo the multiplication when resizing. I suppose that the product would work just as well as the hash value when looking up an entry in a bucket, so you could just store that instead.
- camel-cdr 4y ago
  This is also true for power of two hash tables, but it doesn't work anymore once you use open addressing.
vrglvrglvrgl 4y ago
[dead]
terrelln 4y ago
This style of hash function is used by zstd, lz4, and many other LZ algorithms in their hash tables as a fast hash with good enough quality

204 points by djoldman 4y ago

dang 4y ago

Discussed at the time: Fibonacci Hashing: The Optimization That the World Forgot - https://news.ycombinator.com/item?id=17328756 https://news.ycombinator.com/item?id=17328756 - June 2018 (75 comments)

User23 4y ago

Along the same lines there’s Dijkstra’s use of the Leonardo numbers in smoothsort. I doubt that one in a hundred working computer programmers have heard of them.

goy 4y ago
Can you share a link?
- tmtvl 4y ago
  The first source quoted in the Wikipedia article* for Smoothsort is a link to a transcript of Dijstra's discussion/presentation of it. * https://en.wikipedia.org/wiki/Smoothsort#cite_note-EWD-796a-1 https://en.wikipedia.org/wiki/Smoothsort#cite_note-EWD-796a-...

PcChip 4y ago

How does this compare to tsl::robin_map?

vidarh 4y ago
Skimming the code, it seems to use bitwise and with a mask if the hash size is a power of two, which has the same caveats as described for Dinkumware (it's fast, but if your hash is poor it can have awful results), and uses modulo if not which has all the issues the article describes. This is encapsulated in a single file [1] so it looks like it'd be easy to improve. [1] https://github.com/Tessil/robin-map/blob/master/include/tsl/robin_growth_policy.h https://github.com/Tessil/robin-map/blob/master/include/tsl/...

leed25d 4y ago

Knuth has a great few pages on Fibonacci Hashing TAOCP Vol3 pp 510 - 512

thomasahle 4y ago

They hardly forgot it. It's just that today we prefer hash functions that are seeded, so we use a random number instead of the "magical" fibonacci constant. See for example multiply shift hashing in https://arxiv.org/abs/1504.06804 https://arxiv.org/abs/1504.06804

vidarh 4y ago
The article is not about using Fibonacci hash to replace the hash function, but to replace integer modulo when remapping the hash value to smaller space.
- xxs 4y ago
  Yet, no one in their sane mind uses module on hashing, it's always power of 2 table, so the operation is just: hash & (len -1) which is absolutely trivial. It has been this way for decades.
  - vidarh 4y ago
    And yet just here in this article someone asked how it compares to a recent hash implementation that offers non-power of two tables and uses modulo if you let it do that, and I have seen many other recent hash table implementations do so. But that is also not the only issue: If you use powers of two and resort to bitwise and to pick the bucket, you're even more dependent on a good hash function, which may be impossible to guarantee if implementinf APIs that let the user choose hash function as in the article. Unless you follow the suggestion in this article and uses this method to pick buckets.
    - xxs 4y ago
      Personally I do murmur smear that involves a RoL, an add and two muls on all input hashes.
  - rurban 4y ago
    To the contrary almost everybody who knows a bit about DDOS security uses primes, not power's of two. This has been this way for decades, see the relevant hash tables for glibc, gcc, binutils, ...

ReactiveJelly 4y ago

I first learned this trick for generating hues for colors when you don't know how many you'll need. I think LibreOffice might do this. It always picks blue and orange for the first 2 series in a chart. But you can keep picking and it always has more colors that are just slightly different than all the previous ones.

mungoman2 4y ago

Interesting article, but I'm not convinced about this idea. This is just fixing up the hash function, which should have a good enough distribution from the start. And if it did this remapping wouldn't be necessary. The proper place to add this is in your hash function, to "fix up" the distribution. But then, if your hash function doesn't generate a good enough distribution without this trick you should probably redesign it.

vidarh 4y ago
This misses the point which is two-part: 1) A lot of hash tables uses modulo to map a large range to a small range, and this is slow. 2) Fibonacci hashing is according to the author both faster and as a side effect happens to improve on bad inputs. Yes, you should improve your hash function, but assuming the author is right you should still prefer this over integer modulo to reduce the size of the input hash value to the size of the hash table if you can as a default because it's faster, and the extra mixing is just a bonus. Also, for library implementations where the implementer has no control over which hash function the user provides, being resistant to pathological inputs is good. Especially if you get it as a free side effect of a performance improvement.
- judofyr 4y ago
  > Yes, you should improve your hash function, but assuming the author is right you should still prefer this over integer modulo to reduce the size of the input hash value to the size of the hash table if you can as a default because it's faster, and the extra mixing is just a bonus. What we're comparing here are these two: // We're only dealing with sizes of num_slots = 2^b int key_to_slot1(key) { return hash(key) & (num_slots - 1); } int key_to_slot2(key) { return (hash(key) * k) >> (64 - b); } The only difference is: (1) we're doing an extra multiplication, and (2) we're using the high bits instead of the low bits. This should _only_ help if you use a terrible hash function. I'm also not sure why they claim that integer modulo is slow when the* show how to make it fast by using bitwise AND. > Also, for library implementations where the implementer has no control over which hash function the user provides, being resistant to pathological inputs is good. Especially if you get it as a free side effect of a performance improvement. But we're designing the hash table! There's no reason for us to make it possible for the user to provide a custom hash function. We've learnt this before: Instead of letting the user provide `int hashCode(Key key)` (as in Java), we use `void hash(Hash state, Key key)` (as in Rust). The user will tell us which sources of data needs to be hashed, but we can provide the hash function and mixing functionality.

ultrablack 4y ago

Multiplication is bad. Knuth actually also describes a hash function using random numbers and XOR. Its 10x faster than the modulo, and I belive Mikkel Thorup proved it optimal. The idea is roughly: Say you have a hashtable of size 1024. You then create x uint arrays of size size 256. These arrays you fill up with random numbers 0-1023. To get your hash value, you take your input and for i=0..x-1 determine byte k=input[i] you lookup the value in array[i][k]. These lookup values are then XORed giving a final random value between 0-1023 ready for inserting into the hash array. No modulos. No multiplications. You only have to redo the random tables when the size changes from say 1024 to 2048. Easy peacy. Superfast.

karmakurtisaani 4y ago
How do you fill the array though? Wouldn't filling it with random numbers give you a different hash each time you rebuild the hash function? I can see it being useful for a short-lived data structure, but you wouldn't be able to use it as a shared deterministic hash function?
- RhodesianHunter 4y ago
  Why couldn't you fill it deterministically?
  - karmakurtisaani 4y ago
    I guess that was my question indeed. In the sense of how do you do it in practice? I suppose there are pseudorandom algorithms that can be easily applied.
    - cycomanic 4y ago
      Pseudorandom bit sequences PRBS are deterministic and very easy to implement (just linear feedback shift registers). Something similar is actually done in communication systems, with scrambling, to prevent long strings of transmitted ones or zeros (which cause issues for some of the hardware components). Essentially you just add or multiply the data with the PRBS sequence. At the receiver you just do the reverse operation.

nopurpose 4y ago

TLDR; hash the hash with fast function, like fibonacci hash which is just single multiplication by a constant, then take lower bits as your bucket index.

Findecanor 4y ago
No, you take the highest bits. The product is a fixed-point real fraction. The integer part has overflowed out of the machine word. 0..(2**64-1) represents 0.0<=x<1.0 Picking the n highest bits is like multiplying with 2**n and using the integer result.

Findecanor 4y ago

One property I find interesting about this scheme is that resizing the table (doubling or halving) could be done without recomputing any index — and therefore be superfast compared to the mod-prime method. Each bucket in the smaller table maps to precisely two buckets in the larger table. The differences are in the lowest bit in the larger table's indices. If you'd store the product in each entry then you wouldn't need to redo the multiplication when resizing. I suppose that the product would work just as well as the hash value when looking up an entry in a bucket, so you could just store that instead.

camel-cdr 4y ago
This is also true for power of two hash tables, but it doesn't work anymore once you use open addressing.

vrglvrglvrgl 4y ago

[dead]

terrelln 4y ago

This style of hash function is used by zstd, lz4, and many other LZ algorithms in their hash tables as a fast hash with good enough quality