Skip to content

perf(decoding): copy dictionary matches in the inline sequence executor #507

Description

@polaz

Problem

Dictionary decode of small frames runs at about half the reference's speed. On the benchmark's small-10k-random scenario (10 KiB, 16 KiB-tier trained dictionary; the frame is one block of 9 110 raw literal bytes and 23 sequences, every one of them a match into the dictionary content), i9-9900K, x86-64-v3:

ours libzstd
decompress-dict/level_3_dfast 894 ns 451 ns
decompress-dict/level_12_lazy 1 176 ns 593 ns
instructions a frame (callgrind) ~12 280 ~6 690

The dashboard reports the same scenario at 0.41-0.47 on x86_64-musl.

Every sequence whose match starts in the dictionary leaves the inline executor: the literals go through try_push (a memcpy call behind a runtime SIMD-tier lookup), and the match through repeat_lookahead_prefetched into the out-of-line #[cold] repeat_from_dict, which re-validates, reserves again and copies through the same dispatch (~109 instructions a call). Upstream handles the same case inside ZSTD_execSequence (the extDict branch): a wildcopy for the literals and one copy from dictEnd.

Plan

  • DecodeBuffer gives the executor the source of a match that lies wholly inside reachable dictionary content, or nothing (a match continuing into the output, no dictionary, out of window or out of range stay on the cold path, which reports the errors).
  • Each kernel tier's inline executor copies such a sequence in place: literals with its wildcopy, the match from the dictionary (wildcopy where the dictionary has room past the match, an exact copy otherwise).
  • The no-dictionary decode path keeps its layout; checked with a no-dictionary control arm.

Acceptance

  • decompress-dict on small-10k-random and small-4k-log-lines measurably faster on the i9 (interleaved A/B, control arm flat); decoded output byte-identical.
  • Tests cover the in-dictionary copy (wildcopy and exact-tail forms), a match spanning dictionary and output, and the out-of-window refusal, on every tier the host runs.

Estimate: 1d 4h

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