perf(encode): level-1 entropy stage is 2.8x libzstd on real data; the match finder is not the gap

[polaz]

Context

Measured while comparing both encoders over a real 32 MiB Envoy access log on the i9. Level 1 is where the gap is widest on real data, and the ratio gate passes in our favour — we emit 10,267,998 bytes against libzstd's 10,283,940 on the 80 MB version of the same log — so this is purely about speed.

Where the time goes

40 iterations of the 32 MiB log at level 1, one-shot API on both sides, same process shape (encode_loop_dict against ffi_encode_loop_z000033):

• ours: 9,776 / 10,519 / 10,474 M cycles, 22,680.7 M instructions
• libzstd: 6,347 / 6,325 / 6,512 M cycles, 15,261.8 M instructions

1.65× the cycles, 1.49× the instructions. Split by stage (perf record -e cycles:u, percentages against each side's own total):

stage	ours	libzstd	ratio
match finder	5,093 M (run_fast_kernel_block)	4,398 M (ZSTD_compressBlock_fast)	1.16×
sequence encoding	1,959 M (encode_sequences + encode_raw_sequences_into)	710 M (ZSTD_encodeSequences_bmi2 + ZSTD_seqToCodes)	2.76×
literals	1,439 M (encode_unrolled_bmi2 + compress_literals + append_literals)	494 M (HUF_compress1X_usingCTable_internal_bmi2)	2.91×
histogram	416 M (count_bytes)	416 M (HIST_count_parallel_wksp)	1.00×
frame / block plumbing	604 M (compress_independent_frame_into + compress_block_encoded_borrowed)	no counterpart above 1.5%	—

The match finder is 16% behind and the histogram is at parity. The gap is the entropy stage.

Done

The bit writer's flush schedule. Our sequence loop drained the accumulator twice per sequence, once after the three FSE state diffs and once after the extra-bit fields. Upstream drains once and asks first whether the extras would fail to fit beside the diffs (zstd_compress_sequences.c:350 and :355). Adopting its two conditionals costs -4.6% of the whole level-1 encode, byte-identical, and is neutral at level 9.

Two leads, as filed — one of them was wrong

1. The offset is encoded twice — NOT on the level this issue is about. The premise was that every matcher runs encode_offset_with_history per match and discards the result, so encode_raw_sequences_into recomputes it. That holds for HC, Row, Dfast and BT. It does NOT hold for Fast, which is the backend levels -5..2 use and the one this issue measures: the Fast matcher deliberately does not touch offset_hist at all (fast_matcher.rs, module docs), drives repcodes off its own two-deep rep stack, and leaves the offBase entirely to the downstream pass. So at level 1 nothing is computed twice; what the pass costs there is the pass itself, a copy of every sequence into a second array.

The C-faithful fix is still worth having, and it is a different one: upstream's ZSTD_compressBlock_fast calls ZSTD_storeSeq with REPCODE1_TO_OFFBASE on the rep path and OFFSET_TO_OFFBASE(offset) otherwise, so the kernel already knows the answer and never re-derives it by comparing the actual offset back against the history. Ours does. Making the kernel emit the offBase would remove both the second array and the re-derivation.

Watch for this when doing it: the offBase of a sequence depends on the repcode history, and the history must NOT advance across a partition that ends up written raw. Today emit_single_sequence_block restores state.offset_hist on that path, and the next partition's offBases are then derived from the restored history — which is what the decoder will do, so it is required for correctness, not an optimisation. Precomputing every offBase once during matching breaks that case. Either keep the raw offsets alongside and re-derive the remaining partitions after a discard, or bound the change to the paths that cannot split.

2. The bit writer. Partly done (see above). What remains: we call encode_literal_length / encode_offset / encode_match_len per sequence inside the bit-writing loop, where upstream reads the three codes out of the byte arrays ZSTD_seqToCodes prepared. That is a fused pass against upstream's two, so it should be cheaper rather than dearer, and it needs a disassembly-level comparison rather than another guess.

Not worth retrying: the FSE state value form. Upstream stores tableSize + slot in its next-state table so FSE_encodeSymbol never re-adds the table size; ours stored the raw slot and added it back three times a sequence. Carrying the value form removes 5.07 M instructions a frame at level 1 and is 5.2% slower at level 9 (measured on its own, interleaved, four rounds, no overlap). Fewer instructions, more time.

Where the rest of the level-1 profile sits

After the flush change, on an 8 MiB access log at level 1:

symbol	share
run_fast_kernel_block	44.9%
encode_sequences	24.0%
encode_block_parts_with_sequence_scratch	11.2%
the sequence-emitting closure	9.0%
encode_unrolled_bmi2	3.3%
append_literals	2.0%
count_bytes	1.2%

The literal path (2.91× in the table above) has still not been broken down.

Not in scope here

Level 1 also emits FEWER bytes than levels 2 and 3 on this data, on both sides (libzstd: 10.28 M at level 1, 10.71 M at 2, 11.41 M at 3). That is upstream's own cParams tiering and we reproduce it; it is not a defect.

Files involved

• zstd/src/encoding/blocks/compressed.rs (encode_sequences, encode_raw_sequences_into, compress_literals, append_literals)
• zstd/src/encoding/simple/fast_matcher.rs and zstd/src/encoding/simple/fast_kernel/kernel.rs (where the Fast backend would emit the offBase)
• zstd/src/encoding/hc/generator.rs, zstd/src/encoding/row/mod.rs, zstd/src/encoding/dfast/mod.rs (the discarded encode_offset_with_history results on the non-Fast backends)

Estimate: 1d for lead 1 (contract change across backends + the discard case + measurement), 1d for what is left of lead 2.