Single-pass non-inplace bitmap intersection (AND)

perfloop/roaring · INEFFICIENT ALGORITHM

https://perfloop.ai/t/oss/case_qsx98z9dsk

Verdict

VERIFIED · settled 2026-08-27

Hypothesis

In bitmapcontainer.go (lines 869-883), andBitmap is invoked on the critical path of the 'Parallel bitmap intersections (AND)' workload driven by ParAnd. Each bitmapContainer consists of a 1024-word slice (representing 8 KB of bitmap data). Currently, andBitmap performs two complete traversals over both operand bitmaps. First, it calls popcntAndSlice which computes the popcount of the bitwise AND of both slices, loading all 1024 elements of both slices, performing AND, and popcounting. Second, it does the exact same bitwise AND operations over all 1024 elements again to populate answer.bitmap or inside fillArrayAND. This redundant double-traversal scales directly with the number of bitmap containers and is run at a high cadence during parallel intersections, compounding CPU instruction overhead and memory bandwidth pressure under load.

Change to test: Use a local stack-allocated array (var temp [1024]uint64) to compute the bitwise AND once, then compute its popcount using popcntSlice. If the result is a bitmapContainer, copy temp to the answer; if it is an arrayContainer, populate the array from temp.

Where it lives

perfloop/roaring · parallel.go

Evidence

128-container dense parallel bitmap intersection on AVX2 dispatch · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 349132 310051 −11.3% (−39617) −44368 to −33057 < −17457 PASSED

Checks: 4 of 4 passed. Verification: no defect found.

Timeline