地獄のように遅いレベル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 ファイル レベル12サイズ / 時間 レベル13サイズ / 時間 サイズ差 時間差 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ミリ秒の実行時間を追加しました。最も強い相対的な結果はnciの0.296%で、saoはわずか0.004%の変化でした。