4 ms·

I'm not sure why the author started with bloom filters instead of a hash table, to be honest. The workload seems ideal for a hash table. Interesting to see how

I'm not sure why the author started with bloom filters instead of a hash table, to be honest. The workload seems ideal for a hash table. Interesting to see how big the performance gap was though, I wouldn't have expected such a difference. It probably comes down to the fact that the bloom filter has to spread its data across many locations so if the set is particularly large it's always going to lose to a hash table due to hitting main memory more times (in scenarios where you can use either one, at least). I suppose they started with a bloom filter because they intended to use one when consuming the data, i.e. checking incoming requests against a 'malicious IP' set?

majke 7y ago
The secret is that I used a bloom filter anyway, as the next stage in the pipeline. I needed to load the IP whitelist/blacklist data quickly and rapidly compare packets against it. I had tooling to do bloom filters already. I also had an image in my mind, that bloom filters are perfect for such a use case - "set" data structure with some adjustable loss (probabilistic) parameters. I thought that Bloom filters are underappreciated. I was wrong. As we learned "set" is better done with good old hash table.
- UncleEntity 7y ago
  Radix tree seems like a good fit, was bored one day and implemented one as a CPython module in a couple hours--think I had some idea around IP addresses to use it for. --edit-- Actually, it was a hextree (radix tree specialized for the hexes). Think someone posted a link to the paper on it a while back.
stefan_ 7y ago
I don't know why the author didn't stick to their shell script, which took all of 2 minutes for a manual data cleanup step. Like, go grab a coffee.
- Izkata 7y ago
  My thought was that, plus "use `make` with an intermediate file". No need to re-run it if the sources haven't changed, right?
- majke 7y ago
  2 minutes was for 40M items. I had 1B items to sort/uniq.

majke 7y ago

The secret is that I used a bloom filter anyway, as the next stage in the pipeline. I needed to load the IP whitelist/blacklist data quickly and rapidly compare packets against it. I had tooling to do bloom filters already. I also had an image in my mind, that bloom filters are perfect for such a use case - "set" data structure with some adjustable loss (probabilistic) parameters. I thought that Bloom filters are underappreciated. I was wrong. As we learned "set" is better done with good old hash table.

UncleEntity 7y ago
Radix tree seems like a good fit, was bored one day and implemented one as a CPython module in a couple hours--think I had some idea around IP addresses to use it for. --edit-- Actually, it was a hextree (radix tree specialized for the hexes). Think someone posted a link to the paper on it a while back.

stefan_ 7y ago

I don't know why the author didn't stick to their shell script, which took all of 2 minutes for a manual data cleanup step. Like, go grab a coffee.

Izkata 7y ago
My thought was that, plus "use `make` with an intermediate file". No need to re-run it if the sources haven't changed, right?
majke 7y ago
2 minutes was for 40M items. I had 1B items to sort/uniq.