perf(huff0): donor HUF_optimalTableLog fast-path single-shot tableLog with cheap description-size proxy

[polaz]

Context

Surfaced during review of #166 (FSE_buildCTable_wksp parity / drop per-symbol Vec<State>). Part of #111 Phase 7 Lane A — block compressor entropy coding speed.

Profile of compress/level_2_dfast/small-4k-log-lines/matrix/pure_rust (post-#166):

% inclusive	Function
~32 %	huff0_encoder::HuffmanTable::try_table_description_size
~23 %	huff0_encoder::HuffmanTable::build_from_counts
~18 %	huff0_encoder::HuffmanEncoder::encode_weight_description

Problem

HuffmanTable::build_from_counts runs a speculative search over min_table_log..=11, calling try_table_description_size on each candidate. try_table_description_size actually FSE-encodes the weights to a fresh buffer — this is the expensive operation. The loop pays 7× FSE-encode-of-weights to pick the optimal (desc_size + payload_size) tableLog.

Donor's HUF_optimalTableLog (lib/compress/huf_compress.c:1272) has two modes:

1. Default (fast) — pure arithmetic via FSE_optimalTableLog_internal(maxLog=11, srcSize, maxSV, minus=1). Single tableLog, no per-candidate rebuild.
2. HUF_flags_optimalDepth — full search loop. Gated by strategy >= ZSTD_btultra (level 18+).

For all strategies below btultra (every dfast/lazy level in this codebase's hot path) donor uses the fast path. Rust currently does the slow search unconditionally.

What was tried and why it was reverted

Implemented the donor fast path inside #166 work (Stage 1). Result on compress/level_2_dfast/small-4k-log-lines/matrix/pure_rust:

• Speed: −22 % on top of the perf(fse): donor FSE_buildCTable_wksp parity — drop per-symbol Vec<State> #166 −43 %.
• Ratio: regressed vs donor on one cell — small-4k-log-lines/L1_fast rust_bytes=159 vs ffi_bytes=157 (+2 B). Pre-perf(fse): donor FSE_buildCTable_wksp parity — drop per-symbol Vec<State> #166 search loop produced R=154 (better than donor); single-shot loses that 5 B margin and falls 2 B below the donor.

Per project rule "Ratio first — if rust_bytes > ffi_bytes we lose vs donor → real bug", the single-shot change cannot land while it produces a rust_bytes > ffi_bytes cell. Stage 1 reverted; only Stage 2 (PR #166) landed.

Suggested approach

The expensive component of the current loop is try_table_description_size, which FSE-encodes weights to count bytes. Replace that with a cheap description-size proxy that approximates the FSE-encoded weight description size from a histogram of the per-symbol weights (no actual FSE encode). The proxy should:

1. Compute the histogram of weight values (13 bins, donor max weight = 12).
2. Approximate the FSE-compressed weight description size analytically — e.g. via H(weights) * total_weights / 8 plus a small constant for the FSE header. Possibly compose with a min-of-raw-encoding (weights.len().div_ceil(2) + 1) since the donor picks the cheaper of FSE / raw.
3. Validate that the proxy's relative ranking across tableLog candidates matches try_table_description_size ranking on the bench corpus (small-4k-log-lines, decodecorpus-z000033, large-log-stream, high-entropy-1m).
4. Verify ratio is at least as good as the current search loop vs the donor on every level × scenario cell (compare_ffi REPORT sweep).

If the proxy preserves the optimum within tolerance, the loop becomes:

for table_log in min_table_log..=11 {
    let weights = build_donor_limited_weights(counts, table_log);
    if !huffman_weight_sum_is_power_of_two(&weights) { continue; }
    let table = Self::build_from_weights(&weights);
    let max_bits = table.codes.iter().map(|&(_, b)| b).max().unwrap_or(0) as usize;
    if max_bits < table_log && table_log > min_table_log { break; }
    let desc_size_est = huff_desc_size_proxy(&weights); // <- cheap
    let new_size = table.estimate_compressed_size_from_counts(counts) + desc_size_est;
    if new_size < best_size { best_size = new_size; best_table = Some(table); }
    if new_size > best_size + 1 { break; }
}

— same selection shape, no FSE-encode per candidate. Expected speedup matches the Stage 1 measurement (~−22 % on small-4k-log L2_dfast on top of #166), with no ratio regression vs donor since the proxy still drives the same selection criterion.

Files involved

• zstd/src/huff0/huff0_encoder.rs — HuffmanTable::build_from_counts (~line 220), HuffmanEncoder::encode_weight_description (~line 125), new proxy fn.
• zstd/benches/compare_ffi.rs — REPORT ratio sweep is the validation gate.

Acceptance criteria

• Cheap description-size proxy lands in huff0_encoder.rs with debug_assert cross-checks against try_table_description_size on a representative sample (e.g. property test).
• compare_ffi --features dict_builder REPORT sweep: zero new cells where rust_bytes > ffi_bytes compared to current main.
• compress/level_2_dfast/small-4k-log-lines/matrix/pure_rust improves at least −10 % vs current main (post-perf(fse): donor FSE_buildCTable_wksp parity — drop per-symbol Vec<State> #166 47.4 µs baseline).
• 501/501 lib tests pass, clippy clean.

Related

• Part of feat: encoder architecture rewrite (split monolith, const-generic Strategy, arena allocator) #111 Phase 7 Lane A (block compressor entropy coding speed).
• Builds on perf(fse): donor FSE_buildCTable_wksp parity — drop per-symbol Vec<State> #166 (FSE_buildCTable_wksp parity, drop per-symbol Vec).
• Builds on perf(encoding): #111 Phase 7 — replace FSE encode linear search with donor-parity flat tables #164 / PR perf(fse): replace next_state linear search with donor-parity flat tables + tune CI bench budgets #165 (FSE encode flat nextStateTable + symbolTT).
• Surfaced 2026-05-18 during /review-threads on perf(fse): donor FSE_buildCTable_wksp parity — drop per-symbol Vec<State> #166.

[coderabbitai]

🔗 Related PRs

#44 - feat(encoding): add dictionary compression support [merged]
#54 - perf(decoding): 4-stream interleaved Huffman decode and bulk table init [merged]
#76 - perf(fse): pack decoder entries and align decode tables [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!