Fix SumBigValues int64 overflow without losing multi-core speed (replaces open PR #552)

perfloop-oss/roaring · NUMERIC REPRESENTATION LOSS

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

Verdict

VERIFIED · settled 2026-11-05 · pull request opened as RoaringBitmap/roaring#590

What happened: The check fails before this change and passes with it.

Hypothesis

The sum of selected values can lose high bits before it reaches arbitrary-precision arithmetic. This can return wrong totals. The requested repair must also retain useful multi-core speed and small-index efficiency. The submitter's correctness and performance measurements have not been reproduced in this run; consumer frequency and input distributions remain unknown.

A bit-sliced index (BSI) stores each value bit in a bitmap. At accepted revision 0cca44e8f178ff394b7de93713b92b65f6240841, roaring64.BSI.SumBigValues promises to sum arbitrarily large values (roaring64/bsi64.go:1128-1154). Each ordinary plane sends int64(foundSet.AndCardinality(&b.bA[j]) << uint(j)) through a channel before big.Int addition (1136-1149). The sign-plane subtraction also shifts and converts at fixed width before constructing a big.Int (1151). Thus later arbitrary-precision arithmetic cannot recover information already lost. SetBigValue supports growing the representation for wide inputs (104-137), and BitCount excludes the sign plane (86-89). Nil filters use the existence bitmap (1131-1135); signed weighting, filtered sums, and returned counts must retain their API behavior.

The submitter reports that their base and master returned wrong sums in 96 of 300 random trials. Their example for a 63-bit plane was got -10281014778330224382, want -157854967368006637310. This is an attributed failure report to reproduce, not an established failure rate for consumers.

The submitter reports that the sequential overflow repair in PR #552 slowed 2M-row BSIs at GOMAXPROCS=2: 63-bit values went from 467.2us to 891.9us (+91%); 16-bit values from 123.0us to 178.3us (+45%); and 64-bit values including negatives from 483.2us to 916.4us (+90%), with reported p=0.000 and n=8. They report no change at GOMAXPROCS=1. They also report that #552 improved 128-row BSIs from 35.45us to 11.14us and cut allocations from 132 to 5 per operation. These are unconfirmed reports to check during the Case, not measurements or savings established here.

Fresh upstream reads show https://github.com/RoaringBitmap/roaring/pull/552 remains open, with checked base e9e1ecc5b8fd3dd7247d510bce84d2258dca1362 and head 83c91fb8d27e44ca589efee80e650a086e8c12f0. Its patch repairs the same fixed-width arithmetic using a sequential reusable-big.Int loop, and adds TestSumBigValues plus a 128-row benchmark. Its body names no related issues and reports a separate small-input benchmark, which does not establish the larger-workload regression reported here. The remaining difference is to preserve per-plane parallelism for large BSIs while retaining the small-input benefits and exact signed sums. An open proposal is not evidence of maintainer acceptance of either scheduling policy; no accepted replacement decision is established by these reads.

The submitter explicitly requires including #552's native Go TestSumBigValues regression: positive 2^149+7, negative -(2^120)-11, and filtered sets. The report also requires a random differential against an independent big.Int reference, paired base-versus-head measurements on 2M-row BSIs at GOMAXPROCS 1, 2, and 4, and small-BSI checks at 128 and 100k rows. Retain the reported 63-bit, 16-bit, and signed 64-bit workload distinctions when checking the large-input trade-off. The smallest useful first check is to run the overflow regression on the unchanged code, then compare generated selected-value sums with the independent reference. Reference agreement or a mismatch decides correctness; paired timings and allocs/op across the requested sizes and parallelism settings decide whether the repair preserves multi-core speed and small-input efficiency. The random generator, benchmark file layout, and any threshold chosen during investigation are provisional methods, not additional frozen requirements. This Go arithmetic and scheduling mechanism is architecture-independent and imposes no CPU-generation or ISA target.

The submitter reports that #552 cannot be updated from this workspace and requires a new PR that supersedes it. The PR body must be short and outcome-first, with one sentence saying it supersedes #552 and why. Preserve this whole correctness-and-performance outcome in one Case rather than replacing it with the already-proposed serial-only repair.

Change to test: Make SumBigValues exact for wide positive and negative inputs while keeping per-plane parallelism: each goroutine, or a bounded worker set, should write its unshifted uint64 AndCardinality into a slice, then combine sequentially with big.Int.Lsh by plane index, adding ordinary planes and subtracting the sign plane. Consider a sequential path below a size threshold so small BSIs retain #552's speed gain and few allocations.

Where it lives

perfloop-oss/roaring

Evidence

The check fails before this change and passes with it: `SumBigValues returns exact signed sums for 2^149+7, -(2^120)-11, -9 and 7 with nil and {1,3} filters, returning counts 4 and 2 respectively.`

The check fails before this change and passes with it: `For 300 fixed-seed dense/scattered signed BSI fixtures up to 256 bits and scalar/bulk cardinality/container-boundary fixtures, SumBigValues returns the exact selected-value sum and filter cardinality, and Sum returns that sum's Int64 conversion, with nil, empty, subset and absent-ID filters at GOMAXPROCS 1, 2 and 4, without concurrent mutation.`

SumBigValues rows128 bits63 all procs1 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 21837 1784 −91.4% (−19970) −21030 to −19530 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 5289 144 −97.3% (−5145) −5146 to −5145 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 5 −96.2% (−127) −127 to −127 gain > 0; gain > 0.05 × |baseline median|; arm medians separated; base median within 132 to +∞ PASSED

SumBigValues rows128 bits63 all procs2 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 29036 1820 −93.6% (−27168) −32124 to −26306 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 5293 144 −97.3% (−5149) −5150 to −5149 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 5 −96.2% (−127) −127 to −127 gain > 0; gain > 0.05 × |baseline median|; arm medians separated; base median within 132 to +∞ PASSED

SumBigValues rows128 bits63 all procs4 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 27749 1824 −93.2% (−25860) −32474 to −25141 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 5297 144 −97.3% (−5153) −5156 to −5153 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 5 −96.2% (−127) −127 to −127 gain > 0; gain > 0.05 × |baseline median|; arm medians separated; base median within 132 to +∞ PASSED

SumBigValues rows100000 bits16 all procs1 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 10244 4785 −53.3% (−5462) −5906 to −4816 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 1504 144 −90.4% (−1360) −1360 to −1360 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 38 5 −86.8% (−33) −33 to −33 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows100000 bits16 all procs2 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 11075 4854 −55.6% (−6155) −6608 to −5976 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 1505 144 −90.4% (−1361) −1361 to −1361 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 38 5 −86.8% (−33) −33 to −33 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows100000 bits16 all procs4 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 11228 4827 −56.6% (−6360) −6927 to −6054 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 1507 144 −90.4% (−1363) −1363 to −1362 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 38 5 −86.8% (−33) −33 to −33 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows100000 bits63 all procs1 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 39286 18611 −52.3% (−20551) −23168 to −18912 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 5291 144 −97.3% (−5147) −5148 to −5147 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 5 −96.2% (−127) −127 to −127 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows100000 bits63 all procs2 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 44280 18714 −57.4% (−25417) −31143 to −23942 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 5296 144 −97.3% (−5152) −5153 to −5151 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 5 −96.2% (−127) −127 to −127 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows100000 bits63 all procs4 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 44843 18755 −57.9% (−25971) −31751 to −24543 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 5303 144 −97.3% (−5159) −5162 to −5158 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 5 −96.2% (−127) −127 to −127 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows100000 bits64 all procs1 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 40368 19419 −52.2% (−21090) −26728 to −19839 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 5363 144 −97.3% (−5219) −5219 to −5219 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 134 5 −96.3% (−129) −129 to −129 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows100000 bits64 all procs2 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 45714 19408 −57.3% (−26173) −31554 to −22839 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 5368 144 −97.3% (−5224) −5225 to −5223 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 134 5 −96.3% (−129) −129 to −129 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows100000 bits64 all procs4 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 46899 19344 −58.9% (−27612) −34021 to −24966 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED
B/op 5376 144 −97.3% (−5232) −5234 to −5230 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 134 5 −96.3% (−129) −129 to −129 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits16 all procs1 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 148562 138957 −6% (−8981) −16852 to −501 loss ≤ 0.05 × |baseline median| PASSED
B/op 1504 144 −90.4% (−1360) −1361 to −1360 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 38 5 −86.8% (−33) −33 to −33 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits16 all procs2 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 92692 88883 −4% (−3752) −8029 to −357 loss ≤ 0.05 × |baseline median| PASSED
B/op 1507 442 −70.7% (−1065) −1065 to −1064 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 38 10 −73.7% (−28) −28 to −28 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits16 all procs4 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 81568 79098 −2276 −6865 to +1259 loss ≤ 0.05 × |baseline median| PASSED
B/op 1510 573 −62.1% (−937) −938 to −936 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 38 12 −68.4% (−26) −26 to −26 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits63 all procs1 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 600217 570183 −5.3% (−31757) −42347 to −17736 loss ≤ 0.05 × |baseline median| PASSED
B/op 5303 144 −97.3% (−5159) −5161 to −5159 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 5 −96.2% (−127) −127 to −127 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits63 all procs2 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 329186 320649 −6676 −23934 to +10876 loss ≤ 0.05 × |baseline median| PASSED
B/op 5305 816 −84.6% (−4489) −4491 to −4487 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 10 −92.4% (−122) −122 to −122 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits63 all procs4 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 241744 232518 −8694 −30416 to +6811 loss ≤ 0.05 × |baseline median| PASSED
B/op 5311 951 −82.1% (−4360) −4363 to −4356 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 12 −90.9% (−120) −120 to −120 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits64 all procs1 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 625393 595885 −33635 −59775 to +8886 loss ≤ 0.05 × |baseline median| PASSED
B/op 5376 144 −97.3% (−5232) −5234 to −5232 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 134 5 −96.3% (−129) −129 to −129 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits64 all procs2 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 364484 336098 −8.4% (−30477) −42709 to −10986 loss ≤ 0.05 × |baseline median| PASSED
B/op 5379 881 −83.6% (−4498) −4501 to −4495 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 134 10 −92.5% (−124) −124 to −124 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits64 all procs4 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 264733 240571 −8.5% (−22517) −43453 to −8795 loss ≤ 0.05 × |baseline median| PASSED
B/op 5386 1016 −81.2% (−4371) −4375 to −4368 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 134 12 −91% (−122) −122 to −122 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits63 range100000 procs1 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 37223 16588 −55.7% (−20724) −22822 to −19782 loss ≤ 0.05 × |baseline median| PASSED
B/op 5288 144 −97.3% (−5144) −5145 to −5144 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 5 −96.2% (−127) −127 to −127 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits63 range100000 procs2 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 40764 16412 −59.5% (−24268) −27114 to −23482 loss ≤ 0.05 × |baseline median| PASSED
B/op 5290 144 −97.3% (−5146) −5146 to −5145 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 5 −96.2% (−127) −127 to −127 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits63 range100000 procs4 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 41353 16431 −60.5% (−25025) −26591 to −24050 loss ≤ 0.05 × |baseline median| PASSED
B/op 5292 144 −97.3% (−5148) −5148 to −5147 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 5 −96.2% (−127) −127 to −127 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits63 scattered100000 procs1 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 5649010 5682545 +39307 −186490 to +271379 loss ≤ 0.05 × |baseline median| PASSED
B/op 5430 144 −97.3% (−5286) −5290 to −5285 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 5 −96.2% (−127) −127 to −127 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits63 scattered100000 procs2 · 42 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 3162026 3159796 −18004 −213948 to +152928 loss ≤ 0.05 × |baseline median| PASSED
B/op 5444 865 −84.1% (−4578) −4604 to −4552 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 10 −92.4% (−122) −122 to −122 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits63 scattered100000 procs4 · 38 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 2065530 2059393 −17620 −141760 to +94034 loss ≤ 0.05 × |baseline median| PASSED
B/op 5485 1044 −81% (−4444) −4469 to −4412 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 12 −90.9% (−120) −120 to −120 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits63 scattered262143 procs1 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 628670 594694 −6% (−37407) −49911 to −23135 loss ≤ 0.05 × |baseline median| PASSED
B/op 5304 144 −97.3% (−5160) −5161 to −5160 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 5 −96.2% (−127) −127 to −127 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits63 scattered262143 procs2 · 33 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 336778 334001 −1895 −25044 to +13177 loss ≤ 0.05 × |baseline median| PASSED
B/op 5306 817 −84.6% (−4489) −4490 to −4487 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 10 −92.4% (−122) −122 to −122 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows2000000 bits63 scattered262143 procs4 · 22 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 247706 240066 −7894 −18648 to +10076 loss ≤ 0.05 × |baseline median| PASSED
B/op 5313 952 −82.1% (−4361) −4364 to −4357 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 12 −90.9% (−120) −120 to −120 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows8000000 bits63 scattered250000 procs1 · 46 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 15767570 16042793 +211776 −353408 to +572521 loss ≤ 0.05 × |baseline median| PASSED
B/op 5708 144 −97.5% (−5564) −5588 to −5558 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 5 −96.2% (−127) −127 to −127 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows8000000 bits63 scattered250000 procs2 · 38 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 8544613 8477070 −102737 −464103 to +405210 loss ≤ 0.05 × |baseline median| PASSED
B/op 5708 895.5 −84.4% (−4818) −4852 to −4778 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 132 10 −92.4% (−122) −122 to −122 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

SumBigValues rows8000000 bits63 scattered250000 procs4 · 53 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 5197303 5188906 −5690 −219305 to +242998 loss ≤ 0.05 × |baseline median| PASSED
B/op 5777 1145 −80.3% (−4639) −4674 to −4587 loss ≤ 0.05 × |baseline median| PASSED
allocs/op 133 12 −91% (−121) −121 to −121 gain > 0; gain > 0.05 × |baseline median|; arm medians separated PASSED

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

Timeline