News for hackers. Stuff that matters.
Re:Bloom Filters: More than a space-efficient hashmap by glangdale on Wednesday August 11, 2021 @02:25AM (#28138710)
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.

Re:Bloom Filters: More than a space-efficient hashmap by taeric on Wednesday August 11, 2021 @11:12AM (#28142973)
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.

Re:Bloom Filters: More than a space-efficient hashmap by glangdale on Wednesday August 11, 2021 @01:17PM (#28144820)
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.

Re:Bloom Filters: More than a space-efficient hashmap by yunohn on Wednesday August 11, 2021 @09:47AM (#28141879)
> 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?

Re:Bloom Filters: More than a space-efficient hashmap by glangdale on Wednesday August 11, 2021 @01:37PM (#28145086)
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.

Re:Bloom Filters: More than a space-efficient hashmap by masklinn on Wednesday August 11, 2021 @05:17AM (#28139798)
What issues do you have with cuckoo hashing? Unlike bloom filters it seems like a completely reasonable default / baseline no?
Re:Bloom Filters: More than a space-efficient hashmap by glangdale on Wednesday August 11, 2021 @06:58AM (#28140491)
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.

Re:Bloom Filters: More than a space-efficient hashmap by ot on Wednesday August 11, 2021 @11:51AM (#28143565)
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.

Re:Bloom Filters: More than a space-efficient hashmap by thomasmg on Wednesday August 11, 2021 @08:09AM (#28141007)
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/ for a fast hash table implementation.
Re:Bloom Filters: More than a space-efficient hashmap by masklinn on Wednesday August 11, 2021 @09:03AM (#28141499)
Using hashbrown as evidence in a comment defending linear probing is odd when it specifically notes that it uses quadratic probing.
Re:Bloom Filters: More than a space-efficient hashmap by thomasmg on Wednesday August 11, 2021 @10:01AM (#28142072)
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-has... (of course "fastest" is relative, when it comes to benchmarks)