はじめに

このエントリーは前回の続きです。 PDF.js の方式については今回はほとんど触れていませんので、そちらに興味がある方はごめんなさい。

安定したメモリ使用量にしたかった

前回のおさらいになりますが、まずは PDF.js の実装と自作ライブラリのバッファ使用量の違いを見てみます。

自作ライブラリでは元データのサイズに比例して安定した増加をしているのに対し、PDF.js では2倍ずつ増加しているため元のサイズが大きくなるにつれてバッファを確保してしまいすぎるといった事が見られます。自作ライブラリでは「概ね元データのサイズに比例してバッファを使用したい」と思っていたので、速度を犠牲にしてこのような形になっています。

自作ライブラリでは、ブロックサイズを指定してその大きさずつ増えているのでこのような増加になっています。 ただ、ブロック単位でバッファを増やしているとはいっても、高速化の過程でただのブロックとは異なった形になってしまっています。

自作ライブラリのバッファ管理

というわけで、自作ライブラリではどのような構造で持っているのか説明しようと思います。

簡単に言うと

連結リスト方式です。

初期状態

上記のように、処理用のバッファの前後に固定のブロックがついた作りになっています。 なぜこのような部分が付いているかというと、LZ77処理の高速化のためです。 Deflate で使用されている LZ77 は最大 32,768 Byte 戻ってそこから最大 258 Byte コピーするという仕様のため、このコピーの途中でバッファの断絶が起こると速度面で影響が出るのでこのように長さ距離符号が先頭や末尾に出現してもバッファの断絶を意識しないで良いという構造になっています。

バッファの拡張

バッファがブロックサイズを超えた際はバッファの拡張を行います。 この際、元のバッファはそのままで、新しくブロック分(+はみ出ている場合はその分も)サイズのバッファを作成してそれにコピーし、リストに投げ込みます。 ここで出力サイズの2倍+32,768Byte のコピーが発生していることがわかります。あまり効率的ではないです。 そして、コピーが終わった後は出力用のポインタを初期位置にもどします。あとは初期状態と同じです。

バッファの連結

出力時にはシーケンシャルなデータとなっていないといけないため、これらを連結する処理が走ります。 バッファリストからブロック単位で最初から最後までコピーするため、最後に今までのバッファサイズの合計分のコピーが必要となります。バッファ拡張時の処理と合わせると、概ねサイズの 3 倍のコピーが必要となってしまいます。 PDF.js との一番大きな違いはこの部分で、PDF.js の倍々方式ではすでにシーケンシャルなデータとなっているため、この処理は必要ありません。ビューを切り出す subarray をうまく使っているとおもいます。 また、ピーク時のバッファサイズであまり有利にならないのもこの部分が問題となっています。

おわりに

安定したバッファ量にしようと思って今回の方式をとったのですが、PDF.js の subarray で切り出す方式がかなり有効なため、思ったよりも有利になりませんでした。 今後、PDF.js と同じように拡張時にシーケンシャルなデータに寄せることも考えていますが、同じように倍々方式にはならないと思います。 有効な手段ができたらまたエントリーを書いて報告したいと思います。

はじめに

まずは宣伝から。
このたび 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 の凄さを紹介してきたのですが、一応自分でも作ってみたわけですし、比較を行いました。あ、比較するまでもないのでここでサラッと言っておきますが速度面では大幅に負けています。

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

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

コピー回数

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

続きます

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