4 ms·

The Bloom filter he uses has k=8, that is 8 cache line misses per entry. (k=8 is in the command line output). A "blocked Bloom fiter" requires only one cache li

The Bloom filter he uses has k=8, that is 8 cache line misses per entry. (k=8 is in the command line output). A "blocked Bloom fiter" requires only one cache line miss per entry, with a slightly worse false positive rate. With a good implementation it would be roughly 10 times faster, eg a SIMD implementation. For example here https://github.com/FastFilter/fastfilter_cpp/blob/master/src/bloom/simd-block.h https://github.com/FastFilter/fastfilter_cpp/blob/master/src... (there are others)

majke 2y ago
Thanks for the pointer. The file comment says: // This is a block Bloom filter (from Putze et al.'s "Cache-, Hash- and Space-Efficient Bloom Filters") with some twists: // 1. Each block is a split Bloom filter - see Section 2.1 of Broder and Mitzenmacher's // "Network Applications of Bloom Filters: A Survey". // 2. The number of bits set per Add() is contant in order to take advantage of SIMD instructions. Mentioned papers: https://www.cs.amherst.edu/~ccmcgeoch/cs34/papers/cacheefficientbloomfilters-jea.pdf https://www.cs.amherst.edu/~ccmcgeoch/cs34/papers/cacheeffic... https://www.eecs.harvard.edu/~michaelm/CS222/bloomsurvey.pdf https://www.eecs.harvard.edu/~michaelm/CS222/bloomsurvey.pdf
limit499karma 2y ago
That's the L1. Blocked -- segmented would have been a better name imo -- approach still depends on the blocks to be resident in L2/LLC. OP's problem is that most of the blocks' pages (not cache-line) are not resident in LLC. I wonder about an op-buffer approach. ~: buffer the BF ops to aggregate ops on a specific address ranges. Say first buffer n ops for the filter, sort by the (relevant) hash bits, and then apply m ops for a specific page, and so on. And optimizing that, it may be possible to only process the op-buffer partially, i.e. add ops until the buffer is full, gather the ops that map to a page-segment (4k), and if the rest of the buffer is still all over the place continue buffering, and rinse and repeat. [p.s.] OP's task at hand is an off-line matter whereas general BF approaches assume an on-line use case. By adopting an off-line approach, I should think there remain many opportunities for optimizing the runtime.
- thomasmg 2y ago
  No, it's not the L1. It's the L2/L3/LLC. With a regular Bloom filter (not blocked one), each of the k memory accesses results in a L2/L3/LLC cache miss, if the Bloom filter doesn't fit in the cache. And here, it doesn't. With a blocked Bloom filter, there is still a cache miss, but only one, and not k. So that's 8 times fewer cache misses. But yes, buffering the entries and then sorting them does make sense. That way, each cache line is only accessed once, and prefetch works well. We have used radix sorting for the binary fuse filter https://arxiv.org/abs/2201.01174 https://arxiv.org/abs/2201.01174 . For the blocked Bloom filter I'm not sure if it will help however, due to the added complexity. In my tests, it didn't help. There is the "prefetch" operation but we had mixed results with that (buffering and sorting was faster).

majke 2y ago

Thanks for the pointer. The file comment says: // This is a block Bloom filter (from Putze et al.'s "Cache-, Hash- and Space-Efficient Bloom Filters") with some twists: // 1. Each block is a split Bloom filter - see Section 2.1 of Broder and Mitzenmacher's // "Network Applications of Bloom Filters: A Survey". // 2. The number of bits set per Add() is contant in order to take advantage of SIMD instructions. Mentioned papers: https://www.cs.amherst.edu/~ccmcgeoch/cs34/papers/cacheefficientbloomfilters-jea.pdf https://www.cs.amherst.edu/~ccmcgeoch/cs34/papers/cacheeffic... https://www.eecs.harvard.edu/~michaelm/CS222/bloomsurvey.pdf https://www.eecs.harvard.edu/~michaelm/CS222/bloomsurvey.pdf

limit499karma 2y ago

That's the L1. Blocked -- segmented would have been a better name imo -- approach still depends on the blocks to be resident in L2/LLC. OP's problem is that most of the blocks' pages (not cache-line) are not resident in LLC. I wonder about an op-buffer approach. ~: buffer the BF ops to aggregate ops on a specific address ranges. Say first buffer n ops for the filter, sort by the (relevant) hash bits, and then apply m ops for a specific page, and so on. And optimizing that, it may be possible to only process the op-buffer partially, i.e. add ops until the buffer is full, gather the ops that map to a page-segment (4k), and if the rest of the buffer is still all over the place continue buffering, and rinse and repeat. [p.s.] OP's task at hand is an off-line matter whereas general BF approaches assume an on-line use case. By adopting an off-line approach, I should think there remain many opportunities for optimizing the runtime.

thomasmg 2y ago
No, it's not the L1. It's the L2/L3/LLC. With a regular Bloom filter (not blocked one), each of the k memory accesses results in a L2/L3/LLC cache miss, if the Bloom filter doesn't fit in the cache. And here, it doesn't. With a blocked Bloom filter, there is still a cache miss, but only one, and not k. So that's 8 times fewer cache misses. But yes, buffering the entries and then sorting them does make sense. That way, each cache line is only accessed once, and prefetch works well. We have used radix sorting for the binary fuse filter https://arxiv.org/abs/2201.01174 https://arxiv.org/abs/2201.01174 . For the blocked Bloom filter I'm not sure if it will help however, due to the added complexity. In my tests, it didn't help. There is the "prefetch" operation but we had mixed results with that (buffering and sorting was faster).