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-11-07 · 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

Bitmap overlap GCC 14 -O3 · 29 sample pairs

metric	baseline	candidate	paired median change	confidence range	required	result
`cpu_ns/query`	`728.6`	`653.3`	`−10.3% (−75.38)`	`−90.45 to −45.23`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`tiny_cpu_ns/query`	`16.96`	`9.108`	`−46.3% (−7.852)`	`−8.794 to −7.538`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`cutoff_cpu_ns/query`	`18.84`	`10.05`	`−53.3% (−10.05)`	`−10.05 to −8.794`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`mid_skip_cpu_ns/query`	`28.89`	`15.08`	`−47.8% (−13.82)`	`−15.08 to −13.82`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`long_skip_cpu_ns/query`	`50.25`	`20.1`	`−60% (−30.15)`	`−30.15 to −28.89`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`balanced_cpu_ns/query`	`258.8`	`113.1`	`−56.3% (−145.7)`	`−150.8 to −143.2`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`wide_left_cpu_ns/query`	`153.3`	`30.15`	`−80.3% (−123.1)`	`−130.7 to −120.6`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`wide_right_cpu_ns/query`	`148.2`	`32.66`	`−78% (−115.6)`	`−120.6 to −113.1`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`immediate_cpu_ns/query`	`7.224`	`5.967`	`−17.4% (−1.256)`	`−1.256 to −0.6281`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`early20_ns/query`	`5.346`	`3.526`	`−34.2% (−1.827)`	`−1.988 to −1.711`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`few3_ns/query`	`5.224`	`3.457`	`−33.6% (−1.758)`	`−2.047 to −1.444`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`periodic_skip1_ns/query`	`4546`	`2683`	`−40.9% (−1858)`	`−1976 to −1741`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip2_ns/query`	`5554`	`3526`	`−36.2% (−2012)`	`−2214 to −1635`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip3_ns/query`	`4923`	`3661`	`−25.7% (−1267)`	`−1313 to −1129`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip4_ns/query`	`5249`	`3323`	`−36.7% (−1927)`	`−2148 to −1729`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip5_ns/query`	`4163`	`3058`	`−26.5% (−1105)`	`−1330 to −975.8`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`constructed_rand3_ns/query`	`5.068`	`3.601`	`−29.3% (−1.483)`	`−2.418 to −1.388`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`constructed_rand20_ns/query`	`4.987`	`3.685`	`−26.2% (−1.305)`	`−1.466 to −1.158`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`constructed_rand200_ns/query`	`4.48`	`3.427`	`−23.7% (−1.064)`	`−1.212 to −0.9257`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit1_ns/query`	`4.471`	`2.979`	`−33.4% (−1.493)`	`−1.791 to −1.256`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit2_ns/query`	`6.362`	`3.448`	`−46% (−2.929)`	`−3.236 to −2.822`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit3_ns/query`	`8.284`	`3.878`	`−53.1% (−4.396)`	`−4.565 to −4.182`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit4_ns/query`	`9.529`	`3.93`	`−58.6% (−5.586)`	`−5.708 to −5.479`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit5_ns/query`	`12.09`	`4.359`	`−63.5% (−7.685)`	`−7.889 to −7.231`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit6_ns/query`	`13.27`	`5.439`	`−58.7% (−7.783)`	`−9.034 to −7.563`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit7_ns/query`	`15.01`	`5.379`	`−64.3% (−9.649)`	`−10.19 to −8.926`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit8_ns/query`	`16.09`	`5.857`	`−63.2% (−10.17)`	`−11.06 to −9.685`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit9_ns/query`	`18.13`	`6.669`	`−62.7% (−11.37)`	`−12.32 to −10.76`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit10_ns/query`	`19.21`	`6.775`	`−64.6% (−12.4)`	`−14.13 to −11.94`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`interleave100_ns/query`	`410`	`172.5`	`−58% (−237.8)`	`−246.9 to −233.4`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`interleave2000_ns/query`	`8054`	`3358`	`−58.5% (−4711)`	`−4949 to −4619`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`prefix4000_ns/query`	`4467`	`30.67`	`−99.3% (−4436)`	`−4599 to −4344`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`skew4000_4_ns/query`	`4299`	`47.19`	`−98.8% (−4248)`	`−4486 to −4161`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`long_tiny_ns/query`	`5.21`	`3.765`	`−28.2% (−1.47)`	`−1.531 to −1.262`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`native_weather_ns/query`	`725.3`	`668.7`	`−7.5% (−54.73)`	`−74.32 to −33.06`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`full_left_ns/query`	`6.147`	`6.102`	`−0.04211`	`−1.267 to +0.9328`	`loss ≤ stated 0.5 × \|baseline median\|`	`PASSED`
`full_right_ns/query`	`6.596`	`6.097`	`−7.5% (−0.4949)`	`−0.6124 to −0.3877`	`loss ≤ stated 0.5 × \|baseline median\|`	`PASSED`
`full_full_ns/query`	`6.132`	`6.094`	`−0.04033`	`−0.1071 to +0.6688`	`loss ≤ stated 0.5 × \|baseline median\|`	`PASSED`

Bitmap overlap GCC 12 -O2 · 34 sample pairs

metric	baseline	candidate	paired median change	confidence range	required	result
`cpu_ns/query`	`663.3`	`665.8`	`+5.025`	`−15.08 to +20.1`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`tiny_cpu_ns/query`	`11.62`	`10.05`	`−16.2% (−1.884)`	`−2.827 to −1.57`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`cutoff_cpu_ns/query`	`13.82`	`11.31`	`−18.2% (−2.513)`	`−5.025 to −1.256`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`mid_skip_cpu_ns/query`	`18.84`	`17.59`	`−6.7% (−1.256)`	`−3.769 to −1.256`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`long_skip_cpu_ns/query`	`33.92`	`23.24`	`−33.3% (−11.31)`	`−13.82 to −7.538`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`balanced_cpu_ns/query`	`119.3`	`114.3`	`−4.2% (−5.025)`	`−8.794 to −2.513`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`wide_left_cpu_ns/query`	`110.6`	`32.66`	`−70.5% (−77.89)`	`−80.4 to −77.89`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`wide_right_cpu_ns/query`	`148.2`	`32.66`	`−78% (−115.6)`	`−118.1 to −113.1`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`immediate_cpu_ns/query`	`6.595`	`5.653`	`−14.3% (−0.9422)`	`−1.57 to −0.6281`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`early20_ns/query`	`4.639`	`4.043`	`−12.9% (−0.6)`	`−0.6497 to −0.5483`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`few3_ns/query`	`4.514`	`3.832`	`−15.1% (−0.681)`	`−0.881 to −0.5516`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`periodic_skip1_ns/query`	`2900`	`2776`	`−4.3% (−125.9)`	`−226.6 to −89.05`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip2_ns/query`	`3993`	`3757`	`−6.1% (−244.7)`	`−287 to −180.5`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip3_ns/query`	`3672`	`3670`	`+30.24`	`−78.69 to +100.6`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip4_ns/query`	`3520`	`3430`	`−3% (−106.8)`	`−177.6 to −19.97`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip5_ns/query`	`3568`	`2955`	`−17.2% (−614.3)`	`−695.3 to −582.4`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`constructed_rand3_ns/query`	`4.867`	`4.399`	`−9.7% (−0.4717)`	`−0.5982 to −0.3192`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`constructed_rand20_ns/query`	`4.79`	`4.371`	`−8.8% (−0.422)`	`−0.5498 to −0.3425`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`constructed_rand200_ns/query`	`4.408`	`4.05`	`−8.3% (−0.3664)`	`−0.499 to −0.265`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit1_ns/query`	`4.316`	`3.762`	`−12.5% (−0.539)`	`−0.6054 to −0.3481`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit2_ns/query`	`5.322`	`5.017`	`−5.9% (−0.3147)`	`−0.4344 to −0.2615`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit3_ns/query`	`6.135`	`5.6`	`−8.6% (−0.5275)`	`−0.643 to −0.3769`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit4_ns/query`	`6.846`	`5.811`	`−15.1% (−1.037)`	`−1.458 to −0.9009`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit5_ns/query`	`7.521`	`6.045`	`−19.6% (−1.476)`	`−1.626 to −1.4`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit6_ns/query`	`8.23`	`6.637`	`−19.6% (−1.614)`	`−1.776 to −1.518`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit7_ns/query`	`9.152`	`7.268`	`−20.9% (−1.908)`	`−1.977 to −1.8`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit8_ns/query`	`9.929`	`8.096`	`−18.6% (−1.847)`	`−1.981 to −1.618`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit9_ns/query`	`10.79`	`8.829`	`−18.3% (−1.979)`	`−2.158 to −1.853`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit10_ns/query`	`11.7`	`9.23`	`−21.4% (−2.505)`	`−2.674 to −2.398`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`interleave100_ns/query`	`198.8`	`177`	`−11.1% (−22.09)`	`−29.71 to −20.31`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`interleave2000_ns/query`	`3733`	`3373`	`−9.8% (−367.2)`	`−429.5 to −320.5`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`prefix4000_ns/query`	`3747`	`32.06`	`−99.1% (−3715)`	`−3802 to −3688`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`skew4000_4_ns/query`	`3706`	`48.81`	`−98.7% (−3657)`	`−3742 to −3644`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`long_tiny_ns/query`	`4.789`	`4.106`	`−13.9% (−0.6654)`	`−0.7855 to −0.5972`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`native_weather_ns/query`	`665.7`	`681.3`	`+15.62`	`−1.644 to +29.19`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`full_left_ns/query`	`6.05`	`6.098`	`+0.03195`	`−1.184 to +0.795`	`loss ≤ stated 0.5 × \|baseline median\|`	`PASSED`
`full_right_ns/query`	`6.089`	`6.093`	`−0.007514`	`−0.09172 to +0.2126`	`loss ≤ stated 0.5 × \|baseline median\|`	`PASSED`
`full_full_ns/query`	`6.076`	`6.042`	`−0.03308`	`−0.4075 to +0.09763`	`loss ≤ stated 0.5 × \|baseline median\|`	`PASSED`

Bitmap overlap GCC 12 -O3 · 29 sample pairs

metric	baseline	candidate	paired median change	confidence range	required	result
`cpu_ns/query`	`678.4`	`678.4`	`−5.025`	`−30.15 to +25.13`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`tiny_cpu_ns/query`	`12.56`	`8.794`	`−30% (−3.769)`	`−4.711 to −3.455`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`cutoff_cpu_ns/query`	`13.82`	`10.05`	`−27.3% (−3.769)`	`−6.281 to −2.513`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`mid_skip_cpu_ns/query`	`18.84`	`13.82`	`−33.3% (−6.281)`	`−8.794 to −5.025`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`long_skip_cpu_ns/query`	`37.69`	`21.36`	`−46.7% (−17.59)`	`−23.87 to −10.05`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`balanced_cpu_ns/query`	`164.6`	`108`	`−33.6% (−55.28)`	`−62.81 to −50.25`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`wide_left_cpu_ns/query`	`110.6`	`30.15`	`−72.7% (−80.4)`	`−87.94 to −77.89`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`wide_right_cpu_ns/query`	`148.2`	`32.66`	`−78% (−115.6)`	`−123.1 to −113.1`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`immediate_cpu_ns/query`	`6.91`	`5.653`	`−18.2% (−1.256)`	`−1.57 to −0.9422`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`early20_ns/query`	`6.136`	`3.925`	`−36.2% (−2.219)`	`−2.865 to −1.958`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`few3_ns/query`	`6.032`	`3.721`	`−38.3% (−2.311)`	`−3.48 to −1.9`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`periodic_skip1_ns/query`	`3995`	`2837`	`−28.6% (−1143)`	`−1286 to −1000`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip2_ns/query`	`4803`	`3916`	`−18.6% (−894.7)`	`−1076 to −646.5`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip3_ns/query`	`3974`	`3824`	`−140.9`	`−305.4 to +63.04`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip4_ns/query`	`3690`	`3537`	`−4.2% (−153.7)`	`−506.8 to −9.231`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip5_ns/query`	`3520`	`3067`	`−12.6% (−441.8)`	`−702.1 to −295`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`constructed_rand3_ns/query`	`5.625`	`3.828`	`−32% (−1.798)`	`−1.923 to −1.672`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`constructed_rand20_ns/query`	`5.574`	`3.816`	`−31.1% (−1.736)`	`−1.831 to −1.287`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`constructed_rand200_ns/query`	`5.059`	`3.619`	`−28.8% (−1.455)`	`−1.518 to −1.358`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit1_ns/query`	`5.239`	`3.359`	`−35.3% (−1.852)`	`−2.192 to −1.692`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit2_ns/query`	`6.396`	`3.535`	`−45.1% (−2.886)`	`−3.213 to −2.789`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit3_ns/query`	`7.747`	`3.972`	`−48.6% (−3.766)`	`−3.988 to −3.551`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit4_ns/query`	`8.939`	`3.98`	`−55.3% (−4.941)`	`−5.406 to −4.442`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit5_ns/query`	`10.79`	`5.078`	`−52.8% (−5.699)`	`−6.025 to −5.109`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit6_ns/query`	`11.96`	`5.199`	`−56.6% (−6.766)`	`−6.932 to −6.595`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit7_ns/query`	`13.28`	`5.561`	`−58% (−7.706)`	`−8.082 to −7.336`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit8_ns/query`	`14.43`	`6.096`	`−57.8% (−8.342)`	`−8.576 to −8.131`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit9_ns/query`	`15.37`	`7.198`	`−53.1% (−8.153)`	`−8.494 to −7.645`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit10_ns/query`	`16.94`	`6.807`	`−59.6% (−10.1)`	`−10.46 to −8.387`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`interleave100_ns/query`	`262.1`	`175.4`	`−33% (−86.39)`	`−91.74 to −56.43`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`interleave2000_ns/query`	`5082`	`3392`	`−33.2% (−1687)`	`−1898 to −1598`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`prefix4000_ns/query`	`3918`	`30.67`	`−99.2% (−3887)`	`−5069 to −3709`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`skew4000_4_ns/query`	`3744`	`47.09`	`−98.7% (−3697)`	`−4522 to −3651`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`long_tiny_ns/query`	`5.883`	`3.894`	`−33.8% (−1.988)`	`−2.385 to −1.762`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`native_weather_ns/query`	`650.1`	`644.4`	`−5.321`	`−36.73 to +19.31`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`full_left_ns/query`	`6.508`	`6.408`	`−0.03275`	`−1.277 to +0.8531`	`loss ≤ stated 0.5 × \|baseline median\|`	`PASSED`
`full_right_ns/query`	`6.269`	`6.394`	`+0.1303`	`−0.3969 to +0.8855`	`loss ≤ stated 0.5 × \|baseline median\|`	`PASSED`
`full_full_ns/query`	`6.342`	`6.383`	`+0.03086`	`−0.4252 to +2.08`	`loss ≤ stated 0.5 × \|baseline median\|`	`PASSED`

Bitmap overlap GCC 14 -O2 · 45 sample pairs

metric	baseline	candidate	paired median change	confidence range	required	result
`cpu_ns/query`	`763.8`	`688.4`	`−9.2% (−70.35)`	`−85.43 to −50.25`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`tiny_cpu_ns/query`	`15.08`	`10.68`	`−29.2% (−4.397)`	`−5.025 to −4.083`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`cutoff_cpu_ns/query`	`16.33`	`11.31`	`−30.8% (−5.025)`	`−6.281 to −3.769`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`mid_skip_cpu_ns/query`	`23.87`	`17.59`	`−26.3% (−6.281)`	`−7.538 to −5.025`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`long_skip_cpu_ns/query`	`38.94`	`22.61`	`−41.9% (−16.33)`	`−18.84 to −16.33`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`balanced_cpu_ns/query`	`233.7`	`134.4`	`−43% (−100.5)`	`−104.3 to −95.48`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`wide_left_cpu_ns/query`	`133.2`	`32.66`	`−77.4% (−103)`	`−105.5 to −97.99`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`wide_right_cpu_ns/query`	`145.7`	`32.66`	`−77.6% (−113.1)`	`−115.6 to −110.6`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`immediate_cpu_ns/query`	`7.224`	`6.281`	`−13% (−0.9422)`	`−1.256 to −0.6281`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`early20_ns/query`	`5.542`	`4.776`	`−13.2% (−0.7303)`	`−0.8639 to −0.5808`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`few3_ns/query`	`5.509`	`4.72`	`−13.6% (−0.747)`	`−1.016 to −0.4757`	`loss ≤ stated 0.2 × \|baseline median\|`	`PASSED`
`periodic_skip1_ns/query`	`4365`	`3102`	`−29% (−1267)`	`−1361 to −1213`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip2_ns/query`	`4804`	`4103`	`−14.4% (−691.3)`	`−807.9 to −637`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip3_ns/query`	`4708`	`4090`	`−13% (−611)`	`−701.8 to −546.6`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip4_ns/query`	`4177`	`3675`	`−11.4% (−476.2)`	`−643.4 to −315.7`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`periodic_skip5_ns/query`	`4035`	`3419`	`−15.2% (−614.1)`	`−728.8 to −501.3`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`constructed_rand3_ns/query`	`5.218`	`4.737`	`−8.9% (−0.4624)`	`−0.5842 to −0.2865`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`constructed_rand20_ns/query`	`5.012`	`4.741`	`−5.2% (−0.2596)`	`−0.3722 to −0.1156`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`constructed_rand200_ns/query`	`4.543`	`4.456`	`−0.0898`	`−0.1719 to +0.01941`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit1_ns/query`	`4.43`	`4.353`	`−0.08808`	`−0.2607 to +0.01185`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit2_ns/query`	`6.284`	`5.461`	`−13.2% (−0.8304)`	`−0.9734 to −0.7415`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit3_ns/query`	`8.015`	`5.899`	`−26.3% (−2.108)`	`−2.303 to −1.99`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit4_ns/query`	`9.418`	`6.394`	`−32.1% (−3.023)`	`−3.126 to −2.928`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit5_ns/query`	`12.01`	`7.206`	`−40% (−4.8)`	`−5.888 to −4.169`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit6_ns/query`	`13.12`	`8.532`	`−35.3% (−4.629)`	`−5.453 to −4.336`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit7_ns/query`	`16.23`	`9.066`	`−44.5% (−7.22)`	`−8.03 to −6.493`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit8_ns/query`	`17.52`	`9.528`	`−45% (−7.88)`	`−8.473 to −7.257`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit9_ns/query`	`19.84`	`10.23`	`−48.7% (−9.666)`	`−10.15 to −8.865`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`alternating_hit10_ns/query`	`21.29`	`11.25`	`−47.1% (−10.03)`	`−10.31 to −9.521`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`interleave100_ns/query`	`294.6`	`198`	`−33.7% (−99.4)`	`−133 to −79.89`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`interleave2000_ns/query`	`6448`	`4005`	`−36.3% (−2341)`	`−2789 to −1522`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`prefix4000_ns/query`	`4038`	`32.08`	`−99.2% (−4006)`	`−4097 to −3980`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`skew4000_4_ns/query`	`3997`	`48.69`	`−98.8% (−3948)`	`−3999 to −3922`	`gain > 0; gain > 0.05 × \|baseline median\|; arm medians separated`	`PASSED`
`long_tiny_ns/query`	`5.019`	`4.681`	`−6.7% (−0.3384)`	`−0.4504 to −0.2067`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`native_weather_ns/query`	`738.7`	`681.9`	`−7.8% (−57.64)`	`−66.53 to −40.97`	`loss ≤ 0.05 × \|baseline median\|`	`PASSED`
`full_left_ns/query`	`5.997`	`7.121`	`+17.2% (+1.03)`	`+0.4036 to +1.379`	`loss ≤ stated 0.5 × \|baseline median\|`	`PASSED`
`full_right_ns/query`	`6.422`	`6.95`	`+7.8% (+0.498)`	`+0.3432 to +0.7827`	`loss ≤ stated 0.5 × \|baseline median\|`	`PASSED`
`full_full_ns/query`	`5.969`	`6.923`	`+15.6% (+0.9306)`	`+0.6598 to +1.175`	`loss ≤ stated 0.5 × \|baseline median\|`	`PASSED`

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

Timeline

2026-10-22 · Case opened
2026-10-23 · PR opened
2026-11-07 · Case closed
2026-11-07 · Case closed