地獄のように遅いレベル13 Deflate圧縮
Hellishly Slow Level 13 Deflate Compression (kirill.korins.ky)
要約
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
| file | level 12 size / time | level 13 size / time | size diff | time diff |
|---|---|---|---|---|
| dickens | 3'688'552 / 1'289 ms | 3'684'671 / 83'512 ms | -3'881 (-0.105%) | +82'223 (+6378.8%) |
| mozilla | 18'267'490 / 4'959 ms | 18'235'120 / 110'754 ms | -32'370 (-0.177%) | +105'795 (+2133.4%) |
| mr | 3'448'571 / 1'627 ms | 3'443'723 / 16'260 ms | -4'848 (-0.141%) | +14'633 (+899.4%) |
| nci | 2'766'224 / 7'935 ms | 2'758'044 / 673'648 ms | -8'180 (-0.296%) | +665'713 (+8389.6%) |
| ooffice | 2'998'130 / 424 ms | 2'995'604 / 8'676 ms | -2'526 (-0.084%) | +8'252 (+1946.2%) |
| osdb | 3'642'347 / 798 ms | 3'641'341 / 4'942 ms | -1'006 (-0.028%) | +4'144 (+519.3%) |
| reymont | 1'702'796 / 1'005 ms | 1'699'494 / 81'839 ms | -3'302 (-0.194%) | +80'834 (+8043.2%) |
| samba | 5'135'662 / 2'889 ms | 5'122'812 / 141'227 ms | -12'850 (-0.250%) | +138'338 (+4788.4%) |
| sao | 5'255'575 / 333 ms | 5'255'358 / 1'687 ms | -217 (-0.004%) | +1'354 (+406.6%) |
| webster | 11'565'754 / 6'452 ms | 11'555'293 / 475'196 ms | -10'461 (-0.090%) | +468'744 (+7265.1%) |
| x-ray | 5'754'248 / 305 ms | 5'748'141 / 3'276 ms | -6'107 (-0.106%) | +2'971 (+974.1%) |
| xml | 633'760 / 1'104 ms | 632'518 / 69'504 ms | -1'242 (-0.196%) | +68'400 (+6195.7%) |
| total | 64'859'109 / 29'120 ms | 64'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%の変化でした。