GPU LZ77 Decode Speed Limited by Match Length, New Lever Boosts 78%

The ACEAPEX line of work introduced a lossless LZ77 format using absolute output positions for parallel GPU decompression with sub-millisecond region seek. However, what actually governed decode throughput remained unclear. In this fourth paper, Yakiv Shavidze runs controlled ablations on an NVIDIA H100 and finds that throughput is governed not by occupancy, compute, address scatter, or launch parallelism, but by work granularity: the average match length. Short matches leave most lanes of a cooperative warp idle, severely limiting throughput. A synthetic copy kernel confirms a 3.5x throughput span (212 to 744 GB/s) as average match length grows from 32 to 1024 bytes. Real-world datasets like enwik9 and FASTQ sit at the low end with mean match lengths of 6.5 and 10.1, respectively.

Building on this insight, the paper proposes a practical, encode-side lever: raising the minimum match length by distance class (e.g., from 6/8/10/12 to 12/16/24/32). This improves both compression ratio and decode throughput simultaneously across all eight tested datasets, with no exceptions and no changes to the decode kernel. FASTQ decode rises from 142.6 to 178.6 GB/s while ratio improves 1.8%; enwik9 throughput climbs 78%. This is not a trade-off: removing short matches that cost more entropy than they save yields a win-win. All results are bit‑perfect (FNV on GPU, byte compare on CPU) and git‑verifiable. The scope is limited to device‑resident match‑phase decoding, excluding entropy, host transfer, and hardware bandwidth ceiling claims.