perf(decode): seq decoder branch-prediction architectural refactor (target ~17% cycle recovery)

[polaz]

Diagnosis (baseline = main @ 6a8e6c7, post-#281)

L-3 fast on z000033, i9-9900K, 907 ns/iter, formal perf stat -M TopdownL1:

Topdown category	Share
Retiring	61.0%
Frontend bound	13.9%
Bad speculation	14.1%
Backend bound	11.1%

Frontend drill-down:

Counter	Value	Note
idq.dsb_uops (µop cache hits)	137.2B (60%)
idq.mite_uops (legacy decoder)	92.3B (40%)	slow path
dsb2mite_switches.penalty_cycles	1.95B cyc (~2.5% total)	µop-cache eviction
frontend_retired.any_dsb_miss	9.77B µops stalled
frontend_retired.l1i_miss	3.2M	negligible
frontend_retired.itlb_miss	16K	negligible
br_misp_retired.all_branches	762M	matches bad-spec category
machine_clears.count	6.3M	minor

Branch-miss concentration:

• 77.64% in decode_and_execute_sequences_avx2 (main pipelined loop)
• 15.42% in do_offset_history_repcode (mitigated post-perf(decode): drop inline_never on repcode resolver, keep cold attr #281)
• 3.68% FSE build (cold, one-time)

Two distinct hot-path bottlenecks

A. DSB µop-cache capacity miss (~13.9% frontend bound)

Skylake-X DSB capacity is 1536 µops. decode_and_execute_sequences_avx2 body is ~13.5 KB → ~3000 µops. Hot loop spills out, 40% of µops fall back to MITE legacy decoder, 1.95B cycles cumulative DSB2MITE switch penalty.

This is NOT L1i miss (3.2M misses, negligible 0.34% of cycles). L1i caches 64-byte lines; DSB caches pre-decoded µops in the front-end. Independent metric. L1i is fine (code fits in 32 KB i-cache), DSB is not (µops don't fit in 1536-µop pre-decode cache).

nm -S shows run_pipelined_sequence_loop produces 8+ monomorphic copies at 8 KB–18.7 KB each — fan-out over (B: BufferBackend × K: CpuKernel). The 18.7 KB peak is the AVX2-inlined variant.

B. Branch mispredict (~14.1% bad speculation)

Already mitigated for repcode resolver in #281 (#[cold] retained, #[inline(never)] dropped → LLVM inlines at hot call sites only). Residual 14% lives in main pipelined loop body — FSE state transitions are data-dependent and largely unlearnable for the branch predictor.

Round 1 attempts (closed)

Attempt	Mechanism	Result
3 — split decode/execute	Two-phase decode-into-vec, then execute-vec	+1.7% wall regression on z000033 L-3 (Vec churn + lost prefetch overlap). Branch preserved at perf/#279-split-decode-execute.
2 — branchless cmov repcode	Rewrite RULES dispatch as pure cmov chain	No-op — fn body is already branchless via select_u32 mask ops.
1 — drop #[cold]+#[inline(never)] (PR #280, closed)	Let LLVM heuristic inline	Cross-corpus regression: z000033 -3.5% but low-entropy-1m L14 +15.9%. Net-negative.
1b — drop #[inline(never)], keep #[cold] (PR #281, merged)	Inline at hot sites only	z000033 -2.9% L-3 / -2.4% L14, low-entropy-1m L14 +1.1% (within noise), high-entropy-1m L14 -1.4%. Net-positive.

Branch-mispredict bottleneck partially closed. DSB capacity bottleneck identified but not addressed.

Round 2 attempts

Attempt	Mechanism	Result
#[inline] hint on impl	Encourage LLVM to inline decode_and_execute_sequences_impl into trampolines so K-specific dead branches fold	No-op: codegen unchanged (12 monomorphic copies, same sizes), DSB penalty 1.95B → 1.91B (within noise), wall flat
K-collapse (avx2/vbmi2 → Bmi2Kernel impl)	All bmi2-capable trampolines instantiate K=Bmi2Kernel to halve K fan-out	Catastrophic +7.7% wall regression: DSB penalty 1.95B → 5.45B (+179%). Trampoline's target_feature(bmi2,avx2) does NOT flow across CALL boundary into a non-inline impl; AVX2 chunked-copy helpers inside the impl body fell back to scalar codegen, blowing up MITE uop share. Reverted.
#[inline(always)] on impl	Force impl body inline into each trampoline so target_feature scope flows through; eliminate K × B non-inline cross-product, replace with one inlined-then-specialized body per trampoline	Mixed: DSB:MITE ratio improved 60:40 → 66.5:33.5 ✓, but dsb2mite_switches.penalty_cycles doubled (1.95B → 3.95B) — bigger inlined trampolines (~13 KB each, 9 copies) still exceed DSB capacity but with more switch boundaries per execution. Wall +0.8% slow. Reverted.
Disable pipelined path entirely (donor short-loop shape)	Force every block through the simple decode-then-execute fallback, matching donor's ZSTD_decompressSequences_body which donor reserves the prefetch pipeline for windowSize > 128 MB workloads	+3.2% wall regression on z000033 L-3. DSB2MITE penalty 1.95B → 3.85B (+97%). Pipelined path's prefetch overlap is worth more than its DSB cost on z000033 L-3; removing it exposes match-source load latency. Reverted.
ADVANCE 8 → 4 (halve ring depth)	Smaller ring → fewer prefill/drain iterations + tighter inner-loop ring indexing → shrink DSB footprint while keeping prefetch overlap	+1.5% wall regression on z000033 L-3 / +1.2% L14. 4-deep prefetch lookahead is insufficient to fully hide match-source load latency; the gain from smaller ring is overwhelmed by exposed memory stalls. Reverted.

Round 2 conclusion

Five interventions tried, all net-negative or no-op:

1. #[inline] — no-op
2. K-collapse — +7.7% (AVX2 codegen broken)
3. #[inline(always)] — +0.8% (more switch boundaries)
4. Disable pipelined path — +3.2% (lost prefetch overlap)
5. ADVANCE 8→4 — +1.5% (insufficient prefetch lookahead)

Lessons:

• Pipelined path IS productive on z000033 L-3 (prefetch overlap > DSB penalty)
• 8-deep ring depth is correctly tuned for our target windowSize
• DSB capacity miss is real but tied to inherent loop body size — annotation tweaks can't shrink it
• K monomorphization can't be collapsed without losing inlined helpers' target_feature scope

The remaining theoretical lever — per-instruction µop audit of run_pipelined_sequence_loop — requires surgical refactoring (scratch spill elimination, ring write merging, prefetch_pos arithmetic compaction) rather than annotation changes. That's a multi-day investigation outside the scope of a round-2 dial-tweak session.

Outside this issue's scope but related (i686 amplification): compare_ffi shows decompress regression of 50-60% relative to FFI on i686 (no AVX2). Same architectural cause but amplified because i686 has no exec_sequence_inline fast path (#[cfg(target_arch = "x86_64")] excludes i686) and 32-bit u64 math doubles per-op cost. i686 may need a separate path entirely.

DSB capacity remains an open problem. Round-2 closed without a shippable decoder fix. Future work either:

• PGO / target-cpu pinning at compile time (build-system-level)
• Per-instruction µop audit + surgical body shrink (research)
• Move attention to the orthogonal allocator-pressure axis (see independent finding below) — likely lower-hanging fruit at this point

Independent finding: allocator pressure on decompress

compare_ffi_memory peak-alloc figures show Rust uses 2-3× more memory than FFI on decompress across the entire corpus:

Scenario	Level	Rust peak	FFI peak	Δ
small-4k-log-lines	L3 dfast	143 KB	100 KB	+43%
decodecorpus-z000033	L3 dfast	3.36 MB	1.12 MB	+201%
high-entropy-1m	L3 dfast	2.10 MB	1.14 MB	+84%
low-entropy-1m	L3 dfast	2.10 MB	1.14 MB	+84%
large-log-stream	L3 dfast	29.4 MB	16.9 MB	+74%

Excess working-set fragments TLB / L2 / L3 → indirect wall-time cost on cold-start and bursty decode workloads. The z000033 +201% case is particularly stark because the decoder over-allocates ~2.24 MB above donor for a 1 MB output. Likely culprits (need attribution): persistent scratch over-allocation in DecoderScratch (literals_buffer, sequences, block_content_buffer), FSE table footprint (3 × ~6 KB tables), HUF table, RingBuffer DecodeBuffer at window-size headroom.

This is an independent optimization axis from DSB pressure but related at the L1/L2 cache layer. Tracked via issue #211 (per-alloc-site memory tracker) as the path to identify which call site is responsible.

Bad-spec residual

The ~14% bad-speculation share remaining after #281 lives in the main pipelined loop body — FSE state transitions are data-dependent and largely unlearnable for the branch predictor. Donor's bmi2.constprop.0 has the same bad-spec category at similar share; the absolute gap closes mainly via DSB and allocator improvements.

Measurement protocol

Baseline: 907 ns/iter on z000033 L-3 fast, DSB:MITE 60:40, DSB2MITE penalty 1.95B cyc.

Round 2 target: shift DSB:MITE to 90:10+ (eliminate the µop-cache capacity miss). Estimated wall win 4-7% if fully closed (1.95B cyc penalty + cascading µop-delivery starvation in frontend_retired.any_dsb_miss).

Reproduce on bench host (i9-9900K, Skylake-X):

ssh 192.168.1.200 'cd ~polaz/projects/structured-zstd && \
  cargo build --release --example profile_decode_direct && \
  perf stat -e idq.dsb_uops,idq.mite_uops,dsb2mite_switches.penalty_cycles,\
br_misp_retired.all_branches,cycles \
    -- target/release/examples/profile_decode_direct \
       /tmp/z000033_l3fast.zst 1022035 20000'

Fixture: zstd --fast=3 -f zstd/decodecorpus_files/z000033 -o /tmp/z000033_l3fast.zst (1,022,035 uncompressed → 634,660 bytes).

Cross-corpus validation required per attempt (z000033 L-3/L14, low-entropy-1m L-3/L14, high-entropy-1m L-3/L14). Round-1 PR #280 shipped a z000033 win that regressed low-entropy +15.9%; gate every round-2 candidate on the same matrix.

Stop conditions per round-2 experiment

• DSB:MITE ratio improves but wall time regresses → side effects dominate; revert
• DSB ratio improves AND wall time improves → keep, expand
• DSB ratio unchanged → wrong hypothesis; switch to inner-loop µop-budget audit

Related

• perf(decode + encode-greedy): close 3-5× donor gap on negative-level decompress; share SIMD primitives + add dedicated greedy strategy #178 (umbrella negative-level decode gap)
• perf: top-level CpuKernel dispatch at FrameDecoder/FrameCompressor entry + FSE Entry layout #247 Part 2 (CpuKernel dispatch — baseline this work sits on)
• perf(decode): drop inline_never on repcode resolver, keep cold attr #281 (merged round-1 fix for repcode resolver call/ret BTB pressure)

[coderabbitai]

🔗 Related PRs

#42 - perf(decoding): optimize sequence execution with overlap fast paths [merged]
#90 - perf(decoding): branchless offset history, prefetch pipeline, and BMI2 triple extract [merged]
#92 - perf(decoding): SIMD HUF kernels with runtime dispatch [merged]
#194 - perf(decode): fused sequence executor + SIMD/FSE hot-path cleanup + DoS-safe rollback [merged]
#227 - perf(decode): 8-slot software prefetch pipeline for sequence execution (#208) [merged]
#254 - perf(decode): #247 Part 2 — kill divb in repeat_short_offset + force-inline UserSliceBackend::extend [merged]
#263 - perf(decode): inline sequence executor for direct path + auto-route decode_all (z000033 −24%, high-entropy-1m parity) [merged]
#269 - perf(decode): route short-block fallback through inline executor (z000033 −25%) [merged]
#281 - perf(decode): drop inline_never on repcode resolver, keep cold attr [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!