はじめに

このエントリーは前回の続きです。 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 と同じように拡張時にシーケンシャルなデータに寄せることも考えていますが、同じように倍々方式にはならないと思います。 有効な手段ができたらまたエントリーを書いて報告したいと思います。