nordisk/znippy-zoomies

lbzip2-rs Design

Pure Rust parallel bzip2 decompressor — library + CLI.

CLI Pipeline (lbunzip2)

Three threads, zero-copy ring buffer:

┌──────────┐    sync_channel     ┌──────────────┐    sync_channel     ┌──────────┐
│  READER  │──(slot,len,last)──→ │  MAIN THREAD │──(Vec<u8> segs)──→ │  WRITER  │
│  thread  │                     │ carry+decode  │                     │  thread  │
└────┬─────┘                     └──────────────┘                     └──────────┘
     ↑                                  │
     └──── slot_return channel ─────────┘   (4 × 232 MB recycled buffers)

Ring buffer: 4 pre-allocated slots, each [32 MB headroom | 200 MB chunk]. Slots are never freed — recycled through slot_return channel.

Carry: between chunks, the unconsumed tail (< 1 MB) is copied into the headroom area of the next slot. The 200 MB read data stays in place — never copied.

Per-chunk cycle:

1. Reader fills 200 MB slot from disk (~50-90ms NVMe)
2. Main thread: carry into headroom → decode_chunk_segments() → recycle slot
3. Segments sent individually to writer (no assembly memcpy)

Parallel Split + Decode

O(N) Boundary Finding

Not a full scan. N×oversplit evenly-spaced positions, each forward-scans ~500 bytes for the next BLOCK_MAGIC, then 73-bit quick-verify. Total: 3-5ms for 200 MB.

Segment Decode

Chunk split into ~255 segments at boundaries. Each decoded by one rayon thread. Within a segment: sequential bitstream walk (Huffman → MTF → BWT → RLE2). Oversplit 8× enables rayon work-stealing for load balance.

Block Decode

BitReader (64-bit buffer, bulk 8-byte refill)
  → Header (CRC + orig_ptr + bitmap + selectors)
  → Huffman (10-bit packed u16 lookup, 2KB/table, L1-resident)
  → MTF (fast-path n=0, n=1)
  → RLE1 (RUNA/RUNB) → tt[] array (~3.6 MB)
  → Inverse BWT (in-place T-transformation)
  → RLE2 (pointer chase with 2-step prefetch, raw pointer output)
  → Vec<u8>

Thread-local tt pool: 3.6 MB buffer reused per thread, no alloc/free per block. Zero heap allocs per block: Huffman tables, selectors, bitmaps all on stack.

bzip2 Stream Format

[BZh9]  [BLOCK_MAGIC block_data]...  [FINAL_MAGIC crc32] [pad]

• Block magic: 48-bit 0x314159265359 (π digits), bit-aligned (not byte-aligned)
• End-of-stream: 48-bit 0x177245385090 (√π digits) + CRC32 + byte-pad

pbzip2 Concatenated Streams

Planet files are ~1.3M independent mini-streams concatenated (~120 KB each). FINAL_MAGIC appears every ~120 KB, not just at EOF. Segment decoders handle FINAL_MAGIC → skip CRC + pad + BZhN header → continue.

False Positive Rejection

73-bit quick-verify after magic: randomised=0, orig_ptr < max_blocksize, bitmap ≠ 0.

Module Map

src/
├── lib.rs           # BLOCK_MAGIC/FINAL_MAGIC, dedicated rayon pool (LBZIP2_THREADS)
├── bitreader.rs     # 64-bit buffered reader, arbitrary bit offset, peek/consume
├── block.rs         # Single block: Huffman→MTF→BWT→RLE2, thread-local tt pool
├── block_scan.rs    # 48-bit scanner, split_boundaries_parallel, quick_verify
├── bwt.rs           # Inverse Burrows-Wheeler (in-place T-transformation)
├── chunk.rs         # ChunkDecoder: parallel segment decode, pbzip2 support
├── huffman.rs       # 10-bit packed lookup + tree fallback
├── mtf.rs           # Move-to-front: fast n=0/n=1
├── parallel.rs      # In-memory parallel (small files)
├── reader.rs        # StreamingBz2Read + ParallelBz2Read (mmap)
├── stream.rs        # Sequential decoder (reference path)
└── bin/lbunzip2.rs  # CLI: 3-thread pipeline with ring buffer

Benchmarks

Odin — Threadripper PRO 3975WX, 32 cores, 512 GB DDR4

Liechtenstein (5.2 MB → 60 MB, 71 blocks):

Stage breakdown (single-thread):

RLE2 dominates: dependent pointer chain through ~3.6 MB random-access tt[]. Memory-latency-bound. 2-step prefetch helps but cannot break the serial dependency.

Planet (147 GB, 32 cores, per-chunk timing):

Ideas from Claude — Streaming Worker Pool

The Problem: par_iter().collect() Is a Barrier

Right now, rayon decodes all ~255 segments in parallel, but .collect() waits for every segment to finish before any result goes to the writer. Measured on odin (32 cores, planet_1g.bz2):

More oversplit → better efficiency (less tail-wait) but send phase explodes because more segments means more channel sends. The sweet spot is oversplit=8.

The real issue: between decode finishing and the next decode starting, all 32 cores sit idle during carry + send (~60-150ms). That's 6-15% of wall time with zero CPU. On htop you see 100% → 0% → 100% — the sawtooth.

The Idea: Stream Segments Out During Decode

Instead of:

[=== all 32 cores decode 255 segments ===][--- send 255 results ---][=== next chunk ===]
                                           ^ 32 cores idle here

Do this:

[=== 32 cores decode, finished segments flow to writer as they complete ===][=== next chunk ===]
                                                                            ^ no gap

Each core finishes a segment → drops it into an ordered output queue → writer picks it up immediately. No barrier. Decode and send overlap completely.

Implementation: replace par_iter().collect() with N persistent worker threads. Each worker loops: grab next segment index from an atomic counter → decode → put result into a slot array at that index → signal the drain thread. A drain thread walks the slot array in order, sending completed segments to the writer as soon as they're ready (wait only if segment i isn't done yet).

The drain thread is basically: for i in 0..n_segments { wait(slot[i]); send(slot[i]); }. Like a reorder buffer in a CPU pipeline — results arrive out of order, leave in order.

What This Buys

• Zero idle gap between chunks — send overlaps with decode
• Writer starts earlier — first segment arrives after ~30ms instead of ~950ms
• Eliminates the collect() barrier — fast segments don't wait for slow ones
• Natural backpressure — if writer is slow, drain thread blocks, workers keep decoding into remaining slots

What It Doesn't Change

• Total CPU work per block is the same — this just removes idle gaps between chunks
• Won't help much on 8-core laptop (already 90% utilization, small gaps)

Risk

• Ordered output is critical — segments must reach the writer in order
• More complex than rayon par_iter — but not rocket science, it's a reorder buffer
• Need to handle the pre-allocated output buffer idea at the same time to avoid 255 × 7 MB mallocs per chunk (separate concern, but natural fit)

Performance Philosophy

The bzip2 algorithm is from 1996 when computation was the bottleneck and memory was fast. Modern hardware inverted this. The algorithm is identical — the mechanics are adapted:

History

Earlier Benchmark Numbers (Loki — Ryzen 9 7900, 12 cores)

Stage breakdown (Loki, single-thread):

Wishes for bzip2-rs Crate

API changes that would have made parallel decode possible without reimplementing the decoder:

1. decode_block(data: &[u8], bit_offset, max_blocksize) — single-block from arbitrary offset
2. Zero-copy input: &[u8] + bit_offset, not impl Write
3. Expose block boundary scanning or document the 48-bit magic
4. decode_block_into() — write into caller buffer

Without (1) and (2), parallel decode requires reimplementing the full pipeline.