Defer RunOptimize until after bitmap population in batchEqual
perfloop/roaring · INEFFICIENT ALGORITHM
https://perfloop.ai/t/oss/case_q4eynnf09a
Verdict
VERIFIED · settled 2026-08-04 · merged as RoaringBitmap/roaring#539
What happened: The paired measurements met the required improvement.
Hypothesis
In BitSliceIndexing.batchEqual, 'results.RunOptimize()' is called immediately after 'roaring.NewBitmap()' is created and before any elements have been added in the loop. In the roaring bitmap library, RunOptimize compresses existing consecutive runs of elements within the bitmap's containers; it does not set a persistent flag that automatically compresses subsequently added elements on the fly. As a result, calling RunOptimize on an empty bitmap is a redundant operation that achieves no compression for the populated results. Moving this check to the end of the function (after the loop is finished) ensures the returned bitmap is properly run-optimized, and avoids redundant execution overhead on empty structures. This same pattern is replicated in compareValue, transpose, and transposeWithCounts.
Change to test: Move the run-optimization check 'if e.bsi.runOptimized { results.RunOptimize() }' in BitSliceIndexing.batchEqual (and similarly in compareValue, transpose, and transposeWithCounts) from the beginning of the function to the end, after the population loop has completed.
Where it lives
perfloop/roaring · BitSliceIndexing/bsi.go
Evidence
CompareValue result serialization, 50k contiguous matches, 4 workers · 10 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
2601 |
187.2 |
−92.8% (−2414) |
−2535 to −2359 |
< 0 |
PASSED |
B/op |
9600 |
136 |
−98.6% (−9464) |
−9464 to −9464 |
< 0 |
PASSED |
allocs/op |
4 |
4 |
0 |
0 to 0 |
≤ 0 |
PASSED |
CompareValue end-to-end, 50k contiguous matches, 4 workers · 10 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
844083 |
782418 |
−7.3% (−61920) |
−73717 to −33202 |
≤ 150000 |
PASSED |
BatchEqual end-to-end, 50k contiguous matches, trie path · 10 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
402.7 |
404.1 |
0 |
−4.8 to +4.3 |
≤ 100 |
PASSED |
Checks: 8 of 8 passed. Verification: no defect found.