Batch no-run container reads during decoding

perfloop/roaring · CHATTY IO

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

Verdict

VERIFIED · settled 2026-09-15 · pull request opened as RoaringBitmap/roaring#571

Hypothesis

A counting-reader probe serialized 16,384 singleton high-key containers and decoded them with Bitmap.ReadFrom through an ordinary io.Reader. It completed the round trip and recorded 16,388 direct Read calls for 163,848 bytes. This check establishes call multiplicity only; it does not measure syscall or storage time.

Bitmap.ReadFrom wraps a reader that is not internal.ByteInput in ByteInputAdapter. ByteInputAdapter.Next allocates the requested slice and invokes io.ReadAtLeast. readFrom calls Next once for each container after the descriptive and offset headers. Thus a no-run bitmap with N low-cardinality containers generates N small reader operations per decode in addition to headers; the parser admits up to 65,536 containers and a singleton array payload is two bytes. The cost is only plausible when the supplied reader has no lower coalescing layer and Read reaches a file, socket, or other storage boundary; ByteInput callers and already-buffered readers do not establish the same cost.

For the no-run format, keycard determines every array or bitmap payload length. Read exact, bounded groups of whole container payloads after the offset table and install sub-slices in each container, so the parser does not overread a caller's stream. Reproduce the counting-reader test with unbuffered file and short-read readers, then benchmark sparse container counts; the expected confirmation is reader or syscall calls falling from N plus a constant per decoded bitmap to one per bounded group while output and post-bitmap reader position remain unchanged.

Change to test: Special-case no-run data in roaringArray.readFrom: calculate payload lengths from keycard and issue exact bounded Next calls for contiguous whole-container groups. Slice each returned group into its containers and keep every group boundary at a serialized container boundary to preserve stream position and limit retained backing storage.

Where it lives

perfloop/roaring · roaring.go

Evidence

Bitmap.ReadFrom of a no-run sparse bitmap with 1024 singleton containers from an unbuffered file · 10 sample pairs

metric baseline candidate paired median change confidence range required result
read-calls/op 1028 5 −99.5% (−1023) −1023 to −1023 < −51.4 PASSED
ns/op 2821183 67312 −97.6% (−2753872) −2999274 to −2668946 ≤ 0 PASSED

Bitmap.ReadFrom of a no-run sparse bitmap with 4096 singleton containers from an unbuffered file · 10 sample pairs

metric baseline candidate paired median change confidence range required result
read-calls/op 4100 5 −99.9% (−4095) −4095 to −4095 < −205 PASSED
ns/op 10941639 192735 −98.1% (−10735142) −11270196 to −10575342 ≤ 0 PASSED

Bitmap.ReadFrom of a no-run sparse bitmap with 16384 singleton containers from an unbuffered file · 10 sample pairs

metric baseline candidate paired median change confidence range required result
read-calls/op 16388 5 −100% (−16383) −16383 to −16383 < −819.4 PASSED
ns/op 44080576 796998 −98.2% (−43291660) −44275056 to −42335882 ≤ 0 PASSED

Bitmap.ReadFrom of a no-run sparse bitmap with 1024 singleton containers through a 257-byte short-read file reader · 10 sample pairs

metric baseline candidate paired median change confidence range required result
read-calls/op 1058 42 −96% (−1016) −1016 to −1016 < −52.9 PASSED
ns/op 2811730 163157 −94.4% (−2653159) −2756837 to −2620785 ≤ 0 PASSED

Bitmap.ReadFrom of a no-run sparse bitmap with 4096 singleton containers through a 257-byte short-read file reader · 10 sample pairs

metric baseline candidate paired median change confidence range required result
read-calls/op 4226 162 −96.2% (−4064) −4064 to −4064 < −211.3 PASSED
ns/op 11469151 596807 −94.7% (−10859591) −11089880 to −10518848 ≤ 0 PASSED

Bitmap.ReadFrom of a no-run sparse bitmap with 16384 singleton containers through a 257-byte short-read file reader · 10 sample pairs

metric baseline candidate paired median change confidence range required result
read-calls/op 16898 642 −96.2% (−16256) −16256 to −16256 < −844.9 PASSED
ns/op 44753021 2300427 −94.8% (−42434529) −46064207 to −42114916 ≤ 0 PASSED

Existing BenchmarkUnserializeReadFrom of a 6,500,000-value bitmap through bytes.Reader · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 10499 10174 −4.1% (−430) −842 to −71 ≤ 0 PASSED
B/op 14006 14006 0 0 to 0 ≤ 0 PASSED
allocs/op 207 207 0 0 to 0 ≤ 0 PASSED

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

Timeline