Skip to content

perf(encode): let the fast kernel emit the offBase it already knows #500

Description

@polaz

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

  1. 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.
  2. Call that method at the three discard sites, beside the existing
    state.offset_hist restore.
  3. 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.
  4. 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.
  5. 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.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions