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

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).