Facebook、Zlibを上回る新しい圧縮アルゴリズムをオープンソース化

Facebookが新しい圧縮アルゴリズムZstandard 1.0をオープンソース化した。FacebookのエンジニアであるYann Collet氏とChip Turner氏の記事によると、これは「現在の標準」であるzlibよりも高速かつ高効率な、数少ない圧縮アルゴリズムの1つだという。Facebook ZstandardはCollet氏によるこれまでの成果を利用している。彼はLZ4の作者でもあり、もともと2015年に新しいアルゴリズムの最初のバージョンをリリースした。

Facebookのベンチマークによると、Zstandardはどんな圧縮率と帯域幅の組み合わせでもzlibを上回っている。

特に、標準のロスレス圧縮Silesiaコーパスを用いたとき、Zstandardはずば抜けた性能を見せた。

• 同じ圧縮率で約3–5倍高速
• 同じ圧縮スピードで10–15%小さいファイルを生成
• 圧縮率によらず2倍高速に解凍
• ずっと高い圧縮率 (~3.15に対して~4x) までスケール

ZstandardはFinite State Entropyを用いている。これはJarek Duda氏によるエントロピー符号のためのASN (Asymmetric Numeral Systems)に関する研究に基づいている。ANSは「スピードと圧縮率のトレードオフに決着をつける」ことを目指し、きめ細かな符号と非常に高速なエンコードの両方に使えて、データ暗号化をサポートする。だが、Zstandardのパフォーマンス改善の根底にあるのは、設計と実装における様々な選択にある。

• zlibは32KBウィンドウに制限されていたが、Zstandardはモバイルや組み込み環境を含む最近の環境における巨大なメモリを利用し、固有の制限を課されない。

• 算術演算間のデータ依存性を取り除くことで、複数のALUによって並行してシンボルをデコードするため、新しいHuffmanデコーダーHuff0が使われている。

• Zstandardはできるだけ分岐をなくそうとし、間違った分岐予測によるコストのかかるパイプラインのフラッシュを最小限にする。たとえば、whileループを分岐を使わずに書き直すとどうなるか、以下に示す。

  /* 従来のバージョン */
  while (nbBitsUsed >= 8) { /* 各whileテストは分岐 */
    accumulator <<= 8;
    accumulator += *byte++;
    nbBitsUsed  -= 8;
  }
  
  /* 分岐なしバージョン */
  nbBytesUsed = nbBitsUsed >> 3;
  nbBitsUsed &= 7;
  ptr += nbBytesUsed;
  accumulator = read64(ptr);

• repcodeモデリングによって、数バイトしか違わないシーケンスの圧縮を大幅に改善する。

Zstandardにはコマンドラインツールとライブラリがあり、どちらもCで書かれている。具体的に利用可能なハードウェア、圧縮対象データ、最適化のボトルネックに合わせて慎重に微調整できるよう、20以上の圧縮レベルを提供している。Facebookは、多くのユースケースに適しているデフォルトのレベル3からはじめることを推奨している。それから、スピードとスペースの適切なトレードオフを確かめながらレベル9まで上げてみたり、より高い圧縮率を求めて、圧縮スピードを気にしない場合には、レベル20以上を確保することをすすめている。

また、Zstandardの将来のバージョンに何がやってくるのか、Collet氏とTurner氏はいくつかのヒントを提示している。それにはマルチスレッドのサポート、高速な圧縮と高い圧縮率を可能にする新しい圧縮レベルなどが含まれる。

ZstandardはAppleのZLFSEやGoogleのBrotliに続くものだ。両者ともオープンソースで、それぞれ特定のユースケースに最適化しようとしている。BrotliはWebアセットとAndroid APKにとって高い圧縮率になるようチューンされているようだ。LZFSEはZlibよりも高速で同等の圧縮率でありながら、低消費電力であることを目指している。