document

HTML5 & JavaScript side
twitter: @y_imaya

Inflate 実装の修正

はじめに

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

TypedArray#set の使用

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

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

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

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

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

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

20120520203515

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

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

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

Inflate 実装を作って PDF.js の凄さを思い知った話 (後編)

はじめに

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

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

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

bufsize

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

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

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

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

簡単に言うと

連結リスト方式です。

初期状態

20120426042552

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

バッファの拡張

20120426043909

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

バッファの連結

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

おわりに

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

Inflate 実装を作って 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 を用意して、そこに1つずつコピーして古いバッファを破棄しています。 (倍で足りなさそうなときは、一気に 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 と比べて性能が悪いとわかっている自作のライブラリの構造やアルゴリズムについて書くという罰ゲームのような事をしようと思っています。

png identify という PNG の情報を色々表示するものを作りました

png identify とは

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

使い方

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

どんな情報を表示する?

まずはざっと一覧で。

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

イメージヘッダ情報

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

ihdr

チャンク

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

chunks

パレット

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

plte

フィルタ

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

filter

イメージデータ圧縮関係

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

blocks

制限

  • 一度のドラッグアンドドロップで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 です。

最近実装した最長一致探索について

はじめに

最近のコミットで最長一致探索部分を書きなおしたらシンプルになったのでメモ替わりに書いておきます。

まず、DEFLATE では chained hash table を使用することが推奨されています。 LZ77 関連では処理の高速化に関していろいろ特許があるようなので、今のところ特許問題のでていないこの方法を使用しています。

chained hash table とは、連続する 3 Byte をハッシュのキーとして辞書を持ち、 ハッシュキーの値に該当位置を記録しておくことで、高速に LZ77 の長さ距離符号の判定を行うことができます。 (なぜ 3 Byte をハッシュキーにするかというと、DEFLATE の長さ距離符号の長さの最小が 3 Byte だからだと思います。)

chained hash table を利用したとしても、わかるのは「最低でも 3 Byteは一致している」ので、 複数の候補があった場合はそこから最長のものを絞り込んでいかなければいけません。

最長一致探索

そこで、複数の「最長一致候補」から最長のものを探索する仕組みが必要になります。 以前はちょっと凝ろうとしたことをして、逆に複雑になった上にロクな出来ではなかったので、 今回以下のようなシンプルな方式に修正しました。

最長候補は常に 1 つだけ

以前は最長候補は探索処理の最後まで持っておき、最後に場合によって切り替えられるようにしていました。 ただ、あまり意味がなかったので今回は常に 1 つだけ持っておくようにしました。 この時、最長マッチ長が同じ候補が複数あった場合にどちらを選択するか決定するルールが必要なので、 「マッチ長が同じだった場合は後方(現在の位置と近い)ものを採用する」というようにしました。

なぜ後方のものを採用するかというと、長さ距離符号にした際に距離符号を短くできることがあるからです。 (extra bits はハフマン符号化の対象にならない。下記に長さによる extra bits の長さを示します。)

長さextra bits 長さextra bits
3 - 100 67-1304
11-181 131-2575
19-342 2580
35-663   

これにより無駄な配列関連の処理がばっさり減らせました。

基本は左から 1 Byte ずつ比較処理

以前はちょっと凝ろうとしたことをして複雑になってました。 すでに修正済みなので簡単にどういったことをやっていたか説明すると、例えば以下のようなマッチ候補があった時に

 "abcdefghijklmnop" ...

以下のように一定の長さに分割します。(実際に分割するわけではなく意味上の区切りですが)

  "abcdefgh" "ijklmnop" ...

そして、下記のように後方から比較していました。

  ".......h"
  "......g."
  ".....f.."
  "....e..."
  .
  .

これは何がしたかったのかというと、 chained hash table によって前 3 Byte の一致がしているのはわかっているので、 そこから絞り込む際 4 Byte 一致してるものというのは比較的多いのではないかと考えました。 ( LZ77 で圧縮可能なデータというのは偏りがあるため)

同様に 5 Byte, 6 Byte ... と見ていくよりも末尾から見ていく方が速く候補を落とせると考え、実際一定の速度向上はしました。

今回の実装では、そのへんをばっさりとやめ「基本は」左から1文字ずつ見ていくようにしました。 ただ、全ての候補を1つずつ単純に左から見ていくのも素直すぎるので、今回は以下のような仕組みを加えています。

現在までの最長マッチの長さを記録しておき、次の候補は現在の最長マッチ分右に移動し、そこから左に向かって走査していき、すべて一致していたら最長マッチ以降のデータを右に向かって調べていきます。

以下の最長マッチ候補を例に説明します。

 -. "abcdefghijklmn" // データ
 1. "abcde123456789" // マッチ候補 1
 2. "abcdefgh123456" // マッチ候補 2
 3. "abcdef12345678" // マッチ候補 3
 4. "abcdefg1234567" // マッチ候補 4
 // chained hash table の参照で 3 Byte の一致
 -. "abc..........."
 1. "abc..........."

 // 右に向かって 1 Byte ずつ一致探索した結果 5 Byte が一致
 -. "abcde........."
 1. "abcde........."
 走査方向 → 
 最長一致: 5
 最長一致マッチ: 1
 // 次の候補も chained hash table から 3 Byte の一致
 -. "abc..........."
 2. "abc..........."

 // 5 Byte 目, 4 Byte 目 と確認
 -. "abc.e.........", "abcde........."
 2. "abc.e.........", "abcde........."
 走査方向 ←

 // 最長一致までの長さは全て一致したので右に走査していく
 -. "abcdefgh........"
 2. "abcdefgh........"
 走査方向 →
 最長一致: 8
 最長一致マッチ: 2
 // 次の候補も chained hash table から 3 Byte の一致
 -. "abc..........."
 3. "abc..........."

 // 8 Byte 目を確認するが一致しないので探索終了
 -. "abc....h....."
 3. "abc....2....."
 走査方向 ←
 // 次の候補も chained hash table から 3 Byte の一致
 -. "abc..........."
 4. "abc..........."

 // 8 Byte 目を確認するが一致しないので探索終了
 -. "abc....h....."
 4. "abc....1....."
 走査方向 ←

おわりに

もっと良い方法あったら教えて下さい。

記事検索
最新コメント
最新トラックバック
カテゴリ別アーカイブ
タグクラウド
QRコード
QRコード
  • ライブドアブログ