Roadmap: structured-zstd feature parity with C zstd

[polaz]

Project goal

structured-zstd is a drop-in replacement for libzstd / zstd CLI — same ABI / CLI / feature surface (a superset of upstream: every documented upstream symbol works, plus additional Rust-side higher-level streams). NOT a binary-parity port: compressed output bytes do not have to match upstream — the encoder may make different (and sometimes better) choices. Wire-format interop (frames round-trip both directions, decoder accepts any valid upstream frame) is required; byte-identical reproduction of donor output is not.

Past phases (Phase 1 correctness, Phase 2 coordinode critical path, Phase 3 perf-parity, Phase 4 SIMD, Phase 4B dictionary decode hot path, Phase 5 Fast donor port M1-M8, direct-write decode + skippable frames API + expect-validation setters) have all shipped. Tracking history lives in merged PRs and git log. This roadmap covers what's left.

---

Active path (sequential — do not branch)

#	Issue	What	Status
A1	✅ #246	DoS-safe rollback for the direct-decode path: malformed Compressed blocks past declared FCS return a structured error instead of a release-mode panic.	✅ DONE — reassessed: the direct-decode writers (sequence executor exec_sequence_inline/_avx2, Raw/RLE try_push, tail literals, match-repeat try_reserve) are all fallible as of #263, returning OutputBufferOverflow / FrameContentSizeMismatch; the heavy fallible-trait rewrite was unnecessary. #246 added the Compressed-block regression test + direct-path fuzz target and closed.
A2	✅ #247	Top-level CpuKernel dispatch at FrameDecoder / FrameCompressor entry + FSE Entry layout. One runtime detect → ZST propagated through HUF / FSE / SIMD-copy / bit-reader / match-copy via monomorphization. Lets default rustc build pick up BMI2/AVX2 at runtime without target-cpu=x86-64-v3 build override.	✅ DONE — all five parts merged: Part 1 FSE Entry (#252), Part 2 decoder dispatch (#254/#263 + #291 monolithic + #289/#292/#293/#294/#295 perf chain), Part 3 encoder Row-matcher dispatch (#305/#306), Part 4 memory-copy path parity (#256-#266), Part 5 kernel_* Cargo features (#307).
A3	#178	Negative-level decode gap vs the reference (z000033 at level -1).	⏸ AT KILL-SWITCH — #517 settled the per-sequence questions once per block and fixed the overlapping-match copier: −12.5% instructions, time gap 1.49× → ~1.37×; low-entropy frames now decode 2.4× faster than the reference. The HUF lever does not apply here (negative levels emit raw literals). Every later lever returned <2% or measured worse, and moving code inside the AVX2 loop is at a local optimum for this compiler, so the issue's own kill-switch stops lever-pulling. The remaining gap is spill traffic in frames with many short sequences; it reopens only with a structural idea, not another pointwise edit.
A4	✅ #111 Phase 7	Encoder per-level FFI parity tuning.	✅ CLOSED 2026-06-21 — Phase 1-7 lanes done. Per-level performance work continues as dedicated issues, listed under Background: #337 (optimal parser on small inputs), #493 (level-1 entropy stage), #500 (Fast kernel offBase).
A6	✅ #184	Lazy band investigation — ratio + speed regressions vs FFI on L5-L15.	✅ DONE (#310) — row-matcher minMatch 6→5 (donor parity for the whole L5-15 row band): L5 greedy was +4.7% worse on z000033, now BEATS C; L6-15 all beat C, zero regression; came with −4.85% encode speed win. Residual ratio leads now sit on Fast/Dfast L1/L2 and btultra L18/L19 (separate, tracked under A4).
A7	✅ #27	ZSTD_CCtx_setParameter Rust-side surface — hard prereq for Phase 6.2 (FFI param wiring).	✅ DONE — configurable compression-parameters API shipped.

---

Phase 6 — C ABI / CLI drop-in parity (after active path stabilizes)

Target upstream version: v1.5.7. Vendored headers verbatim + hand-written extern "C" wrappers. Wire-format interop required, byte-identical compressed output NOT required.

Order	Issue	What	Est	Blocked by
6.1	✅ #126	C ABI core: cdylib + vendored headers + simple / context / error / frame-inspection wrappers	10-12d	A4 (#111 stable internal API)
6.2	#127	Advanced + streaming + dictionary C FFI surface. The stable ZSTDLIB_API surface is complete (#400, #409, #413; ZDICT_* shipped earlier in #386). Only ZSTD_c_nbWorkers > 0 remains.	—	#19 (MT)
6.3	#128	zstd CLI v1.5.7 parity. In progress — file selection, display levels, encoder switches, --patch-from, trainers and -b layout landed in #502; unreadable directories under -r fail the run in #528 (#506). Doable next: --train-legacy, --show-default-cparams, --max, -B for -b / --train, upstream --help text. Waiting for #19: -T# / zstdmt real threads, --adapt, --rsyncable. --format=gzip|xz|lz4 stays refused (a dependency-free build; upstream refuses it too when built without those libraries).	3-4d left	6.1 ✅; MT items → #19
6.5	#130	Legacy frame decoders v0.1-v0.4 + per-version Cargo features	14-16d	6.1
6.6	#131	Legacy frame decoders v0.5-v0.7	10-12d	6.5
6.7	#132	Conformance (tests/playTests.sh) + cross-validation + ABI symbol snapshot + reverse-dep smoke	10-12d	6.3, 6.6

Phase 6.4 retired (original Cargo-features subtask folded into 6.5). Phase 6 total: ~66-78 working days.

---

Background / opportunistic

Picked up when active path is blocked or as filler. None block Phase 6.

Issue	What
#337	Optimal parser (L11 on small inputs, L16-L22): small-input speed + L18-L22 synthetic-fixture ratio. The per-frame DP buffer fill is gone (#525, #526: small-4k-log-lines L11 1.79× → 1.51× of the reference); the binary-tree search is the next lever there.
#493	Level-1 entropy stage vs the reference on real data
#500	Fast kernel: emit the offBase it already knows
#72	Parallel block decompression for multi-block frames
#205	HUF burst body x86-64 inline-asm experiment (BMI2) — independent stretch experiment; #247 Part 2 runtime dispatch landed but did NOT subsume this (hand-rolled asm replaces LLVM-generated burst body, separate concern).
✅ #211	Per-alloc-site memory tracker tooling — closed: shipped as the dhat-heap feature wired into the standalone profiling examples

---

Deferred — post-Phase 6 only

Issue	Why deferred
#19	Rust-side rayon MT compression. Strategy doc landed (3 BLOCKERS: matcher pool not per-task ::new(), raw-content prime semantics verification, streaming-shaped job API from day 1). Implementation deferred until drop-in parity (Phase 6) ships. It is what the last items of 6.2 (ZSTD_c_nbWorkers > 0) and 6.3 (-T#, --adapt, --rsyncable) wait for.

lsm-bilateral items shipped ahead of the deferral

These were executed early (consumed by coordinode-lsm-tree):

Issue	What	Status
✅ #172	Skippable-payload visitor callback on FrameDecoder (PR-B).	DONE
✅ #173	FrameEmitInfo block-layout introspection + opt-in per-block XXH64 sidecar (PR-C).	DONE
✅ #176	Skippable Frame Magic Allocations registry + bilateral hygiene policy docs (PR-A bundle).	DONE
✅ #177	Expected-field validation setters on FrameDecoder (expect_dict_id, expect_window_descriptor).	DONE
✅ #174	Block-precise error position on FrameDecoderError (PR-D): lsm-gated FailedToReadBlockHeaderAt / FailedToReadBlockBodyAt variants carrying block_index / frame_offset / FrameBlock.	DONE
✅ #175	Block-subset partial decode (range + recovery) + per-block decompressed byte ranges (PR-E).	DONE (#357)

---

Bilateral commitment status (lsm-tree)

Bilateral commitment with structured-world/coordinode-lsm-tree preserved — fully shipped: PR-A (#176), PR-B (#172), PR-C (#173), PR-D (#174), PR-E (#175). Cross-reference table kept for context:

zstd	lsm-tree counterpart	LSM-T#	Direction
✅ #176	#250	LSM-T1	spec cross-link

[polaz]

Roadmap actualized after merge of #56 (PR #76).

Updated:

• Marked perf: packed FSE Entry layout (4-byte entries + bulk table spreading) #56 as done (perf: packed FSE Entry layout (4-byte entries + bulk table spreading) #56) in Phase 3 table and dependency graph
• Updated Phase 4 dependency note for perf(decoding): SIMD HUF decode kernels with runtime CPU dispatch #66 (blocked-by prerequisite now closed)
• Removed perf: packed FSE Entry layout (4-byte entries + bulk table spreading) #56 from "next actions" list and renumbered remaining priorities
• Recalculated rough remaining estimates (Phase 3 and total)\n\nVerification source: issue perf: packed FSE Entry layout (4-byte entries + bulk table spreading) #56 state = CLOSED, PR perf(fse): pack decoder entries and align decode tables #76 state = MERGED.

[polaz]

Roadmap actualized (2026-04-07):

• Verified referenced issue states against repository issues (no status-marker mismatches found).
• Updated roadmap issue header with wtmp begins Thu Dec 18 20:35:54 EET 2025.
• Recalculated remaining estimate based on currently open roadmap issues:
  • Phase 3: ~5d 1h
  • Phase 4: ~11d 8h
  • Phase 5: ~20d 4h
  • Total: ~36d 13h (~37 working days).

No roadmap items were added/removed in this pass; execution order remains unchanged.

[polaz]

Roadmap actualized after merge of #47.

Changes applied:

• Marked perf(encoding): reuse encoded scratch buffer across streaming blocks #47 as completed in the Phase 3 table (3.10), parallelizable list, and dependency graph (done marker).
• Updated estimates: Phase 3 remaining changed from 5d 1h to 5d; total remaining changed from 36d 13h to 36d 12h.
• Updated Last actualized date to 2026-04-08.

No additional issue status changes were detected in this pass.

[polaz]

Roadmap actualization (2026-04-08):

• verified roadmap issue references against current GitHub issue states
• migrated completed entries from strikethrough format () to issue-mode format ()
• updated Phase 3 to mark as closed
• normalized closed blockers in dependency columns to

Current plan state: completed through Phase 3.11; next highest-impact open queue remains .

[polaz]

Roadmap actualization (2026-04-08):

• verified roadmap issue references against current GitHub issue states
• migrated completed entries from strikethrough format to issue-mode format (✅ #N)
• updated Phase 3 to mark ✅ perf(encoding): rebase HC table positions to remove 4 GiB Better level cutoff #51 as closed
• normalized closed blockers in dependency columns to ✅ #N

Current plan state: completed through Phase 3.11; next highest-impact open queue remains #68 -> #69 -> #66 -> #70 -> #67 -> #71.

Note: previous comment in this thread had shell-escaping artifacts; this comment is the corrected summary.

[polaz]

Roadmap actualized after merge of #67 (PR #84).

Updated in issue body:

• Marked Phase 3 as DONE ✅ and switched 3.12 to ✅ perf(encoding): implement row-based match finder for fast/dfast levels #67
• Updated Phase 3 parallelizable/dependency graph entries to completed state
• Removed perf(encoding): implement row-based match finder for fast/dfast levels #67 from next-actions queue and renumbered priorities
• Recalculated estimates:
  • Phase 3 remaining: ~0d
  • Phase 4: ~11d 8h
  • Phase 5: ~20d 4h
  • Total remaining: ~31d 12h (~32 working days)

Verification source:

• perf(encoding): implement row-based match finder for fast/dfast levels #67 state = CLOSED
• perf(decoding): SIMD wildcopy for literal and match memcpy #68, perf(decoding): branchless offset history, stride prefetch, BMI2 pext #69, perf(decoding): SIMD HUF decode kernels with runtime CPU dispatch #66, perf(encoding): SIMD match-length comparison (SSE4.2/AVX2/NEON) #70, perf: ARM platform optimizations (CRC32 hash, NEON copy, SVE2 histcnt) #71, feat: optimal parsing compression (btopt/btultra/btultra2 strategies) #22, feat: block splitting for improved compression ratio #23, feat: long distance matching (LDM) for compression #18, feat: magicless frame format support #26, feat: configurable compression parameters API #27, feat(encoding): Rust-side rayon-based multi-threaded compression (multi-frame concat) #19, perf(decoding): parallel block decompression for multi-block frames #72 = OPEN

[polaz]

Roadmap actualized after merge of PR #85 (2026-04-09).

Changes applied:

• Marked as complete in Phase 4 and updated critical-path note.
• Reordered next actions to start from (since is done).
• Recomputed remaining estimates: Phase 4 from to , total from to .
• Kept in Phase 4 as the encoding default small-input latency-cliff fix.

Also closed issue #68 explicitly (PR #85 did not auto-close it because it lacked a closing keyword).

[polaz]

Roadmap actualized after merge of PR #85 (2026-04-09).

Changes applied:

• Marked perf(decoding): SIMD wildcopy for literal and match memcpy #68 as complete in Phase 4 and updated critical-path note.
• Reordered next actions to start from perf(decoding): branchless offset history, stride prefetch, BMI2 pext #69 (since perf(decoding): SIMD wildcopy for literal and match memcpy #68 is done).
• Recomputed remaining estimates: Phase 4 from ~13d 8h to ~10d 8h, total from ~34d 16h to ~31d 16h.
• Kept perf(encoding): eliminate default-level small-input dfast reset/table clear cliff #88 in Phase 4 as the encoding default small-input latency-cliff fix.

Also closed issue #68 explicitly (PR #85 did not auto-close it because it lacked a closing keyword).

[polaz]

Roadmap actualization (2026-04-09):

• Marked ✅ perf(decoding): branchless offset history, stride prefetch, BMI2 pext #69 as completed (merged via PR perf(decoding): branchless offset history, prefetch pipeline, and BMI2 triple extract #90 on 2026-04-09).
• Updated Phase 4 critical path: next highest-impact item is now perf(decoding): SIMD HUF decode kernels with runtime CPU dispatch #66.
• Refreshed parallelization notes (removed perf(decoding): branchless offset history, stride prefetch, BMI2 pext #69 from open parallel set).
• Updated dependency graph to show ✅perf(decoding): branchless offset history, stride prefetch, BMI2 pext #69.
• Reordered "next actions" list (now starts with perf(decoding): SIMD HUF decode kernels with runtime CPU dispatch #66, perf(encoding): eliminate default-level small-input dfast reset/table clear cliff #88, perf(encoding): SIMD match-length comparison (SSE4.2/AVX2/NEON) #70).
• Recalculated estimates after perf(decoding): branchless offset history, stride prefetch, BMI2 pext #69 completion:
  • Phase 4 remaining: ~9d 4h (was ~10d 8h)
  • Total remaining: ~30d 12h (~31 working days) (was ~31d 16h).

[polaz]

ROADMAP actualized after merge of #66.

Updated in issue body:

• Marked ✅ perf(decoding): SIMD HUF decode kernels with runtime CPU dispatch #66 in Phase 4 table and dependency graph.
• Updated critical path and parallelization notes (next: perf(encoding): eliminate default-level small-input dfast reset/table clear cliff #88, perf(encoding): SIMD match-length comparison (SSE4.2/AVX2/NEON) #70, perf: ARM platform optimizations (CRC32 hash, NEON copy, SVE2 histcnt) #71, perf(decoding): pre-parsed dictionary handle for repeated dict decode #86).
• Reordered recommended next actions (removed closed perf(decoding): SIMD HUF decode kernels with runtime CPU dispatch #66).
• Recalculated estimates: Phase 4 remaining from ~9d 4h to ~5d 4h; total remaining from ~30d 12h to ~26d 12h.