LlosLab Software 開發部落格面向 PDF、Delphi 與文件軟體開發者的工程筆記

技術文章

PDFlibPas 效能分析：Delphi 中的雜湊索引

Delphi PDF 函式庫

PDFlibPas 是 losLab 為 Delphi 與 C++Builder 提供的 PDF 函式庫，透過將四種重複工作的模式替換為可攤銷的模式，加速渲染與內容產生路徑：用於字典鍵查找的延遲雜湊索引、預先計算的 sRGB 伽瑪查找表、用於內容串流運算子分派的首位元組分桶，以及以 TStringBuilder 取代重複字串串接。這四項並非來自某個戲劇性的發現，而是來自效能分析中同一種不起眼的模式：某個小函式每個運算子、每個像素或每個字元呼叫一次，而呼叫內的線性成本在整份文件中累積後變成二次或接近二次成本。這就是本文的主線：四個看似互不相關的小修正，實際上都在攻擊同一種問題形狀，並誠實說明各自的限制

內容串流渲染器實際將時間花在哪裡

PDFlibPas 的內容串流渲染器幾乎將所有逐權杖成本集中在四個狹窄位置：對 /Resources、/ColorSpace、/Font 與 /ExtGState 進行資源字典查找；對 Lab、Indexed 或帶有 ICC 標記的影像中每個解碼像素進行伽瑪校正；比對每個內容串流中的每個權杖所代表的運算子名稱；以及在函式庫建立輸出時建構字串，包括儲存時的字面字串跳脫、XFDF 匯出、圖章與變數權杖展開。四者各自只做少量工作，但在實際文件中都會執行數千或數百萬次，這正是 O(n) 或 O(n²) 實作細節不再隱形，並開始成為效能分析最高項目的函式形狀

為什麼大型 PDF 的資源字典查找會變慢

TPDFDictionary.FindIndexByKeyName 是渲染器用來解析每個 /Resources、/ColorSpace、/Font 與 /ExtGState 查找的函式，過去每次呼叫都會從頭走訪 Entries 陣列。對三個項目的 Resources 字典而言這沒有問題，但對 Form XObject 或充滿 ExtGState 的頁面而言，同一個字典會在每個接觸色彩或圖形狀態的運算子上被探查，成本就很高。現在，當字典通過 DICT_HASH_THRESHOLD（16）個項目的門檻後，PDFlibPas 會建立延遲雜湊索引，較小的字典則維持線性掃描，因為大多數 PDF 字典根本不會變得那麼大，而為三個鍵建立雜湊表所付出的成本可能高於節省的成本。該索引是以 PLAnsiStringHash 為鍵的平坦開放定址表，這是一個 FNV-1a 雜湊，使用標準偏移基準 2166136261 與質數 16777619，目的是避免為這種對大小敏感的用途引入 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) 重建，還有雜湊表本身的記憶體，大約是在三分之二負載因子下每個槽位一個 Integer。對典型文件中少數幾個過大的字典而言，這只是捨入誤差；而將門檻維持在目前位置，也讓 PDFlibPas 不必讓每個小型字典承擔這項實際成本

預先計算 sRGB 伽瑪，而不是對每個像素呼叫 Power

TPDFSimpleColorManager.XYZ2RGB 會對 Lab、Indexed 或以 ICC 為基礎的影像中每個解碼像素套用 sRGB 傳遞函式——在線性區段門檻以上使用 1.055 * Power(x, 1/2.4) - 0.055——而 Pascal RTL 對分數 y 的 Power(x, y) 沒有便宜的封閉形式：它會先分解成 Ln(x)，再計算 Exp(y * Ln(x))。對紅、綠、藍三個通道每個像素執行這一對超越函式，是逐像素解碼 Lab 或 ICC 影像的主要成本。PDFlibPas 以查找 GSRGBGammaLUT 的一次操作取代每像素三次 Power 呼叫，這是一個透過 EnsureSRGBGammaLUT 建立一次的 4096 項 Double 陣列，並以將限制後的輸入四捨五入至最近槽位的方式建立索引

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 位元輸出通道的十六倍，因此 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，到罕見的 Type 3 字形度量運算子 d0 與 d1。過去它會在每個權杖上對這份清單進行線性走訪，因此一個包含數千個運算子的頁面，就代表對同一個 73 項表格進行數千次線性掃描。現在，PDFlibPas 會在啟動時按照運算子的第一個位元組將表格分桶，放入以固定 AnsiChar 索引的槽位陣列，讓一次查找變成一個陣列索引，再掃描只有少數幾個共用相同首字元的運算子

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 相等比較。陣列為每個字母配置 16 個槽位，足以容納目前的表格。最忙碌的分桶是 T，包含十三個運算子，因為幾乎所有文字狀態與文字定位運算子都以它開頭。不過，當分桶數量達到 16 後，EnsureOpBuckets 會靜默停止加入項目，因此任何需要第十四個項目的分桶都會靜默失敗，而不是明確失敗：運算子會解析為 coUnknown，也不會有例外指出原因。這是以不會進行邊界檢查擴容的資料結構換取較快分派所付出的維護成本，也表示需要有人留意那個接近上限的分桶

從字串建構中移除 O(n²)

Pascal 的 Result := Result + Fragment 模式會在每次迭代重新配置並複製整個累積字串，因此逐段建立 N 字元輸出時，成本是 O(n²) 而不是 O(n)。這在檢閱時很容易被忽略，因為每一行看起來都只是一次便宜的附加操作；但在實務上代價很高，因為 PLDirectEscapeLiteralString 會在儲存期間每次寫入字面 PDF 字串時執行，而 XFDFXMLEscape 會在每個欄位值匯出至 XFDF 時執行。PDFlibPas 以不同技術修正這兩者，取決於每個函式能否預先推算輸出長度。PLDirectEscapeLiteralString 在寫入第一個位元組前就知道輸出長度：第一次走訪會將每個字元分類為一般或跳脫字元並加總總長度，SetLength 只配置一次，第二次走訪則依索引填入緩衝區。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;

兩者之間的選擇，實際上取決於迴圈開始前已知的資訊。當輸出大小容易計算時，先計數再填入較快，因為不會重新配置，也不需要超出 Integer 計數器以外的簿記，但這表示分類邏輯要寫兩次——一次用於計數，一次用於輸出。如果兩份副本逐漸偏離，便會產生自身的維護風險。TStringBuilder 以些微的峰值吞吐量換取只寫一次邏輯，並透過幾何式緩衝區成長取得攤銷 O(1) 的附加操作；只要輸出大小不容易事先知道，它就是更安全的預設選擇

這種模式適用與不適用的地方

以上四項修正都是同一個想法的實例：找出每個輸入單位執行一次的呼叫——每個字典鍵、每個像素、每個運算子權杖、每個字元——再以預先計算的表格、雜湊索引或預先配置大小的緩衝區，取代其線性或不可預測的成本。這些做法都不只適用於 PDF；一個每個要求中解析同一查找鍵數千次、在緊密迴圈中轉換值、依固定權杖詞彙分派，或一次一個字元建立長字串的 Delphi 服務，也會遇到相同的失效形狀，並採用相同的修正。這四項變更沒有觸及的是並行性與記憶體占用：較快的單執行緒字典查找，無法解決兩個執行緒同時競爭同一 TPDFlib 執行個體的問題，那是由平行頁面渲染的執行緒安全性文章另外處理的結構性問題；它也無法處理大到根本無法以物件樹載入記憶體的 PDF，那正是 PDFlibPas 中 Direct Access 層的用途，詳見合併與分割 GB 級 PDF 的文章

本文討論的字典、色彩管理、內容串流分派與字串建構程式碼，都是標準PDFlibPas的一部分。PDFlibPas 是 losLab 為 Delphi 與 C++Builder 提供的 PDF 函式庫，不需要額外設定即可取得這些功能