nordisk/znippy
.nornir/zoomies-reasoning.md
# 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`](zoomies-design.md),
> which by rule mentions none of this; the how-to is in [`zoomies-guide.md`](zoomies-guide.md); the
> numbers in [`benchmarks.md`](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`](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`](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.