What this is
The Fast matcher knows, at the moment it emits a match, whether it took a
repeat offset or an explicit one. It throws that away and passes the raw byte
offset downstream, where encode_offset_with_history_fast derives the answer
back by comparing against the repeat-offset history. Upstream does not: its
ZSTD_compressBlock_fast calls ZSTD_storeSeq with REPCODE1_TO_OFFBASE on
the rep path and OFFSET_TO_OFFBASE(offset) otherwise, so the code is decided
where it is known.
This is the half of #493's lead 1 that was not done. The other half — removing
the second sequence array — is on perf/#493-sequence-array.
What it is worth
Measured on the i9, 8 MiB access log at level 1, LBR call-graph profile of the
per-function inlined breakdown:
encode_offset_with_history_fast is 3.18% of the frame. It is not
instruction count: the derivation is one compare and a three-word rotation. It
is a serial dependency — each sequence compares against a history slot the
previous sequence may have written, so the chain runs the length of the block.
Only moving the decision to the kernel removes it; making the derivation
cheaper cannot.
Level 1 and the negative levels are the whole of the win: the Fast backend is
the only one this touches.
Why it is not a small change
The flag needs its own channel. It cannot ride in Sequence::Triple.offset
— that field is the raw byte offset by contract, and the sequence comparator
(encoding/sequence_capture.rs) records it as such to diff our stream against
libzstd's. Stealing a bit there would silently corrupt that tool's output.
Either Sequence::Triple grows a field, or the matcher exposes the flags as a
side channel the collector reads after the scan.
The repeat-offset state has to become rollback-able, and that is the real
work. Today the wire code is derived from state.offset_hist, which the
emitter restores whenever a block or partition is written raw. The kernel's own
rep stack is not restored — it keeps advancing through discarded blocks —
and that is harmless only because nothing downstream reads it. The moment the
kernel's answer becomes the wire code, a discarded block leaves the kernel's
reps ahead of the decoder's history, and the next block's offBase 1 decodes to
the wrong offset.
Upstream has exactly this separation already: it matches into
nextCBlock->rep and confirms into prevCBlock->rep only for a block it
keeps. We need the same, which means a rollback hook on the matcher and a call
to it at each of the three encoder sites that discard:
encoding/blocks/compressed.rs, emit_single_sequence_block, the
not-smaller-than-raw branch
encoding/levels/fastest.rs, both raw-fallback branches
The failure mode if a site is missed is a stream that decodes to the wrong
bytes, with nothing failing at build or test time unless the fixture happens to
trigger a discard. That is what makes this its own change rather than a tail
added to a perf branch.
Plan
- Give the Fast matcher a repeat-offset snapshot taken when a block's scan
starts, and a Matcher method that restores it, defaulting to a no-op so
the other backends are unaffected.
- Call that method at the three discard sites, beside the existing
state.offset_hist restore.
- Carry a per-sequence "this is the immediate repeat" flag out of the kernel.
Six emit sites, two in each of the three kernel variants (no-dict, dict,
borrowed); is_rep is already in scope at each.
- In
fill_and_count's FAST_REPCODE arm, take the code from the flag —
1 for a repeat, offset + 3 otherwise — and stop touching the history
there.
- Under
debug_assertions, keep deriving the code the old way from a shadow
history and assert it equals the kernel's. This is the acceptance evidence:
the whole debug suite then checks the correspondence on every fixture and
level, including the litLength-0 rotation, which is where the two are most
likely to disagree.
Acceptance
- Output byte-identical to the branch point across the standard grid: three
fixture shapes against ten levels, plain and dictionary-primed. The
incompressible fixture matters most here — it is the one that discards
blocks, so it is the one that would catch a missing rollback.
- The FFI cross-validation round-trip stays green at every level with and
without dictionary and LDM.
- The debug-build assertion from step 5 fires nowhere in the test suite.
- Level 1 on the 8 MiB access log improves; the other levels are unchanged in
retired instructions, since the Fast backend is the only path touched.
Estimate
1d.
Part of #493.
What this is
The Fast matcher knows, at the moment it emits a match, whether it took a
repeat offset or an explicit one. It throws that away and passes the raw byte
offset downstream, where
encode_offset_with_history_fastderives the answerback by comparing against the repeat-offset history. Upstream does not: its
ZSTD_compressBlock_fastcallsZSTD_storeSeqwithREPCODE1_TO_OFFBASEonthe rep path and
OFFSET_TO_OFFBASE(offset)otherwise, so the code is decidedwhere it is known.
This is the half of #493's lead 1 that was not done. The other half — removing
the second sequence array — is on
perf/#493-sequence-array.What it is worth
Measured on the i9, 8 MiB access log at level 1, LBR call-graph profile of the
per-function inlined breakdown:
encode_offset_with_history_fastis 3.18% of the frame. It is notinstruction count: the derivation is one compare and a three-word rotation. It
is a serial dependency — each sequence compares against a history slot the
previous sequence may have written, so the chain runs the length of the block.
Only moving the decision to the kernel removes it; making the derivation
cheaper cannot.
Level 1 and the negative levels are the whole of the win: the Fast backend is
the only one this touches.
Why it is not a small change
The flag needs its own channel. It cannot ride in
Sequence::Triple.offset— that field is the raw byte offset by contract, and the sequence comparator
(
encoding/sequence_capture.rs) records it as such to diff our stream againstlibzstd's. Stealing a bit there would silently corrupt that tool's output.
Either
Sequence::Triplegrows a field, or the matcher exposes the flags as aside channel the collector reads after the scan.
The repeat-offset state has to become rollback-able, and that is the real
work. Today the wire code is derived from
state.offset_hist, which theemitter restores whenever a block or partition is written raw. The kernel's own
repstack is not restored — it keeps advancing through discarded blocks —and that is harmless only because nothing downstream reads it. The moment the
kernel's answer becomes the wire code, a discarded block leaves the kernel's
reps ahead of the decoder's history, and the next block's offBase 1 decodes to
the wrong offset.
Upstream has exactly this separation already: it matches into
nextCBlock->repand confirms intoprevCBlock->reponly for a block itkeeps. We need the same, which means a rollback hook on the matcher and a call
to it at each of the three encoder sites that discard:
encoding/blocks/compressed.rs,emit_single_sequence_block, thenot-smaller-than-raw branch
encoding/levels/fastest.rs, both raw-fallback branchesThe failure mode if a site is missed is a stream that decodes to the wrong
bytes, with nothing failing at build or test time unless the fixture happens to
trigger a discard. That is what makes this its own change rather than a tail
added to a perf branch.
Plan
starts, and a
Matchermethod that restores it, defaulting to a no-op sothe other backends are unaffected.
state.offset_histrestore.Six emit sites, two in each of the three kernel variants (no-dict, dict,
borrowed);
is_repis already in scope at each.fill_and_count'sFAST_REPCODEarm, take the code from the flag —1 for a repeat,
offset + 3otherwise — and stop touching the historythere.
debug_assertions, keep deriving the code the old way from a shadowhistory and assert it equals the kernel's. This is the acceptance evidence:
the whole debug suite then checks the correspondence on every fixture and
level, including the litLength-0 rotation, which is where the two are most
likely to disagree.
Acceptance
fixture shapes against ten levels, plain and dictionary-primed. The
incompressible fixture matters most here — it is the one that discards
blocks, so it is the one that would catch a missing rollback.
without dictionary and LDM.
retired instructions, since the Fast backend is the only path touched.
Estimate
1d.
Part of #493.