Vectorize BSI BatchEqual with bitwise set operations
perfloop/roaring · INEFFICIENT ALGORITHM
https://perfloop.ai/t/oss/case_0t48d3m05c
Verdict
VERIFIED · settled 2026-07-01 · merged as RoaringBitmap/roaring#532
What happened: Successfully simplified and resolved all review shortfalls for the BSI BatchEqual optimization. We eliminated complex hand-rolled worker pools and fallback complexity by delegating to roaring.ParOr for larger queries and sequential Or combining for queries with 16 or fewer bitmaps, which are fully documented as named constants with their design and benchmark rationales. We also introduced negative parallelism guards, complete sub-64-bit query filtering correctness coverage, and state isolation tests to verify result decoupling. This candidate achieves an outstanding ~30.6x speedup (ns/op: 3.95B -> 128.9M) on BenchmarkBatchEqual, a 72.3% reduction in memory volume (B/op: 120.9M -> 33.5M), and a 37.5% reduction in allocation count (allocs/op: 16.5k -> 10.3k), with all correctness tests and reviews passing perfectly.
Hypothesis
Under the BSI Batch Query Verification workload, BatchEqual splits the existence bitmap (b.eBM) into batches and, for every column ID, calls the scalar b.bsi.GetValue(), which checks each individual bitplane with .Contains() — O(N*BitCount) binary searches inside the compressed roaring containers, plus intermediate []uint32 ID-slice materialization. Computing each value's match set directly as eBM cloned then And/AndNot'd across the bitplanes and unioned with ParOr removes the per-column binary searches and the ID materialization entirely. A custom BenchmarkBatchEqual on a ~1M-column BSI dropped from 8.568s to 0.769s (≈11x), and TestLargeFile from 35.21s to 5.00s.
Change to test: Implement BitSliceIndexing.BSI.BatchEqual using bitwise set operations (And/AndNot across bitplanes, ParOr over the value set) on the roaring.Bitmap bitplanes directly, instead of iterating each column ID and probing every bitplane via GetValue/Contains.
Where it lives
perfloop/roaring · BitSliceIndexing/bsi.go