Make the scattered BatchEqual scan fallback no slower than the trie it replaced

perfloop-oss/roaring · INEFFICIENT ALGORITHM

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

Verdict

VERIFIED · settled 2026-11-04 · pull request opened as RoaringBitmap/roaring#589

What happened: The paired measurements met the required improvement.

Hypothesis

Scattered-value BatchEqual queries can switch from a trie, which shares bitmap work across query values, to a scan of every existing column. The submitter reports that this fallback reduced memory but made queries slower. The requested outcome is to retain the memory bound without the reported latency regression; its current cost and any consumer impact remain unmeasured here.

The subject is parallelBatchEqualScan at BitSliceIndexing/bsi.go:771-824, already reached by the supported BSI.BatchEqual operation on path_rt6669hppk through hop_tp9shez70p. BatchEqual calls it at line 712 when there are at least 128 distinct representable query values and shouldUseParallelScan holds (BitSliceIndexing/bsi.go:684-724). That guard requires an estimated branch count of at least 64 and at least 100,000 existing columns (lines 731-733). The scan materializes all existing column IDs into dense []uint32 worker batches, reconstructs each column's value with GetValue, and tests membership in the query-value set (lines 771-824). GetValue checks existence and probes each value bit plane (lines 137-149). Cardinality, bit-plane width, and query distribution therefore matter; source alone does not establish which work dominates elapsed time.

The submitter attributes the regression to upstream PR #533, merged as 7900bdcab8fb, and reports that it is still present here. They report that, on 2 cores, the PR's BenchmarkBatchEqualM128Scattered on the testdata/age fixture went from 799 ms to 2,506 ms against base 873a1e356cf5, with all 4/4 interleaved pairs slower, although the PR claimed equal speed. They report that memory fell 44-72%. They also report a 300,000-column index showing +133% elapsed time with 200 values and +286% with 1,000 values, with p=0.000, and about 156 MB/op for the dense column-ID materialization. These are attributed, unconfirmed measurements for the Case to check, not results obtained in this run.

The proof must retain the complete requested comparison: interleaved pairs on M128Scattered, M128, M200 and a wide index, at 2 cores and at default parallelism, plus result comparisons with the trie on random queries. Existing benchmark entries are at BitSliceIndexing/bsi_benchmark_test.go:274-292; setupLargeBSI loads the checked-in age fixture at BitSliceIndexing/bsi_test.go:48-67. Record core availability and the BatchEqual worker argument separately: the scan maps nonpositive parallelism to runtime.NumCPU() (bsi.go:777-786), so a two-core execution limit does not by itself select two workers. Correctness comparisons should include the deserialized age fixture and its authoritative existence bitmap, not only freshly constructed indexes, as described by BitSliceIndexing/bsi_benchmark_test.go:235-269.

The smallest useful next check is an interleaved current-versus-pre-#533-trie pair for M128Scattered on the same age fixture under the reported two-core setting, checking the returned bitmap and collecting ns/op and B/op. Then complete the required workload and parallelism matrix, random-query differential, and memory-bound comparison. This shallow checkout lacks the historical objects for both reported comparison revisions, so the exact historical comparator must first be recovered or verified against upstream; their local absence does not refute the report. No benchmark or profile was run during anchoring.

Upstream https://github.com/RoaringBitmap/roaring/pull/533 confirms the merged fallback implementation and its stated latency-parity and memory-reduction goals. Its merge is 7900bdcab8fb280efad0b6473cb3eff7dc4e96fb; the maintainer's merging decision is at https://github.com/RoaringBitmap/roaring/pull/533#issuecomment-4937138255. That record establishes acceptance of #533, not independent confirmation of its performance claim or agreement on a follow-up design. Both current open-proposal pages were reviewed. Inspected hunks of open https://github.com/RoaringBitmap/roaring/pull/540 replace CompareValue's column-ID work, not this BatchEqual fallback. Inspected hunks of open https://github.com/RoaringBitmap/roaring/pull/553 optimize ManyIterator extraction while retaining materialized output IDs. Neither inspected implementation establishes the requested dual latency-and-memory outcome here. Other proposal bodies and unselected hunks were not exhaustively reviewed, and no linked GitHub issue was identified for #533; upstream coverage is therefore partial, not an upstream-clear assertion.

Change to test: Keep #533's memory bound on scattered IN-lists, but make the scan path at least as fast as the pre-#533 trie at 2 cores, for example by testing columns per container against the value set without materializing every column ID. Prove with interleaved pairs on M128Scattered, M128, M200 and a wide index, at 2 cores and at the default parallelism, and compare results with the trie on random queries.

Where it lives

perfloop-oss/roaring · BitSliceIndexing/bsi.go

Evidence

BatchEqual AgeRandom p2-w2 vs trie · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 562178282 395727720 −28.8% (−161734940) −206965020 to −112489206 loss ≤ min(0, 0.05 × |baseline median|) PASSED
B/op 229682320 46243264 −79.9% (−183439072) −183439616 to −183438960 gain > 0; gain > 0.05 × |baseline median|; arm medians separated; base median within 78000000 to 312000000 PASSED

BatchEqual AgeRandom p2-w2 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 3325559037 403829666 −87.8% (−2920752717) −3054394114 to −2795561938 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 157836400 46243184 −70.7% (−111593312) −111593776 to −111592768 loss ≤ min(0, 0.05 × |baseline median|); base median within 78000000 to 312000000 PASSED

BatchEqual AgeNearCube p2-w2 vs trie · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 890879714 330133782 −63.2% (−562677801) −629978192 to −530715406 loss ≤ min(0, 0.05 × |baseline median|) PASSED
B/op 285047504 46939920 −83.5% (−238107504) −238107712 to −238107056 gain > 0; gain > 0.05 × |baseline median|; arm medians separated; base median within 78000000 to 312000000 PASSED

BatchEqual AgeNearCube p2-w2 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 3191091888 333109969 −89.4% (−2853030967) −2920352964 to −2732093901 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 158533584 46940352 −70.4% (−111593312) −111593856 to −111592656 loss ≤ min(0, 0.05 × |baseline median|); base median within 78000000 to 312000000 PASSED

BatchEqual Narrow14 p2-w2 vs trie · 41 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 5111031 4061983 −21.3% (−1090161) −1521009 to −196681 loss ≤ min(0, 0.05 × |baseline median|) PASSED
Narrow14 B/op 2893592 391234 −86.5% (−2502556) −2503292 to −2501670 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

BatchEqual Narrow14 p2-w2 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 25878029 4064029 −84% (−21741008) −24093484 to −20491570 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
Narrow14 B/op 1273470 391068 −69.3% (−882272) −883142 to −881200 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual Wide200 p2-w2 vs trie · 41 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 5488314 4663261 −15.3% (−838822) −1551926 to −16050 loss ≤ min(0, 0.05 × |baseline median|) PASSED
Wide200 B/op 2873572 359322 −87.5% (−2514254) −2514806 to −2514080 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

BatchEqual Wide200 p2-w2 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 90116276 4856222 −95.2% (−85761046) −91998514 to −82558504 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
Wide200 B/op 1226876 359368 −70.7% (−867550) −867784 to −867316 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual Wide1000 p2-w2 vs trie · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 11493467 6106299 −47.5% (−5455298) −6865506 to −3708718 loss ≤ min(0, 0.05 × |baseline median|) PASSED
Wide1000 B/op 4721672 404842 −91.4% (−4316840) −4317628 to −4316142 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

BatchEqual Wide1000 p2-w2 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 88093738 6184275 −93.1% (−82046903) −90486021 to −78691726 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
Wide1000 B/op 1304484 404754 −69% (−899730) −899860 to −898902 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual WideStride2 p2-w2 vs trie · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 23919933 7104913 −69.9% (−16724892) −21969052 to −15589169 loss ≤ min(0, 0.05 × |baseline median|) PASSED
WideStride2 B/op 5710350 405044 −92.9% (−5305308) −5306006 to −5305294 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

BatchEqual WideStride2 p2-w2 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 124605867 7149428 −94.2% (−117338935) −124758347 to −110984818 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
WideStride2 B/op 1304414 405032 −69% (−899426) −899834 to −899258 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual WideSharedPrefix p2-w2 vs trie · 53 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 5445120 4716800 −16.3% (−888451) −1306438 to −83850 loss ≤ min(0, 0.05 × |baseline median|) PASSED
WideSharedPrefix B/op 2844404 368558 −87% (−2475882) −2476522 to −2475772 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

BatchEqual WideSharedPrefix p2-w2 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 89205976 4913116 −94.4% (−84227113) −91583345 to −80157817 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
WideSharedPrefix B/op 1226854 368560 −70% (−858264) −858520 to −857930 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual Composite22 p2-w2 vs trie · 114 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 577400 578237 +3826 −17639 to +27944 loss ≤ 0.05 × |baseline median| PASSED
Composite22 B/op 276159 276215 +56 +54 to +57 loss ≤ 0.05 × |baseline median| PASSED

BatchEqual Composite22 p2-w2 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 36477191 575355 −98.4% (−35884584) −36591855 to −34682869 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
Composite22 B/op 1243460 276215 −77.8% (−967183) −967274 to −967024 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual CompositeWide p2-w2 vs trie · 90 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 573033 578425 −44.5 −21094 to +26452 loss ≤ 0.05 × |baseline median| PASSED
CompositeWide B/op 276159 276215 +56 +53 to +58 loss ≤ 0.05 × |baseline median| PASSED

BatchEqual CompositeWide p2-w2 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 56921115 574766 −99% (−56333827) −57784628 to −54826475 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
CompositeWide B/op 1243429 276215 −77.8% (−967198) −967281 to −967086 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual M128Scattered p2-w2 vs trie · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 891347304 5147042 −99.4% (−885710801) −934287311 to −836360955 loss ≤ min(0, 0.05 × |baseline median|) PASSED
B/op 285024128 9343392 −96.7% (−275680736) −275680848 to −275680608 gain > 0; gain > 0.05 × |baseline median|; arm medians separated; base median within 78000000 to 312000000 PASSED

BatchEqual M128Scattered p2-w2 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 3183623081 5230875 −99.8% (−3178378562) −3253076364 to −3109346902 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 158533584 9343392 −94.1% (−149190192) −149190288 to −149189376 loss ≤ min(0, 0.05 × |baseline median|); base median within 78000000 to 312000000 PASSED

BatchEqual M128 p2-w2 vs trie · 36 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 2413837 2371847 −44453 −183356 to +92734 loss ≤ 0.05 × |baseline median| PASSED
M128 B/op 9343343 9343391 +48 +46 to +50 loss ≤ 0.05 × |baseline median| PASSED

BatchEqual M200 p2-w2 vs trie · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 6297418 6353163 −27558 −408776 to +277363 loss ≤ 0.05 × |baseline median| PASSED
M200 B/op 9566336 9566385 +49 +45 to +67 loss ≤ 0.05 × |baseline median| PASSED

BatchEqual AgeRandom p2-w0 vs trie · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 547376526 398979511 −26.6% (−145342753) −188298155 to −118287619 loss ≤ min(0, 0.05 × |baseline median|) PASSED
B/op 229682256 46243184 −79.9% (−183439136) −183439616 to −183438960 gain > 0; gain > 0.05 × |baseline median|; arm medians separated; base median within 78000000 to 312000000 PASSED

BatchEqual AgeRandom p2-w0 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 3305888931 403634508 −87.8% (−2903775760) −2984585309 to −2833275768 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 155623656 46243168 −70.3% (−109380840) −111654664 to −107114256 loss ≤ min(0, 0.05 × |baseline median|); base median within 78000000 to 312000000 PASSED

BatchEqual AgeNearCube p2-w0 vs trie · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 861122394 336089442 −61.3% (−527991104) −570150722 to −477138862 loss ≤ min(0, 0.05 × |baseline median|) PASSED
B/op 285047520 46940160 −83.5% (−238107376) −238107824 to −238107056 gain > 0; gain > 0.05 × |baseline median|; arm medians separated; base median within 78000000 to 312000000 PASSED

BatchEqual AgeNearCube p2-w0 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 3162397334 327992232 −89.4% (−2828571641) −2928373982 to −2760640162 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 156328312 46940352 −70% (−109387944) −111664320 to −109386968 loss ≤ min(0, 0.05 × |baseline median|); base median within 78000000 to 312000000 PASSED

BatchEqual Narrow14 p2-w0 vs trie · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 5135555 4026390 −19.3% (−988971) −1636748 to −236232 loss ≤ min(0, 0.05 × |baseline median|) PASSED
Narrow14 B/op 2893586 391300 −86.5% (−2502296) −2502940 to −2501762 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

BatchEqual Narrow14 p2-w0 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 25585937 3992584 −84.3% (−21559594) −25023945 to −20024436 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
Narrow14 B/op 1287009 391244 −69.6% (−895765) −897335 to −893808 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual Wide200 p2-w0 vs trie · 53 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 5541073 4833783 −13% (−722744) −1423292 to −53 loss ≤ min(0, 0.05 × |baseline median|) PASSED
Wide200 B/op 2873574 359376 −87.5% (−2514212) −2514908 to −2514122 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

BatchEqual Wide200 p2-w0 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 86390965 4734965 −93.8% (−81067598) −86324294 to −78468772 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
Wide200 B/op 1227634 359378 −70.7% (−868224) −868802 to −867534 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual Wide1000 p2-w0 vs trie · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 11564916 5994212 −47.6% (−5507906) −7909905 to −2248827 loss ≤ min(0, 0.05 × |baseline median|) PASSED
Wide1000 B/op 4721670 404830 −91.4% (−4316854) −4317530 to −4316778 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

BatchEqual Wide1000 p2-w0 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 83263073 6128052 −93% (−77434714) −85911898 to −71361895 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
Wide1000 B/op 1305248 404828 −69% (−900418) −900942 to −900084 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual WideStride2 p2-w0 vs trie · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 24054504 7264518 −69.7% (−16759169) −18944353 to −15435778 loss ≤ min(0, 0.05 × |baseline median|) PASSED
WideStride2 B/op 5710344 405044 −92.9% (−5305306) −5305980 to −5305292 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

BatchEqual WideStride2 p2-w0 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 111397154 7133376 −93.7% (−104328212) −107585396 to −100242670 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
WideStride2 B/op 1305234 405044 −69% (−900200) −900536 to −899964 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual WideSharedPrefix p2-w0 vs trie · 36 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 5479930 4594832 −15.6% (−854113) −1393264 to −61688 loss ≤ min(0, 0.05 × |baseline median|) PASSED
WideSharedPrefix B/op 2844402 368564 −87% (−2475837) −2476602 to −2475666 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

BatchEqual WideSharedPrefix p2-w0 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 85681992 4624960 −94.8% (−81204592) −89886977 to −76512092 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
WideSharedPrefix B/op 1227600 368572 −70% (−859010) −859568 to −858648 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual Composite22 p2-w0 vs trie · 117 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 580207 585987 +6293 −15823 to +27285 loss ≤ 0.05 × |baseline median| PASSED
Composite22 B/op 276159 276215 +57 +55 to +59 loss ≤ 0.05 × |baseline median| PASSED

BatchEqual Composite22 p2-w0 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 36210303 586814 −98.4% (−35615195) −37539183 to −34149625 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
Composite22 B/op 1252704 276215 −78% (−976487) −977286 to −975998 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual CompositeWide p2-w0 vs trie · 90 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 580466 585828 +4940 −23623 to +27718 loss ≤ 0.05 × |baseline median| PASSED
CompositeWide B/op 276159 276215 +56 +54 to +57 loss ≤ 0.05 × |baseline median| PASSED

BatchEqual CompositeWide p2-w0 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 60040239 581186 −99% (−59448207) −60649956 to −58241814 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
CompositeWide B/op 1253189 276215 −78% (−976952) −977355 to −976286 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual M128Scattered p2-w0 vs trie · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 860620889 5603619 −99.4% (−855577300) −891880214 to −835460789 loss ≤ min(0, 0.05 × |baseline median|) PASSED
B/op 285024128 9343392 −96.7% (−275680736) −275680848 to −275680592 gain > 0; gain > 0.05 × |baseline median|; arm medians separated; base median within 78000000 to 312000000 PASSED

BatchEqual M128Scattered p2-w0 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 3185448722 6315178 −99.8% (−3180523835) −3231729866 to −3078032739 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 158595904 9343392 −94.1% (−149252512) −149260848 to −144789000 loss ≤ min(0, 0.05 × |baseline median|); base median within 78000000 to 312000000 PASSED

BatchEqual M128 p2-w0 vs trie · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 2388940 2377560 −17232 −228387 to +112979 loss ≤ 0.05 × |baseline median| PASSED
M128 B/op 9343343 9343391 +48 +47 to +50 loss ≤ 0.05 × |baseline median| PASSED

BatchEqual M200 p2-w0 vs trie · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 6193725 6132565 −52484 −421600 to +225906 loss ≤ 0.05 × |baseline median| PASSED
M200 B/op 9566336 9566385 +48 +46 to +51 loss ≤ 0.05 × |baseline median| PASSED

BatchEqual AgeRandom default-w0 vs trie · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 541236819 258459310 −51.5% (−278908567) −303604143 to −238850864 loss ≤ min(0, 0.05 × |baseline median|) PASSED
B/op 229682256 46881080 −79.6% (−182801256) −182806760 to −182800968 gain > 0; gain > 0.05 × |baseline median|; arm medians separated; base median within 78000000 to 312000000 PASSED

BatchEqual AgeRandom default-w0 vs scan · 25 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 1899553402 269854667 −86% (−1634071801) −1715663756 to −1514628083 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 155624024 46880744 −69.9% (−108743392) −111025168 to −108741520 loss ≤ min(0, 0.05 × |baseline median|); base median within 78000000 to 312000000 PASSED

BatchEqual AgeNearCube default-w0 vs trie · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 861171348 233848511 −72.3% (−622562506) −654763160 to −574309158 loss ≤ min(0, 0.05 × |baseline median|) PASSED
B/op 285047496 47579720 −83.3% (−237467744) −237468560 to −237467344 gain > 0; gain > 0.05 × |baseline median|; arm medians separated; base median within 78000000 to 312000000 PASSED

BatchEqual AgeNearCube default-w0 vs scan · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 1815081608 229440844 −86.7% (−1572836592) −1769838228 to −1474362357 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 156408992 47579672 −69.6% (−108829376) −111025184 to −106478528 loss ≤ min(0, 0.05 × |baseline median|); base median within 78000000 to 312000000 PASSED

BatchEqual Narrow14 default-w0 vs trie · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 5029487 4182845 −16.9% (−848471) −1672986 to −168280 loss ≤ min(0, 0.05 × |baseline median|) PASSED
Narrow14 B/op 2893601 743594 −74.3% (−2150031) −2150780 to −2149602 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

BatchEqual Narrow14 default-w0 vs scan · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 17129510 4096574 −75.7% (−12969541) −14352060 to −10558646 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
Narrow14 B/op 1291564 743501 −42.4% (−547796) −549994 to −545615 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual Wide200 default-w0 vs trie · 45 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 5326304 4858756 −9.5% (−504283) −1232246 to −39825 loss ≤ min(0, 0.05 × |baseline median|) PASSED
Wide200 B/op 2873584 702038 −75.6% (−2171570) −2172240 to −2170982 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

BatchEqual Wide200 default-w0 vs scan · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 56832262 4937987 −90.9% (−51678646) −60559770 to −47113324 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
Wide200 B/op 1227792 702035 −42.8% (−525749) −526388 to −524984 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual Wide1000 default-w0 vs trie · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 11062724 5800447 −48.2% (−5332303) −7748500 to −4596539 loss ≤ min(0, 0.05 × |baseline median|) PASSED
Wide1000 B/op 4721713 747603 −84.2% (−3974141) −3975674 to −3973340 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

BatchEqual Wide1000 default-w0 vs scan · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 55256361 5667678 −89.5% (−49441710) −55403227 to −44098797 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
Wide1000 B/op 1305467 747593 −42.7% (−557902) −558936 to −557214 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual WideStride2 default-w0 vs trie · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 23584600 6534337 −72.6% (−17123225) −21868800 to −16172757 loss ≤ min(0, 0.05 × |baseline median|) PASSED
WideStride2 B/op 5710368 747910 −86.9% (−4962530) −4963160 to −4962300 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

BatchEqual WideStride2 default-w0 vs scan · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 81883042 6652383 −91.7% (−75089460) −90025033 to −69276511 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
WideStride2 B/op 1305459 747879 −42.7% (−557581) −558130 to −557228 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual WideSharedPrefix default-w0 vs trie · 37 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 5281510 4794849 −9.1% (−479342) −1632481 to −116373 loss ≤ min(0, 0.05 × |baseline median|) PASSED
WideSharedPrefix B/op 2844434 711428 −75% (−2133152) −2133976 to −2132540 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

BatchEqual WideSharedPrefix default-w0 vs scan · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 55978635 4741178 −91.8% (−51410679) −57417688 to −47437691 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
WideSharedPrefix B/op 1227803 711278 −42.1% (−516572) −517702 to −515534 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual Composite22 default-w0 vs trie · 64 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 569558 569959 +64 −28734 to +27735 loss ≤ 0.05 × |baseline median| PASSED
Composite22 B/op 276160 276217 +56.5 +52 to +140 loss ≤ 0.05 × |baseline median| PASSED

BatchEqual Composite22 default-w0 vs scan · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 24450566 566831 −97.7% (−23888382) −24849099 to −22486817 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
Composite22 B/op 1257782 276218 −78% (−981521) −982312 to −980806 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual CompositeWide default-w0 vs trie · 74 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 570701 562540 −5093 −40447 to +23434 loss ≤ 0.05 × |baseline median| PASSED
CompositeWide B/op 276161 276217 +55 −26 to +141 loss ≤ 0.05 × |baseline median| PASSED

BatchEqual CompositeWide default-w0 vs scan · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 38610454 566430 −98.5% (−38022948) −39104248 to −35808573 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
CompositeWide B/op 1257532 276216 −78% (−981315) −982317 to −980514 loss ≤ min(0, 0.05 × |baseline median|) PASSED

BatchEqual M128Scattered default-w0 vs trie · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 855672459 5237209 −99.4% (−850616148) −887378133 to −818423903 loss ≤ min(0, 0.05 × |baseline median|) PASSED
B/op 285024120 9343392 −96.7% (−275680728) −275680976 to −275680624 gain > 0; gain > 0.05 × |baseline median|; arm medians separated; base median within 78000000 to 312000000 PASSED

BatchEqual M128Scattered default-w0 vs scan · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 1822154767 5209440 −99.6% (−1815197135) −1975072409 to −1723106883 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 156328336 9343392 −94% (−146984944) −149261584 to −144788160 loss ≤ min(0, 0.05 × |baseline median|); base median within 78000000 to 312000000 PASSED

BatchEqual M128 default-w0 vs trie · 57 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 2366639 2352672 −17745 −100669 to +115181 loss ≤ 0.05 × |baseline median| PASSED
M128 B/op 9343343 9343391 +48 +46 to +50 loss ≤ 0.05 × |baseline median| PASSED

BatchEqual M200 default-w0 vs trie · 26 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 6349226 6259226 −142590 −348024 to +233302 loss ≤ 0.05 × |baseline median| PASSED
M200 B/op 9566337 9566385 +48 +26 to +69 loss ≤ 0.05 × |baseline median| PASSED

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

Timeline