Skip to content

feat: implement Better compression level (zstd level 7, lazy2 strategy) #6

Description

@polaz

Summary

CompressionLevel::Better currently triggers unimplemented!(). Level 7 uses lazy2 strategy — significantly better compression ratio than dfast at moderate speed cost.

Analysis

C reference implementation (zstd level 7)

  • Strategy: ZSTD_lazy2 (lazy matching with 2-step look-ahead)
  • Parameters: windowLog=23, chainLog=23, hashLog=22, searchLog=3, minMatch=3, targetLength=48
  • Key files: lib/compress/zstd_lazy.c

Algorithm

  1. Hash chain table — hash → linked list of positions with same hash
  2. Lazy matching — at each position:
    • Find best match at position N
    • Find best match at position N+1 (with 1 extra literal)
    • Find best match at position N+2 (with 2 extra literals)
    • Pick the best overall (longer match justifies extra literals)
  3. Common-length caching — when traversing hash chains, skip bytes already compared (critical optimization from C code)
  4. Row matchingZSTD_RowMatchState with SIMD tag matching for faster chain traversal

What needs to be implemented

  1. Hash chain data structure — position chains indexed by hash
  2. Lazy2 match finder — 2-step look-ahead with price comparison
  3. Match length comparison — efficient byte-level comparison with early exit
  4. Chain depth limitingsearchLog=3 means max 8 chain entries checked
  5. Rep code integration — check repeat offsets at each lazy step

Acceptance criteria

  • CompressionLevel::Better no longer panics
  • Roundtrip + interop tests pass
  • Compression ratio within 10% of C zstd level 7 on silesia corpus
  • Speed slower than Default but ratio measurably better

Dependencies

Time estimate

4d

Blocked by

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

    P1-highHigh priority — core functionalityenhancementNew feature or request

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions