Long bitmap overlap scans leave x86-64 SIMD unused

perfloop-oss/croaring · DATA PARALLEL GAP

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

Verdict

VERIFIED · settled 2026-10-22 · pull request opened as RoaringBitmap/CRoaring#916

What happened: The paired measurements met the required improvement.

Hypothesis

The public bitmap-overlap query scans balanced sparse arrays one value at a time, including on x86-64 with AVX2 available. A replay over the repository’s retained weather sets attributes 81.10% of sampled CPU to this scalar loop. Block comparisons may reduce query CPU, but no speedup has been measured. Confidence is medium.

The benefiting operation is `roaring_bitmap_intersect`, offered in `include/roaring/roaring.h:234-238`. README.md describes CRoaring as a library at line 10 and documents default x64 runtime dispatch at lines 94-98. At revision 5fce11dbf8f8227125a466ce895266967e708816, the ordinary entry at `src/roaring.c:3078-3107` compares matching high-16-bit keys and calls `container_intersect`. Its ARRAY/ARRAY arm reaches `array_container_intersect`, whose scalar branch handles pairs where neither cardinality exceeds 64 times the other (`src/containers/array.c:367-382`). Shared containers are unwrapped before dispatch. This is a normal representation route, not an error fallback. Consumer prevalence outside the retained workload is unknown.

The input evidence is independent of a synthetic worst-case generator. `benchmarks/realdata/README.md` describes its files as integer sets for bitmap testing. `tests/realdata_unit.c:23-37,365-377` constructs bitmaps from these sets and checks adjacent pairs; `benchmarks/numbersfromtextfiles.h:105-110` establishes alphabetical file ordering. A Python corpus-route check replaying early returns found 701 balanced-array calls across the 199 adjacent weather queries. Of these, 533 pairs had at least eight values on both sides and accounted for 622,794 of 633,513 simulated pointer advances. These are source-level traversal counts, not CPU measurements or evidence of production frequency. Endpoint-disjoint pairs accounted for only 15 advances, so a broader range-rejection shortcut does not remove the material work in this workload.

Receipt call_feUcApbjqBUFJLqgiGnPifYm ran the public API over all retained `weather_sept_85` sets for 5,000 adjacent-pair passes. It used default containers from `roaring_bitmap_of_ptr`, without run optimization or forced ISA flags, compiled with GCC at -O3. The constructor calls create/add-many without run optimization (`src/roaring.c:195-199`). The run completed its cardinality differential and before/after serialized-content-hash checks. The complete 100 Hz profile contains 10.69 sampled CPU seconds, including loading, validation and cleanup; `intersect_uint16_nonempty` owns 8.67 seconds. This is attributable baseline workload cost, not a measured saving. As an illustrative impact estimate, halving this loop’s CPU while leaving other work unchanged would save about 40.5% of this replay’s CPU. Partial eligibility and added dispatch overhead reduce that estimate.

For nonempty pairs with absent or late matches, the loop can advance through a linear number of input values. Equality returns immediately, so large cardinality alone does not force a long scan. The neighboring `intersect_vector16` at `src/array_util.c:385-459` already computes equality masks over unsigned-16-bit blocks and advances blocks using their maxima. The opcodex lookup confirms the existing `_mm_cmpestrm` primitive’s SSE4.2 mapping, and the profiling host reports that feature and AVX2. This establishes an available block operation, not its performance advantage. The proposal targets only x86-64 under the existing AVX2 gate and creates no consumer-visible operations or configuration.

The required Case proof is lower CPU per public overlap query on the unchanged, warm weather adjacent-pair replay, including dispatch and early exits. Reject the performance claim if savings appear only in a helper benchmark or the full replay does not improve. Sweep sizes and ratios on both sides of any introduced cutoff to identify the crossover. Tiny inputs and first-value matches are required regression controls because setup can outweigh their existing work. Correctness checks must compare with `roaring_bitmap_and_cardinality > 0`, preserve inputs, and cover empty sets, zero, 65535, block tails, absent/first/last matches, swapped inputs and shared COW containers. Other retained datasets and run-optimized bitmaps are optional additional samples; their savings are not established by this profile.

Change to test: Add an internal early-exit SIMD predicate for balanced array pairs on x86-64 through the existing AVX2 support gate, replacing per-value scanning without counting or materializing the intersection. Retain a cheap scalar route for tiny inputs, immediate matches and tails, preserving exact answers, bounded reads and unchanged inputs without adding public API.

Where it lives

perfloop-oss/croaring · src/roaring.c

Evidence

warm public overlap query replay · 9 sample pairs

metric baseline candidate paired median change confidence range required result
weather_process_cpu_ns_per_query 10432 3678 −64.6% (−6744) −6834 to −6633 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
tiny_process_cpu_ns_per_query 12.66 12.44 −3.3% (−0.42) −0.78 to +0.14 loss ≤ 0.05 × |baseline median| PASSED
first_match_process_cpu_ns_per_query 6.7 4.98 −26% (−1.74) −1.9 to −1.48 loss ≤ 0.05 × |baseline median| PASSED

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

Timeline