Encoder workspace

Retained encoder storage, shared stream scheduling, SIMD dispatch, and writer backpressure live behind the public compressor API.

Ownership and public boundary

Compressor owns one retained encoder, input staging and pending output. Public configuration remains small and copyable. Backend is an opaque, host-validated value: Default detects the host and available() enumerates distinct runnable backends from lower to higher SIMD levels. SCALAR is crate-private under cfg(test) and is included first in the internal unit-test matrix. with_backend selects one through the builder; no SIMD or implementation type is exposed.

fearless_simd/force_support_fallback is enabled only by a dev-dependency. Production dispatch compiles the backends supported by the target; targets with no supported SIMD retain their required portable fallback. Every encoder kernel — fast fragments, copy extension, greedy and Zopfli searches, block assignment and stitching — runs at the one selected backend. Scalar decisions in tag filtering and histogram assignment use Level::is_fallback().

flowchart TD
    Build{Build kind} -->|Production| Native[Target-supported SIMD levels]
    Build -->|Unit tests| Scalar[Force fallback; private Backend::SCALAR]
    Native -->|No supported SIMD| Portable[Required portable fallback]
    Native --> Public[Public Backend::available matrix]
    Scalar --> Matrix[Scalar plus host SIMD differential tests]
    Public --> Select[Select once; retain Backend]
    Portable --> Select
    Matrix --> Select

graph TD
    C[Compressor] --> Cache[EncoderCache: one resolved encoder]
    C --> Staging[undecided input tail]
    C --> Pending[initialized output backing, completed end and served cursor]
    Cache --> Family[Fast / Greedy / HQ]
    Family --> Kernel[retained Backend: dispatch! per block]
    Family --> Search[retained matcher and ring buffer]
    Family --> Entropy[retained splits, histograms, trees and codes]
    Session[public EncoderSession] --> Owner[private SessionCore: borrows Compressor]
    Owner --> Operation[private non-borrowing OperationState]
    Operation --> State[private StreamState]
    Framed[framed resource core] --> Operation
    OneShot[private one-shot driver] --> State
    Dictionary[immutable PreparedDictionary] -. borrowed .-> Family

retained_bytes sums every owned heap allocation, including boxed state and capacity rather than length for vectors. It excludes stack fields, caller output, shared dictionaries and allocator bookkeeping. The allocator-instrumented compressor_memory tests compare this sum with live requested heap bytes at all qualities. With hotpath enabled, each quality first runs through a temporary compressor to initialize profiling storage outside the measured interval. That compressor is dropped before measuring a fresh compressor, so cold workspace allocations and their release remain covered. This is allocation accounting, not a process-RSS estimate.

flowchart LR
    Features{hotpath enabled?} -->|yes| Warm[Compress at this quality with temporary encoder]
    Warm --> Drop[Drop temporary encoder and clear caller output]
    Drop --> Baseline[Record live heap bytes]
    Features -->|no| Baseline
    Baseline --> Fresh[Create fresh compressor and compress]
    Fresh --> Count[Compare live byte delta with retained_bytes]
    Count --> Trim[Trim and verify live bytes return to baseline]

The configured retention policy applies after one-shot completion and when a session drops, including through readers/writers. A finished session can retain its resettable encoder; abandonment invalidates it first. Bounded first drops the storage a greedy encoder parks for match finders of other plans (see Parked match-finder storage); if the full accounting still exceeds the ceiling, it releases the workspace. Session staging and pending buffers obey the same policy. A forgotten session still requires explicit recover; the exclusive borrow alone cannot detect mem::forget.

One scheduler, borrowed complete blocks

core::stream::StreamState owns the phase, resolved block limit and continuation restart flag. core::session::SessionCore owns the compressor/dictionary borrows and delegates to the non-borrowing OperationState shared with framed resource drivers. That state checks logical positions, and translates private encoder errors into EncodeError. One-shot vector and slice entry points call the same scheduler with Finish.

flowchart TD
    Call[Process / Flush / Finish] --> Drain[drain durable pending output]
    Drain --> Pending{suffix remains?}
    Pending -->|yes| NeedOut[NeedsOutput, accept no new input]
    Pending -->|no| Finished{final block already emitted?}
    Finished -->|yes| Done[Finished]
    Finished -->|no| Decide{block end or explicit operation known?}
    Decide -->|no| Stage[stage undecided tail, NeedsInput]
    Decide -->|yes| Source{staging empty?}
    Source -->|yes| Borrow[borrow input block directly]
    Source -->|no| Fill[complete staged block]
    Borrow --> Encode[encode / flush / finish selected family]
    Fill --> Encode
    Encode --> Deliver[direct destination or completed prefix of retained backing]
    Deliver --> Drain

One-shot calls need no staging or pending allocation: all input and its finality are known, and the output is an append destination or a non-resumable slice. Fast encoders write directly to slices with enough fragment reservation and into append destinations through a statically specialized growing bit writer. Fast session blocks that do not fit the caller’s slice, including uninitialized destinations, use the fixed bit writer directly in the compressor’s pending backing storage. Flushes and other encoder families use retained encoder scratch. Before a one-shot append, Compressor::compress_into reserves bound::append_reserve: the full bound for q0/q1, whose bit writer fills the vector’s spare capacity, and for every other quality the reference’s BrotliEncoderMaxCompressedSize (input, four bytes per 16 KiB, six framing bytes), since those append each finished meta-block from scratch and a longer stream just grows the vector. Reserving twice the input there made a cold 1 MiB call’s peak footprint exceed glibc’s adaptive trim threshold, so every call faulted its pages in again. Bit output describes the storage and partial-byte invariants. Slice overflow returns a private output-capacity error; sessions retain the suffix and report NeedsOutput.

stateDiagram-v2
    [*] --> Open
    Open --> Open: emit non-final block or stage tail
    Open --> Flushed: explicit Flush
    Flushed --> Flushed: redundant Flush
    Flushed --> Open: accept new input
    Open --> FinalPending: Finish emits final block
    Flushed --> FinalPending: Finish
    FinalPending --> FinalPending: drain part of output, NeedsOutput
    FinalPending --> Finished: no output remains
    Finished --> Finished: ignore later input
    Open --> Failed: encoder failure
    Flushed --> Failed: encoder failure
    Failed --> Failed: session rejects further processing

FinalPending and Finished share the internal final phase; equality of the served and completed-end cursors distinguishes them. Public is_finished() is true only in the latter. For experimental continuations, the logical position is checked before input acceptance and advanced by consumed bytes. The two-byte restart uses the same scheduler’s flush action. Finished sessions ignore even input that would overflow the logical-position limit.

The one-shot driver shares the streaming finish path described in universal-encoding.md. All output destinations receive the same stream, or an output-capacity error. Vector appends roll back on failure. Slice contents may be partially written on failure, as documented.

Initialized backing and completed output

Compressor::pending retains its initialized length across drains and sessions. Its pending_end marks the completed encoded prefix; served marks the bytes already delivered. The invariant is served <= pending_end <= pending.len(). Bytes after pending_end are initialized scratch, never caller-visible output.

For q0/q1 non-flush session blocks, Delivery grows this backing to FastEncoder::fragment_reserve only when necessary, then calls the existing fixed-slice encoder. It publishes the completed end only after success. This avoids both the scratch-to-pending copy and repeated initialization of retained storage. The fast encoder still owns its partial byte and bit count separately. Flush and higher-quality output copy their unserved suffix into the initialized prefix, extending the vector only when that suffix exceeds its current length.

Draining resets both cursors to zero after the completed prefix is delivered; it does not clear or truncate the backing. Starting, releasing or recovering a session also resets only these cursors. has_pending() compares them, so stale initialized bytes cannot delay Finished or enter the next stream. Releasing the workspace under the retention policy drops the vector as before; accounting continues to use capacity. Encoder failure leaves the new end unpublished and the session failed, so partially written storage is not delivered.

flowchart TD
    Empty[served = end = 0; backing retained] --> Grow[Grow initialized length only if reservation increases]
    Grow --> Encode[Fixed writer encodes into backing]
    Encode -->|success| Publish[Set end to completed bytes]
    Encode -->|error| Failed[Fail session; publish no bytes]
    Publish --> Copy[Copy backing from served to end into caller output]
    Copy --> More{served below end?}
    More -->|yes| Wait[NeedsOutput]
    Wait --> Copy
    More -->|no| Empty

Extending copies across input blocks

Greedy and HQ encoders dispatch their retained Backend and pass a borrowed CommandExtension to the #[simd] extend_last_command; inside the token’s feature context it runs the shared exact match-length scan. Each scan is bounded by both physical wrap points and the remaining input; a fully matching chunk advances the command and repeats after wrapping either index. The dictionary-prefix branch retains its existing seam handling. No public API or error variant changes.

flowchart TD
    Block[Next input block] --> Eligible{Last copy can continue?}
    Eligible -->|yes| Kernel[dispatch Backend: extend_last_command]
    Kernel --> Source{Distance addresses ring?}
    Source -->|yes| Bound[Bound both slices at wrap and input end]
    Bound --> Scan[Exact scalar or SIMD match length]
    Scan --> Advance[Advance command length and block span]
    Advance --> More{Whole chunk matched and input remains?}
    More -->|yes| Bound
    More -->|no| Symbol[Recompute command symbol]
    Source -->|no| Prefix[Existing prefix seam extension]
    Prefix --> Symbol

Reusable entropy and search storage

Fast arena resets clear fixed tables in place while retaining command, literal and tree vectors. The quality 0 arena itself is created by the first fragment that scans for matches, not by the constructor, so a stream stored verbatim never allocates it. Before its first wrap, the ring buffer allocates only the written prefix plus seven lookahead bytes. Its logical size and mask remain fixed. A prefix write appends the new bytes and the zero margin (append_prefix) instead of zero-extending the buffer and copying over the zeros, so each byte is written once. The greedy encoder passes its size hint to the window (expect_input, also on retarget): the first growth then reserves the whole expected prefix, or the complete layout when the hint reaches the window, so a one-shot call does not reallocate and copy the prefix at every doubling. The hint only changes capacity, never the layout. Before reaching the last two window bytes or reading into the tail, it allocates the complete layout and replays deferred tail copies. A short first write retains the reference’s omitted tail range and sentinel. Reset retains capacity and restores the prefix-growth state; subsequent writes restore head and margin bytes. The shared meta-block writer starts with empty vectors and no context-map arena. It materializes scratch only when an entropy code needs it, then retains it. A q2 block using static command/distance codes allocates only literal depths/bits. Full and trivial codes prepare their larger depth and bit tables; the context-map arena is initialized on first use. The Huffman node pool is shared by every code and is never pre-sized: each build counts the symbols it uses and grows the pool to 2 * used + 1 nodes (huffman::nodes_for), so a cold encoder writing a block with a few dozen literals never zero-fills the 1,409-node pool the full command alphabet would need. Nothing in the pool is cleared between builds, because every build writes each node it reads. Block encoders borrow the retained tables. Move-to-front uses bounded stack scratch. Greedy splitters accept their previous split and histogram storage. HQ retains split/cluster/literal-cost storage and the full meta-block shape. Its cost model also retains command prices arranged by insert code and distance policy, with 32 copy-code slots per row. These rows extend the existing symbol price vector outside the dynamic program and are included by capacity in retained_bytes. Blocks below 128 bytes keep only the symbol prefix active and fill one stack row per useful match; a cold short stream adds no retained price storage. A short block after a large one retains the vector’s capacity. Greedy sparse matchers reserve bounded extra pool capacity only after enough buckets have been populated; their position and tag capacities remain part of the same accounting. See the greedy and HQ specifications for the growth rules.

flowchart TD
    Write[RingBuffer::write bytes] --> Lap{before the first wrap and end below size - 8?}
    Lap -->|yes| Reserve[reserve expected prefix, or full layout when the hint reaches the window]
    Reserve --> Append[truncate to head + pos, append bytes, append 7 zero bytes, zero head]
    Lap -->|no| Full[init_buffer total_size, sentinel, replay deferred tail copies]
    Full --> Copy[copy into window and tail mirror, refresh head bytes]

HQ prefix candidates occupy retained workspace. They merge backwards into the existing match arena, without split_off or a temporary merge vector. Earlier arena entries remain unchanged; the ordering remains ascending match length, then smaller distance, with tree matches first on exact ties. Boundary tests pin the tie rule using distinguishable dictionary length codes.

flowchart LR
    Reset[reset logical lengths and validity] --> Search[fill retained matcher / candidate arena]
    Search --> Split[fill retained splits and histograms]
    Split --> Codes[borrow retained entropy tables]
    Codes --> Output[emit completed bytes]
    Output --> Policy{retention policy}
    Policy -->|keep| Reset
    Policy -->|exceed ceiling| Parked[drop parked finder storage]
    Parked -->|within ceiling| Reset
    Parked -->|still over| Drop[drop all owned storage]
    Policy -->|release| Drop

Parked match-finder storage

A greedy encoder reused for a stream whose parameters differ only in the window, the block size, the size hint or the match-finder plan keeps everything but the finder. When the plan changes — the chain finders below a sixteen-bit window and the bucket finders above it at qualities five to nine, the bucket finders’ H5 and H6 at the one-mebibyte hint, or quick storage for short inputs — GreedyEncoder::retarget_for_new_stream builds the new finder and parks the old one’s large tables in ParkedTables:

A plan change therefore costs what a steady reuse costs — clearing counters and chain heads — instead of zeroing a fresh table of up to several mebibytes. Parked storage counts in retained_bytes; the Bounded policy drops it before it would release the workspace, so parking never turns a retained encoder into a released one. The quick finders park nothing: a reused quick table needs a full wipe anyway.

sequenceDiagram
    participant Driver as EncoderCache::acquire
    participant Encoder as GreedyEncoder
    participant Parked as ParkedTables
    Driver->>Encoder: reset_for(params, hint)
    Encoder->>Encoder: same plan? clean finder, reshape window
    Encoder->>Parked: another plan: MatchFinder::rebuilt(plan, parked)
    Parked-->>Encoder: dense storage / chain slots of that kind
    Encoder->>Parked: old finder.park()
    Encoder->>Encoder: reshape window, reset

Cold matcher allocation and SIMD

Quick H2/H3/H4 matchers use SmallSlots when the expected input (the declared size, or a session’s inferred total of at most 4 KiB when its first encode is a finish) is between 1 and 2048 bytes. It stores packed logical hash keys and positions in one open addressed vector; a missing key reads as position zero, exactly like a fresh full table. Keys are bounded by the quick matcher’s logical bucket range, so the all-ones packed value is an unambiguous empty marker even for a u32::MAX position. Linear probing and growth never change the logical slot or candidate order. The vector starts at 32 entries on first insertion, doubles before exceeding half occupancy, and retains capacity across clearing. A small hint may underestimate the stream: growth preserves correctness. Other hints use the full quick table. The matcher variant is selected before scanning, so large-input scans have no compact-map branch inside their loops.

flowchart TD
    Hint[Resolved quick-matcher size hint] --> Small{1 to 2048 bytes?}
    Small -->|no| Full[Full logical slot array]
    Small -->|yes| Map[SmallSlots: packed key and position]
    Map --> Read{Logical key present?}
    Read -->|no| Zero[Read position zero]
    Read -->|yes| Position[Read stored position]
    Map --> Insert[Insert or overwrite same logical key]
    Insert --> Capacity{Next insertion fits half occupancy?}
    Capacity -->|no| Grow[Double capacity and rehash entries]
    Capacity -->|yes| Store[Store key and position]
    Grow --> Store

Bucket matchers own exactly one storage layout; see the greedy encoder for the selection rule and migration state diagram. Sparse generation-stamped entries activate sixteen-slot (one cache line) starter blocks on demand and promote them into a full-block pool on the seventeenth store, leaving the starter allocated until reset or migration. Compact one-shot streams instead link their stores into one chain. Promotion from compact to sparse reuses the larger word buffer; promotion from sparse to dense flattens the larger position and tag pools and releases the unused storage. A prepared sparse or dense table remains in use even for subsequent tiny streams. The dense layout, taken when the matcher’s size hint is at least the shape’s dense limit (on the first stream a thirty-second of the table for the tagged q5 shape, a sixteenth for q6 and an eighth for deep q7–q9 shapes; a sixty-fourth for every shape once the matcher is reused), or switched to mid-stream by a sparse stream whose store rate repays the clear (a fresh table the live buckets are copied into), preallocates every block at key << block_bits, zeroed once per matcher, and clears only its u16 counters per stream. Counters, or the generation stamp, govern validity; a block’s stale bytes are never read. Preparation reports Sweep::SelfCleaning, so a reset neither replays a sweep nor marks the table dirty. A reused compressor may therefore allocate once more on its second stream — the dense table — and nothing after that; the allocator-instrumented tests warm a compressor twice before they count. The quick matchers’ SmallSlots map is sized for the input at preparation, even on a fresh encoder, so it never rehashes during the stream. reset zeroes the entries it already has and extends the same vector when the input needs more, so a larger stream keeps growing one allocation instead of replacing it.

flowchart LR
    Reset["SmallSlots::reset(input_size)"] --> Size["size = next power of two of 2 × input, at least 32"]
    Size --> Zero["fill existing entries with 0"]
    Zero --> Fits{"len >= size?"}
    Fits -->|yes| Keep["keep length and allocation"]
    Fits -->|no| Extend["resize the same Vec to size with zeros"]

Forgetful-chain matchers materialize banks on first touch rather than allocating every bank’s slots up front. Their heads/counters likewise govern validity.

q5/q6 use parallel byte tags. One fearless_simd comparison covers the complete 16- or 32-position bucket; slots fill downwards, so rotating the mask by the newest slot and splitting it at that slot yields the newest-to-oldest order as two ascending scans. Unfilled slots are masked off. The scalar backend, and any starter block, deliberately scan without filtering as an independent oracle. q7–q9 use untagged bucket scans. Per input block the search loop works through a MatchRun view that holds the tables as slices bound once, the way the reference keeps restrict pointers, so a store never forces the loop to reload the table it is about to read.

Each encoder retains the Backend it was built with; detection happened once, when that Backend was created. At every block boundary the encoder matches it with fearless_simd::dispatch! — the only dispatch point — enters the selected feature-enabled body and passes the concrete token to generic inner loops. There is no trait object, per-candidate feature detection or virtual call. Whether an encoder serves an independent parallel worker is the encoder’s const parameter INDEPENDENT (Encoder<true> in the fragment adapter, the default false elsewhere), so serial builds never link the fragment-only kernels. Cache reuse checks the backend and resolved parameter shape before reset.

The outer kernels are #[simd] functions (fearless_simd_macros): each enters the token’s feature context once, with its arguments passed separately to the feature-enabled entry. After matcher specialization, greedy reference generation calls the #[simd] search_positions for its search body, keeping tag and match-length operations in the selected feature context. This static entry stays outside the loop and uses the existing token. Helpers kept out of line on purpose — the greedy accept_cached and accept_candidate measurements, the match_len_tail scan and the four-slot matchers’ match_len_at_current — are #[simd] functions with an #[inline(always)] wrapper: the loop calls the level’s feature-enabled entry directly and the vector compares inline into it. An #[inline(never)] body compiled without the level’s features would instead call a feature-enabled helper per SIMD operation above SSE2 (measured: binary q5–q9 +14–19% time with greedy at AVX2).

sequenceDiagram
    participant Builder
    participant Cache
    participant Encoder as Encoder<INDEPENDENT> (retained Backend)
    participant Inner as generic inner loops
    Builder->>Builder: validate opaque Backend
    Cache->>Encoder: construct with the Backend
    loop blocks and reused streams
        Cache->>Encoder: encode block
        Encoder->>Encoder: dispatch!(backend) once per block
        Encoder->>Inner: call #[simd] kernel, pass S
        opt greedy reference generation
            Inner->>Inner: specialize matcher, #[simd] search_positions with S
        end
        Inner-->>Cache: reference-ordered results
    end

Bounded writer backpressure

The writer retains an initialized 128 KiB outbox; only head..end is live. It does not clear/reinitialize the whole allocation for every sink write. write drains previously owned bytes before accepting new input, pumps a bounded session output, and returns the amount accepted. A sink error after acceptance is deferred until the next drain, so callers do not replay input already owned. Flush and Finish loop over bounded pulls. Finishing forbids new writes even while final bytes await delivery. Fault-injection tests cover every output byte position, short writes, Interrupted, WouldBlock, zero writes and retryable flush/finalization failures.

Verification

Allocator-instrumented tests check retained requested-byte accounting and that a compressor warmed for two streams allocates nothing on the third. Lifecycle and streaming tests cover workspace reuse, retention, abandonment, recovery and writer backpressure. Private tests cover sparse promotion, prefix merge ordering and baseline/host-SIMD equivalence.

See development checks and benchmarking for commands.

Known gaps

• The cache has one slot; alternating incompatible resolved settings (another quality, mode or distance layout) rebuilds it. Windows, size hints and match-finder plans are compatible: see compressor and parked storage.
• Only the dense bucket tables and the chain slots are parked. A bucket finder on its sparse layout (deep qualities seven to nine below their promotion point) rebuilds its index after a plan switch, which still costs about 1% at quality seven and 6% at quality nine on 60–85 KiB inputs.
• Retained-byte accounting excludes allocator overhead and is not process RSS.
• Host-backend tests only exercise instruction sets available on the test host.
• Every encoder kernel, the greedy loops included, is compiled once per x86 level (SSE2, SSE4.2, AVX2, AVX-512): about 1.85x the machine code of the former SSE2-only greedy loops. Running the greedy loops at AVX2 leaves the quality 4 bucket loop with more spills on incompressible input (random 64 KiB q4 +3–4% time, +5% instructions).