BCE, loop unrolling, and redundant copy elimination in lazyIORBitmap and lazyORBitmap
perfloop/roaring · DATA PARALLEL GAP
https://perfloop.ai/t/oss/case_gh0svmf28c
Verdict
VERIFIED · settled 2026-08-04 · merged as RoaringBitmap/roaring#542
What happened: All 5 declared checks passed.
Hypothesis
In bitmapcontainer.go, lazyIORBitmap performs an element-by-element bitwise OR on slices of length 1024. Because the Go compiler cannot guarantee that the second operand's slice is large enough, it likely inserts a bounds check on value2.bitmap[k] in every loop iteration. Adding a BCE hint (_ = answer.bitmap[1023]; _ = value2.bitmap[1023]) and unrolling the loop by 4 is hypothesized to unlock compiler instruction-level parallelism and potentially enable vectorization. In addition, its caller lazyORBitmap clones the receiver container, copying 1024 elements (8 KB of memory) into a new slice, only for lazyIORBitmap to immediately overwrite those elements in a second pass. Allocating a new container and performing the bitwise OR directly in one pass is hypothesized to avoid this redundant copy. Proof Target: To prove this, a case session can measure end-to-end CPU latency and memory allocation bytes with a Go benchmark that runs ParOr or lazyOR over bitmapContainers. We can also verify bounds check elimination statically using go build -gcflags='-d=ssa/check_bce/debug=1' on bitmapcontainer.go.
Change to test: Introduce a bounds check elimination (BCE) hint (e.g. asserting len of both bitmaps >= 1024) and unroll the loop by 4 in lazyIORBitmap. For lazyORBitmap, avoid cloning the receiver beforehand; instead, allocate a new bitmapContainer using newBitmapContainer() and compute the bitwise OR directly in a single pass.
Where it lives
perfloop/roaring · parallel.go
Evidence
ParOr over four dense bitmaps with 64 aligned bitmap containers and four workers · 10 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
370418 |
302755 |
−15.3% (−56581) |
−93983 to −41428 |
< 0 |
PASSED |
B/op |
532102 |
532097 |
−2 |
−10 to 0 |
≤ 8 |
PASSED |
allocs/op |
234 |
234 |
0 |
0 to 0 |
≤ 0 |
PASSED |
Checks: 5 of 5 passed. Verification: no defect found.