`zipimport._zstd_decompress()` repeatedly processes remaining input for concatenated frames

Bug description

zipimport._zstd_decompress() handles concatenated Zstandard frames by creating a new _zstd.ZstdDecompressor for each frame. Each decompressor is passed the entire remaining compressed suffix, and the next iteration obtains the same suffix, minus the frame just decoded, through unused_data.

As a result, when a zstd-compressed ZIP entry using compression method 93 contains many concatenated frames, most of the compressed input is passed to decompressor calls repeatedly. For N similarly sized frames, the cumulative amount of input handled across those calls grows quadratically rather than linearly with the size of the entry.

Reproducer and local results

import time
import zipimport
from compression import zstd

FRAMES = 64_000

frame = zstd.compress(b"x")
data = frame * FRAMES
input_sizes = []
original = zipimport._get_zstd_decompressor_class()


class RecordingDecompressor:
    def __init__(self, *args, **kwargs):
        self._decompressor = original(*args, **kwargs)

    def __getattr__(self, name):
        return getattr(self._decompressor, name)

    def decompress(self, data, max_length=-1):
        input_sizes.append(memoryview(data).nbytes)
        return self._decompressor.decompress(data, max_length)


zipimport._zstd_decompressor_class = RecordingDecompressor
start = time.perf_counter()
try:
    output = zipimport._zstd_decompress(data)
finally:
    elapsed = time.perf_counter() - start
    zipimport._zstd_decompressor_class = original

print(f"input size: {len(data):,} bytes")
print(f"output size: {len(output):,} bytes")
print(f"decompress calls: {len(input_sizes):,}")
print(f"cumulative input passed: {sum(input_sizes):,} bytes")
print(f"amplification: {sum(input_sizes) / len(data):,.2f}x")
print(f"elapsed: {elapsed:.4f} seconds")

Local result:

input size: 640,000 bytes
output size: 64,000 bytes
decompress calls: 64,000
cumulative input passed: 20,480,320,000 bytes
amplification: 32,000.50x
elapsed: 1.5364 seconds

After fix:

input size: 640,000 bytes
output size: 64,000 bytes
decompress calls: 64,000
cumulative input passed: 640,000 bytes
amplification: 1.00x
elapsed: 0.2333 seconds

CPython versions tested on:

CPython main branch

Operating systems tested on:

Linux

Linked PRs

• gh-155154

エントリーポイントは zipimport._zstd_decompress() です。まず、提供されている連結フレームの再現プログラムを実行し、各デコンプレッサー呼び出しが受け取る入力を調べてください。完了の条件は、報告された 1.00x の結果と同様に、累積して渡される入力が線形でありながら、出力が正しいままであることです。リンク先の PR gh-155154 は、すでに作業が進行中であることを示しています。