6 ms·

I like Bloom filters well enough, but I've noticed them getting cargo-culted into projects where they aren't even remotely necessary. There are a few techniques

I like Bloom filters well enough, but I've noticed them getting cargo-culted into projects where they aren't even remotely necessary. There are a few techniques that people seem to love (Cuckoo hashes are another) and uncritically apply without much analysis. Where they are good, they're good, but I've seen techniques with Impressive Papers being used more or less at random where the basic data structure would have been fine.

masklinn 5y ago
What issues do you have with cuckoo hashing? Unlike bloom filters it seems like a completely reasonable default / baseline no?
- glangdale 5y ago
  Cuckoo hashes are great if you really understand why you're using them, but 99% of people would be fine with chaining for most applications or a simpler set-associative scheme if open addressing is not negotiable. Their locality is problematic, they are fantastically hard to get right in a multi-reader/multi-writer case (if you don't want to just lock the whole damn table) and they're just all-round complex with surprising sharp edges. The fact that you have to go wandering off with a bunch of unpredictable data-dependent reads if you don't find what you're looking for is ... wild. Alternately you can pay the costs of multiple parallel accesses preemptively, but now you've smashed throughput in case the table is big enough to be bandwidth limited (L3, memory). They look pretty great when the load factor is low, but everything looks great with a light load factor. As far as open-addressing schemes go, they're OK, but I see people reaching for them for reasons that don't seem to make any sense.
  - thomasmg 5y ago
    Yes, exactly. Linear probing is often easier and faster. Using buckets also helps (each bucket contains multiple slots), for both cuckoo hashing and linear probing. E.g. the cuckoo filter uses a bucket size of 4. See also https://gankra.github.io/blah/hashbrown-tldr/ https://gankra.github.io/blah/hashbrown-tldr/ for a fast hash table implementation.
    - masklinn 5y ago
      Using hashbrown as evidence in a comment defending linear probing is odd when it specifically notes that it uses quadratic probing.
      - thomasmg 5y ago
        I'm sorry! I thought this implementation uses linear probing. Yes this is not an example of linear probing. But it is much closer to linear probing than to cuckoo hashing (I hope we can agree on this). I also found this blog entry interesting: https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/ https://probablydance.com/2017/02/26/i-wrote-the-fastest-has... (of course "fastest" is relative, when it comes to benchmarks)
  - ot 5y ago
    Biggest problem with Cuckoo tables is that if your hash function doesn't have the right properties insertions do not converge. They literally go into an infinite loop. This makes them not viable as a generic primitive for hash tables. Besides, as you mention, that they're in fact slower than modern engineered hash table implementation that do only one random memory access in the vast majority of cases.
yunohn 5y ago
> I've noticed them getting cargo-culted into projects where they aren't even remotely necessary Do you have some examples that can be shared?
- glangdale 5y ago
  That would be mean, and perhaps even career-limiting or break NDAs or both. One example I can point to is the fact that we (Sensory Networks) had cargo-culted in a recursive hash function for a string matching engine (back when we made hardware). There was no real reason to be using a recursive hash at all, but there was a cool paper from the NSA about recursive hashing, so there it was. No-one had even evaluated anything simpler. Again, recursive hashing is cool. Arguably Bloom filters and (maybe) Cuckoo hashes are cool too - but my problem isn't with the existence of these techniques but the way that people seem to get a rush of blood to the head and use them when they're kind of pointless and overcomplex.
taeric 5y ago
Same goes for prefix and suffix trees. And for a lot of dynamic algorithms. It is tough, as these are definitely good skills. But they are stupid easy ways to stall out projects.
- glangdale 5y ago
  I built a beautiful dynamic algorithm a while back to assign strings to "buckets" in Hyperscan. The problem is (roughly) that you can pack lots of strings into buckets for a "bucketed super-character shift-or matcher", but if you pack strings of wildly disparate length together (e.g. "foobar" and "xyz") into the same bucket they wind up weakening the power of the matcher for the longer strings (it's still correct; the primary table is just a prefilter). But "foobar" and "xyz" together are pretty close to "bar" and "xyz" (there are some subtleties). So the problem was you have a bunch of strings of different lengths but only 8 buckets to pack things into. I had some neat heuristics to estimate the cost of weakening strings of various lengths based on estimated false positive rates - and then a dynamic function to optimize packing for various choices. However, I buggered up the heuristic function. Due to the complexity of the dynamic algorithm, the magic numbers were pretty hard to debug or even understand, and it created a weird performance corner we didn't discover for a year or so. Most of the answers it gave were pretty plausible even with the wrong heuristic... sigh.

masklinn 5y ago

What issues do you have with cuckoo hashing? Unlike bloom filters it seems like a completely reasonable default / baseline no?

glangdale 5y ago
Cuckoo hashes are great if you really understand why you're using them, but 99% of people would be fine with chaining for most applications or a simpler set-associative scheme if open addressing is not negotiable. Their locality is problematic, they are fantastically hard to get right in a multi-reader/multi-writer case (if you don't want to just lock the whole damn table) and they're just all-round complex with surprising sharp edges. The fact that you have to go wandering off with a bunch of unpredictable data-dependent reads if you don't find what you're looking for is ... wild. Alternately you can pay the costs of multiple parallel accesses preemptively, but now you've smashed throughput in case the table is big enough to be bandwidth limited (L3, memory). They look pretty great when the load factor is low, but everything looks great with a light load factor. As far as open-addressing schemes go, they're OK, but I see people reaching for them for reasons that don't seem to make any sense.
- thomasmg 5y ago
  Yes, exactly. Linear probing is often easier and faster. Using buckets also helps (each bucket contains multiple slots), for both cuckoo hashing and linear probing. E.g. the cuckoo filter uses a bucket size of 4. See also https://gankra.github.io/blah/hashbrown-tldr/ https://gankra.github.io/blah/hashbrown-tldr/ for a fast hash table implementation.
  - masklinn 5y ago
    Using hashbrown as evidence in a comment defending linear probing is odd when it specifically notes that it uses quadratic probing.
    - thomasmg 5y ago
      I'm sorry! I thought this implementation uses linear probing. Yes this is not an example of linear probing. But it is much closer to linear probing than to cuckoo hashing (I hope we can agree on this). I also found this blog entry interesting: https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/ https://probablydance.com/2017/02/26/i-wrote-the-fastest-has... (of course "fastest" is relative, when it comes to benchmarks)
- ot 5y ago
  Biggest problem with Cuckoo tables is that if your hash function doesn't have the right properties insertions do not converge. They literally go into an infinite loop. This makes them not viable as a generic primitive for hash tables. Besides, as you mention, that they're in fact slower than modern engineered hash table implementation that do only one random memory access in the vast majority of cases.

yunohn 5y ago

> I've noticed them getting cargo-culted into projects where they aren't even remotely necessary Do you have some examples that can be shared?

glangdale 5y ago
That would be mean, and perhaps even career-limiting or break NDAs or both. One example I can point to is the fact that we (Sensory Networks) had cargo-culted in a recursive hash function for a string matching engine (back when we made hardware). There was no real reason to be using a recursive hash at all, but there was a cool paper from the NSA about recursive hashing, so there it was. No-one had even evaluated anything simpler. Again, recursive hashing is cool. Arguably Bloom filters and (maybe) Cuckoo hashes are cool too - but my problem isn't with the existence of these techniques but the way that people seem to get a rush of blood to the head and use them when they're kind of pointless and overcomplex.

taeric 5y ago

Same goes for prefix and suffix trees. And for a lot of dynamic algorithms. It is tough, as these are definitely good skills. But they are stupid easy ways to stall out projects.

glangdale 5y ago
I built a beautiful dynamic algorithm a while back to assign strings to "buckets" in Hyperscan. The problem is (roughly) that you can pack lots of strings into buckets for a "bucketed super-character shift-or matcher", but if you pack strings of wildly disparate length together (e.g. "foobar" and "xyz") into the same bucket they wind up weakening the power of the matcher for the longer strings (it's still correct; the primary table is just a prefilter). But "foobar" and "xyz" together are pretty close to "bar" and "xyz" (there are some subtleties). So the problem was you have a bunch of strings of different lengths but only 8 buckets to pack things into. I had some neat heuristics to estimate the cost of weakening strings of various lengths based on estimated false positive rates - and then a dynamic function to optimize packing for various choices. However, I buggered up the heuristic function. Due to the complexity of the dynamic algorithm, the magic numbers were pretty hard to debug or even understand, and it created a weird performance corner we didn't discover for a year or so. Most of the answers it gave were pretty plausible even with the wrong heuristic... sigh.