perf(huff0): investigate shared Huffman weight-description cache between planner and emitter [SPIKE]

[polaz]

Status

Investigation / spike. Outcome may be "doesn't pay off, close." That's an acceptable result — the point is to measure, not to commit to landing.

Context

After #168 + #167, the FSE-encode of Huffman weights still runs twice per emitted compressed-literals block:

1. Planner — compute_block_size_to_compressed (compressed.rs:458): builds a fresh HuffmanTable, calls writeable_table_description_size (= try_table_description_size) which FSE-encodes the weight stream to count bytes. Used in payload + desc to decide raw-vs-FSE literals.
2. Emitter — compress_literals_or_reuse (compressed.rs:1546): independently builds another fresh HuffmanTable (same literals → same counts → same weights), calls writeable_table_description_size again (same FSE-encode), feeds it into decide_huff_reuse_like_encoder. Then HuffmanEncoder::write_table FSE-encodes the weights a THIRD time (the actual emit).

So we currently pay 3 FSE-encodes of weights per emitted block for what is mathematically the same computation on the same input.

What was tried and rejected

#167-followup attempt (commit drafted, then reverted on this branch in the post-#168 work session 2026-05-18): replacing writeable_table_description_size with the cheap_desc_size_proxy upper bound. Result:

• Speed: ~1-2 µs / block — marginal.
• Ratio: decodecorpus-z000033 L18 / L19 worsened by +13 B each (already R > C donor cells; the proxy's conservative upper-bound biases the planner toward raw literals on borderline blocks). Per project rule "Ratio first — if rust_bytes > ffi_bytes we lose vs donor → real bug", any worsening of an already-R-above-C cell is unacceptable.

Single-shot proxy in the planner is not the right path. The planner needs the exact size; the cost we want to eliminate is the duplication, not the exactness.

Proposed investigation

Share the FSE-encoded weight description between the three call sites. Concrete shape to try:

1. Lift table construction out of the duplicate code path. Make compute_block_size_to_compressed (planner) and compress_literals_or_reuse (emitter) consume a single HuffmanTable instance built once per logical block, instead of building two copies from the same counts.
2. Cache the encoded description on HuffmanTable. Add description: OnceCell<Option<Vec<u8>>> (or equivalent interior-mutability slot for &self access — core::cell::OnceCell on the assumption the table isn't shared across threads inside one frame). Populate lazily on the first writeable_table_description_size call; reuse the bytes verbatim in HuffmanEncoder::write_table (currently calls encode_weight_description again).
3. Confirm the emitter's write_table path can ingest pre-encoded bytes — donor HUF_writeCTable_wksp produces the exact same byte stream we'd cache from the FSE encoder; emit becomes writer.append_bytes(&cached) instead of re-running FSE.

Acceptance criteria (kill-switch — must hit ALL)

• No new R > C cells in the compare_ffi REPORT sweep across every supported (scenario, level).
• No worsening (no positive delta) of any existing R > C cell vs the post-perf(huff0): #167 cheap entropy proxy for table_log selection — no FSE-encode per candidate #168 / pre-investigation baseline (f61dde38 on this branch, or the latest main HEAD).
• Measurable speedup (>= 5 %) on compress/level_2_dfast/small-4k-log-lines/matrix/pure_rust vs the same baseline. Below 5 % is not worth the refactor surface.
• All 503/503 lib tests pass; cargo clippy -- -D warnings clean.

If any of these fail, close without landing. The investigation will have produced a measurement + rationale that future work can reference — that is the deliverable, not the code.

Surface area

• zstd/src/huff0/huff0_encoder.rs — HuffmanTable struct + lazy cache, HuffmanEncoder::write_table rework.
• zstd/src/encoding/blocks/compressed.rs — compute_block_size_to_compressed + compress_literals_or_reuse plumbing (share the table).

Estimated size: ~150-300 LoC of code + tests, single PR.

Related

• Part of feat: encoder architecture rewrite (split monolith, const-generic Strategy, arena allocator) #111 Phase 7 Lane A (block compressor entropy coding speed).
• Follow-up from perf(huff0): donor HUF_optimalTableLog fast-path single-shot tableLog with cheap description-size proxy #167 / PR perf(huff0): #167 cheap entropy proxy for table_log selection — no FSE-encode per candidate #168 (cheap entropy proxy for table_log selection).
• Builds on perf(fse): donor FSE_buildCTable_wksp parity — drop per-symbol Vec<State> #166 (FSE_buildCTable_wksp parity, drop per-symbol Vec).
• Surfaced 2026-05-18 during perf(huff0): #167 cheap entropy proxy for table_log selection — no FSE-encode per candidate #168 review cycle.

[coderabbitai]

🔗 Related PRs

#54 - perf(decoding): 4-stream interleaved Huffman decode and bulk table init [merged]
#76 - perf(fse): pack decoder entries and align decode tables [merged]
#90 - perf(decoding): branchless offset history, prefetch pipeline, and BMI2 triple extract [merged]
#165 - perf(fse): replace next_state linear search with donor-parity flat tables + tune CI bench budgets [merged]
#166 - perf(fse): donor FSE_buildCTable_wksp parity — drop per-symbol Vec [closed]

---

📝 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!

[coderabbitai]

🧩 Analysis chain

🏁 Script executed:

#!/bin/bash
# Fetch issue `#169` details
gh issue view 169 --repo structured-world/structured-zstd --json title,body,labels,assignees,comments,state,author

# Also fetch related PR `#165` for context on recent FSE work
gh pr view 165 --repo structured-world/structured-zstd --json title,body,mergedAt 2>/dev/null | head -100

Length of output: 11732

---

Let me pull the relevant source files to provide a thorough code-level review.

---

🏁 Script executed:

#!/bin/bash
# Get the file structure first
fd -e rs . zstd/src/huff0/ zstd/src/encoding/blocks/ 2>/dev/null || \
  fd -e rs . --search-path zstd/src 2>/dev/null | grep -E "(huff0|compressed)" | head -30

# Look at HuffmanTable struct and write_table
rg -n "struct HuffmanTable|fn write_table|fn writeable_table_description_size|fn try_table_description_size|fn encode_weight_description|fn compute_block_size_to_compressed|fn compress_literals_or_reuse" zstd/src/ -A3 2>/dev/null

# Get line counts of key files
wc -l zstd/src/huff0/huff0_encoder.rs zstd/src/encoding/blocks/compressed.rs 2>/dev/null

Length of output: 2770

---

🏁 Script executed:

#!/bin/bash
# Read HuffmanTable struct and surrounding impl methods (lines 200-320)
sed -n '200,320p' zstd/src/huff0/huff0_encoder.rs

echo "=== write_table and encode_weight_description (lines 100-200) ==="
sed -n '100,210p' zstd/src/huff0/huff0_encoder.rs

echo "=== compressed.rs compute_block_size_to_compressed ==="
rg -n "compute_block_size_to_compressed|compress_literals_or_reuse|writeable_table_description_size|HuffmanTable::new\|HuffmanTable {" zstd/src/encoding/blocks/compressed.rs -B2 -A8

echo "=== compressed.rs around line 458 ==="
sed -n '440,520p' zstd/src/encoding/blocks/compressed.rs

echo "=== compressed.rs around line 1540 ==="
sed -n '1520,1620p' zstd/src/encoding/blocks/compressed.rs

Length of output: 16298

---

@polaz — here is a full review of the issue.

---

Issue #169 Review — perf(huff0): shared Huffman weight-description cache [SPIKE]

Problem statement — accurate, with one additional source of redundancy

The three-encode count is correct as described. Looking at the code:

• compute_block_size_to_compressed (compressed.rs ~Line 476): builds HuffmanTable::build_from_counts → writeable_table_description_size() → encode_weight_description (encode 1)
• compress_literals (compressed.rs ~Line 1563): independently calls HuffmanTable::build_from_data (re-histograms the same bytes) → writeable_table_description_size() → encode_weight_description (encode 2)
• HuffmanEncoder::write_table (huff0_encoder.rs Line 114): called inside encode/encode4x → encode_weight_description (encode 3)

There is also an unaccounted-for source not called out in the issue: build_from_counts itself calls try_table_description_size() inside the table_log selection loop (Lines ~250–270) — up to ~9 iterations, each on a freshly constructed HuffmanTable. These are separate instances so no shared cache would help them, but it means the true per-logical-block encode count is (table_log_iterations_for_planner_call) + (table_log_iterations_for_emitter_call) + 1 — potentially 10–20 encodes, not 3. This is worth adding to the investigation scope.

---

Proposed approach — analysis

Step 2: OnceCell description cache — sound, no blockers

HuffmanTable.codes fully determines weights(), so the cache is always valid. The proposed OnceCell<Option<Vec<u8>>> on the struct is correct:

• #[derive(Clone)] still compiles: core::cell::OnceCell<Option<Vec<u8>>> implements Clone since Vec<u8>: Clone.
• core::cell::OnceCell is !Sync, which is appropriate given the single-threaded-per-frame assumption. One risk to document: if HuffmanTable is ever wrapped in Arc for concurrent frame encoding, the cache field would need to become std::sync::OnceLock<Option<Vec<u8>>> (same API, Sync-safe). A // SAFETY: comment on the struct noting the thread-isolation assumption would make this visible to future readers.
• The cache should store the raw FSE bytes returned by encode_weight_description (without the 1-byte length-prefix header). This matches the existing split in write_table: the header byte is written separately via write_bits(fse_description.len() as u8, 8), and the raw bytes follow via append_bytes. The +1 in try_table_description_size already accounts for the header.

One subtlety: encode_weight_description also runs weight_description_roundtrips (a decode-and-compare validation) before returning. Caching the result means this validation runs at most once per table instance — that is strictly correct behaviour, not a regression.

Step 1: Share a single HuffmanTable instance — the hard part

compute_block_size_to_compressed builds via build_from_counts (counts already computed), while compress_literals calls build_from_data (re-histograms). A natural factoring:

// Sketch — build once, pass to both sites
pub struct PreparedLiterals<'a> {
    pub data: &'a [u8],
    pub table: HuffmanTable,           // built once from the histogram
    pub desc_size: usize,              // cached from try_table_description_size()
}

The complication is that compute_block_size_to_compressed is a planner called speculatively — potentially many times per block — while compress_literals is the emitter called once. You don't want to build and cache a table for every speculative probe. The minimum viable approach may be:

• Keep the planner building transiently (accept the duplicate builds for probe calls that are discarded).
• Only at the commit point (final planner call that determines the split), stash the HuffmanTable somewhere the emitter can consume instead of rebuilding.

This could be as lightweight as returning Option<HuffmanTable> from compute_block_size_to_compressed and threading it through to compress_literals — no heavyweight struct needed if the call sites are already co-located.

Step 3: write_table consuming pre-encoded bytes — confirmed feasible

write_table today (Lines 111–120):

fn write_table(&mut self) {
    let weights = self.weights();
    let weights = &weights[..weights.len() - 1];
    if let Some(fse_description) = Self::encode_weight_description(weights) {
        self.writer.write_bits(fse_description.len() as u8, 8);
        self.writer.append_bytes(&fse_description);
    } else {
        Self::write_raw_weight_description(self.writer, weights);
    }
}

With a cached description: OnceCell<Option<Vec<u8>>> on HuffmanTable, this becomes:

fn write_table(&mut self) {
    match self.table.cached_description() {   // populated by prior try_table_description_size call
        Some(fse_bytes) => {
            self.writer.write_bits(fse_bytes.len() as u8, 8);
            self.writer.append_bytes(fse_bytes);
        }
        None => {
            let weights = self.weights();
            let weights = &weights[..weights.len() - 1];
            Self::write_raw_weight_description(self.writer, weights);
        }
    }
}

The donor HUF_writeCTable_wksp produces the same FSE byte stream (confirmed by the roundtrip validator already in place), so byte-level correctness is preserved.

---

Acceptance criteria — observations

• The ≥5% speedup gate on compress/level_2_dfast/small-4k-log-lines/matrix/pure_rust is reasonable for a 4 KiB block workload where table-build overhead is proportionally larger. However, if the build_from_counts table_log loop dominates (see above), eliminating only the 3 cross-call-site encodes may fall short of 5% — it is worth measuring the per-encode cost in isolation before committing to the full shared-table plumbing, since the OnceCell cache alone (Step 2) might yield most of the gain with far less refactor surface.
• The no-new-R>C-cell criterion is appropriate and consistent with the rejection of the proxy approach. The cached path is mathematically identical to the current path (same FSE output), so this should be a non-issue — but the CI sweep is still the right gate.
• 503/503 tests — note the PR #165 body references 526/526 via nextest; double-check which count is current baseline.

---

Suggested investigation sequence

1. Instrument first: add a counter (cfg-gated) to encode_weight_description and log calls-per-block on the target corpus. This will confirm whether the table_log loop is a significant contributor and whether eliminating calls 1 & 2 alone would hit the 5% gate without Step 1 plumbing.
2. Land Step 2 alone (OnceCell cache): low-risk, ~30 LoC. Measure speedup. If ≥5%, the plumbing of Step 1 may be skippable.
3. Only if Step 2 is insufficient: implement Step 1 (shared table instance across planner/emitter).

This reduces risk of landing a large refactor that still misses the speedup gate.

---

Minor nits

• The writeable_table_description_size alias (Line 303–305) that simply delegates to try_table_description_size is a good candidate to collapse into one name as part of this refactor — the distinction appears to be vestigial.
• encode_weight_description is a fn (not pub), so the cache accessor can be a clean pub(crate) fn cached_fse_description(&self) -> Option<&[u8]> without leaking internals.

Overall the issue is well-scoped and the kill-switch criteria are the right ones. The main risk is that Steps 1 + 2 together are a larger surface than needed — Step 2 alone is worth measuring first.