Roadmap: structured-zstd feature parity with C zstd

[polaz]

Execution order (sequential, focused)

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), but NOT binary parity (compressed output bytes do not have to match upstream — encoder may make different and sometimes better choices). Wire-format interop (frames round-trip both directions) is required; byte-identical reproduction of donor output is not.

Phase 1: Correctness & Core (P0-critical) — DONE ✅

✅ #15 (large-literals panic), ✅ #17 (FSE table reuse + offset history), ✅ #5 (default level dfast/3).

Phase 2: CoordiNode Critical Path (P1-high) — DONE ✅

✅ #24 (bench suite), ✅ #14 (encoder match interleaving), ✅ #12 (sequence execution wildcopy), ✅ #8 (dictionary), ✅ #9 (streaming encoder), ✅ #6 (better level lazy2/7).

Phase 3: Performance Parity (P2-medium) — DONE ✅

✅ #10 (Huffman 4-stream), ✅ #11 (FSE batched refill), ✅ #13 (bitstream reader), ✅ #20 (decoder pre-alloc), ✅ #16 (frame content size), ✅ #7 (best level btlazy2/11), ✅ #21 (numeric levels 1-22), ✅ #25 (FastCOVER), ✅ #56 (packed FSE Entry), ✅ #47 (scratch reuse), ✅ #51 (HC rebase), ✅ #67 (row matcher).

Phase 4: SIMD & Hardware (P1/P2) — DONE ✅

✅ #68 (SIMD wildcopy), ✅ #69 (branchless offset + prefetch + pext), ✅ #66 (SIMD HUF decode BMI2/AVX2/VBMI2/NEON), ✅ #88 (default small-input dfast cliff), ✅ #70 (SIMD match-length), ✅ #97 (early incompressible fast-path), ✅ #71 (ARM CRC32/NEON/SVE2), ✅ #108 (AVX2 unroll-2 wildcopy candidate).

Phase 4B: Dictionary Decode Hot Path — DONE ✅

✅ #86 (pre-parsed dictionary handle).

Phase 4C: Encoder Architecture Rewrite — IN PROGRESS

#111 — split the 9000+ line match_generator.rs monolith, introduce const-generic Strategy dispatch, arena allocator, drop defensive saturating_* from hot path. Internal phases: structural split ✅ → cost_model+arena ✅ → Strategy const generics ✅ → bt/hc/opt clean ✅ → LDM (#18) ✅ → block splitting (#23) 🟡 IN PROGRESS (pre-split borders PR #140 ✅; superblock multi-table + literal-compression decisions still open).

Phase 5: Fast Strategy Donor Port — DONE ✅

#198 — ported ZSTD_compressBlock_fast_noDict_generic to recover the catastrophic 22× regression introduced by phase 1b. Shipped across PR #215 (phase 1a modules), #217 (phase 1b wiring), and #229 (phase 3 — 4-cursor + per-level cParams + cmov + window correctness).

M1-M8 milestones delivered:

• M1: per-level fast_hash_log / fast_mls dispatch in LevelParams
• M2: full 4-cursor ip0/ip1/ip2/ip3 lookahead body + immediate-rep2 inner loop (donor zstd_fast.c:192-420)
• M3: cmov match-found variant + per-window dispatch surface
• M4: beyond-donor fast_hash_log: 13 → 14 for negative levels (+32 KB memory, 2× fewer collisions on structured corpora)
• M6: per-level fast_step_size from donor's targetLength = -level; restores negative-level acceleration gradient
• M7: added donor's missing current0+2 hash insertion after each match emit (zstd_fast.c:407); raised L1/decodecorpus seq match rate 43.1% → 57.7%
• M8: dropped RESERVED_PREFIX_BYTES dummy byte; history layout now matches donor's, sentinel-0 protection via INITIAL_PREFIX_START_INDEX = 1

Headline results on large-log-stream (25 MiB dense):

• Phase 1b state (perf(encoder): wire donor-shape Fast kernel into MatchGeneratorDriver (#198 phase 1b) #217 merged): +122% time vs main (~235 MiB/s)
• Phase 3 (M1-M8): −22% time vs main (~790 MiB/s) — 3.4× faster than phase 1b

Residual ratio gap: L1 Fast +7.43% on decodecorpus-z000033 → tracked as follow-up #220. All other levels in parity or better (lazy band −5.7..−6.2%, btopt L17 parity, btultra2 within ±0.2%).

---

Tier 1 — critical path (sequential, focused)

Strict sequential ordering. No parallel scope expansion until each item completes. Bench / profile / test gates apply to every step before advancing.

Order	Issue	What	Est	Status
T1.1	#111	encoder architecture rewrite (incl. #23 block splitting as internal Phase 6)	~8-13d remaining	IN PROGRESS (Phase 1-5 merged; rewrite Phase 6 #23 in progress)
T1.2	#220	Fast L1 +7.43% ratio residual on decodecorpus	2-3d	OPEN (follow-up to #198)
T1.3	#180	skip_matching_with_hint self-time dominance (~25%) — drop eager block-boundary inserts	1-2d	OPEN
T1.4	#27	configurable parameters API (ZSTD_CCtx_setParameter surface — hard prereq for Phase 6.2)	1d	OPEN, blocked by #111 stable internal API

Phase 6 — drop-in C ABI / CLI parity (after Tier 1 ships)

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

Order	Issue	What	Est	Blocked by
6.1	#126	C ABI core (cdylib + vendored headers + simple/context/error/frame-inspection wrappers)	10-12d	#111
6.2	#127	advanced + streaming + dict C FFI surface (incl. ZSTD_c_nbWorkers inline wiring — does NOT depend on #19)	10-12d	#126, #27
6.3	#128	zstd CLI v1.5.7 parity (argv[0] dispatch, env vars, dict, list/test, -T#)	12-14d	#126, #127
6.5	#130	legacy frame decoders v0.1-v0.4 + per-version Cargo features	14-16d	#126
6.6	#131	legacy frame decoders v0.5-v0.7	10-12d	#130
6.7	#132	conformance (tests/playTests.sh) + cross-validation + ABI symbol snapshot + reverse-dep smoke	10-12d	#128, #131

Note: Phase 6.4 number retired (originally a separate Cargo features subtask, folded into 6.5).

Phase 6 total: ~66-78 working days (~13-16 weeks).

Tier 3 — additional speed/decode after drop-in ships

Issue	What	Est
#72	parallel block decompression for multi-block frames	3d
#184	lazy band investigation — ratio + speed regressions	3-5d
#199	HUF 4-stream rewrite — sentinel-bit refill + 5-symbol unroll + const-generic kernel	4-6d
#205	HUF burst body x86-64 inline asm experiment (BMI2) — may be subsumed by #199	2-3d
#206	block splitter donor-parity vs ZSTD_splitBlock (refinement of #23)	2-3d
#207	strategy-aware literal compression gates G4+G5 (skipLitCheck + minGain)	2-3d
#208	match prefetch 4-stage pipeline for long-distance matches — 🟡 PR #227 open	3-4d
#211	per-alloc-site memory tracker tooling (compare_ffi_memory.rs)	1-2d
#230	dictionary training + dict-driven compress/decompress benches vs FFI	2-3d

Deferred — post-Phase 6 only

Issue	Why deferred	Note
#19	Rust-side rayon MT — expands test matrix + adds bench noise during focus phase	Phase 6.2 (#127) wires ZSTD_c_nbWorkers inline without #19
#171	typed SkippableFrame Rust API (lsm bilateral PR-A)	Banner in body
#172	skippable-payload visitor callback (lsm bilateral PR-B)	Banner in body
#173	FrameEmitInfo + per-block XXH64 sidecar (lsm bilateral PR-C)	Banner in body
#174	block-precise error position (lsm bilateral PR-D)	Banner in body
#175	partial-decode SPIKE (lsm bilateral PR-E)	Banner in body
#176	magic allocations registry docs (lsm bilateral PR-A bundle)	Banner in body
#177	expected-field validation setters (lsm bilateral PR-F)	Banner in body
#46	CLI aliasing decompress	rideable with #128
#49	HcMatchGenerator cross-slice unit test	minor test gap

Bilateral commitment status (lsm-tree)

Bilateral commitment with structured-world/coordinode-lsm-tree preserved. Execution defers until drop-in parity (Phase 6) ships. Cross-reference table kept for context:

zstd	lsm-tree counterpart	LSM-T#	Direction
#171	#251	LSM-T2	blocks lsm wire-format
#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).