HN 日本語サマリー

← 一覧へ戻る
プログラミング

地獄のように遅いレベル13 Deflate圧縮

Hellishly Slow Level 13 Deflate Compression (kirill.korins.ky)

86 pointsby zX41ZdbW25 コメント

要約

DEFLATEレベル13は、libdeflateの意図的に非実用的な圧縮レベルで、出力は標準DEFLATEのままでありながら、エンコーダは解析、ハフマン、ブロック分割の選択により多くの時間を費やします。Silesiaコーパスでは、レベル12と比較して86,990バイト(0.134%)のサイズ削減を達成しましたが、実行速度は56.4倍遅くなりました。このコストは、データが一度圧縮され、何度も配布される場合にのみ許容されます。

全文翻訳

地獄のように遅いレベル13 DEFLATE圧縮

要約

DEFLATEレベル13は、意図的に非実用的なlibdeflateの圧縮レベルです。出力は標準的なDEFLATEのままで、エンコーダーはパース、ハフマン符号化、ブロック分割の選択肢を探索するのに遥かに多くの時間を費やします。Silesiaコーパスでは、レベル12と比較して86,990バイト(0.134%)節約できましたが、実行速度は56.4倍遅くなりました。このコストは、データが一度だけ圧縮され、多数回配布される場合にのみ許容されます。

なぜDEFLATEか

DEFLATEは、そのデコーダーが既にどこにでも存在するため、最適化する価値があります。HTTPコンテンツエンコーディング、ZIPアーカイブ、PNGの内部、ソフトウェア配布、バックアップツール、組み込みフォーマットなどで、同じLZ77とハフマン符号化の設計が依然として使用されています。デコーダーの契約は固定されていますが、エンコーダーは依然としてマッチング、ブロック境界、ハフマンテーブルを選択します。より良い選択は、互換性を変えずにサイズを改善します。

ベースラインはlibdeflateレベル12であり、これは最も強力な実用的なDEFLATEエンコーダーの1つです。レベル13の実装は、プルリクエストとしてアップストリームに提供されました。

レベル13の仕組み

レベル13は、libdeflateのほぼ最適なパーサーを維持しますが、その選択をより高コストにします。32 KiBのDEFLATEウィンドウ全体を検索し、15回の最適化パスを許可し、最大50,000バイトのブロックに静的ハフマン最適化を適用します。フォーマットの拡張は一切行われません。

テキストのようなデータの場合、レベル13はブロックサイズの確定を遅延させます。現在のブロック開始位置から最大64 KiBをサンプリングします。サンプルにNULLバイトが含まれておらず、最大97種類のバイト値しか含まれていない場合、ソフトブロックサイズは300,000バイトから1,000,000バイトに増加します。この仮定は単純です。安定したバイト分布があれば、1つのハフマンテーブルでより多くのデータをカバーできます。

パーサーは、最小コスト検索を広げます。各マッチ長に対して最も安いオフセットを選択し、リテラルとマッチ長統計から初期ハフマンコストを推定し、キャッシュされたマッチからオフセットスロットの頻度を推定し、測定された動的ハフマンコストを静的ハフマンおよびリテラルのみのエンコーディングと比較できます。

ブロック分割も遅延されます。コンプレッサーは、パーサーの状態とともに最大9つの分割候補を格納し、その後、ブロック全体と候補区間に対する境界付き最短パスをスコアリングします。単一の分割でコストが勝つことがあります。複数分割パスは、ブロック全体よりも少なくとも512ビット上回る必要があります。選択されたパースは、最終的なフラッシュのためにキャッシュされます。

遅さは制限されています。検索パス、分割候補、ブロックサイズはキャップされているため、レベル13はturtledeflateのような無限最適化ループや、ECTのようなより広範なファイルオプティマイザーに入ることはできません。

リグレッションポリシー

開発は、Silesiaコーパスに対するゼロ圧縮リグレッションポリシーを使用して行われました。多くの手法が試みられましたが、他の圧縮ファイルを増やさずに、少なくとも1つの圧縮ファイルを厳密に減少させた変更のみが、最終的なレベル13構成に生き残りました。

Silesiaコーパスは、繰り返し開発を行うには十分小さいですが、単一ファイルのチューニングを罰するには十分混合されています。テキスト、バイナリ、データベース、画像、構造化データが含まれています。

Silesiaの結果

Silesiaコーパスにおけるlibdeflateレベル12対レベル13

filelevel 12 size / timelevel 13 size / timesize difftime diff
dickens3'688'552 / 1'289 ms3'684'671 / 83'512 ms-3'881 (-0.105%)+82'223 (+6378.8%)
mozilla18'267'490 / 4'959 ms18'235'120 / 110'754 ms-32'370 (-0.177%)+105'795 (+2133.4%)
mr3'448'571 / 1'627 ms3'443'723 / 16'260 ms-4'848 (-0.141%)+14'633 (+899.4%)
nci2'766'224 / 7'935 ms2'758'044 / 673'648 ms-8'180 (-0.296%)+665'713 (+8389.6%)
ooffice2'998'130 / 424 ms2'995'604 / 8'676 ms-2'526 (-0.084%)+8'252 (+1946.2%)
osdb3'642'347 / 798 ms3'641'341 / 4'942 ms-1'006 (-0.028%)+4'144 (+519.3%)
reymont1'702'796 / 1'005 ms1'699'494 / 81'839 ms-3'302 (-0.194%)+80'834 (+8043.2%)
samba5'135'662 / 2'889 ms5'122'812 / 141'227 ms-12'850 (-0.250%)+138'338 (+4788.4%)
sao5'255'575 / 333 ms5'255'358 / 1'687 ms-217 (-0.004%)+1'354 (+406.6%)
webster11'565'754 / 6'452 ms11'555'293 / 475'196 ms-10'461 (-0.090%)+468'744 (+7265.1%)
x-ray5'754'248 / 305 ms5'748'141 / 3'276 ms-6'107 (-0.106%)+2'971 (+974.1%)
xml633'760 / 1'104 ms632'518 / 69'504 ms-1'242 (-0.196%)+68'400 (+6195.7%)
total64'859'109 / 29'120 ms64'772'119 / 1'670'521 ms-86'990 (-0.134%)+1'641'401 (+5636.7%)

レベル13はコーパス全体で86,990バイトを節約し、0.134%の削減となりました。実行時間は1,641,401 ms(約27.4分)増加しました。最も相対的に効果が高かったのはnciで0.296%でした。saoはわずか0.004%の変化でした。