はじめに

まずは宣伝から。
このたび JavaScript で Inflate の実装を行いました！ GitHubで公開中で MIT License です。（以前作った Deflate 実装もセットになってます）

https://github.com/imaya/zlib.js

このエントリーでは、本来ならいかに自分の実装がスゴいかを紹介するところなのですが、前編では自分よりはるか以前に公開された PDF.js の Inflate 実装の素晴らしさを、最適化を進めるにつれて思い知ったのでご紹介させていただくことにします。

バッファ管理の効率の良さ

最初は気持ち悪いと思っていたのですが、一番よく考えてるなと思ったのがバッファ管理です。

PDF.js は Typed Array でバッファを持っているのですが、Typed Array は通常の Array のように後からサイズを大きくするという事ができません。 では Inflate 処理を行なっている時に出力用のバッファがあふれた時にどうするのかというと、長さが倍の Uint8Array を用意して、そこに１つずつコピーして古いバッファを破棄しています。 （倍で足りなさそうなときは、一気に 2, 4, 8 倍…などとしています）

なぜ最初、この実装が気持ち悪いと思ったかというと、最初の方のデータはバッファが拡張されるたびに何度もコピーされるため、非効率に思えたのです。 しかし、拡張後の大きさを 2 倍にするという事で必ずコピーの回数は最後に拡張した大きさの2倍を超えることはありません。 また、常にシーケンシャルな形で持っているために、 LZ77 の前方からコピーする処理がシンプルに出来る事や、出力する際に subarray で切り出すだけで良い(ビューを提供するだけなのでコピーが発生しない)というのも大きな利点です。 これらが何故利点になるかというと、LZ77 のコピーの処理がシンプルということは何万回も呼ばれるループ処理の処理を簡単にすることなので、ここでも速度の面で有利になり、subarray で切り出すだけで良いというのは最後にシーケンシャルなデータにするためのコピーが発生しないということで、これも速度の面で有利になります。

その他諸々の高速化手法

一番効率的だと感じたのがバッファ管理ですが、PDF.js はそれ以外の効率化ももちろん行なっています。例えばハフマン符号のデコードを事前計算テーブルを使って効率化しています。ハフマン符号のデコードは当然ですがデータサイズ分行われるので重要な部分です。他にもループ内で使われるようなプロパティはローカル変数にするなどの基本的なテクニックなども使われていたりします。

RFC1951 によると、一番短いビット長の符号からビット長を大きくしていって合致するハフマン符号があるかないかで判断するといった事が書かれていますが、事前計算テーブルを使う方法ではこれと逆の事を行います。 つまり、一番長いビット長で全てのビットパターンを格納できるテーブルを作っておき、短いビット長の場合は余った部分にも短いビット長と同じデータを入れておくのです。こうすることで、最長のビット長で1回データ先読みして、そこから元の記号がわかり、合致した符号の分だけ読み進めるというだけで効率的にデコードすることができます。

性能比較

そんなわけで PDF.js の凄さを紹介してきたのですが、一応自分でも作ってみたわけですし、比較を行いました。あ、比較するまでもないのでここでサラッと言っておきますが速度面では大幅に負けています。

バッファサイズ(ピーク時)

bufsize

オレンジの方が PDF.js で青の方が自作のライブラリです。PDF.js が大雑把な増え方をするのに比べて、自作のライブラリはサイズに比例してバッファを細かく増やしているのがわかると思います。この点だけは PDF.js に比べて有利な場面があると思っています。

コピー回数

copycount

JavaScript の Typed Array ではデータをまとめてコピーという事ができないので、要素1つずつ丹念にコピーしています。ですので、ここでカウントされた値は総コピーバイト数と思っていただいて良いと思います。詳しくは次回にしますが、PDF.jsが省略可能な、最後にシーケンシャルなデータにする部分で大きな差がでているためこのような結果になっています。前述のとおり、コピー回数の差が処理速度の差なので、速度の差も大半がここだと思っています。

続きます

本当は1回で終わらせるつもりだったのですが、予想外にグラフの作成に時間がかかってしまったため次回に回したいと思います。
次回は、これだけ PDF.js と比べて性能が悪いとわかっている自作のライブラリの構造やアルゴリズムについて書くという罰ゲームのような事をしようと思っています。