はじめに

最近、Inflate 実装のチューニングを行うことが多かったので、現状でどの程度の速度が出ているか把握するため、他の実装と比較してみました。

比較に使用した ZLIB ライブラリ

今回の比較では、以下のライブラリの存在を確認しています。 uncompress.js に関しては、今回入手できなかったため比較対象からはずしています。

各ライブラリの簡単な特徴

分類について

見た感じ、大きく分けて３種類に分類することが出来ます。

• zlib 移植系
  • zlib-js
  • uncompress.js
  • zpipe
• pdf.js 系
  • pdf.js
  • jsziptools
• 独自実装系
  • zlib.js

FlateStream について

FlateStream の入力は同じ stream.js 内で定義されている Stream のオブジェクトです。
new FlateStream(new Stream(array)) のような形で使います。array は Uint8Array のコンストラクタに渡せるものならば何でも OK です。
FlateStream を利用しているライブラリでは、この Stream を直接使うのではなく、getBytes メソッドを呼ぶ部分のコードを削って Uint8Array をそのまま渡すようにしていることが多いようです。

ビルドについて

ビルドスクリプトなどがついていて、Inflate の比較においてサイズ削減が可能なものに関してはすべて最低限で行っています。

jsziptools

jsziptools はビルドスクリプトが添付されていて、必要な実装のみでビルドすることが可能です。
今回は以下のようにして、zlib 伸張のみでビルドしました。

$ python build.py -m zlib.decompress

zlib.js

zlib.js では全ての実装を分離してビルドすることが出来、リポジトリの bin ディレクトリにそれぞれのファイルが生成されています。
今回は ZLIB の伸張なので inflate.min.js と inflate_stream.min.js をそのまま利用しています。

比較条件

速度比較に利用したデータ

http://www.compression.ca/act/act-files.html で使用しているデータの中からいくつかを Node.js の Zlib でデフォルト設定のまま圧縮したものです。
また、画像に関しては HTML5 Logo (PNG) から IDAT チャンクを抜き出したものを使用しています。

それぞれのライブラリで入力データの形式が違うので、データは予め String, Array, Uint8Array それぞれの形式に変換し、最も速度の出るものを利用しています。(純粋に伸張処理にかかった時間で比較しています。)
実際にライブラリで使用する際には、対応していない入力形式だった場合は変換コストも考慮して選ぶと良いかもしれません。

Adler-32 Checksum について

ほとんどの実装では Adler-32 によるチェックは行われないか、あるいはオプショナルであるため、今回の比較では行わないようにしています。

その他

比較結果について

Inflate は実装毎にバッファの管理方法が異なったりするため、展開するデータによって性能が上下することがあります。ここでの結果はあくまでも参考として利用した方が良いです。

zlib.js について

zlib.js では最新のコードは develop ブランチになっています。今回の比較では develop ブランチの実装を用いています。

ストリーム版 (inflate_stream.js) の結果も添付していますが、一度に全てのデータを流し込んでいるのであまり参考になりません。これは本来、断片的にデータが取得可能な場合に威力を発揮する実装です。

比較時の名前について

zlib-js と zlib.js は名前が似ているため zlib-js は iz-zlib と表記させていただきます。
すみません…。

比較結果

テキストデータ

The Three Musketeers

実行可能バイナリ

PINE

画像データ

HTML5 Logo (IDAT)

補足 (2012/08/15 - 23:22)

グラフの表示には jsperfview というものを使っているのですが、それで利用している Browserscope の API では最近のブラウザは表示されないようです。できるだけリンクをクリックして jsperf の方のグラフを見ることをおすすめします。

補足の補足 (2012/08/16 - 12:30)

jsperfview で利用している Browserscope の API パラメータを変更し、全てのブラウザの結果を表示するようにしました。

はじめに

前回までは他の実装に速度面で負けていた zlib.js の Inflate 実装ですが、最近の修正により他の実装と渡り合えるくらいまで速度向上したので、どんな修正をしたのかまとめておこうと思います。

TypedArray#set の使用

前回までは for-loop でバッファのコピーを行なっていましたが、Uint8Array などには set メソッドという値をまとめてセットするものがあるので(利用できる場合は)これを利用するようにしました。 このメソッドを使用することにより、従来の形式でもかなりの速度向上ができました。
実はこのメソッドの存在を完璧に失念していたのですが、@haxe さんと @polygon_planet さんのお陰で使うことができました。ありがとうございました！

新しいバッファ確保方法の実装

zlib.js のバッファ確保はブロック単位の連結リスト方式のような形式でしたが、新しいバッファの保持方法を実装しました。現在はデフォルトで新しい方を利用するようになっていますが、従来の方式も有利な点があるため選択可能になっています。

伸張後のサイズを予測して拡張

新しい方式は、基本的には倍々で増やす方法と同じく、常に連続したデータを保持します。 違うのは拡張する際の挙動で、倍々方式は2倍ずつ固定で増やしますが、こちらの戦略は伸長後のサイズをなんとなく予測して一気に拡張します。

伸長後のサイズ予測というと、難しそうな感じがするかもしれませんが、初期ブロックが埋まった際に、入力データのサイズと現在の読み込み位置から比率を計算して、初期ブロックのサイズに掛けるだけです。（本当はもっと正確な計算ができるのかもしれませんが、現時点ではアイデアがありません。）

この方式だと、運が良ければ1回の拡張で終わるのでとても速いですが、初期部分とそれ以降の部分で全然圧縮率が違う場合は拡張後のサイズが小さすぎるか、あるいは大幅に余ってしまいます。

そこで今回の実装では、小さすぎる場合の対処として最小の拡張倍率を2倍にして最低でも倍々方式と同じくらいの速度が出るようにしています。最大のサイズが大きすぎる場合は特に上限を設けていません。ただし、大きく取った後、出力する際に新しいバッファに切り詰める設定というのは用意しておきました。

今回の実装では対象データによって大きく結果がかわりますので、比較用のデータはなしです。ただし、最小でも2倍で拡張するのと、サイズを計算する部分はほとんどコストがかかっていないため、大体の場合で速度ははやくなっていると思います。

はじめに

このエントリーは前回の続きです。 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 と比べて性能が悪いとわかっている自作のライブラリの構造やアルゴリズムについて書くという罰ゲームのような事をしようと思っています。

png identify とは

JavaScript で書かれた、PNG ファイルの様々な情報を表示するウェブブラウザ上で動作するアプリケーションです。(Chrome 16.0.912.77, Firefox 9.0.1 で動作確認) PNG, ZLIB の圧縮率向上をはかる際に、自分の求める詳細な情報を表示するツールが見当たらなかったので作成しました。

使い方

http://imaya.github.com/png.identify/
上記のページを開き、そのページに PNG ファイルをドラッグアンドドロップするだけです。

どんな情報を表示する？

まずはざっと一覧で。

• ファイル名
• イメージヘッダ
• チャンク
• パレット
• フィルタ
• イメージデータ圧縮関係

イメージヘッダ情報

PNG の IHDR チャンクの情報を表示します。

チャンク

すべてのチャンクの位置とサイズ、CRC32ハッシュ値を表示します。

パレット

PLTE チャンクがある場合はパレットの詳細を表示します。

フィルタ

画像で使用されているフィルタを表示します。 複数フィルタのフィルタが混在している場合は、各フィルタの割合と全てのフィルタを表示します。

イメージデータ圧縮関係

IDAT チャンクで利用されている ZLIB に含まれるブロックの圧縮前と圧縮後のサイズと割合を表示します。

制限

• 一度のドラッグアンドドロップで1つのファイルしか使えません。
• Typed Array, Drag and Drop API, File API の使えるブラウザじゃないと動作しません。
• Web Workers などは使っていないので、スペックによってはスクリプトの停止ダイアログが出るかもしれません。

使用ライブラリ

png.js: https://github.com/devongovett/png.js

ソースコード

GitHub リポジトリ: https://github.com/imaya/png.identify
ライセンスは MIT License です。