feat: encoder architecture rewrite (split monolith, const-generic Strategy, arena allocator)

[polaz]

Summary

Full architectural rewrite of the encoder pipeline: split the 9000+ line monolithic match_generator.rs into a module hierarchy, introduce const-generic Strategy dispatch, switch to raw arithmetic by default (drop hot-path saturating_* defensive ops), and ship LDM + block splitting on top of the cleaner foundation.

This is a prerequisite for clean integration of #18 (LDM) and #23 (block splitting) — both currently sit in Matcher-trait territory that is hard to extend in the current monolith.

Update (post-Phase 2): The original plan also called for a ZSTD_cwksp-parity arena allocator. After Phase 2 measurement that work was deferred: Rust's Vec-based scratch already amortizes per-frame allocation across frames via mem::take / clear, so the donor's "single cwksp + cursor reset" model does not translate to a measurable win without unsafe pointer juggling to publish multiple disjoint &mut [T] slices out of one buffer. Revisit only if a flamegraph identifies Vec metadata / allocator traffic as a hot spot. See #120 / PR #121 for full rationale.

Update (PR #354 — merged): Phase 7 config + block-split rework.

• LEVEL_TABLE → donor clevels.h (default row): L3/L4 (dfast), L5 (greedy), L6-15 (lazy) now carry the donor windowLog / hashLog / chainLog / 1<<searchLog / targetLength values verbatim. The larger-than-donor preset windows are dropped (Better=L7 and Best=L11 now use donor windows 21 / 22, not the old 8 / 16 MiB; BETTER_WINDOW_LOG const removed).
• Per-strategy Option<…> config: LevelParams now holds fast / dfast / hc / row as Option, exactly one Some per row (the strategy's backend) — the table self-documents which knobs a level consumes instead of carrying dead placeholder values.
• dfast hash sizing config-driven: new DfastConfig { long_hash_log, short_hash_log } per level (L3 = 17/16, L4 = 18/18 donor), replacing the hardcoded DFAST_HASH_BITS = 17 clamp ceiling that capped L4 below its donor hashLog of 18.
• Donor-correct pre-split — see the Phase 6 update below.
• Decode exec-macro monolith: the AVX2 match-copy ZSTD_execSequence body is fused into the per-tier sequence loop via macro_rules! (a #[target_feature] fn can't be #[inline(always)], rust#145574), and the same fuse is shared to the VBMI2 and BMI2 tiers. ~−4.4 % decode on z000033 vs prior (closes the gap to C ~1.53× → ~1.40×; still slower than C in absolute terms).
• Bench (i9, z000033): ratio beats C at L1-L4 and L11 (e.g. L11 465 120 vs C 509 326); encode +20-31 % vs prior main (the block-split + deeper donor search cost); decode −4.4 % vs prior.

Update (2026-06-11): Greedy (L5) and the whole Lazy band (L6-12) now run on the Row finder (reference ZSTD_resolveRowMatchFinderMode parity) with donor clevels.h row configs, donor mask-iteration probing, and the 4-byte rep gate; L13-15 carry a real monotonic ladder (Btlazy2). The reused-compressor path is zero-allocation per frame at every level band (row-table width oscillation, estimator workspace, Huffman seed clone, frame-header temporaries, BT dms tree rebuild — all eliminated), which closed the musl compress-dict outsiders (5.5×). Dfast L3/L4 got the donor greedy double-fast reshape + monolithic kernel inlining. These continue Lane A: 7-compress-better groundwork landed via the Row switch; 7-compress-fastest re-measured at 0.57× donor (from 0.44×).

Motivation

PR #110 (perf/level22-donor-parity) closed level22 gap to C donor FFI from ~2.45× → ~2.22× through intrinsics refactor and saturating cleanup. After deep-reading the donor (zstd_opt.c / zstd_lazy.c / zstd_compress_internal.h) we identified the residual gap is driven by architectural shape, not algorithmic divergence:

1. 9000+ line monolith — match_generator.rs mixes cost_model, DP, BT walk, HC chain, Row hash, Dfast in a single struct. Each match self.parse_mode branch is runtime dispatch on the hot path.
2. 158 saturating_* ops — defensive default vs donor's raw arithmetic. Cleanup of cost-model subset alone gave +9.5% on level22, +34% on default (see PR perf(level22): complete donor parity path #110 bench).
3. #[target_feature] ABI barriers — PR perf(level22): complete donor parity path #110 worked around via fastpath umbrella, but full encoder modules under per-CPU specialization not done.
4. chain_table dual-purpose as HC chain AND BT pointers through runtime branches — donor specializes via templates so dead code is dropped.

Approach

Each phase is a separate PR.

Phase 1: Structural split — ✅ DONE

Phase 1 split across four merged PRs:

• Phase 1 / 1a (refactor(encoding): #111 Phase 1 — structural split of match_generator monolith #113): structural split of match_generator.rs monolith.
• Phase 1b (refactor(encoding): #111 Phase 1b — extract shared match-finder helpers #116): extract shared match-finder helpers.
• Phase 1c (refactor(encoding): #111 Phase 1c — extract Simple matcher into simple/ #117): extract the Simple matcher into simple/.
• Phase 1d (refactor(encoding): #111 Phase 1d — split HcMatchGenerator into MatchTable / HcMatcher / BtMatcher #118): split HcMatchGenerator into MatchTable / HcMatcher / BtMatcher (ownership boundary).
• Phase 1e (refactor(encoding): #111 Phase 1e — migrate methods off HcMatchGenerator (Stages A–D) #119): migrate ~95 methods off HcMatchGenerator onto the per-backend impls (Stages A–D), introduce enum HcBackend { Hc, Bt(Box<BtMatcher>) } so HC modes no longer carry the ~4 KiB BT scratch payload.

Phase 2: hot-path saturating_* cleanup — ✅ DONE (#120 / PR #121)

Delivered:

• Frame-level overflow gate check_stream_abs_headroom (STREAM_ABS_HEADROOM = HC_OPT_NUM + 16) wired into every match-finder backend (MatchTable, DfastMatchGenerator, RowMatchGenerator).
• 4 hot-path body macros converted from saturating_* to raw arithmetic.
• bt_pair_index_for_abs migrated to wrapping_add (modulo-ring semantics).
• Underflow-guard saturating_sub sites intentionally kept (different concern).

Measurements: −10 % to −19 % on level22. C FFI gap narrowed from 2.95× to 2.39×.

Arena allocator deferred — see Summary update above.

Phase 3: const-generic Strategy dispatch — ✅ DONE (PR #123)

Delivered:

• Strategy trait with seven ZST implementors (Fast / Dfast / Greedy / Lazy / BtOpt / BtUltra / BtUltra2); associated consts BACKEND, MIN_MATCH, ACCURATE_PRICE, FAVOR_SMALL_OFFSETS, USE_HASH3, USE_BT, OPT_LEVEL, MAX_CHAIN_DEPTH, SUFFICIENT_MATCH_LEN.
• LevelParams.strategy_tag: StrategyTag as single source of truth.
• MatchGeneratorDriver::compress_block::<S> const-folds per monomorphisation.
• Full rip-out of enum HcParseMode + enum MatcherBackend; parse_mode field gone.
• CI infra: bench matrix split target × level (18 shards), wall-clock 45 min → 25 min.

Perf result: original #122 targets not hit on host because runtime reads were already cache-hot. Structural foundation is the real deliverable.

Phase 4: bt/hc/opt module clean — ✅ DONE (#124 / PR #125)

Delivered:

• 4.1 — HC speculative tail check (donor zstd_lazy.c:714 parity). Gate skips common_prefix_len walk when 4-byte tail compare proves the new candidate cannot strictly outscore best. Backward-extension-aware bound tail_off = best.match_len − lit_len − 3.
• 4.2 — matchEndIdx − 8 skip audited, not applicable. Donor construct is a cache-prefetch heuristic, not a correctness skip.
• 4.3 — MatcherStorage enum dispatch. Replaced four parallel backend fields with a single tagged enum.
• 4.4 — strategy_tag sweep. Audited every remaining match self.…parse_mode; none survived Phase 3 cleanup.
• Bonus: Dfast donor post-match rep-0 extension (extend_with_repcode_after_match).

Phase 5: LDM module — ✅ DONE (#18 / PR #139, merged 2026-05-15 as 05036ced)

Donor-parity port of lib/compress/zstd_ldm.c v1.5.7. Delivered:

New module encoding/ldm/ (5 files, ~600 LoC core + ~1000 LoC tests):

• gear_hash.rs — verbatim 256-entry GEAR_TAB from donor zstd_ldm_geartab.h, GearHashState with init/reset/feed, hash_rate_log.min(63) defensive clamp.
• params.rs — LdmParams + adjust_for(window_log, strategy) port of ZSTD_ldm_adjustParameters (zstd_ldm.c:135). Runtime assert!(strategy in 1..=9) (not debug_assert!) prevents u32 underflow in 7 − strategy/3 on out-of-range strategies.
• table.rs — bucket-based hash table with position_base rebase scheme. LdmEntry.offset is u32 relative+1 to position_base; ensure_room_for loops over REBASE_GUARD_BAND = 1 << 30 shifts so multi-guard-band jumps cannot leave rel > u32::MAX − GUARD_BAND. insert() rejects offset == 0 (empty-slot sentinel) with a runtime assert!. Hardened insert_absolute with checked_sub().unwrap_or_else(panic!).
• search.rs — count_backwards_match + find_best_match with FindBestMatchInputs struct. Filter is inclusive lower bound (match_abs < lowest_index_abs rejects; entries at exactly lowest_index_abs survive).
• mod.rs — LdmProducer aggregator + generate_into(live_history, history_abs_start, block_start_abs, block_end_abs, out) pipeline.

Wired into BtMatcher::prepare_ldm_candidates (bt/mod.rs) behind #[cfg(feature = "hash")]. Uses MatchTable::live_history() + raw current_abs_start + current_len (no min(...)); frame-level check_stream_abs_headroom guarantees the invariant.

Activation policy: LDM never auto-enabled on any CompressionLevel preset — mirrors upstream ZSTD_compress(..., level) which gates on explicit ZSTD_c_enableLongDistanceMatching. Opt-in surface deferred to #27.

Feature gating: entire module gated behind hash feature for no_std support. [package.metadata.docs.rs] switched from all-features = true to explicit features = ["std", "hash", "dict_builder"] to exclude rustc-dep-of-std / bench_internals / fuzz_exports.

Tests: 474 lib tests (default features) + 10 doctests + 472 lib tests (--no-default-features). Two regression tests for the rebase code path: ensure_room_for_rebases_above_guard_band (single shift) + ensure_room_for_loops_across_multiple_guard_bands (5×guard-band jump, gated #[cfg(target_pointer_width = "64")] because 5 * REBASE_GUARD_BAND = 5 GiB overflows usize::MAX on i686). One regression test for the sentinel guard (insert_panics_on_sentinel_offset_zero).

Docs: README rewritten for early adopters (P1–P9 plan, no perf numbers). docs.rs preamble + per-module preambles overhauled.

Phase 6: Block splitting — ✅ DONE (#23 / PR #140, merged 2026-05-16 as 1e0f6954)

Donor-parity port of lib/compress/zstd_preSplit.c v1.5.7 wired into the frame compressor's main loop. Delivered:

• donor_split_block_by_chunks (already in place from earlier work): the donor _byChunks algorithm — 8 KiB chunk sliding window with 1024-slot fingerprint, threshold-driven split point detection with penalty decay. Active for Level(16..=22) with split_level = 4 (donor's btopt/btultra/btultra2 default).
• donor_split_block_from_borders (new in feat(encoding): #23 add donor _fromBorders pre-split heuristic + broaden level coverage #140): port of ZSTD_splitBlock_fromBorders (zstd_preSplit.c:198). Two 512-byte byte-histograms from each end of the 128 KiB block drive the split decision; a third 512-byte sample from the midpoint disambiguates 32 KiB / 64 KiB / 96 KiB. Touches at most 1.5 KiB of input regardless of block size — per-block cost is flat (median +1.2% encode latency overhead on a 4 MiB homogeneous fixture at Level(13), well below p99 jitter).
• Level coverage (as shipped in feat(encoding): #23 add donor _fromBorders pre-split heuristic + broaden level coverage #140): donor_pre_split_level mapped Level(11..=15) → Some(0) (borders), Level(16..=22) → Some(4) (byChunks at internal level 3); Fast / Default / Better and Level(<11) kept the no-split behaviour. Dispatch happens once per 128 KiB block via donor_optimal_block_size, gated on savings >= 3 and full-block preconditions. Superseded by PR perf(codec): per-strategy block-split levels + per-tier exec-macro seq monolith #354: pre_split is now keyed by strategy to mirror the donor splitLevels[] table (ZSTD_optimalBlockSize) — Fast → 0, Dfast → 1, greedy / lazy → 2, lazy2 / btlazy2 (Lazy tag at lazy_depth == 2) → 3, btopt / btultra / btultra2 → 4. So Fast (L1-2), Dfast (L3-4) and Default now split too, and the split path is wired into the Fast one-shot loop (run_borrowed_block_loop) in addition to the owned loop.
• Sub-block emission: when the splitter returns a length < MAX_BLOCK_SIZE, the frame compressor shrinks the current block, parks the suffix as pending_input, and emits the next iteration on it. Each emitted sub-block is a regular zstd block with its own header and entropy tables — superblock-style independent Huffman/FSE per sub-block is implicit in the existing per-block entropy pipeline.

Tests: 4 new tests pin the borders semantics — keeps_homogeneous_block (block.len() early-return on identical fingerprints), returns_midpoint_for_centred_transition (exact 64 * 1024 assertion for the centred-transition fixture, replaces the looser matches!(32K|64K|96K) check), donor_pre_split_level_dispatches_by_compression_level (level → split-level mapping), and level_13_borders_split_roundtrips_through_own_decoder (end-to-end 256 KiB heterogeneous payload at Level(13) round-trips bit-exact through FrameCompressor + FrameDecoder).

Perf (Level(13), 4 MiB fixture, clean rebuilds): borders ON vs OFF, median encode latency: homogeneous-4M 19243 → 19009 µs (+1.2%), heterogeneous-4M 18766 → 18655 µs (+0.6%). Both within p99 jitter.

Phase 7: Per-level FFI parity tuning

Goal: drive every compression level (-7..=-1, 1..=22) to FFI-donor parity on three axes — compression ratio, encode/decode throughput, peak allocation bytes — measured against the published baseline tag.

Phase 7 baseline infrastructure — ✅ DONE (#143)

Delivered:

• compare_ffi_memory bench binary (new, separate from compare_ffi timing bench). Installs a #[global_allocator] tracking wrapper + routes libzstd's ZSTD_customMem callbacks through the same atomic counters via System.{alloc,dealloc} bypass. Single observer, byte-exact for both Rust and FFI sides. Override on realloc so Vec growth doesn't double-count.
• compare_ffi strip: timing/ratio bench now runs on a vanilla system allocator — no allocator wrapper, no RSS sampler, no customMem hooks on the criterion path. Timing samples unbiased.
• CI bench-matrix reshape: PR shards run only the canonical pair (level_3_dfast + level_22_btultra2) bundled in one shard per target (3 PR shards); main pushes run strategy-grouped shards (one per Fast/Dfast/Greedy/Lazy/BtOpt/BtUltra/BtUltra2 family × 3 targets = 21 main shards). Memory bench runs only on main pushes. github-action-benchmark alerts fire only on the canonical pair.
• CI isolation gates: (1) compare_ffi and compare_ffi_memory must not require bench_internals in Cargo.toml (tomllib parse). (2) zstd/src/ may not contain TrackingAllocator / ALLOC_PEAK / ALLOC_CURRENT / TRACKING_ENABLED / ZSTD_customMem / customMem( identifier references (comment-only mentions allowed via rg -v filter).
• Dfast initial parity (Level 3): DFAST_HASH_BITS ceiling 20 → 17 (donor clevels.h:31 Level 3 sizing); slot storage [usize; 4] → [u32; 4] + position_base rebase scheme (donor ZSTD_window_reduce parity). Result on decodecorpus-z000033 Level 3: Rust peak 70 MB → 9.7 MB (7.2× ↓), throughput 9.89 → 16.0 MB/s (1.6× ↑), compression ratio unchanged.
• Sample-count tuning: criterion sample_size reduced 10 → 3 for Corpus/Entropy/Large/Silesia at heavy levels (was emitting "Unable to complete 10 samples in 4s" warnings at level_22_btultra2 / 1 MiB+).

Phase 7 sub-phase taxonomy — REMAINING

Re-scope note (2026-05-17): the original Phase 7 plan had nine per-strategy sub-tasks (7a..7i) numbered by donor source order. In practice the first PR to land Phase 7 work expanded beyond a single strategy into cross-level groundwork (FSE default-table caching, FrameCompressor::new ctor cleanup, Matcher trait surface refactors, raw-pointer aliasing invariants, doc / panic-mode polish). That PR is now classified as Phase 7pre: enablement — prerequisite cross-cutting work that unblocks subsequent per-strategy / per-axis sub-phases. The remaining sub-phases are reordered default-first (Level 3 / Dfast is what users see when they pass CompressionLevel::Default, so closing its gap has highest user-visible impact) and split into four lanes by axis (compress / decompress / memory / tooling) rather than numbered alphabetically.

Each sub-phase takes one PR. Per-PR workflow:

1. Read donor source for the target strategy / module (zstd_fast.c, zstd_double_fast.c, zstd_lazy.c, zstd_opt.c, fse_decompress.c, huf_decompress*.c).
2. Capture baseline ratio + speed + memory from dashboard for the levels under target on decodecorpus-z000033 + silesia-* (when available).
3. Memory breakdown (compress lanes): what dominates Rust peak vs donor's ZSTD_estimateCCtxSize?
4. Algorithm / storage / kernel gap analysis written up in docs/perf/phase7-<sub-phase>.md.
5. Implement narrow refactor (storage rebase, table sizing, kernel rewrite, etc.). Keep production isolation gate green.
6. Bench before/after; ratio gate (level22_sequences_match_donor_on_corpus_proxy etc.) must remain green.

Lane A — Compress (per-strategy, default-first)

Sub-phase	Strategy	Levels	Status	Notes
7pre	enablement (cross-level)	all	✅ DONE (PR #146, merged 2026-05-17)	Cross-level groundwork: FSE default-table cache (&'static AtomicPtr), FrameCompressor::new cleanup, Dfast Level 3 baseline (donor outer/inner loop, MIN_MATCH 5, scalar hash, rep1 peek, distance-driven skip-step, OOB fix, fast-loop rebase, trim_to_window reclaim, probe_tail_ip0_only, short-hash floor enforcement, InnerExit exit-shape enum), Matcher trait surface refactors (trim_to_window per-backend signature, get_last_space empty-safe), raw-pointer aliasing invariant doc, compress_slice_to_vec public API + panic-mode docs. Drives small-1k-random/level_2_dfast 44.25 µs → 6.08 µs (7.3× compress-time speedup, all levels).
7-compress-default	Dfast residual	3	PARTIAL (PR #354)	#354 made dfast hash sizing config-driven (donor hashLog/chainLog via DfastConfig, window 21) — z000033 L3 rust 489 251 < ffi 527 148 (beats C on ratio). Remaining algorithmic deviations: kStepIncr 64 vs 256 audit, initial ip shift / saved-offset rotation (current task #103), block splitter boundary parity vs donor ZSTD_splitBlock (current task #104), branchless ZSTD_selectAddr-equivalent on hash hits (current task #106 — saves a branch per hash slot write on the dfast hot path). Gated on 7-tooling-seq-cmp (#99) for ratio-divergence audit.
7-compress-better	Lazy (preset target)	7	TODO	"Better" preset; donor zstd_lazy.c lazy2 entry.
7-compress-best	BtOpt / BtUltra	16-19	TODO	"Best" tier; BT walk + cost-model verification; opt-array sizing; long-mode tables. Ratio note (2026-06-01 analysis): L18/L19 btultra lose ~3.5% ratio on z000033 (rust 443196 vs ffi 428025). Root cause is architectural: our btopt/btultra route the price parser over HASH-CHAIN candidates (search_depth = chain-walk depth) while donor uses a real BINARY-TREE matcher (ZSTD_BtFindBestMatch, searchLog=6). A 32-deep hash chain finds fewer/worse matches than a binary tree. Real fix = add a BT matcher backend (deep, multi-day); cheap partial mitigation (bump chain depth 32→64) expected to cost speed.
7-compress-entropy	FSE / Huffman / sequence emit (encode side)	all	TODO	Encode-side counterpart to 7-decompress-fse / 7-decompress-huffman. Rewrite the block compressor's entropy emit path (FSE state machine encode, Huffman encode, sequence section serialization) for register-resident state + BMI2 / NEON acceleration where applicable. Per current task #110; affects every level since every compressed block goes through this path.
7-compress-fastest	Fast / Simple	-7..=1	IN PROGRESS	8 negative levels + Level 1; donor zstd_fast.c; hash table sizing per level. Sequence-level parity on Level 1 closed (PR #231 — compare_ffi_sequences on decodecorpus-z000033 Level(1) reports rust_seqs=27763 ffi_seqs=27763 match=27763 (100.0%), root cause was kSearchStrength=6→8). Throughput gap remains: pure_rust ~205 MiB/s vs FFI ~360 MiB/s on i9-9900K BMI2/AVX2 (0.57× donor, re-measured 2026-06-11; was 0.44×). Follow-up scope: matcher hot-loop SIMD intrinsics in compress_block_fast (BMI2 _bzhi_u64 on x86_64, NEON variant on aarch64), profile-guided unroll, donor-equivalent #[target_feature] specialization, branchless cmov-style match-found gate (ZSTD_match4Found_cmov is already on USE_CMOV=true paths but the surrounding scan loop is not vectorized). Target: ≥ 0.85× FFI on level_1_fast/decodecorpus-z000033. Negative levels (Level(-7..=0)) inherit the same hot path — once the SIMD intrinsics land they apply to the whole -7..=1 band.
7-compress-dfast-2	Dfast (Level 2)	2	TODO	Lower Dfast preset; verify Level 2 hash budget matches donor clevels.h:30.
7-compress-greedy	Greedy	5 (numeric)	RATIO DONE (#310 / #184)	Row-matcher acceptance floor ROW_MIN_MATCH_LEN 6→5 (donor parity; clevels.h pins minMatch=5 for the whole L5-15 row band). Numeric Level 5 greedy on z000033 was +4.7% worse, now BEATS C; came with a −4.85% encode speed win (fewer rejected 5-byte matches = fewer literals to entropy-encode). Residual is Row tag-scan SIMD speed — the Row kernel dispatch landed separately in #305/#306.
7-compress-lazy-lower	Lazy (lower)	6-9 (numeric)	RATIO DONE (#310; values tightened #354)	Same minMatch 6→5 row-band fix: L6-15 all beat C on z000033 with large margins, zero regression. Residual is throughput, not ratio. PR #354 additionally aligned L6-12 window / hash / chain / 1<<searchLog to the exact donor clevels.h row values.
7-compress-lazy-upper	Lazy (upper)	10-15	RATIO DONE (#310)	Covered by the same minMatch 6→5 row-band fix (donor pins minMatch=5 through L15). Residual: chain depth / hash log scaling / row-hash gating throughput.
7-compress-btultra2	BtUltra2 residual	20-22	TODO	PR #110 closed level22 to 2.22×; finish to ≤1.5× target.

Lane B — Decompress (NEW, was implicitly out-of-scope of original 7a..7i)

Sub-phase	Scope	Status	Notes
7-decompress-baseline	block_content_buffer 0-fill skip + NEON-overshoot match copy	TODO	Two small mechanical wins (each ~1% decompress, noise-level individually but compounding). Skip Vec::resize(_, 0) zero-fill before read_exact via reserve + set_len (block_decoder.rs:117). NEON-overshoot path in simd_copy::copy_strategy for copy_at_least in 5..15 byte range (currently falls back to scalar). Subsumes current task #112's "top hot funcs" umbrella for the bottom two entries; #112's FSE / Huffman picks fall under the next two sub-phases below.
7-decompress-fse	FSE state machine register-resident + BMI2 (x86) / NEON bit-extract (aarch64)	TODO	Largest single decompress lever. Audit FSE_decompress_usingDTable donor; rewrite state machine to register-resident state, add BMI2 pdep/pext parallel-bit-extract on x86, NEON bit-shift path on aarch64. ~200-500 LoC rewrite.
7-decompress-huffman	Huffman decoder rewrite	TODO	Second-biggest decompress lever. Audit HUF_decompress_4X* donor variants; rewrite for parallelism + table-driven decode. ~200-500 LoC.

Lane C — Memory (NEW)

Sub-phase	Scope	Status	Notes
7-memory-tracker	Per-alloc-site tracker in compare_ffi_memory.rs	TODO	Pre-requisite — gates 7-memory-medium / 7-memory-large. Records backtrace::trace_unsynchronized IPs for allocations ≥ 32 KiB; post-process via atos.
7-memory-medium	Medium 1 MiB scenarios	TODO	After tracker lands: identify dominant Vec / buffer source of +1.2 MiB gap on high-entropy-1m.
7-memory-large	Large 100 MiB stream	TODO	After tracker lands: identify source of +6.1 MiB gap on large-log-stream.

Lane D — Tooling (NEW)

Sub-phase	Scope	Status	Notes
7-tooling-seq-cmp	Sequence-stream comparator (Rust ↔ FFI)	TODO	Pre-requisite for 7-compress-default ratio-divergence audit. Per-sequence diff (offset, lit_len, match_len) on small fixtures so deviations from donor (e.g. the −7% size delta on level_3_dfast/decodecorpus-z000033) can be triaged into "algorithmic win" vs "cost source" vs "missed match upstream skipped".

Lane E — Cross-cutting kernels (NEW)

Optimizations whose code lives outside any single strategy or compress/decompress lane — they touch both sides of the codec or sit in shared infrastructure. Each is one PR.

Sub-phase	Scope	Status	Notes
7-perf-xxh64	SIMD-XXH64 for frame checksum	TODO	Per current task #108. We currently use scalar twox_hash::XxHash64 for the frame-level checksum (RFC 8878 §3.1.3); donor's XXH64_* path is SIMD-accelerated on x86_64 (SSE2 + AVX2 lane variants) and aarch64 (NEON 16-byte parallel mix). Affects both encode (writes the checksum) and decode (verifies it). Expected ~3-4% compress / decompress throughput win on payloads ≥ 64 KiB where the checksum stage shows up in the flamegraph.
7-perf-target-feature	Target-feature umbrella for fastpath kernels	TODO	Ad-hoc holding slot — concrete sub-PRs spawn from this when a flamegraph in any of the per-strategy sub-phases identifies a kernel that would profit from #[target_feature] specialization beyond the existing encoding::fastpath::dispatch_common_prefix_len_ptr umbrella (the only kernel currently behind it). Examples: SVE2 / NEON variants of insert_positions, AVX2 memcmp for long-hash 8-byte equality gates, hand-vectorized XXH64_update (if 7-perf-xxh64 doesn't fully cover it).

target_feature tuning + extra fastpath kernels: by default scheduled as ad-hoc follow-ups inside individual per-strategy sub-phases if flamegraph profitable; when a kernel demonstrably profits across more than one strategy / lane (e.g. an 8-byte memcmp helper used by both Dfast long-hash gate and BtOpt sequence comparison), promote it to 7-perf-target-feature so the umbrella stays a single review surface.

Phase 7 baseline tag

After PR #143 merge: tag main as perf/post-phase6-baseline. Each sub-task PR compares against that tag.

Phase 8: Cleanup (2-3 days)

Test matrix, edge cases, docs, no-std variant.

Total estimate

Phase 7 baseline infra (PR #143) DONE; Phase 7pre enablement DONE (PR #146 merged 2026-05-17). Remaining: 10 compress sub-phases (default-first, incl. encode-side entropy rewrite), 3 decompress sub-phases, 3 memory sub-phases, 1 tooling sub-phase, 2 cross-cutting kernel sub-phases — see "Phase 7 sub-phase taxonomy" above. Each scoped to a single PR. Phase 8 cleanup after.

Acceptance criteria

• Phase 1 merged (refactor(encoding): #111 Phase 1 — structural split of match_generator monolith #113 / refactor(encoding): #111 Phase 1b — extract shared match-finder helpers #116 / refactor(encoding): #111 Phase 1c — extract Simple matcher into simple/ #117 / refactor(encoding): #111 Phase 1d — split HcMatchGenerator into MatchTable / HcMatcher / BtMatcher #118 / refactor(encoding): #111 Phase 1e — migrate methods off HcMatchGenerator (Stages A–D) #119)
• Phase 2 merged (PR perf(encoding): #111 Phase 2 — saturating_* cleanup on hot path #121) — hot-path saturating_* cleanup done
• Phase 3 merged (PR perf(encoding): #111 Phase 3 — const-generic Strategy dispatch #123) — const-generic Strategy dispatch
• Phase 4 merged (feat(encoding): #111 Phase 4 — donor fast paths + Matcher trait #124 / PR perf(encoding): #124 Phase 4 — HC speculative tail check + MatcherStorage enum dispatch #125) — HC speculative tail check + Dfast post-match rep-0 extension + MatcherStorage enum dispatch
• Phase 5 merged (feat: long distance matching (LDM) for compression #18 / PR perf(encoding): #18 Phase 5 — LDM producer (gear hash + bucket table + search/emit) #139) — LDM producer donor-parity, gated behind hash feature
• Phase 6 merged (feat: block splitting for improved compression ratio #23 / PR feat(encoding): #23 add donor _fromBorders pre-split heuristic + broaden level coverage #140) — donor _fromBorders + _byChunks pre-splitters wired into frame_compressor.rs; level coverage 11..=22
• Phase 7 baseline infra merged (PR bench: add real peak-alloc metric for full encode/decode/memory baseline #143) — separate compare_ffi_memory bench binary, single-observer TrackingAllocator + customMem-bypass, CI shard reshape + isolation gates, Dfast Level 3 initial parity (7.2× memory ↓, 1.6× speedup)
• Phase 7pre enablement merged (PR perf(7pre): enablement — donor outer/inner dfast Level 3 + cross-level FSE cache #146): cross-level FSE cache + dfast Level 3 baseline + correctness/soundness polish
• Phase 7 compress lane merged (default-first ordering): every (strategy, level) within target band on ratio/speed
• Phase 7 decompress lane merged: block_content_buffer 0-fill skip + NEON-overshoot match copy + FSE state machine + Huffman decoder rewrite
• Phase 7 memory lane merged: per-alloc tracker + medium / large gap close
• Phase 7 tooling lane merged: sequence-stream comparator
• match_generator.rs reduced to ≤ 1500 LoC (orchestration only) OR removed
• No file in encoding/ exceeds 1500 LoC
• Zero saturating_* calls on the encoder hot path (overflow class — underflow guards kept by design)
• cargo nextest run --features dict_builder 100% pass on every phase
• level22_sequences_match_donor_on_corpus_proxy ratio gate PASS on every commit (held green through Phase 1–5)
• Final bench vs perf/post-phase6-baseline: every (strategy, level) within target band on ratio/speed/memory
• #[deny(unsafe_op_in_unsafe_fn)] opt-in works (Rust 2024 strict mode)
• Public Matcher trait API unchanged (backwards compat for downstream)

Dropped from criteria: arena allocator and "no Vec allocations on per-frame hot path" — measurement-driven decision in Phase 2.

Working rules

1. Each phase = separate PR. Do not bundle phases.
2. Ratio gate on every commit (level22_sequences_match_donor_on_corpus_proxy).
3. Roundtrip + cross-validation tests on every commit.
4. Build clean + clippy clean on every commit (CI x86_64 + aarch64 + i686).
5. Do not roll back if individual phase shows no perf gain — final comparison vs baseline tag after Phase 7.
6. Baseline tag for Phase 7 sub-tasks: perf/post-phase6-baseline (cut from main after PR bench: add real peak-alloc metric for full encode/decode/memory baseline #143 merge). Each Phase 7 sub-task PR compares against this tag.

Blocking relationships

• Blocked by: PR perf(level22): complete donor parity path #110 merge ✅
• Blocks: feat: long distance matching (LDM) for compression #18 (LDM — implemented as Phase 5 ✅), feat: block splitting for improved compression ratio #23 (block splitting — implemented as Phase 6 ✅)

Not in scope

• #26 (magicless format) — orthogonal frame format toggle
• #27 (configurable params API) — public API change, deferred until after rewrite stabilizes internal API. Will surface LDM activation knobs delivered in Phase 5.
• #19 (multi-threaded compression), #72 (parallel block decompression) — explicitly deferred
• ZSTD_cwksp arena allocator — deferred (revisit on flamegraph evidence)

References

• Donor source: zstd_opt.c, zstd_lazy.c, zstd_ldm.c, zstd_compress_internal.h, clevels.h
• PR perf(level22): complete donor parity path #110 (intrinsics refactor)
• PRs refactor(encoding): #111 Phase 1 — structural split of match_generator monolith #113 / refactor(encoding): #111 Phase 1b — extract shared match-finder helpers #116 / refactor(encoding): #111 Phase 1c — extract Simple matcher into simple/ #117 / refactor(encoding): #111 Phase 1d — split HcMatchGenerator into MatchTable / HcMatcher / BtMatcher #118 / refactor(encoding): #111 Phase 1e — migrate methods off HcMatchGenerator (Stages A–D) #119 (Phase 1)
• PR perf(encoding): #111 Phase 2 — saturating_* cleanup on hot path #121 (Phase 2), PR perf(encoding): #111 Phase 3 — const-generic Strategy dispatch #123 (Phase 3), PR perf(encoding): #124 Phase 4 — HC speculative tail check + MatcherStorage enum dispatch #125 (Phase 4), PR perf(encoding): #18 Phase 5 — LDM producer (gear hash + bucket table + search/emit) #139 (Phase 5 / LDM), PR feat(encoding): #23 add donor _fromBorders pre-split heuristic + broaden level coverage #140 (Phase 6 / block splitting)
• Roadmap: Roadmap: structured-zstd feature parity with C zstd #28

[coderabbitai]

🔗 Related PRs

#113 - refactor(encoding): #111 Phase 1 — structural split of match_generator monolith [merged]
#121 - perf(encoding): #111 Phase 2 — saturating_* cleanup on hot path [merged]
#123 - perf(encoding): #111 Phase 3 — const-generic Strategy dispatch [merged]
#125 - perf(encoding): #124 Phase 4 — HC speculative tail check + MatcherStorage enum dispatch [merged]
#143 - bench: add real peak-alloc metric for full encode/decode/memory baseline [merged]
#182 - feat(encoder): strategy-aware literal gates (G4 + G5) [merged]
#194 - perf(decode): fused sequence executor + SIMD/FSE hot-path cleanup + DoS-safe rollback [merged]
#291 - perf(decode): R12 monolithic per-kernel decoder foundation [closed]
#315 - perf(encode): map level 19 to btultra2 + align bench labels to clevels.h [merged]
#319 - perf(encode): drop redundant per-match offset coding in Fast matcher [merged]
#336 - perf(encode): donor-correct block-split + block-precise decode errors [merged]
#364 - feat(wasm): simd128 kernel tier + npm package; LDM bench matrix variants [merged]
#390 - perf(encode): reshape dfast match-find toward donor structure [merged]

---

📝 Issue Planner

_{Check the box below or use the @coderabbitai plan command to generate an implementation plan and prompts that you can use with your favorite coding assistant.}

• Create Plan

---

🧪 Issue enrichment is currently in open beta.

You can configure auto-planning by selecting labels in the issue_enrichment configuration.

To disable automatic issue enrichment, add the following to your .coderabbit.yaml:

issue_enrichment:
  auto_enrich:
    enabled: false

💬 Have feedback or questions? Drop into our discord!