An implementation of batched bloom filter query, optimised for memory prefetch.

Key algorithm concepts

There is almost no opportunity for memory prefetching when looking up a single key in a single Bloom filter. So this is a bulk algorithm, to do a lot of work all in one go, which does create the opportunity to prefetch memory. It also provides an opportunity to share key hashes across filters.

We have as inputs N bloom filters and M keys to look up in them. So overall there are N * M independent bloom filter tests. The result is expected to be sparse, with roughly M*(1+FPR) positive results. So we use a sparse representation for the result: pairs of indexes identifying input Bloom filters and input keys with a positive test result.

We aim for the number of memory operations in-flight simultaneously to be on the order of 32. This trades-off memory parallelism with cache use. In particular this means the algorithm must be able to use a fixed prefetch "distance" rather than this being dependent on the input sizes. To achieve this, we use a fixed size circular buffer (queue). The buffer size can be tuned to optimise the prefetch behaviour: indeed we pick exactly 32.

Micro optimisation

We use primitive arrays and arrays -- rather than vectors -- so as to minimise the number of function variables, to be able to keep most things in registers. Normal vectors use two additional variables, which triples register pressure.

We use an Array of Strict BloomFilter. This avoids the test for WHNF in the inner loop, which causes all registered to be spilled to and restored from the stack.