Scalar XOR write loop after cardinality count

perfloop/roaring · DATA PARALLEL GAP

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

Verdict

VERIFIED · settled 2026-08-27

What happened: The paired measurements met the required improvement.

Hypothesis

I ran the repository's `BenchmarkXorDense` through a compiled test binary with a 1 s CPU profile on the supplied amd64 host. It measured 65,210 ns/op and 0 B/op; `pprof -list` put 630 ms flat on the high-cardinality loop at lines 941–942, 450 ms on its XOR assignment, and 420 ms in the AVX2 `popcntXorSlice` call during a 2 s sample. A `go tool objdump` check showed the write loop as a 64-bit load/XOR/store sequence per iteration rather than a widened store loop.

`Bitmap.Xor` calls `ixor` once for each matching high key, and this target is selected only when both containers are bitmaps. A bitmap container holds 1,024 `uint64` words; when XOR cardinality exceeds 4,096, `ixorBitmap` first computes cardinality from both inputs and then recomputes each word to store it. `BenchmarkXorDense` constructs 50 matching dense chunks, so its cadence is up to 50 of these 1,024-word writes per `Xor`; the profile confirms its sampled run reached this branch. This is a medium-confidence candidate: the source and check show scalar work on this path, but they do not establish a production speedup or density distribution.

The delta would replace only the post-count, high-cardinality scalar write traversal with a bulk XOR-and-store backend, leaving the count, threshold, and array materialization semantics intact. A case session should benchmark identical bitmap pairs with outputs above and below 4,096 while sweeping 1, 50, and realistic matching-key counts, then compare ns/op, cycles or line-level CPU samples, and exact bitmap results including copy-on-write aliases. Confirm the finding only if the replacement lowers the lines-941–942 CPU share without shifting a regression to the scalar fallback or array-conversion path.

Change to test: Replace the high-cardinality scalar XOR loop with a bulk XOR-and-store helper that has architecture-specific wide implementations and a portable fallback. Preserve the existing cardinality calculation and low-cardinality array path.

Where it lives

perfloop/roaring · roaring.go

Evidence

Bitmap.Xor on 50 dense matching containers with AVX-512 disabled · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 45113 20500 −55.1% (−24847) −25947 to −22358 < −2256 PASSED
B/op 0 0 0 0 to 0 ≤ 0 PASSED
allocs/op 0 0 0 0 to 0 ≤ 0 PASSED

Out-of-place Xor on 64 dense containers with AVX-512 disabled · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 242037 214687 −10.9% (−26294) −41916 to −17892 ≤ 0 PASSED
B/op 528947 528947 −0.5 −1 to +1 ≤ 1 PASSED
allocs/op 145 145 0 0 to 0 ≤ 0 PASSED

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

Timeline