はじめに

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

TypedArray#set の使用

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

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

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

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

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

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

20120520203515

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

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

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