LlosLabソフトウェア開発ブログPDF、Delphi、およびドキュメントソフトウェア開発者向けのエンジニアリングノート。

技術記事

PDFlibPasのパフォーマンスプロファイリング:Delphiにおけるハッシュインデックス

Delphi PDF Library

DelphiおよびC++Builder向けのlosLabのPDFライブラリであるPDFlibPasは、4つの繰り返し作業のパターンを償却されたものに置き換えることで、そのレンダリングとコンテンツ生成の経路を高速化する:辞書キーのルックアップ用の遅延ハッシュインデックス、事前計算されたsRGBガンマルックアップテーブル、コンテンツストリーム演算子のディスパッチ用の先頭バイトによるバケット化、そして繰り返しの文字列連結の代わりのTStringBuilderである。この4つのどれも1つの劇的な発見から来たものではなかった——それらはすべて、プロファイルにおける同じ地味なパターンから来た:演算子ごとに一度、ピクセルごとに一度、あるいは文字ごとに一度呼ばれる小さな関数であり、その呼び出し内部の線形コストが文書全体にわたって2次あるいはそれに近いコストになってしまう。これがここでの一貫した筋である:同じ形の問題を攻める、4つの小さく無関係に見える修正、そしてそれぞれの正直な限界である

コンテンツストリームレンダラーは実際どこに時間を費やしているのか

PDFlibPasのコンテンツストリームレンダラーは、そのトークンごとのコストのほぼすべてを4つの狭いポイントに集中させる:/Resources、/ColorSpace、/Font、/ExtGStateに対するリソース辞書のルックアップ;Lab、Indexed、あるいはICCタグ付き画像のあらゆるデコード済みピクセルに対するガンマ補正;あらゆるコンテンツストリームのあらゆるトークンに対する演算子名のマッチング;そしてライブラリが出力を構築するあらゆる場所——保存時のリテラル文字列のエスケープ、XFDFエクスポート、スタンプと変数トークンの展開——における文字列の構築である。この4つそれぞれは単独ではわずかな作業しか行わないが、それぞれが現実的な文書全体で数千から数百万回実行される。これはまさに、O(n)やO(n²)の実装上の詳細が目に見えないものであることをやめ、プロファイルのトップエントリになり始める関数の形である

なぜ大きなPDFではリソース辞書のルックアップが遅くなるのか

TPDFDictionary.FindIndexByKeyNameは、レンダラーがすべての/Resources、/ColorSpace、/Font、/ExtGStateのルックアップを解決するために呼ぶものであり、以前は呼び出しのたびにEntries配列を先頭から歩いていた——3エントリのResources辞書には問題ないが、色やグラフィックステートに触れるあらゆる演算子で同じ辞書が探られるForm XObjectやExtGStateの多いページには高くつく。PDFlibPasは今や、辞書がDICT_HASH_THRESHOLD(16)エントリを超えると一度だけ遅延ハッシュインデックスを構築し、より小さい辞書は線形走査のままにする。なぜならほとんどのPDF辞書はそれほど大きくならず、3個のキーのためのハッシュテーブルは、それが節約する以上に構築コストがかかるからだ。このインデックスはPLAnsiStringHashをキーとするフラットなオープンアドレッシングテーブルであり、これは標準のオフセット基底2166136261と素数16777619を持つFNV-1aハッシュであり、このサイズに敏感な用途のためにSystem.Generics.Collectionsを持ち込むことを避けるために選ばれた

Const
  DICT_HASH_THRESHOLD = 16;

Function TPDFDictionary.LookupKeyIndex(Const Key: AnsiString): Integer;
Var
  H, Probe: Integer;
Begin
  Result:= -1;
  If FKeyHashMask= 0 Then
  Begin
    // Not built yet; small dictionaries stay linear since the
    // build cost would not amortize over a handful of entries.
    If Length(Entries)> DICT_HASH_THRESHOLD Then
      BuildKeyHash
    Else
      Exit;
  End;
  H:= PLAnsiStringHash(Key) And FKeyHashMask;
  Probe:= 1;
  While FKeyHash[H]<> -1 Do
  Begin
    If Entries[FKeyHash[H]].Key.Name= Key Then
    Begin
      Result:= FKeyHash[H];
      Exit;
    End;
    H:= (H+ Probe) And FKeyHashMask;
    Inc(Probe);
  End;
End;

このインデックスは、少しずつ維持されるのではなく無効化される:あらゆる変更を伴う呼び出し——AddEntry、DeleteEntryByKeyName、Assign、AddDict——はハッシュをクリアし、次のルックアップにゼロから再構築させる。これは、辞書のキーがTPDFNameオブジェクトであり、TPDFName.SetToは、辞書自身のメソッドを一切経由せずに、辞書のEntries配列にすでに座っているキーをリネームできることに気づくまでは無駄に見える——インクリメンタルなインデックスにはそのリネームを観測する方法がないが、遅延インデックスは単に再構築し、構造上正しいままである。その安全性の代償は、書き込みの後に大きな辞書が最初にクエリされたときのO(n)の再構築と、ハッシュテーブル自体のためのメモリ(3分の2の負荷率でスロットあたりおおよそ1つの整数)である——典型的な文書内の一握りの過大な辞書にとっては丸め誤差にすぎず、しきい値を現在の位置に保つことでPDFlibPasが小さい辞書ごとに支払うことを避けている本物のコストである

ピクセルごとにPowerを呼ぶ代わりにsRGBガンマを事前計算する

TPDFSimpleColorManager.XYZ2RGBは、Lab、Indexed、あるいはICCベースの画像のあらゆるデコード済みピクセルにsRGB転送関数を適用する——線形セグメントのしきい値を超えると1.055 * Power(x, 1/2.4) - 0.055である——そして分数のyに対するPower(x, y)にはPascal RTLに安価な閉形式が存在しない:それはLn(x)、続いてExp(y * Ln(x))に分解され、赤・緑・青のチャネルそれぞれについてピクセルあたり3回実行されるその一対の超越関数呼び出しは、LabまたはICC画像をピクセル単位でデコードする際の支配的なコストである。PDFlibPasは、ピクセルごとの3回のPower呼び出しを、一度EnsureSRGBGammaLUTを通じて構築される4096エントリのDouble配列であるGSRGBGammaLUTへの1回のルックアップに置き換える。これはクランプされた入力を最も近いスロットに丸めることでインデックス付けされる

Const
  SRGB_GAMMA_LUT_SIZE = 4096;
Var
  GSRGBGammaLUT: Array [0..SRGB_GAMMA_LUT_SIZE- 1] Of Double;
  GSRGBGammaLUTReady: Boolean= False;

Procedure EnsureSRGBGammaLUT;
Var
  I: Integer;
  X: Double;
Begin
  If GSRGBGammaLUTReady Then
    Exit;
  For I:= 0 To SRGB_GAMMA_LUT_SIZE- 1 Do
  Begin
    X:= I/ SRGB_GAMMA_LUT_SIZE;
    If X> 0.0031308 Then
      GSRGBGammaLUT[I]:= 1.055* Power(X, 1/ 2.4)- 0.055
    Else
      GSRGBGammaLUT[I]:= 12.92* X;
  End;
  GSRGBGammaLUTReady:= True;
End;

Function SRGBGamma(X: Double): Double;
Var
  Idx: Integer;
Begin
  If X<= 0 Then
    Result:= 0
  Else If X>= 1 Then
    Result:= 1
  Else
  Begin
    Idx:= Round(X* SRGB_GAMMA_LUT_SIZE);
    If Idx> SRGB_GAMMA_LUT_SIZE- 1 Then
      Idx:= SRGB_GAMMA_LUT_SIZE- 1;
    Result:= GSRGBGammaLUT[Idx];
  End;
End;

[0, 1]の入力範囲にわたる4096スロットのテーブルは、8ビット出力チャネルのおよそ16倍の解像度を与える。そのためLUTが導入する量子化は、最終的なRGBバイトが表現できるものより下に位置する——ここではテーブルルックアップが、目に見える精度のコストなしに超越数学を置き換える。同じ理由がその隣のLab2XYZにも現れており、そこではPower(LMN[i], 3)が単純なLMN[i]*LMN[i]*LMN[i]になった:整数のべき乗はそもそもLn/Expを必要としないため、それはLUTのトレードオフでは全くなく、単に冗長なPower呼び出しが取り除かれただけである。このLUTのトリックは、その転送関数が単一のDoubleの純粋な関数であるからこそ元が取れる——それは複数のピクセル値やそれ以上の状態に依存する色変換にはきれいには拡張できないだろう

73個のコンテンツストリーム演算子をどうやって速くディスパッチするのか

ContentOperatorFromNameは、PDFlibPasがコンテンツストリームから読み取るあらゆるトークンに対して一度呼ばれ、ISO 32000-1の表51の73個の演算子全体——wやqから、めったに見られないd0とd1のType 3グリフメトリクス演算子まで——に対してそれを照合していた。それは以前、すべての単一のトークンでそのリストを線形に歩いていた。そのため数千個の演算子を持つページは、同じ73エントリのテーブルにわたる数千回の線形走査を意味していた。PDFlibPasは今や、起動時にその演算子の先頭バイトによってテーブルをバケット化し、固定のAnsiCharでインデックス付けされたスロットの配列にする。そのためルックアップは1回の配列インデックスと、その先頭文字を共有する一握りの演算子だけの走査になる

Type
  TOpSlot= Record
    Count: Integer;
    Ops: Array [0..15] Of TPDFContentOperator;
  End;

Var
  GOpBuckets: Array [AnsiChar] Of TOpSlot;
  GBucketsReady: Boolean= False;

Function ContentOperatorFromName(Const Name: AnsiString): TPDFContentOperator;
Var
  Ch: AnsiChar;
  Slot: ^TOpSlot;
  I: Integer;
  Op: TPDFContentOperator;
Begin
  Result:= coUnknown;
  If (Name= '') Then
    Exit;
  EnsureOpBuckets;
  Ch:= Name[1];
  Slot:= @GOpBuckets[Ch];
  If Slot^.Count= 0 Then
    Exit;
  For I:= 0 To Slot^.Count- 1 Do
  Begin
    Op:= Slot^.Ops[I];
    If (PDFContentOpInfo[Op].Name= Name) Then
    Begin
      Result:= Op;
      Exit;
    End;
  End;
End;

PDFの演算子は大文字小文字を区別する——wとW、fとF、scとSCはすべて異なる演算子である——そのためGOpBucketsは生のバイトをキーとし、バケット内部の残りの比較は単純で大文字小文字を区別するAnsiStringの等価性である。この配列は1文字あたり16スロットのサイズであり、今日のテーブルを快適にカバーしている——最も混雑しているバケットであるTは13個の演算子を保持している、なぜならほとんどすべてのテキスト状態・テキスト位置決めの演算子はそれで始まるからだ——しかしEnsureOpBucketsは、あるバケットのカウントが16に達すると静かにそれ以上の追加を止める。そのため、14個目のエントリを必要としたことのあるバケットは、大声ではなく静かに失敗するだろう:その演算子は、なぜかを指し示す例外もなくcoUnknownに解決される。これが、優雅に劣化するデータ構造をそうでないものと引き換えにすることの保守コストである——それはより速くディスパッチする、なぜなら境界チェックされた拡張を一切必要としないからだ、そしてそれは、上限に近い1つのバケットを見張っている人間を必要とする

文字列構築からO(n²)を取り除く

PascalのResult := Result + Fragmentパターンは、反復のたびに蓄積された文字列全体を再割り当てしコピーする。そのため、N文字の出力を一度に1断片ずつ構築することは、O(n)ではなくO(n²)かかる——各行が1回の安価な追加のように見えるためレビューで見逃しやすく、PLDirectEscapeLiteralStringが保存中のあらゆるリテラルPDF文字列に対して実行され、XFDFXMLEscapeがXFDFにエクスポートされるあらゆるフィールド値に対して実行されるため、実際には高くつく。PDFlibPasは、それぞれの関数が事前に何を予測できるかによって選ばれた異なる技法でこの2つを修正する。PLDirectEscapeLiteralStringは、1バイトも書く前にその出力の長さを知っている——1回のパスで各文字をプレーンかエスケープ済みかに分類し合計を集計し、SetLengthが一度だけ割り当て、2回目のパスがインデックスでバッファを埋める。XFDFXMLEscapeはその出力長を安価に予測できない、なぜならUnicodeのフィールドテキストは事前計算するには変動が大きすぎるからだ。そのため代わりに、入力長のおよそ大きさで事前にサイズ設定されたTStringBuilderに追加していく

Function XFDFXMLEscape(Const W: WideString): WideString;
Var
  I: Integer;
  Builder: TStringBuilder;
Begin
  // TStringBuilder avoids the O(n^2) WideString concatenation that
  // XFDF export used to hit on every field value
  Builder:= TStringBuilder.Create(Length(W)+ 16);
  Try
    For I:= 1 To Length(W) Do
    Begin
      Case W[I] Of
        '&':  Builder.Append('&amp;');
        '<':  Builder.Append('&lt;');
        '>':  Builder.Append('&gt;');
        // ...'"', tab, CR and LF cases follow the same shape
      Else
        Builder.Append(W[I]);
      End;
    End;
    Result:= Builder.ToString;
  Finally
    Builder.Free;
  End;
End;

この2つの間の選択は、実際にはループが始まる前に何を知っているかについてのものである。カウントしてから埋める方式は、出力サイズが安価に計算できる場合はより速い方であり、再割り当てをゼロにし、Integerのカウンタ以上の記帳を必要としないが、それは分類ロジックを2回書くことを意味する——一度は数えるため、もう一度は出力するため——この2つのコピーがずれてしまえばそれ自体が保守上のリスクになる。TStringBuilderは、そのピークスループットのわずかな部分を犠牲にする代わりに、ロジックを一度書くだけで、幾何学的なバッファ成長から償却O(1)の追加を得る。これは、出力サイズが事前に知りやすくないときはいつでもより安全な既定である

このパターンがどこに当てはまり、どこには当てはまらないか

上記の4つの修正はすべて1つの発想の実例である:入力の単位ごとに一度実行される呼び出し——辞書キーごと、ピクセルごと、演算子トークンごと、文字ごと——を見つけ、その線形あるいは予測不能なコストを、事前計算されたテーブル、ハッシュインデックス、あるいは事前にサイズ設定されたバッファに置き換えることだ。これはどれもPDFに特有のものではない;リクエストごとに同じルックアップキーを何千回も解決し、タイトなループの中で値を変換し、固定された語彙のトークンにディスパッチし、あるいは長い文字列を1文字ずつ構築するDelphiのサービスは、同じ失敗の形にぶつかり、同じ修正を取る。この4つの変更のどれも触れないのは並行性やメモリのフットプリントである:より速い単一スレッドの辞書ルックアップは、同じTPDFlibインスタンス上で競合する2つのスレッドには何もしない。これは並列ページレンダリングにおけるスレッドセーフティに関する記事で別途扱われている構造的な問題である。そしてそれは、オブジェクトツリーとしてメモリに読み込むには大きすぎるPDFには何もしない、これはPDFlibPasのDirect Accessレイヤーの出番であり、ギガバイト級PDFのマージと分割に関する記事で扱われている

ここで議論した辞書、色管理、コンテンツストリームディスパッチ、文字列構築のコードは、DelphiおよびC++Builder向けlosLabのPDFライブラリである標準PDFlibPasの一部として出荷され、そのいずれを得るにも追加の設定は一切必要ない