JavaScriptで書いたDeflate圧縮アルゴリズム高速化の話

これは ドリコム Advent Calendar 2018 の6日目です。
5日目は dhiroki さんによる デスクワークを再発明するためにフック入力キーボードを作りました です。

自己紹介

株式会社ドリコム enza事業本部 ゲームSDK開発部 山﨑です。
業務ではHTML5 ゲームプラットフォーム enza にて、HTML5ゲーム開発における課題解決とSDK提供を行なっています。

はじめに

業務外ですが、ブラウザで動くJavaScriptのモダンで軽量なDeflate圧縮ライブラリを目指してzlib.esを作成しました。
しかし、Deflate仕様を愚直に実装した初版は50MBのデータ圧縮で1.5兆回以上のデータ比較が発生するような状態で、大きなデータでは処理速度が遅く使い物になりませんでした。
最新版ではまずまずの速度が出るようになったので、どのように改善してきたか共有したいと思います。

Deflateについて

処理をイメージしやすいよう、Deflate圧縮アルゴリズムについてスーパーざっくり説明します。

DeflateはLZ77とハフマン符号化という2つの圧縮アルゴリズムの組み合わせになっています。

スーパーざっくりLZ77

LZ77では繰り返しデータの圧縮を行います。

繰り返しデータの圧縮は
"AAAAAAAA"という8桁のデータを、Aが8回繰り返すことを示す"A8"という2桁のデータに省略するイメージの圧縮方法です。

LZ77では出現位置と一致した長さの2つのデータに置き換えることで、同じ文字だけでなく同じ文字パターンの繰り返しデータを圧縮できます。

スーパーざっくりハフマン符号化

ハフマン符号化では偏りのあるデータの圧縮を行います。

偏りのあるデータの圧縮は
本来なら8bitで表現するデータを、出現するデータのみで再定義した出来る限り短いbit表現に置き換える圧縮方法です。

例えば

AAAABBBB

という8バイトのASCII文字をbitで表現すると

01000001 01000001 01000001 01000001 01000010 01000010 01000010 01000010

という64bitのデータになります。

この例ではAB2種類の文字のみに出現が偏っているため、A=0 B=1と再定義すれば、合計64bit必要だったデータを8bitに省略する事ができます。

00001111

ハフマン符号化では、より多く出現するデータをより短いbit表現に置き換える圧縮を行います。

詳細を知りたい方は

以下のサイトがオススメです。

https://www.futomi.com/lecture/japanese/rfc1951.html
https://www.slideshare.net/7shi/deflate
https://www.marguerite.jp/Nihongo/Labo/Image/Deflate.html
http://darkcrowcorvus.hatenablog.jp/entry/2016/09/23/195644

改善内容

速度改善に有効だった内容とその効果をまとめました。

前提

計測環境

MacBook Air (11-inch, Mid 2013, メモリ4GB)
Node.js 8.12.0

計測方法

圧縮/解凍にはPNG画像から抜き出したデータ¹を使用します。
記載しているデータ量は圧縮前のデータ量です。
記載している処理時間は5回計測した平均値です。

MapからObjectへの書き換え

ES2015らしくと思いMapを多用してましたが、単純なキーバリューの辞書として使うだけなのでObjectに変更しました。

480KBのデータ解凍が
150ms -> 100ms に改善

https://github.com/zprodev/zlib.es/commit/75deef6e6d4f173fd86a0889c37a2c217f6d62b0
https://github.com/zprodev/zlib.es/commit/173fe0d6b8e8d9e4c1c67078b2b4130da1aa0b34

メモリの再割り当てを減らす

解凍後データの格納配列を固定値で少しずつ拡張する実装でしたが、解凍後データが巨大だと拡張回数も膨大になるため、解凍前データサイズを基準にある程度大きめに確保するようにしました。

50MBのデータ解凍が
28000ms -> 1300ms に改善

インデックス検索の実装

LZ77仕様の一部に下記があります

• 最大32768バイトまで遡って繰り返しデータを検索できる
• 最小3バイト以上一致するデータを繰り返しデータとして扱う

改善前は、1バイト進むごとに32768バイト前から一致するデータを検索していました。
その場合、1バイトにつき3万回以上の比較が行われ、100KBなら30億回以上、50MBなら1.5兆回以上の比較が行われることになります。

そこで、最初に1度だけデータ全体をなめて連続3バイトをキーとした出現位置のインデックスを作成し、1バイトにつき1回だけインデックス検索を行えば繰り返しデータの出現位置が分かるよう変更しました。

// ABCDEABCDEABCDEのインデックスイメージ
{
  ABC:[0,5,10],
  BCD:[1,6,11],
  CDE:[2,7,12],
  DEA:[3,8],
  EAB:[4,9],
}

これにより
480KBのデータ圧縮が
35000ms -> 19000ms に改善

forEachからforへの書き換え

よく言われている話ですが、やっぱりforが速かったです。
何度も繰り返し処理が行われる箇所に対し、forEachからforへの書き換えを行いました。

480KBのデータ圧縮が
19000ms -> 5500ms に改善

繰り返しデータ検索を末尾から開始

LZ77仕様の一部に下記があります（先の説明と一部重複）

• 最大32768バイトまで遡って繰り返しデータを検索できる
• 繰り返しデータの[出現位置]は何バイト遡ったかを表す数値
• 繰り返しデータの[一致した長さ]の最大値は258バイト

改善前は、32768遡った位置を先頭としてデータの検索を始めていました。
圧縮率を上げるために出来る限り[出現位置]の数値を小さく、出来る限り[一致した長さ]が長いデータを見つけるべく、先頭から末尾まで全て検索していました。

改善後は、末尾から32768まで遡りながらデータの検索を行うようにしました。
こうすることで、繰り返し長258以上のデータが見つかった時点で、[出現位置]が最も小さく[一致した長さ]も最も長いデータである事が断定でき、それ以上検索を続ける必要がなくなりました。

4MBのデータ圧縮が
19000ms -> 3800ms に改善

https://github.com/zprodev/zlib.es/commit/0dc86ec773525a8006235e6c6e675e4ba7f92bbe
(他の改修も混ざってますが、インパクトが大きかったのは末尾から検索への変更でした)

圧縮率と速度のトレード

50MBのデータ圧縮は数分待っても処理できない状態でした。
閾値を設定してある程度良い感じに圧縮できたところで切り上げるよう変更しました。

50MBのデータ圧縮が
計測不能 -> 19000ms に改善

圧縮率は数%低下しますが、動かないよりは良いかなと。

ブロック分割

Deflateでは任意の数にデータを区切って圧縮する事ができます。
1つのブロックにまとめた方が圧縮効率は良いと思いますが、巨大なデータの圧縮ではメモリ使用量起因だと思われる速度低下が見られたため、ブロック分割を導入しました。

50MBのデータ圧縮が
19000ms -> 13500ms に改善

まとめ

• MapよりObject、forEachよりforなどよく言われている高速化はやはり有効でした
• インクリメント系ではi++より++iやi=(i+1)|0も試しましたが目に見える改善は確認できませんでした
• メモリ（配列）割り当てのインパクトが結構大きいので巨大な可変長データを扱う場合は要注意です
• 圧縮率と処理速度の両立はなかなか難しいものですね

1. 圧縮が効きやすいようにPNG独自のフィルタリングが行われているデータ ↩