4 ms·

Why do cuckoo hashing advertisements always sound like snake oil sales pitches? Claim: "A simple and beautiful technique that can achieve 99% occupancy and ser

Why do cuckoo hashing advertisements always sound like snake oil sales pitches? Claim: "A simple and beautiful technique that can achieve 99% occupancy and serve all lookups with just two memory accesses thanks to the power of two choices." Great, so apparently I can achieve 99% occupancy? Reality [1]: "Insertions succeed in expected constant time [...] as long as the number of keys is kept below half of the capacity of the hash table, i.e., the load factor is below 50%." Ok so never mind... [1] https://en.wikipedia.org/wiki/Cuckoo_hashing#Theory https://en.wikipedia.org/wiki/Cuckoo_hashing#Theory

truenindb 5y ago
It's because the internet is a perfect sterling engine, guaranteeing that all eyeballs will be monotized in an adiabatic flow. It is know as "The Permanent November of ImaginosVictory Law" to those of us that have been using the internet since Salman Rushdie invented email, which is one of the best exemplars of a good protocol since Google Wave.
- xarope 5y ago
  bingo?
- lrem 5y ago
  Was this generated with some GPT3-like or something?
  - orf 5y ago
    I think so, the only result on Google for “ ImaginosVictory” is that very comment.
- chana_masala 5y ago
  Do you have an ICO I buy into?
- DiabloD3 5y ago
  I don't know who's running a GPT bot on HN, but this is a beautiful work of art.
throwaway81523 5y ago
IIRC you can get to high occupancy by doing enough rehashes. After that, if you do no more insertions and only lookups, it is a good deal since each lookup takes at most two memory accesses. So this is useful if you are willing to spend a long time building what will then be a read-only table. Obviously there are uses for that.
- dataflow 5y ago
  > IIRC you can get to high occupancy by doing enough rehashes. Yeah so how many total insertions (as part of the rehashing) do you expect to have to do to achieve 99% occupancy? Wouldn't it be even worse than O(n^2)? And if you're going to spend a lot of time rebuilding the hash table all the time, then why not just use a perfect hash generator?
  - throwaway81523 5y ago
    Large perfect hash tables have to store an awful lot of information. I don't remember quite how it's done but it's not a free lunch. The hash function itself has a size that grows with the total size of all the keys. I don't know offhand how many rehashes you need to get 98% occupancy with cuckoo hashing. There may be ways to optimize it by sharding the table into smaller ones. I'll re-read the wikipedia article when I get a chance. It's a fun algorithm and I've sometimes looked for places to use it.
  - nullc 5y ago
    > Yeah so how many total insertions (as part of the rehashing) do you expect to have to do to achieve 99% occupancy? Wouldn't it be even worse than It depends on your bucket sizes and how many hashes you use. If you attempt 99% occupancy with 2 hashes and 4 entries per bucket, then you are going to be doing a LOT of kicking. 92% with that geometry, OTOH, is fine and will end up with just a couple kicks per insert on average.
signa11 5y ago
i found this (https://codecapsule.com/?s=hashing https://codecapsule.com/?s=hashing) to be quite instructive as an overview of various hashing techniques. check it out for some fun ?
deleted 5y ago
[deleted]
FreakLegion 5y ago
> Ok so never mind... Keep reading, specifically the Variations section. 50% occupancy is for constructions with a per-bucket capacity of 1. At a capacity of 2, occupancy improves to a little under 90%, and at 4 to just under 98%. The linked write-up uses 8, which does in fact achieve very high occupancy. They could've done better, though. By using windows instead of buckets (i.e. allowing the buckets to overlap), a capacity of 2 already yields > 96% occupancy, and 4 reaches 99.9%, so smaller and faster (lookups examine fewer keys on average). This approach is detailed in "3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit".
- dataflow 5y ago
  Thanks, that explains what they're saying now. But I'm still skeptical. How achievable is 98% fill for 4-element buckets in the first place? Intuitively I feel like you'd frequently have to scrap the table and rehash or enlarge it... is that not the case?
  - phkahler 5y ago
    Seems like a good point. If you're at 90+ percent occupancy you're going to run into trouble adding more data.
  - jasonwatkinspdx 5y ago
    So, for the complete formal answer get Mitzenmacher's book: https://www.amazon.com/Probability-Computing-Randomized-Algorithms-Probabilistic/dp/0521835402 https://www.amazon.com/Probability-Computing-Randomized-Algo... There are incrementally resizing versions, generally under the name Levelized Hashing. The most state of the art versions of these are lock free. (example: https://www.usenix.org/conference/atc20/presentation/chen https://www.usenix.org/conference/atc20/presentation/chen)
  - FreakLegion 5y ago
    Like with Bloom filters (which also draw their power from hashing items into multiple buckets), the statistical guarantees are quite strong, and things work well in practice. There are other options for the insertion algorithm than the standard random walk, too. E.g. take a look at page 18 of "Load Thresholds for Cuckoo Hashing with Overlapping Blocks" [1] for empirical data on 2-3 hash functions for 2-3 size windows. They don't show 4- or 8-size windows, but you get the gist. Like nullc says below, it's trivial to tune things for your requirements. Want fast insertions? Overprovision. Want more predictable insertions? Use a smarter insertion algorithm. Want small tables? Use more hash functions and/or larger buckets. Want fast queries? Keep the hash count and bucket sizes small. Rehashing isn't really a concern beyond the case of 2 hash functions and non-overlapping buckets of size 1. 1. https://arxiv.org/pdf/1707.06855.pdf https://arxiv.org/pdf/1707.06855.pdf

truenindb 5y ago

It's because the internet is a perfect sterling engine, guaranteeing that all eyeballs will be monotized in an adiabatic flow. It is know as "The Permanent November of ImaginosVictory Law" to those of us that have been using the internet since Salman Rushdie invented email, which is one of the best exemplars of a good protocol since Google Wave.

xarope 5y ago
bingo?
lrem 5y ago
Was this generated with some GPT3-like or something?
- orf 5y ago
  I think so, the only result on Google for “ ImaginosVictory” is that very comment.
chana_masala 5y ago
Do you have an ICO I buy into?
DiabloD3 5y ago
I don't know who's running a GPT bot on HN, but this is a beautiful work of art.

throwaway81523 5y ago

IIRC you can get to high occupancy by doing enough rehashes. After that, if you do no more insertions and only lookups, it is a good deal since each lookup takes at most two memory accesses. So this is useful if you are willing to spend a long time building what will then be a read-only table. Obviously there are uses for that.

dataflow 5y ago
> IIRC you can get to high occupancy by doing enough rehashes. Yeah so how many total insertions (as part of the rehashing) do you expect to have to do to achieve 99% occupancy? Wouldn't it be even worse than O(n^2)? And if you're going to spend a lot of time rebuilding the hash table all the time, then why not just use a perfect hash generator?
- throwaway81523 5y ago
  Large perfect hash tables have to store an awful lot of information. I don't remember quite how it's done but it's not a free lunch. The hash function itself has a size that grows with the total size of all the keys. I don't know offhand how many rehashes you need to get 98% occupancy with cuckoo hashing. There may be ways to optimize it by sharding the table into smaller ones. I'll re-read the wikipedia article when I get a chance. It's a fun algorithm and I've sometimes looked for places to use it.
- nullc 5y ago
  > Yeah so how many total insertions (as part of the rehashing) do you expect to have to do to achieve 99% occupancy? Wouldn't it be even worse than It depends on your bucket sizes and how many hashes you use. If you attempt 99% occupancy with 2 hashes and 4 entries per bucket, then you are going to be doing a LOT of kicking. 92% with that geometry, OTOH, is fine and will end up with just a couple kicks per insert on average.

signa11 5y ago

i found this (https://codecapsule.com/?s=hashing https://codecapsule.com/?s=hashing) to be quite instructive as an overview of various hashing techniques. check it out for some fun ?

deleted 5y ago

[deleted]

FreakLegion 5y ago

> Ok so never mind... Keep reading, specifically the Variations section. 50% occupancy is for constructions with a per-bucket capacity of 1. At a capacity of 2, occupancy improves to a little under 90%, and at 4 to just under 98%. The linked write-up uses 8, which does in fact achieve very high occupancy. They could've done better, though. By using windows instead of buckets (i.e. allowing the buckets to overlap), a capacity of 2 already yields > 96% occupancy, and 4 reaches 99.9%, so smaller and faster (lookups examine fewer keys on average). This approach is detailed in "3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit".

dataflow 5y ago
Thanks, that explains what they're saying now. But I'm still skeptical. How achievable is 98% fill for 4-element buckets in the first place? Intuitively I feel like you'd frequently have to scrap the table and rehash or enlarge it... is that not the case?
- phkahler 5y ago
  Seems like a good point. If you're at 90+ percent occupancy you're going to run into trouble adding more data.
- jasonwatkinspdx 5y ago
  So, for the complete formal answer get Mitzenmacher's book: https://www.amazon.com/Probability-Computing-Randomized-Algorithms-Probabilistic/dp/0521835402 https://www.amazon.com/Probability-Computing-Randomized-Algo... There are incrementally resizing versions, generally under the name Levelized Hashing. The most state of the art versions of these are lock free. (example: https://www.usenix.org/conference/atc20/presentation/chen https://www.usenix.org/conference/atc20/presentation/chen)
- FreakLegion 5y ago
  Like with Bloom filters (which also draw their power from hashing items into multiple buckets), the statistical guarantees are quite strong, and things work well in practice. There are other options for the insertion algorithm than the standard random walk, too. E.g. take a look at page 18 of "Load Thresholds for Cuckoo Hashing with Overlapping Blocks" [1] for empirical data on 2-3 hash functions for 2-3 size windows. They don't show 4- or 8-size windows, but you get the gist. Like nullc says below, it's trivial to tune things for your requirements. Want fast insertions? Overprovision. Want more predictable insertions? Use a smarter insertion algorithm. Want small tables? Use more hash functions and/or larger buckets. Want fast queries? Keep the hash count and bucket sizes small. Rehashing isn't really a concern beyond the case of 2 hash functions and non-overlapping buckets of size 1. 1. https://arxiv.org/pdf/1707.06855.pdf https://arxiv.org/pdf/1707.06855.pdf