perf: encoder match finding — hash interleaving and match length counting

[polaz]

Summary

The current Fastest level encoder uses a basic hash table matcher. The C reference zstd_fast.c employs a pipeline-style interleaving pattern that hides memory latency — the single biggest optimization for compression speed.

C reference optimizations (zstd_fast.c)

Pipeline-style hash+lookup interleaving

The C code interleaves operations across multiple positions to hide memory latency:

Position N:   ... Match
Position N+1: ... TableLookup Match
Position N+2: Read Hash TableLookup Match
Position N+3:      Hash TableLookup Match

While waiting for hash table lookup result for position N, the code is already computing hash for position N+1 and reading data for position N+2. This keeps the CPU pipeline full.

Match length counting

• ZSTD_count(): Compare 8 bytes at a time using MEM_read64() XOR + CTZ
• Processes sizeof(size_t) bytes per iteration on 64-bit systems
• Final cleanup for remaining bytes

Hash fill strategies

• fastHashFillStep = 3: Only every 3rd position gets hash entry (speed vs. ratio trade-off)
• Dictionary fill: every position (accuracy matters more for small data)

Rep code checking

• Before hash lookup: check if repeat offset matches at current position
• Repeat matches are free (0-bit offset encoding) — huge ratio win

Current Rust implementation

• encoding/match_generator.rs — basic sequential hash lookup
• No pipeline interleaving
• Match counting likely byte-by-byte or small chunks
• Rep code handling: offset history hardcoded [1, 4, 8], not updated during encoding (compressed.rs:27)

What needs to be implemented

1. Pipeline-style interleaving — prefetch next hash while processing current match
2. Bulk match counting — 8-byte XOR + trailing_zeros for O(8) bytes per iteration
3. Rep code optimization — check repeat offsets before hash lookup
4. Offset history tracking — update [rep0, rep1, rep2] during encoding (currently broken)
5. Hash fill step tuning — configurable fill rate for speed vs ratio

Performance impact estimate

• Pipeline interleaving: ~20-30% compression speed improvement
• Bulk match counting: ~10-15% on match-heavy data
• Rep codes: ~5-15% better compression ratio (free matches)

Acceptance criteria

• Pipeline-style hash interleaving in Fastest matcher
• 8-byte bulk match length counting
• Offset history correctly tracked and used for rep codes
• Benchmark shows compression speed improvement
• Compression ratio improves (rep code utilization)
• All roundtrip tests pass

Time estimate

2d

[coderabbitai]

🔗 Related PRs

#2 - feat: managed fork setup — README, FUNDING, crate rename to structured-zstd [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!