3 ms·
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 mos
by 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 agoNo, 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).