Impact of 7-Zip Match Finder Algorithms on CPU Usage

The efficiency of 7-Zip's LZMA and LZMA2 compression formats heavily relies on match finder algorithms, which scan incoming data to detect repeating sequences. These algorithms—primarily Hash Chains (HC) and Binary Trees (BT)—represent the most computationally expensive phase of the compression pipeline. This article examines how the choice of match finder dictates CPU cycle consumption, how different variants balance throughput against compression ratios, and how secondary parameters like dictionary size and fast bytes amplify processor workload.

The Role of Match Finders in 7-Zip

During LZMA/LZMA2 compression, the encoder replaces redundant byte patterns with references to previously seen data. The match finder's job is to scan a sliding dictionary window and identify the longest possible matching sequences. Because checking every potential byte offset across megabytes or gigabytes of memory is computationally infeasible, 7-Zip uses algorithmic data structures to narrow the search space.

This phase is typically responsible for 70% to 90% of the total CPU cycles consumed during compression. Consequently, the chosen match finder algorithm serves as the primary governor of CPU cycle utilization and execution time.

Hash Chains vs. Binary Trees

7-Zip provides several match finder implementations, broadly categorized into Hash Chains and Binary Trees, denoted with prefixes (HC or BT) and suffix numbers indicating the minimum hashing depth (e.g., HC4, BT4):

  • Hash Chains (HC2, HC3, HC4): Hash chain finders index prefixes of 2, 3, or 4 bytes into hash tables pointing to linked lists of previous occurrences. When seeking matches, the algorithm traverses these chains sequentially. Hash chains terminate earlier and make fewer pointer jumps, leading to significantly lower CPU cycle consumption and higher compression speed at the expense of a slightly lower compression ratio.
  • Binary Trees (BT2, BT3, BT4): Binary tree finders maintain self-balancing search trees for matched sequences. This structure allows the algorithm to locate longer and more optimal matches across larger dictionary windows. However, maintaining and traversing binary trees requires substantially more comparisons, memory pointer dereferencing, and branch evaluations, resulting in high CPU cycle consumption per processed megabyte.

Factors Amplifying CPU Cycle Consumption

The workload imposed by a match finder scales according to several configuration parameters:

  • Fast Bytes (fb parameter): The fast bytes setting defines the maximum length of a match the finder attempts to evaluate before stopping. Increasing this value (e.g., from 32 to 273) forces match finders—especially BT4—to execute significantly deeper comparisons inside the search tree, causing CPU cycle usage to spike non-linearly.
  • Dictionary Size: Larger dictionary sizes expand the search window. While modern algorithms use hash tables to limit direct lookups, larger windows cause CPU cache invalidations. As data sizes exceed L1, L2, and L3 caches, memory latency forces CPU execution pipelines to stall, increasing the effective cycle cost per byte compressed.
  • Branch Prediction and Cache Misses: Binary tree implementations generate frequent, pseudo-random pointer dereferencing as nodes are inserted and rotated. On modern out-of-order processors, mispredicted branches and cache misses waste substantial clock cycles compared to linear hash chain traversals.

Impact on Multi-Core Utilization

Under LZMA, match finding is largely single-threaded, meaning a heavy match finder like BT4 will saturate a single core at 100% until completion. Under LZMA2, 7-Zip partitions streams into discrete chunks compressed in parallel. In this scenario, intensive match finders consume 100% of the available cycles across all assigned logical cores, driving maximum CPU power draw and thermal throttling on high-core-count processors.

Selecting the Right Algorithm

  • Use Hash Chains (HC4): When optimizing for throughput, battery life, or constrained CPU capacity. Fast and normal presets in 7-Zip leverage HC-based logic to reduce cycle costs while retaining acceptable compression ratios.
  • Use Binary Trees (BT4): When final archive size is the only priority and compute resources are abundant. Maximum and Ultra presets mandate BT4, allocating massive CPU cycle budgets to extract the smallest possible file sizes.