Decode dense bitmap containers with TrailingZeros64
perfloop/roaring · DATA PARALLEL GAP
https://perfloop.ai/t/oss/case_74j4gzmye2
Verdict
VERIFIED · settled 2026-07-12 · merged as RoaringBitmap/roaring#534
Hypothesis
The current dense bitmap-to-array materialization loop extracts every set bit by computing t := bitset & -bitset, then popcount(t-1), then bitset ^= t. The model-build eval catalog measured this exact site as a real win on dense bitmap decode. Bitmap.ToArray and many-iterator paths call fillLeastSignificant16bits for bitmap containers, so dense bitmap materialization pays this per-set-bit scalar decode cost on set-query and export workloads. The proof should benchmark dense bitmap decode and confirm the same values are emitted in the same order.
Change to test: Replace the isolate-lowest-bit plus popcount(t-1) decode loop in bitmapContainer.fillLeastSignificant16bits with bits.TrailingZeros64(bitset) and bitset &= bitset - 1, preserving output order while reducing per-set-bit scalar work.
Where it lives
perfloop/roaring · roaring.go
Evidence
This candidate optimizes the dense bitmap array materialization in bitmapContainer.fillLeastSignificant16bits using math/bits.TrailingZeros64 and bitset &= bitset-1, and adds a rigorous, upstream-facing differential property test verifying range correctness, boundary conditions, and return values. The assembly comments have been scoped specifically to the amd64 platform to address review feedback rev_632x5c0ga7. Co-measurement on linux/amd64 demonstrates a 30.10% reduction in execution time (41864.5 ns/op to 29265 ns/op) with high statistical significance (p < 1e-4), while keeping memory allocations at 0 B/op and 0 allocs/op.