4 ms·

Another slightly fancier than the usual textbook approaches is cuckoo hashing. Has anyone done a comparison with cuckoo vs. robinhood?

by jabl 10y ago

doomrobo 10y ago
They're pretty similar in philosophy. I'd guess that Robin Hood would perform better on average just by virtue of linear probing. If you get a collision in a Cukoo hash, you're pretty much guaranteed a cache miss. With a Robin Hood hash, it's pretty likely that the element you're looking for is in the same cacheline as the collision.
- erichocean 10y ago
  > If you get a collision in a Cukoo hash, you're pretty much guaranteed a cache miss. Don't people usually use buckets with cuckoo hashing, so that each location houses 2 or more values (one right after the other)? I guess I'm not seeing how that's fundamentally different from linear probing...
  - doomrobo 10y ago
    It's the same problem though. As the other comment said, you have 2 uncorrelated memory locations. If you check the first one and your element isn't there, then checking the second one will probably incur a cache miss. The difference between linear probing and buckets is a big one: buckets are linked lists. That means that hitting a bucket doesn't pull everything else inside the bucket into the CPU cache. So iterating through the bucket may incur a cache miss for every element. On the other hand, linear probing in open addressing does away with buckets and instead searches the neighbors of the collision. Because they're nearby in memory, it's a lot quicker to search.
    - pkhuong 10y ago
      You can have preallocated buckets in an array. What's the difference you ask? When you have more elements per buckets, the variance becomes smaller as a fraction of the bucket's size. Imagine you had a hash table with buckets of 1000 elements. You'd probably feel comfortable with a 90% load even without any strategy to handle bucket overflow except growing and rehashing. Obviously, the downside is that we have to do more work to search in buckets.
  - pbasista 10y ago
    Why would they do that? The cuckoo hashing is just a collision resolution technique used in open addressing hashing schemes. Having two possible hashes of a key always next to each other (that is what you suggest by using buckets if I understand correctly) would cause the cuckoo algorithm for kicking out the conflicting items to stop working. If both possible locations for a key are always in the same bucket, the two keys with a colliding hash would also share the alternative hash (i.e. it would be the other place in the same bucket). And so, they would only be able to kick each other out. A loop of length 2. Always. If three keys hash into the same bucket, you will have to rehash the entire table. You can have larger buckets, but the problem remains. Once a big enough number of keys hash into the same bucket, you will have to rehash the table. That would most probably mean low typical load factors. Of course, what you will be getting in return is the locality of memory references. But is that a reasonable trade-off? I think there are better ways to achieve locality of memory references...
    - cmurphycode 10y ago
      Forgive me, but I think you've misunderstood something here. The most important thing about the cuckoo is that your bucket choice functions (i.e. hashing function) are independent. If two keys hash to the same first choice bucket, their alternate hashes will (almost certainly) hash to DIFFERENT buckets. For instance, take the SHA-1 of the key. Your first bucket choice is defined by the first x bits, your second bucket choice is defined by the next x bits. But inside a bucket, you can have a bunch of slots. It works like this. A typical sizing is 4 slots in a bucket, with 2 bucket choices. So your first choice, you arrive at a bucket, and it is just a linear array of length 4. You can put your element anywhere! After a while, when you go to insert into your first choice and you find all 4 slots taken, then you can take ANY of those and try to put it in its alternate bucket. If that alternate bucket is full, you evict from that bucket, too! Thanks to the random nature of your hash functions, it works out very well. 2 bucket 4 slot gets you near 95% occupancy without many evictions on insert. When you go to lookup, you check your first bucket, and you check all 4 elements until you find it. If you don't find it, you go to your alternate bucket and check all 4 elements. But that's it - only two random accesses (the 4 slots will easily fit in a cache line). It's not so bad to check all 4 elements because the cost is really dominated by loading the line to begin with. I really recommend a read of some of the cuckoo papers, it's cool stuff.
pkhuong 10y ago
Lookups in cuckoo tables hit two uncorrelated ("random") locations in the hash table. That's not a problem for hardware implementations that can just read from two different SRAMs. On commodity hardware with virtual memory, it depends. If the table fits in your TLBs, you're probably OK… but at such small sizes, the complexity of Cuckoo hashing and its sensitivity to bad hash functions might not be ideal. If, however, both accesses are expected to incur TLB misses, you're very likely screwed: handling the misses takes a lot of resources and the vast majority of (commodity) CPUs can only handle one TLB miss at a time. After hashing, the time for lookups is now dominated by two TLB misses; compare to one TLB miss with linear probing. You can also play the odds and only do the second lookup conditionally; that's still ~1.5 random accesses on average (versus 1). Cuckoo hashing can get you 95-99% occupancy versus 80-90% with simpler schemes. Unless you have specialised size or cost requirements, it seems to me the extra 10-20% space usage is a better choice than double the random accesses.
- nkurz 10y ago
  I lost you in the last paragraph. Are you maybe missing a word, or saying cuckoo where you mean Robin Hood? Separately, aren't TLB misses pretty fast compared to hitting RAM? I'd think they would only dominate if the TLB itself it too large for cache, which I don't think is common. And if you are using so much memory that this is happening, moving to GB Hugepages would solve it The "sensitivity to a bad hash function" seems like an odd weakness. For a given quality of hash, wouldn't cuckoo tend to be less susceptible than any single hash approach? I ask because I'm currently bullish on d-ary cuckoo hashes, and think they'd be a good fit for the fast gather on Skylake.
  - pkhuong 10y ago
    My last paragraph says you're probably better off with a solution that doesn't achieve the same density but avoids the uncorrelated accesses. In other words, stick to some form of local probing and take the hit in density. Why would TLB misses be small compared to RAM latency? A TLB miss must be serviced by reading more memory, and misses aren't handled in parallel, unlike random reads to RAM. Sure, you could use very large (1G) pages, but that's a pretty specialised setup that's not available on every platform and tends to require a reboot to enable/tweak. Not something we want to rely on in general. Cuckoo is particularly sensitive to bad hash functions: if a few elements always hash to the same pair of values, you're screwed. That's particularly problematic with the usual interfaces that don't let the hash table specify a seed to the hash function and expect a machine word: we have to map values to hashes, and remix or split the hashes (in theory, that's defensible as long as the intermediate hash is strong and its codomain is at least (hash set size)^2), but there's nothing to remix away if we have too many values that map to the same intermediate hash. If the hash table specifies calls the hash function with two different seeds, that means double the time spent in hashing, and that overhead can cover for a lot of linear probing. Simple deterministic probing technique just take a hit with a bigger cluster than expected; a performance degradation, but the table still work. You can also see theoretical analyses that'll lead you to similar conclusions if you look at the k-independence needed for each hashing technique. Finally, I don't think gathers are faster than independent memory accesses unless everything is in the same cache line. You don't need SIMD instructions to expose memory level parallelism, you just need independent dependency graphs in your serial computation (until you're bottlenecked on an execution resource that's not duplicated and rarely pipelined, like the TLB miss logic).

Another slightly fancier than the usual textbook approaches is cuckoo hashing. Has anyone done a comparison with cuckoo vs. robinhood?

by jabl 10y ago

Another slightly fancier than the usual textbook approaches is cuckoo hashing. Has anyone done a comparison with cuckoo vs. robinhood?

doomrobo 10y ago

They're pretty similar in philosophy. I'd guess that Robin Hood would perform better on average just by virtue of linear probing. If you get a collision in a Cukoo hash, you're pretty much guaranteed a cache miss. With a Robin Hood hash, it's pretty likely that the element you're looking for is in the same cacheline as the collision.

erichocean 10y ago
> If you get a collision in a Cukoo hash, you're pretty much guaranteed a cache miss. Don't people usually use buckets with cuckoo hashing, so that each location houses 2 or more values (one right after the other)? I guess I'm not seeing how that's fundamentally different from linear probing...
- doomrobo 10y ago
  It's the same problem though. As the other comment said, you have 2 uncorrelated memory locations. If you check the first one and your element isn't there, then checking the second one will probably incur a cache miss. The difference between linear probing and buckets is a big one: buckets are linked lists. That means that hitting a bucket doesn't pull everything else inside the bucket into the CPU cache. So iterating through the bucket may incur a cache miss for every element. On the other hand, linear probing in open addressing does away with buckets and instead searches the neighbors of the collision. Because they're nearby in memory, it's a lot quicker to search.
  - pkhuong 10y ago
    You can have preallocated buckets in an array. What's the difference you ask? When you have more elements per buckets, the variance becomes smaller as a fraction of the bucket's size. Imagine you had a hash table with buckets of 1000 elements. You'd probably feel comfortable with a 90% load even without any strategy to handle bucket overflow except growing and rehashing. Obviously, the downside is that we have to do more work to search in buckets.
- pbasista 10y ago
  Why would they do that? The cuckoo hashing is just a collision resolution technique used in open addressing hashing schemes. Having two possible hashes of a key always next to each other (that is what you suggest by using buckets if I understand correctly) would cause the cuckoo algorithm for kicking out the conflicting items to stop working. If both possible locations for a key are always in the same bucket, the two keys with a colliding hash would also share the alternative hash (i.e. it would be the other place in the same bucket). And so, they would only be able to kick each other out. A loop of length 2. Always. If three keys hash into the same bucket, you will have to rehash the entire table. You can have larger buckets, but the problem remains. Once a big enough number of keys hash into the same bucket, you will have to rehash the table. That would most probably mean low typical load factors. Of course, what you will be getting in return is the locality of memory references. But is that a reasonable trade-off? I think there are better ways to achieve locality of memory references...
  - cmurphycode 10y ago
    Forgive me, but I think you've misunderstood something here. The most important thing about the cuckoo is that your bucket choice functions (i.e. hashing function) are independent. If two keys hash to the same first choice bucket, their alternate hashes will (almost certainly) hash to DIFFERENT buckets. For instance, take the SHA-1 of the key. Your first bucket choice is defined by the first x bits, your second bucket choice is defined by the next x bits. But inside a bucket, you can have a bunch of slots. It works like this. A typical sizing is 4 slots in a bucket, with 2 bucket choices. So your first choice, you arrive at a bucket, and it is just a linear array of length 4. You can put your element anywhere! After a while, when you go to insert into your first choice and you find all 4 slots taken, then you can take ANY of those and try to put it in its alternate bucket. If that alternate bucket is full, you evict from that bucket, too! Thanks to the random nature of your hash functions, it works out very well. 2 bucket 4 slot gets you near 95% occupancy without many evictions on insert. When you go to lookup, you check your first bucket, and you check all 4 elements until you find it. If you don't find it, you go to your alternate bucket and check all 4 elements. But that's it - only two random accesses (the 4 slots will easily fit in a cache line). It's not so bad to check all 4 elements because the cost is really dominated by loading the line to begin with. I really recommend a read of some of the cuckoo papers, it's cool stuff.

pkhuong 10y ago

Lookups in cuckoo tables hit two uncorrelated ("random") locations in the hash table. That's not a problem for hardware implementations that can just read from two different SRAMs. On commodity hardware with virtual memory, it depends. If the table fits in your TLBs, you're probably OK… but at such small sizes, the complexity of Cuckoo hashing and its sensitivity to bad hash functions might not be ideal. If, however, both accesses are expected to incur TLB misses, you're very likely screwed: handling the misses takes a lot of resources and the vast majority of (commodity) CPUs can only handle one TLB miss at a time. After hashing, the time for lookups is now dominated by two TLB misses; compare to one TLB miss with linear probing. You can also play the odds and only do the second lookup conditionally; that's still ~1.5 random accesses on average (versus 1). Cuckoo hashing can get you 95-99% occupancy versus 80-90% with simpler schemes. Unless you have specialised size or cost requirements, it seems to me the extra 10-20% space usage is a better choice than double the random accesses.

nkurz 10y ago
I lost you in the last paragraph. Are you maybe missing a word, or saying cuckoo where you mean Robin Hood? Separately, aren't TLB misses pretty fast compared to hitting RAM? I'd think they would only dominate if the TLB itself it too large for cache, which I don't think is common. And if you are using so much memory that this is happening, moving to GB Hugepages would solve it The "sensitivity to a bad hash function" seems like an odd weakness. For a given quality of hash, wouldn't cuckoo tend to be less susceptible than any single hash approach? I ask because I'm currently bullish on d-ary cuckoo hashes, and think they'd be a good fit for the fast gather on Skylake.
- pkhuong 10y ago
  My last paragraph says you're probably better off with a solution that doesn't achieve the same density but avoids the uncorrelated accesses. In other words, stick to some form of local probing and take the hit in density. Why would TLB misses be small compared to RAM latency? A TLB miss must be serviced by reading more memory, and misses aren't handled in parallel, unlike random reads to RAM. Sure, you could use very large (1G) pages, but that's a pretty specialised setup that's not available on every platform and tends to require a reboot to enable/tweak. Not something we want to rely on in general. Cuckoo is particularly sensitive to bad hash functions: if a few elements always hash to the same pair of values, you're screwed. That's particularly problematic with the usual interfaces that don't let the hash table specify a seed to the hash function and expect a machine word: we have to map values to hashes, and remix or split the hashes (in theory, that's defensible as long as the intermediate hash is strong and its codomain is at least (hash set size)^2), but there's nothing to remix away if we have too many values that map to the same intermediate hash. If the hash table specifies calls the hash function with two different seeds, that means double the time spent in hashing, and that overhead can cover for a lot of linear probing. Simple deterministic probing technique just take a hit with a bigger cluster than expected; a performance degradation, but the table still work. You can also see theoretical analyses that'll lead you to similar conclusions if you look at the k-independence needed for each hashing technique. Finally, I don't think gathers are faster than independent memory accesses unless everything is in the same cache line. You don't need SIMD instructions to expose memory level parallelism, you just need independent dependency graphs in your serial computation (until you're bottlenecked on an execution resource that's not duplicated and rarely pipelined, like the TLB miss logic).