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

![eyecatch_AdventCalendar2018_06.png](https://qiita-image-store.s3.amazonaws.com/0/142643/6a57587a-d98e-dbe8-bd99-ce698aee32f1.png)
これは [ドリコム Advent Calendar 2018](https://adventar.org/calendars/3421) の6日目です。
5日目は dhiroki さんによる [デスクワークを再発明するためにフック入力キーボードを作りました](https://tech.drecom.co.jp/make-new-kewboard/) です。

## 自己紹介
株式会社ドリコム enza事業本部 ゲームSDK開発部 山﨑です。
業務ではHTML5 ゲームプラットフォーム [enza](https://enza.fun/) にて、HTML5ゲーム開発における課題解決とSDK提供を行なっています。

## はじめに
業務外ですが、ブラウザで動くJavaScriptのモダンで軽量なDeflate圧縮ライブラリを目指して[zlib.es](https://github.com/zprodev/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画像から抜き出したデータ[^1]を使用します。
記載しているデータ量は圧縮前のデータ量です。
記載している処理時間は5回計測した平均値です。

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

### 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 に改善

https://github.com/zprodev/zlib.es/commit/b35157dce5c9d2a8fef91cca79a2c0cd14c092d6

### インデックス検索の実装
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 に改善

https://github.com/zprodev/zlib.es/commit/86d6642cdbbdcd4dc34dfa6de694fc58b1ef6bc9

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

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

https://github.com/zprodev/zlib.es/commit/0728c08521c179805488d686e8ffd068fb686b60

### 繰り返しデータ検索を末尾から開始
LZ77仕様の一部に下記があります（先の説明と一部重複）

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

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

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

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

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

### 圧縮率と速度のトレード

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

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

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

https://github.com/zprodev/zlib.es/commit/218afcfe105074a8345bcb312315fb71edc7bc23

### ブロック分割

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

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

https://github.com/zprodev/zlib.es/commit/fcbf3d1529f51e83a8fb27c254d036e7e5c1da65

## まとめ

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