nordisk/znippy

znippy-zoomies — reasoning

Class: reasoning. This file holds the why, the trade-offs, and every design we rejected. The descriptive shape we actually run is in zoomies-design.md, which by rule mentions none of this; the how-to is in zoomies-guide.md; the numbers in benchmarks.md. If you want to know "why not X?" — X is here.

f0 — why zoomies exists at all

The goal was one number: decompression throughput on many cores, on the corpora znippy actually handles — JARs, gzip, the 164 GB OSM planet. Every mainstream decompressor is single-threaded per stream (igzip, libdeflate, zlib, unzip); pigz and the C lbzip2 parallelise but only for formats with explicit markers. znippy's inputs are large and awkward, so we needed a decoder that is multi-core in every row of the capability matrix — and to get there without paying a copy per byte on a planet-scale file. Everything below serves those two aims: never copy the input, and keep every heavy stage on a worker, never on a lone reader or writer.

Why "never copy the input" is the load-bearing rule

A 164 GB planet file cannot afford a second owning buffer. If decoders took Vec<u8> (owned) instead of &[u8] (borrowed), every stage boundary would clone. By making the whole decoder family borrow, the planet streams through on one read-copy: bytes land in a slot once, get sliced, decoded in place, and stitched. The rule is contagious on purpose — gatling payloads move (bytes::Bytes moved, never cloned), and the candidate-offset model decodes in place. Any owning copy anywhere would re-introduce the very allocation churn we removed (see B6 below).

Rejected: a streaming-window inflate (zlib/miniz model)

The obvious inflate is a streaming one with a 32 KB sliding window — it handles unbounded output in bounded memory. We rejected it for the full-buffer libdeflate model (whole output allocated up front, no window). Reasons: (1) a streaming window forces a bounds check and wrap on every back-reference; the full-buffer model lets copy::<N> blast vmovdqu straight into the output with no wrap logic. (2) Only a full-buffer decode can be segmented — a mid-stream segment needs its back-references to reach into a decoded prefix that is simply there in the buffer, not evicted from a window. The streaming model and parallel segment decode are mutually exclusive; we chose parallel.

Rejected: streaming inflate ⇒ and therefore OVERWRITE_HEADROOM as UB slack

Because copy::<N> writes a fixed-width SIMD chunk, it can write past the last real output byte. The lazy option is "just make callers allocate a bit extra and hope." We instead made OVERWRITE_HEADROOM (copy::CHUNK_SIZE + 258) part of the API contract: an output region that omits it returns OutputOverflow — a typed error — rather than silently corrupting a neighbour. The point is that "the SIMD copy overran" is a checked condition, not undefined behaviour. In the candidate-offset model where every segment shares one buffer, that guarantee is what makes over-copy safe by construction.

Rejected: per-segment allocation for parallel decode (the pre-B6 layout)

The first parallel layout gave each segment its own output Vec, decoded in parallel, then concatenated. It worked but the allocator was the bottleneck: 163 840 segments = 163 840 allocations, and best-of-5 wall time swung wildly (7.1–11.3 s) as the allocator thrashed. B6 (candidate-offset model) replaced it: one buffer, candidate offsets = prefix sum of generous caps, all segments decode in place, then a forward-seek compaction slides each down to its true offset. Result: 7.12 s → 6.70 s best-of-5 and variance collapsed to 6.7–7.4 s, output byte-identical (see benchmarks.md §3). The allocator churn is simply gone.

Why forward-seek compaction is safe: caps are generous, so actual ≤ cap for every segment, so every compaction move is leftward — a segment only ever slides down into space already vacated. Nothing not-yet-moved is clobbered. The one failure mode, a segment outgrowing its cap, spills to an owned Vec and rebuilds sequentially — rare, never corrupting. We accept a rare slow path to keep the common path allocation-free.

Rejected: barriers between pipeline stages (fork-join per stage)

The tidy pipeline is stage-synchronous: read all, then split all, then decode all, then write all, with a barrier between. We rejected barriers for the no-barrier / self-dispatch design: a worker that finishes a small segment immediately pulls the next item, so fast and slow segments never wait on each other. A barrier makes every stage run at the speed of its slowest unit; self-dispatch runs at the average. This is the whole reason gatling and the ljar binary hit near-linear core scaling.

Why 1→32→1, and never heavy work on the ends

The reader does only a cheap O(n_workers) candidate-offset split — no CPU work. The writer only stitches in order. All heavy stages — boundary-find, decode, parse, encode, sort — ride one worker unit end to end. The reasoning is Amdahl's law made concrete: anything the lone reader or lone writer computes is serial and becomes the ceiling. So we push every gram of CPU onto the N-wide middle. A reader that decoded, or a writer that sorted, would cap the whole engine at one core.

Rejected: SlotFill::Incremental everywhere

Growing each slot to exactly the bytes read is the memory-frugal default and it's right for small or partial inputs. But at planet scale it re-zeroes and re-grows every slot on every chunk — pure waste when every full chunk touches the same region anyway. So SlotFill::Big sizes each slot once (carry_headroom + chunk_size), reuses it, and never re-zeroes. Two policies because the small-input and planet-scale regimes genuinely want opposite things; one knob picks.

Rejected: byte-mode (run) for record-producing workers

gatling::run has the collector concatenate Vec<u8> and cut at a safe_end. That's wrong when a worker produces records (parsed OSM features, Arrow batches) rather than a byte substream — you'd serialize and re-parse. run_typed / TypedCodec / TypedSink let the split pre-cut logical segments so the collector just forwards each Output in order, no reassembly. Two modes because "reassemble a byte stream" and "order a sequence of typed outputs" are different jobs.

Rejected: sync gatling for I/O-bound work

The sync engine binds a thread per in-flight unit — fine when workers are CPU-bound. For I/O-bound fan-out (S3 multi-PUT, network fetch) a thread-per-request wastes threads parked on sockets. The async sibling gatling::io keeps the same no-barrier, ordered, zero-copy invariants on tokio, bounded by max_in_flight instead of ring_slots, with bytes::Bytes moved, never cloned. It is the only tokio-touching part of the otherwise tokio-free workspace (with the iceberg crate) — we quarantined async to exactly where the work is I/O-bound.

Rejected: writing our own static search tree from scratch

For OSM id→position lookup we needed sub-100 ns random lookups over sparse sorted i64 keys. Rather than invent a layout, we derived stree from Ragnar Groot Koerkamp's static-search-tree (MIT, © 2025) — a cache-line S⁺-tree with branchless SIMD compare and prefetched batch traversal. Thank you, Ragnar. Our only original contribution is at i64 width: B=16 nodes (two cache lines) instead of one, which trades a second line-fetch for half the tree height — a win in the RAM-bound regime that mirrors his hugepage results. We validated the port by baseline: our binary-search reference (~1050 ns) matches his (~1150 ns), so the harness is sound (see benchmarks.md §4).

Rejected: cargo bench / criterion for the suite

Criterion is per-crate, wall-clock-noisy, and produces nothing a warehouse can gate on. We run one suite through nornir's Bencher trait (xtask/examples/nornir-bench.rs) that prints a single BenchRun JSON line, historized in Iceberg by git SHA and gated at >10% regression. One artifact, one number per bench, one gate — that is what makes a regression fail CI instead of a human eyeballing criterion HTML.