nordisk/znippy-zoomies

lbunzip2 — design

Class: design · Function: lbunzip2 (parallel bzip2 CLI). Strict: the shipped shape, every claim a real file:symbol. Run it via lbunzip2-guide.md; why bzip2 saturates cleanly in lbunzip2-reasoning.md. The in-memory / Read-trait library twins are lbzip2-readers-design.md.

What it is

lbzip2/src/bin/lbunzip2.rs — a pure-Rust CLI decoder for the stock .bz2 format, decoding independent BWT blocks across every core. lbunzip2 in.bz2 [out] (strips the .bz2 extension when out is omitted).

The exact dataflow

bzip2 is a stream of independent blocks (100 KB–900 KB uncompressed each, level 1–9), every block a self-contained Huffman + MTF + BWT unit prefixed by the 48-bit magic 0x314159265359 at an arbitrary bit offset. That independence is the whole parallelism story, and lbunzip2 rides the shared gatling ordered engine (gatling::gatling::ordered::run_ordered_sink, gatling/src/gatling_ordered.rs:113) end to end — there is no hand-rolled pool.

1. Producer (one dispatch thread). Runs on the engine's dispatch thread so its I/O overlaps decode. It reads 8 MB compressed chunks (CHUNK_SIZE), prepends the carry (the previous chunk's undecoded tail, seeded with the 4-byte BZh header), and calls chunk::split_chunk (lbzip2/src/chunk.rs:35) to cut the chunk into per-block segments. It yields one segment at a time as SegIn { data: Arc<Vec<u8>>, start_bit, end_bit, max_blocksize } (lbunzip2.rs:88) — the Arc keeps the chunk buffer alive across every segment referencing it (the ownership-based replacement for the old raw-pointer-into-a-recycled-slot).

2. Block-boundary scan. split_chunk locates block magics with the bit-level sliding-window scanner in lbzip2/src/block_scan.rs: split_boundaries_parallel (block_scan.rs:279) fans the N−1 nominal split points across cores via gatling_for_each, each core forward-scanning for the next magic and quick_verify_block-ing 73 header bits (block_scan.rs:214) to reject false-positive magic patterns inside compressed data — no full decode needed.

3. N map workers (self-dispatch, no barrier). Each pulls the next segment and runs chunk::decode_segment_checked (lbzip2/src/chunk.rs:117): Huffman → MTF → inverse-BWT, then a per-block CRC-32 check. A CRC mismatch is fatal — the worker prints corrupt input and exits non-zero rather than emit silently-truncated bytes (lbunzip2.rs:270).

4. Ordered sink. WriteSink::emit (lbunzip2.rs:110) writes each decoded segment in strict producer order to a 4 MB BufWriter. The engine's counting-permit pool bounds in-flight memory to cap segments, so resident decoded output is a handful of segments — never the whole file.

The segmentation floor (a real correctness fix, not tuning)

n_segments = n_workers.max(2) (lbunzip2.rs:173). The producer holds back the last segment of every non-final chunk as carry (its trailing block may continue into the next chunk), decoding decode_segments = n − 1. With a single segment split_chunk returns None for non-last chunks, so the producer would discard those bytes and only the final chunk would ever decode — a silent truncation to the last ~8 MB (and a bogus "single-core faster than all cores" bench). Flooring at 2 means even LBZIP2_THREADS=1 streams the whole file (segments decoded one at a time, in order) while worker parallelism stays exactly n_workers.

Whereabouts

Saturation state (just-landed)

lbunzip2 sits at ~7.8–11.5/12 cores on the quiet box — the highest of the DEFLATE family's siblings because bzip2's block independence needs no writer trick (the per-block work dwarfs the ordered write). Real cores_busy lands in the README.md A/B/C mashup on the heavy-bench wave; nothing is fabricated here. Note the honest loss recorded in the README: mature C lbzip2 still edges us on raw bzip2, while we crush serial bzip2 ~10×.