Why BZip2 and LZMA2 Scale Differently in 7-Zip

When compressing files using 7-Zip, BZip2 and LZMA2 exhibit starkly different multi-threading behaviors across modern multi-core processors. This article explores the architectural differences between BZip2's block-sorting design and LZMA2's dictionary-based approach, explaining how block independence, per-thread memory footprints, and CPU cache saturation determine why BZip2 scales near-linearly across high thread counts while LZMA2 faces diminishing returns.

Algorithmic Foundations: Block-Sorting vs. Sliding Dictionaries

The primary reason for the difference in scaling lies in how each algorithm handles input data:

  • BZip2 (Burrows-Wheeler Transform): BZip2 partitions incoming data into small, completely independent blocks (typically 900 KB). Because each block is self-contained and requires no awareness of preceding or subsequent blocks, 7-Zip can assign each block to an isolated CPU thread without synchronization or shared memory states.
  • LZMA2 (Lempel-Ziv-Markov chain Algorithm): LZMA relies on a sliding dictionary to locate repeated byte sequences across large spans of data. Because standard LZMA is inherently sequential, LZMA2 achieves parallelism by splitting the data stream into larger chunks (often several megabytes to match the dictionary size) and compressing them as separate streams. However, these chunks must frequently reset or manage dictionary states, introducing coordination overhead and limiting fine-grained distribution.

Memory Footprint and Memory Bandwidth

Thread scaling is rarely limited by raw CPU compute alone; memory subsystem throughput plays a critical role.

BZip2 uses a fixed, lightweight memory footprint—roughly 8 MB of RAM per compression thread at the maximum 900 KB block size. Because the working set for each thread is small enough to fit comfortably within the processor's L2 and L3 caches, dozens of BZip2 threads can execute concurrently without saturating the system's central memory bus.

In contrast, LZMA2 requires a substantial amount of RAM per thread. With common dictionary sizes ranging from 16 MB to 64 MB (or higher), a single thread can consume several hundred megabytes of RAM. When 16, 32, or 64 threads run simultaneously:

  1. The combined working set far exceeds the CPU cache capacity.
  2. Threads begin competing aggressively for access to the system RAM.
  3. Memory bus bottlenecks stall CPU execution pipelines, causing performance scaling to plateau even if CPU utilization metrics report 100%.

Workload Granularity and Thread Allocation

BZip2's fixed 900 KB block size allows 7-Zip to saturate high-core-count CPUs regardless of the total file size, provided the input exceeds a few megabytes. Work distribution is uniform, meaning thread starvation is virtually nonexistent.

LZMA2's chunk size is tied to dictionary size and specific internal chunk thresholds. When compressing smaller datasets or operating with very large dictionaries on high-core processors, 7-Zip may not be able to subdivide the input into enough distinct chunks to feed every available thread. Consequently, some CPU cores remain idle or finish their workloads long before others, reducing overall multi-threaded efficiency.

Summary of Differences

  • Scaling Linearity: BZip2 maintains near-linear scaling up to high thread counts (32–64+ threads) due to tiny, independent blocks. LZMA2 scales well at low to moderate core counts (4–16 threads) but plateaus as thread counts increase.
  • Cache Efficiency: BZip2 operates largely within CPU cache hierarchies; LZMA2 heavily stresses the external memory controller.
  • Compression Efficiency Trade-off: While BZip2 scales better across many CPU cores, LZMA2 achieves significantly higher compression ratios, making LZMA2 computationally heavier per byte but far more space-efficient.