Set-based bitmap operations for BSI CompareValue

perfloop/roaring · INEFFICIENT ALGORITHM

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

Verdict

VERIFIED · settled 2026-08-12

Hypothesis

We appended a custom benchmark BenchmarkCompareValue on setupLargeBSI and ran it with profiling. The benchmark showed that CompareValue takes ~5.8s per call and allocates ~115MB of heap memory. CPU profiling showed 40.1% of time spent in roaring.(*roaringArray).binarySearch and 5.5% in roaring.(*Bitmap).Contains, which is driven by compareValue performing pointwise Contains checks inside a nested loop over bits and elements. Memory profiling attributed 59% (426MB) of allocations to parallelExecutor making batch slices ([]uint32) to extract and hold all IDs from the roaring bitmap. Transitioning to set-based bitmap operations removes the loop-carried binary searches and intermediate slice allocations entirely.

Change to test: Implement CompareValue using set-based roaring bitmap operations (AND, OR, ANDNOT) across the bit slices rather than pointwise Contains() checks inside a nested loop over a temporary slice of extracted IDs.

Where it lives

perfloop/roaring · BitSliceIndexing/bsi.go

Evidence

run-optimized equality query over 50,000 contiguous IDs · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 680861 211.5 −100% (−680648) −730626 to −644905 < 0 PASSED
B/op 371693 144 −100% (−371549) −371554 to −371543 < 0 PASSED
allocs/op 104 6 −94.2% (−98) −98 to −98 < 0 PASSED

large age-fixture range query from 40 through 70 · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 1273826977 138180249 −89.2% (−1135639407) −1172953585 to −1115449793 < 0 PASSED
B/op 157471304 60321105 −61.7% (−97150192) −97158253 to −94890270 < 0 PASSED
allocs/op 23630 20378 −13.8% (−3252) −3254 to −2698 < 0 PASSED

singleton found-set signed less-than miss over 50,000 rows · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 3635 837.4 −76.2% (−2768) −2870 to −2442 < 0 PASSED
B/op 1052 336 −68.1% (−716) −716 to −716 < 0 PASSED
allocs/op 18 8 −55.6% (−10) −10 to −10 < 0 PASSED

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

Timeline