What Is Long Distance Matching in Zstd? A Complete Technical Guide

Long distance matching (LDM) is an optional compression mode in facebook/zstd that maintains a dedicated hash table indexing data up to 128 MiB back in the stream, enabling the compressor to discover repeated patterns at large offsets that standard short-distance matchers cannot detect.

The facebook/zstd repository implements long distance matching as an advanced compression strategy designed for massive files containing recurring content separated by significant byte distances. When activated through the public API or command-line interface, LDM allocates supplemental memory structures to track patterns across the entire compression window, significantly improving compression ratios for large log files and multi-gigabyte archives while keeping decompression speed unchanged.

How Long Distance Matching Works

Standard zstd compression examines a limited search buffer that only considers recent data for duplicate strings. Long distance matching extends this capability by implementing a secondary indexing mechanism that spans the full window.

The Extended Window Architecture

When you enable LDM via ZSTD_c_enableLongDistanceMatching, the compressor automatically expands the sliding window to accommodate distant references. By default, enabling this parameter sets the window log to 27, which corresponds to a 128 MiB window size. This configuration allows the matcher to identify matches at offsets up to the full window limit, far beyond the reach of the standard match finder used for short-distance redundancy.

Hash Table Indexing for Distant Patterns

The implementation in lib/compress/zstd_ldm.h maintains a specialized hash table controlled by ZSTD_c_ldmHashLog (default value: windowLog - 7). This structure indexes candidate matches at intervals determined by ZSTD_c_ldmHashRateLog, while ZSTD_c_ldmMinMatch enforces a default 64-byte minimum match length to filter out short matches offering minimal compression benefit. The ZSTD_c_ldmBucketSizeLog parameter manages collision resolution granularity within the hash buckets.

Performance Characteristics and Trade-offs

Enabling long distance matching involves specific computational costs and memory requirements that vary based on your input data characteristics.

• Compression Ratio: LDM excels with large inputs containing repeated patterns at offsets greater than traditional search distances. Multi-gigabyte archives and extensive log files typically see measurable size reductions when identical blocks appear megabytes apart.

• Memory Consumption: Memory usage scales proportionally with the window size and hash table dimensions. The additional state required for ZSTD_c_ldmHashLog allocations means LDM is not recommended for memory-constrained environments processing small buffers.

• Speed Impact: Compression speed decreases slightly due to the additional hash table maintenance and broader search scope. However, decompression speed remains unaffected because the decoder simply follows distance codes without rebuilding the LDM structures.

Configuring Long Distance Matching via the C API

The public header lib/zstd.h defines the parameter enums and setter functions required to control LDM behavior programmatically.

#include <zstd.h>

ZSTD_CCtx *cctx = ZSTD_createCCtx();

/* Enable long distance matching */
size_t err = ZSTD_CCtx_setParameter(cctx,
    ZSTD_c_enableLongDistanceMatching, 1);
if (ZSTD_isError(err)) return err;

/* Optional: tune LDM parameters */
ZSTD_CCtx_setParameter(cctx, ZSTD_c_ldmHashLog, 24);   // 16 MiB hash table
ZSTD_CCtx_setParameter(cctx, ZSTD_c_ldmMinMatch, 64); // Minimum match length

This configuration activates the long-distance matcher with custom memory allocation. The ZSTD_c_ldmHashLog value of 24 creates a 16 MiB hash table (2^24 entries), while maintaining the 64-byte minimum match threshold defined in the source code.

For streaming compression scenarios, apply these parameters to a compression context before invoking ZSTD_compressStream:

ZSTD_CCtx *cctx = ZSTD_createCCtx();
ZSTD_CCtx_setParameter(cctx, ZSTD_c_enableLongDistanceMatching, 1);
ZSTD_CCtx_setParameter(cctx, ZSTD_c_ldmHashLog, 25);   // 32 MiB hash table

ZSTD_inBuffer  in  = { src, srcSize, 0 };
ZSTD_outBuffer out = { dst, dstCap, 0 };

while (in.pos < in.size) {
    size_t ret = ZSTD_compressStream(cctx, &out, &in);
    if (ZSTD_isError(ret)) { /* handle error */ }
    /* Flush output buffer before continuing */
}
ZSTD_endStream(cctx, &out);

Command-Line Interface Usage

The zstd CLI exposes long distance matching through the --long flag, implemented in programs/zstd.c and documented in programs/zstd.1.

Enable LDM with the default 128 MiB window:

zstd --long input.bin -o output.zst

Specify a custom window size using the optional parameter. A window log of 28 allocates 256 MiB:

zstd --long=28 input.bin -o output.zst

Omitting the numeric value defaults to window log 27, as defined in the command-line parser logic in the facebook/zstd source tree.

Implementation Files and Architecture

Understanding the source layout helps developers integrate LDM effectively:

• lib/zstd.h: Declares the five LDM configuration enums (ZSTD_c_enableLongDistanceMatching, ZSTD_c_ldmHashLog, ZSTD_c_ldmMinMatch, ZSTD_c_ldmBucketSizeLog, ZSTD_c_ldmHashRateLog) and parameter validation logic.

• lib/compress/zstd_ldm.h: Contains the core matching algorithm, hash table management, and insertion/lookup routines for distant offsets.

• programs/zstd.c: Parses the --long command-line argument and maps it to internal window log calculations.

• tests/zstreamtest.c: Validates LDM behavior across various window sizes and buffer configurations.

Summary

• Long distance matching extends zstd's search window up to 128 MiB, finding repeated patterns at large offsets that standard matchers miss.
• The feature activates via ZSTD_c_enableLongDistanceMatching in the C API or --long on the command line.
• Five parameters control LDM behavior: enable flag, hash log, minimum match length, bucket size log, and hash rate log.
• Memory consumption scales with ZSTD_c_ldmHashLog and window size, making LDM suitable for large-file compression rather than small-buffer scenarios.
• Compression speed decreases slightly due to additional indexing work, but decompression speed remains unchanged.
• Core implementation resides in lib/compress/zstd_ldm.h with API definitions in lib/zstd.h.

Frequently Asked Questions

What is the maximum window size for long distance matching in zstd?

The maximum window size when using long distance matching is 128 MiB by default (window log 27), though you can extend this to 256 MiB (window log 28) or higher depending on your specific build configuration and available memory. This is significantly larger than the standard matcher window, allowing the algorithm to reference data from much earlier in the stream.

Does enabling long distance matching affect decompression speed?

No, long distance matching does not impact decompression performance. The decompression engine simply reads distance codes from the compressed stream and copies referenced data without reconstructing the LDM hash tables or performing the expensive search operations required during compression. Only compression speed and memory usage increase when LDM is active.

When should I use long distance matching instead of standard compression?

Use long distance matching when compressing large files (multi-gigabyte archives, extensive log files) that contain identical patterns separated by many megabytes of data. If your data contains repeated blocks of 64 bytes or more at offsets exceeding traditional search distances, LDM will improve compression ratio. For small files or data without long-range redundancy, standard compression provides better speed-to-ratio efficiency.

How do I tune the hash table size for long distance matching?

Adjust the ZSTD_c_ldmHashLog parameter to control memory allocation, where the table size equals 2^hashLog bytes. The default calculation (windowLog - 7) balances memory usage and match discovery, but you can increase this value for better pattern detection at the cost of higher RAM consumption, or decrease it for memory-constrained environments. For example, setting ZSTD_c_ldmHashLog to 24 creates a 16 MiB hash table.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}