Preserve full-width runs during batched bitmap iteration
perfloop-oss/roaring-rs · NUMERIC REPRESENTATION LOSS
https://perfloop.ai/t/oss/case_fkrdb8dgjq
Verdict
VERIFIED · settled 2026-11-09
What happened: The check fails before this change and passes with it.
Hypothesis
Batched bitmap iteration cannot reliably read an untouched full-width run. A supported range insertion creates this state, and a one-slot batch panics in the normal test profile. Unchecked arithmetic also appears able to discard the run. Consumer frequency is unknown; this is a value-preservation finding, not a measured performance claim.
RoaringBitmap::insert_range(0..=65535) reaches Container::new_with_range and creates one inclusive run. RunIter<I>::next_many computes `(end - start + 1) as usize` at line 894. The addition still occurs in u16, which cannot represent 65,536. The relevant condition is a nonempty destination with effective start 0 and end 65535; an empty destination returns earlier, and trimming either end avoids this particular overflow. With unchecked overflow, the source calculation becomes zero and the whole-interval branch removes the run without incrementing the output count. Other containers may still produce output, so an empty result is not predicted for every affected call.
The native check `cargo test -p roaring --test perfloop_batch_values_property -- --nocapture`, stored on prop_y0awq36wrf, failed at the addition in checkProperty run call_3PRUxSnxh8Hbp3ZhpKzv1LKx on f845305c4b6df310ad4aab9e355749c6badd56e4. The fixed-seed proptest search had four successful cases before shrinking to high=0, low=(0,65535), capacity=1. Scalar iteration first matched the independently constructed range. The property now retains the returned proptest regression file and a deterministic native replay, so no new search is needed. The separate empty-buffer property passed its complete small-state enumeration; that does not establish correctness for nonempty batches.
The smallest useful next check is to replay the counterexample without overflow checks and compare repeated batches with scalar iteration, including a 65,536-slot destination and neighboring run lengths. The Case should confirm the unchecked-loss prediction and establish correct count and advancement arithmetic across the inclusive run domain. A test layout or bounded generator is a provisional proof method, not a restriction of that domain.
The refreshed open-PR list and actual overlapping hunks show distinct work: https://github.com/RoaringBitmap/roaring-rs/pull/398 only shrinks storage capacity, https://github.com/RoaringBitmap/roaring-rs/pull/354 adds archive derives/access, and https://github.com/RoaringBitmap/roaring-rs/pull/348 adds const qualifiers. None changes this batch arithmetic. The draft https://github.com/RoaringBitmap/roaring-rs/pull/356 changes serialization policy, not in-memory run expansion; its implementation and discussion do not remove this input class. Its serialization proposal is not a landed replacement for this iterator. There are no customer closure reasons or supplied prior findings for this path.
Change to test: Compute inclusive run cardinalities in a type that represents 65,536 before adding one, and establish that full and partial batches preserve every value and report exhaustion correctly with overflow checking both enabled and disabled. Regression-test placement is provisional; the public batch API and its run-expansion behavior are the repair target.
Where it lives
perfloop-oss/roaring-rs · roaring/src/bitmap/iter.rs
Evidence
The check fails before this change and passes with it: `For run-backed RoaringBitmap ranges, borrowed and owned next_many preserve the next min(destination length, remaining length) ordered values and iterator advancement, including full 65,536-value runs, empty destinations, and front/back-trimmed states.`
The check fails before this change and passes with it: `For run-backed RoaringBitmap ranges, borrowed and owned next_many preserve the next min(destination length, remaining length) ordered values and iterator advancement, including full 65,536-value runs, empty destinations, and front/back-trimmed states.`
Checks: 6 of 6 passed. Verification: no defect found.