Bitmap overlap walks long nonmatching run prefixes one at a time

perfloop-oss/croaring · INEFFICIENT ALGORITHM

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

Verdict

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

What happened: The paired measurements met the required improvement.

Hypothesis

The public bitmap-overlap query walks nonmatching runs—consecutive integer spans—one at a time. On a replay of retained, run-compressed weather sets, this routine accounts for 43.78% of sampled CPU. The possible saving from skipping long prefixes is unmeasured. Confidence is medium.

The benefiting library operation is `roaring_bitmap_intersect`, documented in `include/roaring/roaring.h:234-238`. At revision `5fce11dbf8f8227125a466ce895266967e708816`, its ordinary entry at `src/roaring.c:3078-3107` compares high-16-bit keys and calls `container_intersect` for each matching key reached before the first overlap. The dispatcher unwraps shared containers and sends RUN/RUN pairs to this routine (`include/roaring/containers/containers.h:864-879`). This is an ordinary representation route under documented run compression, not an error fallback. Consumer prevalence beyond the retained population is unknown.

The input conditions are evidenced independently of the probe. `benchmarks/realdata/README.md` describes retained integer sets for bitmap testing. `tests/realdata_unit.c:796-805` run-optimizes those sets, and lines 365-385 exercise adjacent-pair overlap queries. The replay uses all 200 `weather_sept_85_srt` sets in the alphabetical order supplied by `benchmarks/numbersfromtextfiles.h:105-110`, with normal `roaring_bitmap_of_ptr` construction followed by `roaring_bitmap_run_optimize`. README.md:219-220 documents this compression step, and lines 600-602 recommend it for large data volumes. The direction is architecture-independent and creates no new operations, types, configuration or serialization format.

The retained workload's one-pass route check observed 205 RUN/RUN calls across 199 public queries: 13 full-container shortcuts, 52 nonfull matches and 140 nonfull misses. Nonfull calls made 26,069 pointer advances, with lists reaching 1,485 runs. Of these advances, 14,263 occurred in consecutive same-side groups of at least eight, and 11,839 in groups of at least 32. These are traversal counts, not CPU measurements. A broader endpoint-disjoint shortcut covers 27 calls but only 56 advances here, so it does not remove the material internal-prefix work.

Each failed comparison at `src/containers/run.c:555-567` advances exactly one cursor. A group of g losing runs therefore takes g advances even when the opposite cursor does not move. Valid run endpoints are strictly ordered: `run_container_validate` at lines 671-718 rejects empty, overlapping, adjacent-unmerged and out-of-range runs. Every run whose end is no later than the opposing start is excluded from overlap. An absent pair can require work linear in the two run counts; successful calls stop at their first match and need not scan long lists. Full-container calls already have a constant-time shortcut. The public entry already uses ordered advancement for unmatched high keys, locating the remaining mechanism inside the run predicate.

Receipt `call_SnKwVkX4fW1MhfRjDNQ2arFL` ran 50,000 passes, or 9,950,000 public queries, compiled with GCC at -O3 without forced ISA flags. Its complete 100 Hz native profile contains 7.88 sampled CPU seconds, including setup and checks. `run_container_intersect` owns 3.39 seconds directly and 3.45 seconds including inlined work; the heavy frames are in the scan at lines 555-566. It is the largest single cost in this replay. The receipt workload's separate one-pass rerun completed the cardinality differential and before/after serialized-content-hash checks. Illustratively, halving the routine's CPU while leaving other work unchanged would save about 21.9% of whole-replay CPU. Partial eligibility and search overhead reduce that estimate. Neither a replacement speedup nor production frequency was measured.

The required Case proof is lower CPU per full public overlap query on the unchanged, warm, run-optimized weather adjacent-pair replay, including dispatch and early returns. Reject the performance claim if improvement exists only in a helper benchmark or the full replay does not improve. Sweep run counts, ratios and skip distances on both sides of any introduced cutoff; tiny lists and immediate matches are regression risks because search setup can exceed their current work. Differentially compare with `roaring_bitmap_and_cardinality > 0` and preserve input contents. Include portable-deserialized retained sets, shared COW containers, empty and full bitmaps, 0 and 65535, adjacent nonoverlapping runs, one-value overlaps, absent/first/last matches and swapped operands. Other retained datasets are optional additional samples, not established beneficiaries of this profile.

Change to test: Use adaptive exponential-plus-binary forward search to skip long prefixes of runs ending before the opposing run starts, instead of advancing through each run. Retain cheap scalar handling for short prefixes and immediate matches, preserving exact overlap answers, bounded reads and unchanged inputs without adding public API.

Where it lives

perfloop-oss/croaring · src/roaring.c

Evidence

warm weather overlap replay with cutoff-shape guards · 9 sample pairs

metric baseline candidate paired median change confidence range required result
cpu_ns/query 759.8 711.6 −6.3% (−48.24) −52.26 to −45.23 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
tiny_cpu_ns/query 14.45 9.673 −32.6% (−4.711) −4.962 to −4.334 loss ≤ 0.05 × |baseline median| PASSED
cutoff_cpu_ns/query 16.58 11.06 −33.3% (−5.528) −5.779 to −5.025 loss ≤ 0.05 × |baseline median| PASSED
mid_skip_cpu_ns/query 22.11 15.08 −31.8% (−7.035) −8.04 to −6.533 loss ≤ 0.05 × |baseline median| PASSED
long_skip_cpu_ns/query 35.68 21.86 −38.7% (−13.82) −14.32 to −13.57 loss ≤ 0.05 × |baseline median| PASSED
balanced_cpu_ns/query 169.6 166.3 −2.1% (−3.518) −5.025 to −2.513 loss ≤ 0.05 × |baseline median| PASSED
wide_left_cpu_ns/query 138.2 28.64 −79.6% (−110.1) −112.6 to −108.5 loss ≤ 0.05 × |baseline median| PASSED
wide_right_cpu_ns/query 169.3 30.15 −82.5% (−139.7) −142.2 to −137.7 loss ≤ 0.05 × |baseline median| PASSED
immediate_cpu_ns/query 6.91 6.91 0 −0.1256 to +0.06281 loss ≤ 0.05 × |baseline median| PASSED

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

Timeline