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... (there are others)
// 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.
https://www.cs.amherst.edu/~ccmcgeoch/cs34/papers/cacheeffic...
https://www.eecs.harvard.edu/~michaelm/CS222/bloomsurvey.pdf
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.
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 . 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).