Repository navigation
perf(decode + encode-greedy): close 3-5× donor gap on negative-level decompress; share SIMD primitives + add dedicated greedy strategy #178
Description
Activity
🔗 Related PRs
#92 - perf(decoding): SIMD HUF kernels with runtime dispatch [merged]
#179 - perf(encoder): donor-parity greedy parse at L4 — ratio + speed win [merged]
#194 - perf(decode): fused sequence executor + SIMD/FSE hot-path cleanup + DoS-safe rollback [merged]
#213 - perf(decode): SIMD-16 fast path for short offsets {1, 2, 4} [merged]
#238 - perf(decode): collapse HUF 4-stream burst-gate to single-cursor olimit [merged]
#269 - perf(decode): route short-block fallback through inline executor (z000033 −25%) [merged]
#278 - perf(encoding): HUF_flags_preferRepeat for fast strategies + small literals (#23G6) [merged]
#331 - perf(encode): close level-5 greedy speed gap (row match-span cap) [merged]
#377 - perf(decode): cut HUF/FSE entropy-build overhead on the decode hot path [merged]
📝 Issue Planner
Check the box below or use the
@coderabbitai plancommand 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!
- added a commit that references this issue
on May 18, 2026 Reopening — dashboard alert resurfaces the same regression on a different cell:
x86_64-gnu • scenario • stage:level • none • decodecorpus-z000033 + stage=decompress, level=level_-7_fast, source=rust_stream: 0.1517 (-84.83%) outside band
Fresh i9-9900K (Linux, BMI2/AVX2) measurement on current main confirms:
- rust pure_rust: 6.84 ms
- ffi c_ffi: 854 µs
- gap: 8× slower (15.17% of ffi speed, matching dashboard's -84.83%)
The Phase 1 (dedicated greedy strategy) and Phase 2 (SIMD primitives) acceptance items from this issue partially shipped via PRs #213 (SIMD-16 for short offsets), #194 (fused sequence executor), #197 (LL/ML pack), #227 (8-slot prefetch pipeline) — but the structural gap on the negative-Fast / rust_stream cell persists. Phase 3 (decode_blocks slim-down) never landed.
Dispatching a fresh flamegraph to localize the residual hot spot. Will post diagnostic + tracking plan in a follow-up.
- added 4 commits that reference this issue
on May 23, 2026 - added a commit that references this issue
on Jun 9, 2026 - added 11 commits that reference this issue
on Sep 1, 2026
Status (re-measured)
The original 3-5× negative-level decode gap is closed to 1.3-1.4×; the missing dedicated greedy strategy has landed. This issue now tracks the residual negative-level decode parity work only.
Current numbers (i9, decodecorpus-z000033, level_-1_fast):
c_streamrust_streamLanded since the original report
Greedy strategy: dedicated
StrategyTag::Greedy(L5) withlazy_depth = 0on the Row finder — the reference's own greedy shape (its greedy/lazy share the row-search template with depth 0). The L4 dfast outlier was separately closed by the donor greedy double-fast port.XXH64 frame checksum: gated on the frame's checksum flag (−61% on flag-off frames) and hashed per-block while cache-hot on the direct path; no longer a post-decode cold walk.
Per-kernel decoders: four ISA tiers (Scalar/BMI2/AVX2/VBMI2) with monolithic per-tier sequence loops, BMI2 bit-reader specialization, per-tier match-copy chains.
SIMD wildcopy / overshooting copies: donor-shape overshoot-tolerant copies with bounded tails per kernel.
Per-sequence questions settled once per block (perf(decoding): settle per-sequence questions once per block; fix the overlapping-match copier #517): literal slack checked per block, the nonzero offset asserted, the output cursor carried in locals, one bit-reader refill per sequence, and the overlapping-match copier moved to block moves. −12.5% instructions on z000033 at level -1 (runner1, bench profile), time gap 1.49× → ~1.37×; low-entropy frames decode 2.4× faster than the reference.
Residual (~1.37×), and why lever-pulling is paused
HUF does not apply: negative levels emit raw literals, and neither profile has any Huffman decode in it. The whole gap is the sequence loop, one monolith against one monolith with matching profile shape, and it sits in frames with many short sequences.
After #517 every further lever returned under 2% or measured worse: outlining any arm of the loop, freeing live values, fusing the two output-room checks (fewer instructions, slower), handing the FSE advance its entry. Moving code inside the AVX2 loop is at a local optimum for this compiler, and the residual is spill traffic (about 18 extra memory touches per sequence). The kill-switch below is therefore met: this issue reopens only with a structural idea for the loop, not with another pointwise edit.
Kill-switch criteria
Stop pulling individual levers when both stream sources sit within ~1.1× of the reference on the negative-level corpus, or when a lever returns <2% twice in a row (record the negative result and move on).