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 很多的页面来说代价昂贵，因为每个涉及颜色或图形状态的运算符都会探查同一个字典。现在，PDFlibPas 会在字典达到 DICT_HASH_THRESHOLD（16）个条目后延迟构建哈希索引，并让较小字典继续使用线性扫描，因为大多数 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 中的 Power(x, y) 对小数 y 没有廉价的闭式形式：它会先分解为 Ln(x)，再计算 Exp(y * Ln(x))，而这对超越函数调用在每个像素的红、绿、蓝三个通道上各执行一次，正是逐像素解码 Lab 或 ICC 图像的主要成本。PDFlibPas 用一次对 GSRGBGammaLUT 的查找替代每个像素的三次 Power 调用；这是一个 4096 项 Double 数组，由 EnsureSRGBGammaLUT 构建一次，索引方式是把截断到有效范围的输入四舍五入到最近的槽位

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 中有 13 个运算符，因为几乎所有文本状态和文本定位运算符都以它开头。但当某个分桶的数量达到 16 后，EnsureOpBuckets 会静默停止向其中添加内容，因此如果某个分桶将来需要第 14 个条目，系统会静默失败，而不是明确失败：运算符会解析为 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，这是 losLab 面向 Delphi 和 C++Builder 的 PDF 库，无需额外配置即可使用其中任何优化