nordisk/znippy-zoomies

lbzip2 library readers — reasoning

Class: reasoning · Function: lbzip2-readers. Why three readers, and why the scan is parallel. Shipped shape in lbzip2-readers-design.md.

Why the block scan had to go parallel

bzip2's per-block decode is trivially parallel — but you cannot decode a block until you know where it starts, and the 48-bit magic sits at an arbitrary bit offset, so finding blocks means bit-scanning the whole compressed stream. Done serially (find_all_blocks, one thread walking the whole buffer) that scan is a serial prefix that dominates on large inputs: on a 1 GB .bz2 the box sits ~1-core-busy scanning while every other core waits for the first boundary. find_all_blocks_parallel (lbzip2/src/block_scan.rs:143) splits the buffer across cores (with an 8-byte overlap so a straddling magic is not lost) and merges to the identical boundary set — the scan stops being the bottleneck. The core-saturation law ([core-saturation-law.md] in memory) treats a serial prefix like this as a bug to fix, not an Amdahl inevitability, and this is the fix.

Why three readers instead of one

They trade memory against input shape:

• decompress_parallel is the simplest and fastest when you already hold the bytes and want the whole output — but it materialises the full decompressed Vec, which for a 10× bzip2 ratio is a real peak-RSS cost.
• StreamingBz2Read exists precisely to bound that: a Read source decoded in ~100 MB chunks, one chunk's output live at a time, next-chunk I/O overlapping current-chunk consumption. It is the reader osm-katana's bz2 convert path leans on, where a planet .osm.bz2 cannot be held resident.
• ParallelBz2Read is the mmap middle ground: it scans all boundaries up front (the bytes are already mapped, faulting lazily) and streams 64-block batches through Read — cheap random access without a whole-output buffer.

Why segment-grouping, not block-per-worker

decompress_parallel groups blocks into ~4 segments/thread rather than fanning every block as its own unit (parallel.rs:61). Decoding each of ~1000 blocks into its own Vec and concatenating them is ~1 GB of extra copying plus a heap allocation per block; grouping lets each worker append its whole segment's blocks into one growing buffer (decode_segment_checked → decode_block_into), so the final assembly concatenates only n_segments buffers. The 4× oversubscription keeps gatling_for_each's self-dispatch able to steal past a fat block without stranding a worker.

Why the CRC fold is kept

The combined-stream CRC (rotate-left-1-then-XOR of per-block CRCs, parallel.rs:97) is checked against the stream trailer for a single stream; concatenated pbzip2 inputs (multiple FINAL_MAGICs) skip the whole-stream fold and lean on the per-block CRCs, so a coincidental extra magic never causes a false rejection while corruption is still caught. Same security posture as the CLI: never emit unverified bytes.