Proposal: Operator context. A new hope for memory churn

Problem statement

While performing binary operations roaring-rs makes every effort to reuse stores from an owned bitmap that will otherwise be dropped and the end of the op. This is generally accomplished by taking the store out of the to-be-dropped bitmap, then then using the assigning equivalent of the operation. A simpler version of this is: Given an owned a the expression a = a & b is equivalent to a &= b.

For bitmap stores, this is always good news. For arrays however, it depends.

For scalar ops

For operators that can only remove values: this is fine. There are simple algorithms for intersection and difference that given some slices mut a, b can traverse both in one pass, copying items from b or from further ahead in a, then truncating at the end.

Operators that can add values are more costly to perform in place: as they may need to insert values from b into a, meaning large portions of a may need to be copied forwards or backwards. Time complexity can be traded for space complexity by writing to a buffer rather than performing the operation in place. Surprisingly, this is how union is implemented today, but not symmetric difference. There is no impl for BitOrAssign for array stores, but there is for BitXOrAssign with a curious // TODO improve this function

To summarize so far:

1. We want to prevent needlessly allocating when possible
2. For array stores:
   • For intersection and difference it does not affect the time complexity
   • For union and symmetric difference it does, there are time-memory trade-offs to having an output buffer

SIMD

SIMD is merged, however it further complicates the issues outlined above as none of the block algorithms (as they are written) can run in place. The blocks are stored in full from registers into the output buffer, however not all the values in the block are valid. This is fine, because we truncate the len to the number of valid values, thus the invalid values are overwritten by the next block write (or, for the last block: remain, but are never accessed because they are beyond the vec len). Intersection and difference can be made to operate in place, but that would require some mechanism of storing values without doing a simple store to the buffer. Options are either a SIMD scatter operation, or store to an intermediate buffer then copy to the output. Scatter latencies can be 10-15x compared to a store, storing to a small [u16; 4] then copying whatever subslice is valid is probably better, but obviously still slower than just the store.

More summary:

1. Array-array SIMD ops are merged, but only wired up for code paths that do not operate in place. For reasons defined in the first section, this is the minority of code paths.

Note: In the experimental SIMD branch we just decided to let all array ops allocate a new vec. As far as time-space tradeoffs go, allocating a new vec, using the vectorized alg, then dropping the old one is still much faster.
Unfortunately though this playing fast-and-loose with memory goes against much of the hard work we've already done to be conservative with it.

We also tried keeping a thread local buffer around. It worked well but @Kerollmops pointed out it's got some portability issues.

Proposal

As a solution to the above problems I propose introducing an operator context that is created at the operator entry point and passed down through each layer. Its role is to hold on to stores that can be reused, and either hand them out when necessary, or create new ones if it does not have any. ensure_correct_store can also add and remove from the context as necessary, further reducing needless memory churn. The context will of course be dropped after the op has completed, along with all it's owned stores.

I have validated the idea by implementing a naive context that only holds one array store, only implemented adding/removing for intersection, (not including ensure_correct_store) and demonstrated it's time performance was at least as good as, if not faster than always allocating for all datasets. Being able to hold many arrays, and also bitmap stores, plus wiring up to ensure_correct_store should further decrease time and memory requirements.

criterion.zip

TL;DR: "Time or memory: pick two!" (but we pay for them with some added complexity)

No concrete files or tests are named. Start at the operator entry points and trace how stores flow through ensure_correct_store, then compare the existing in-place and allocating array and SIMD paths; use the supplied criterion.zip results as a performance reference. Done means an operator context can reuse the relevant stores while preserving the intended time and memory trade-offs.