开源软件的性能
以光速解析 XML

前言

XML 是一种标准化的标记语言，它定义了一组规则，用于以人类可读的文本格式对层次结构化的文档进行编码。 XML 广泛使用，文档范围从非常短而简单（如 SOAP 查询）到具有复杂数据关系（COLLADA）的多吉字节文档（OpenStreetMap）。为了处理 XML 文档，用户通常需要一个特殊的库：一个 XML 解析器，它将文档从文本转换为内部表示。 XML 是解析性能、人类可读性和解析代码复杂性之间的折衷方案 - 因此，快速 XML 解析器可以使选择 XML 作为应用程序数据模型的基础格式更可取。

本章介绍了作者使用 C++ 编写一个高性能解析器所需的各种性能技巧：pugixml。虽然这些技术是为 XML 解析器而使用的，但大多数技术可以应用于其他格式的解析器，甚至与之无关的软件（例如，内存管理算法在解析器之外也具有广泛的应用）。

由于有几种实质上不同的 XML 解析方法，并且解析器必须执行即使是熟悉 XML 的人也不知道的额外处理，因此在深入研究实现细节之前，首先概述整个任务非常重要。

XML 解析模型

每种不同的 XML 解析模型在不同的情况下都是合适的，并且每种模型对性能和内存消耗都有影响。以下模型被广泛使用

• 使用 SAX（用于 XML 的简单 API）解析器，用户向解析器提供一个文档流作为输入，以及几个回调，例如“标签开始”、“标签结束”、“标签内的字符数据”。解析器根据文档中的数据调用回调。解析所需的上下文受当前元素的树深度的限制，这意味着内存需求大大减少。这种类型的解析可用于流式传输文档，其中文档的一部分在任何给定时间都可用。
• 拉式解析在解析过程中类似于 SAX - 即，文档一次处理一个元素 - 但控制被反转：在 SAX 中，解析由解析器通过回调控制，而在拉式解析中，用户通过类似迭代器的对象控制解析过程。
• 使用 DOM（文档对象模型）解析器，用户向解析器提供整个文档作为文本流/缓冲区，解析器由此生成文档对象 - 整个文档树的内存表示，它对每个特定的 XML 元素或属性都有一个单独的对象，以及一组允许的操作（例如，“获取此节点的所有子元素”）。Pugixml 遵循这种模型。

解析模型的选择通常取决于文档的大小和结构。由于 pugixml 是一个 DOM 解析器，因此它对于以下文档非常有效

• 足够小以适合内存，
• 具有复杂结构，节点之间存在需要遍历的引用，或者
• 需要复杂的文档转换。

pugixml 中的设计选择

Pugixml 主要关注 DOM 解析问题，因为在 pugixml 创建（2006 年）时，虽然快速轻量级的 SAX 解析器（如 Expat）可用，但所有生产就绪的 XML DOM 解析器要么不轻量级，要么不快，或者通常两者都不是。因此，pugixml 的主要目标是成为一个非常快速轻量级的基于 DOM 的 XML 操作库。

XML 由 W3C 建议 定义，该建议指定了两种不同类型的解析：验证和非验证（换句话说，非验证解析器检查 XML 语法，而验证解析器还可以检查数据语义）。即使是非验证解析器也必须执行一些相对资源密集型的验证工作。

当性能是首要目标时，必须在性能和一致性之间取得折衷。对于 pugixml，折衷方案如下：任何格式良好的 XML 文档都将被完全解析，包括所有必需的转换，除了文档类型声明。¹ 由于只检查快速验证的规则，因此非格式良好的文档有时可以成功解析。

在 XML 文档中的数据到达用户之前，通常必须以某种方式转换。转换包括行尾处理、属性值规范化和字符引用扩展。这些转换有相关的性能成本；pugixml 尽可能优化它们，同时提供一种方法来禁用它们以获得最大性能。

手头的任务是创建一个快速 DOM 解析器，它能够成功解析具有所需转换的符合规范的 XML 文档，尽可能快，并且是生产就绪的。为了性能目的，“生产就绪”主要意味着它能够抵抗格式错误的数据。为了提高性能而牺牲缓冲区溢出检查是不可行的。

接下来，我们将讨论 pugixml 使用的解析过程。最后一节将介绍 pugixml 用于存储文档对象模型的数据结构以及 pugixml 用于为该数据结构分配内存的算法。

解析

DOM 解析器的目标是接受一个输入 - 包含 XML 文档的字符串 - 并生成一个对象树，该树在内存中表示相同的文档。解析器通常由两个阶段组成：词法分析器和解析器。词法分析器接受输入字符流并生成标记流。（对于 XML 解析器，标记集可以包括左尖括号、引号、标签名称和属性名称。）解析器消耗标记流并根据语法生成语法树，使用许多解析算法之一，例如递归下降。当遇到包含字符串数据的标记时，例如标签名称，词法分析器或解析器将字符串内容复制到堆中，并在树节点中存储对该字符串的引用。

为了提高解析性能，pugixml 在几个方面偏离了典型的方法。

标记流与字符流

如前所述，解析器传统上使用词法分析器将字符流转换为标记流。这可以在解析器必须进行大量回溯的情况下提高性能，但对于 XML 解析器来说，词法分析器阶段只是增加了复杂性的额外一层，它增加了每个字符的开销。因此，pugixml 在字符流而不是标记流上运行。

通常，流由 UTF-8 字符组成，pugixml 逐字节读取流。由于 UTF-8 结构，除非您正在寻找特定的非 ASCII 字符，否则无需解析 UTF-8 字节序列，因为在有效的 UTF-8 流中，所有低于 128 的字节都是独立的 ASCII 字符（即，不是 UTF-8 字符的一部分）。²

就地解析

解析器典型实现中存在几个低效之处。其中之一是将字符串数据复制到堆中。这涉及分配许多大小不同的块，从字节到兆字节，并要求我们从原始流中复制所有字符串到堆中。避免复制操作可以让我们消除这两种开销来源。使用一种称为就地（或 *就地*）解析的技术，解析器可以使用流中的数据直接。这是 pugixml 使用的解析策略。

基本的就地解析器接受存储在连续内存缓冲区中的输入字符串，以字符流的形式扫描字符串，并创建必要的树结构。遇到作为数据模型一部分的字符串时，例如标签名称，解析器会保存一个指向该字符串及其长度的指针（/而不是保存整个字符串）。³

因此，这是性能和内存使用之间的权衡。就地解析通常比将字符串复制到堆中进行解析更快，但它可能会消耗更多内存。就地解析器需要在内存中保留原始流以及它自己的描述文档结构的数据。非就地解析器可以存储原始流的相关部分。

图 4.1 - 调整就地解析以用于以 null 结尾的字符串

第二个问题更复杂：通常字符串值和 XML 文件中的表示是不同的。符合规范的解析器应执行表示的解码。由于在节点对象访问期间执行此操作会导致对象访问性能不可预测，因此我们更愿意在解析时执行此操作。根据内容类型，XML 解析器可能需要执行以下转换

• 行尾处理：输入文档可以包含各种类型的行尾，解析器应将其规范化为以下形式：任何回车 (ASCII 0xD) 和换行 (ASCII 0xA) 的两个字符序列，以及任何独立的回车都应替换为换行符。例如，行

    `line1\xD\xAline2\xDline3\xA\xA`

  应转换为

    `line1\xAline2\xAline3\xA\xA`.

• 字符引用扩展：XML 支持使用其 Unicode 代码点以十进制或十六进制表示法转义字符。例如，a 应扩展为 a，而 ø 应扩展为 ø。
• 实体引用扩展：XML 支持通用实体引用，其中 &name; 将被替换为实体名称的值。有五个预定义的实体：< (<)、> (>)、" (")、' (‘) 和 & (&).

• 属性值规范化：除了扩展引用之外，解析器在解析属性值时还应执行空格规范化。所有空格字符（空格、制表符、回车和换行符）都应替换为空格。此外，根据属性的类型，应删除前导和尾随空格，并将字符串中间的空格序列折叠成一个空格。

只要满足一个重要约束，就可以在就地解析器中支持任意的转换，即修改字符串内容：转换永远不会增加字符串的长度。如果这样做，结果可能会与文档中的重要数据重叠。幸运的是，以上所有转换都满足此要求。⁴

通用实体扩展 *不* 满足此约束。由于 pugixml 不支持 DOCTYPE 声明，并且在没有 DOCTYPE 的情况下无法指定自定义实体，因此任何受支持的文档都可以使用就地解析完全解析。⁵

图 4.2 - 使用就地文本解析进行文本转换

有趣的是，内存映射文件 I/O⁶ 可以用于就地解析。支持空终止符和文本转换需要一种称为写时复制的特殊内存映射模式，以避免修改磁盘上的文件。

使用内存映射文件 I/O 进行就地解析具有以下优点

• 内核通常可以直接将缓存页映射到进程地址空间，从而避免了标准文件 I/O 中发生的内存复制。
• 如果文件尚未位于缓存中，则内核可以从磁盘预取文件的各个部分，有效地使 I/O 和解析并行。
• 由于只有修改过的页面需要分配物理内存，因此在具有大文本部分的文档中，内存消耗可以大大减少。

优化字符级操作

消除字符串复制并不是我们可以用来优化解析器性能的唯一方法。在比较解析器性能时，一个有用的指标是每个字符消耗的平均处理器周期数。虽然这在文档和处理器架构之间会有所不同，但对于结构相似的文档来说，它相当稳定。因此，针对此指标进行优化是有意义的，一个明显的起点是针对每个字符执行的操作。

最重要的操作是检测字符集成员资格：给定输入流中的一个字符，它是否属于某个特定字符集？

一个有用的方法是创建一个布尔标志表，其中为每个字符值存储一个真/假值，具体取决于该字符是否属于该集合。根据编码，不同的表数据结构和大小是有意义的，如下所示

• 对于每个字符占用不超过 8 位的编码，大小为 256 的表就足够了。

• 对于 UTF-8，我们希望使用一个字节索引表来避免代码点解码；但这只有在所有代码点（即数值）大于 127 的字符都属于该集合或没有代码点大于 127 的字符属于该集合时才有效。如果这两个条件中的任何一个为真，则大小为 256 的表就足够了。表的前 128 个条目用真或假填充（具体取决于字符是否在目标集合中），表的后 128 个条目共享同一个值。由于 UTF-8 编码数据的方式，所有大于 127 的代码点将用值大于 127 的字节序列表示。此外，序列的第一个字符也将大于 127。

• 对于 UTF-16 或 UTF-32，通常情况下，大尺寸的表是不切实际的。在与优化的 UTF-8 相同的约束条件下，我们可以将表的大小保持为 128 或 256 个条目，并添加一个额外的比较来处理超出范围的值。

请注意，我们只需要一个比特来存储真/假值，因此使用位掩码在一个 256 字节表中存储八个不同的字符集可能是有意义的。Pugixml 使用这种方法来节省缓存空间：在 x86 架构中，检查布尔值通常与检查字节中的一个比特具有相同的成本，前提是比特位置是编译时常量。这段 C 代码演示了这种方法

enum chartype_t {
  ct_parse_pcdata  = 1, // \0, &, \\r, \<
  ct_parse_attr    = 2, // \0, &, \\r, ', "
  ct_parse_attr_ws = 4, // \0, &, \\r, ', ", \\n, tab
  // ...
};
static const unsigned char table[256] = {
  55, 0, 0, 0, 0, 0, 0, 0, 0, 12, 12, 0, 0, 63, 0, 0, // 0-15
  // ...
};
bool ischartype_utf8(char c, chartype_t ct) {
  // note: unsigned cast is important to
  // guarantee that the value is in 0..255 range
  return ct & table[(unsigned char)c];
}

bool ischartype_utf16_32(wchar_t c, chartype_t ct) {
  // note: unsigned cast is important to
  // guarantee that the value is not negative
  return ct & ((unsigned)c < 128 ? table[(unsigned)c] : table[128]);
}

如果测试范围包含某个区间中的所有字符，则使用比较而不是表查找可能更有意义。通过仔细使用无符号算术，只需进行一次比较即可。例如，测试一个字符是否是数字

bool isdigit(char ch) { return (ch >= '0' && ch <= '9'); }

可以使用一次比较重写

bool isdigit(char ch) { return (unsigned)(ch - '0') < 10; }

如果我们逐字符地进行操作，通常无法改进上述方法。但是，有时可以对字符组进行操作，并使用矢量化检查。如果目标系统具有某种形式的 SIMD 指令可用，则通常可以使用这些指令快速操作 16 个或更多个字符组。

即使不使用特定于平台的指令集，有时也可以矢量化字符操作。例如，以下是一种检查 UTF-8 字节流中四个连续字节是否代表 ASCII 符号⁷ 的方法

(*(const uint32_t*)data & 0x80808080) == 0

最后，无论您做什么，都不要在对性能敏感的代码中使用标准库中的 is.*() 函数（例如 isalpha()）。即使是最好的实现也会检查当前区域设置是否为“C”，这比表查找本身更昂贵，最糟糕的实现比这慢两个数量级。⁸

优化字符串转换

在 pugixml 中，值的读取和转换尤其耗时。例如，让我们看看读取纯字符数据 (PCDATA)；例如，XML 标签之间的文本。如前所述，任何符合标准的解析器都应在 PCDATA 内容处理期间执行引用扩展和行尾规范化。⁹

例如，以下文本在 XML 中

A < B.

应转换为

A < B.

PCDATA 解析函数获取指向 PCDATA 值开头的指针，并通过读取值的其余部分，就地转换值数据并用空终止符终止结果来进行操作。

由于有两个布尔标志，因此我们有四个函数变体。为了避免昂贵的运行时检查，我们正在使用布尔模板参数来表示这些标志——因此我们正在从单个模板中编译四个函数变体，然后在解析开始之前使用运行时调度来获取正确的函数指针。解析器使用此函数指针调用该函数。

这允许编译器删除标志的条件检查并删除函数每个特化的死代码。重要的是，在函数解析循环内部，我们使用一个快速字符集测试来跳过所有属于通常 PCDATA 内容的字符，并且只处理我们感兴趣的字符。以下是代码的外观

template <bool opt_eol, bool opt_escape> struct
strconv_pcdata_impl {
  static char_t* parse(char_t* s) {
    gap g;
    while (true) {
      while (!PUGI__IS_CHARTYPE(*s, ct_parse_pcdata)) ++s;
      if (*s == '<') { // PCDATA ends here
        *g.flush(s) = 0;
        return s + 1;
      } else if (opt_eol && *s == '\r') { // 0x0d or 0x0d 0x0a pair
        *s++ = '\n'; // replace first one with 0x0a
        if (*s == '\n') g.push(s, 1);
      } else if (opt_escape && *s == '&') {
        s = strconv_escape(/s, g);
      } else if (*s == 0) {
        return s;
      } else {
        ++s;
      }
    }
  }
};

一个额外的函数根据运行时标志获取指向适当实现的指针；例如，&strconv_pcdata_impl<false, true>::parse。

此代码中的一个不寻常的项目是 gap 类实例。如前所示，如果我们进行字符串转换，则结果字符串会变短，因为一些字符必须被删除。有几种方法可以做到这一点。

一种策略（pugixml 没有使用）是保持单独的 read 和 write 指针，它们都指向同一个缓冲区。在这种情况下，read 指针跟踪当前读取位置，write 指针跟踪当前写入位置。始终应该保持 write <= read 不变。任何必须成为结果字符串一部分的字符都必须显式地写入 write 指针。此技术避免了简单字符删除的二次成本，但效率仍然低下，因为我们现在每次都会读取和写入字符串中的所有字符，即使我们不需要修改字符串。

这个想法的一个明显扩展是跳过不需要修改的原始字符串的前缀，并且只在该前缀之后开始写入字符——实际上，这就是 std::remove_if() 背后的算法通常执行的方式。

Pugixml 遵循不同的方法（参见图 4.3）。在任何时候，字符串中最多只有一个间隙。间隙是不再有效的字符序列，因为它们不再是最终字符串的一部分。当由于另一个替换而必须添加一个新的间隙时（例如，将 " 替换为 " 会产生一个 5 个字符的间隙），通过将两个间隙之间的​​数据移动到第一个间隙的开头，然后记住新的间隙来折叠现有的间隙。就复杂性而言，这种方法等同于使用 read 和 write 指针的方法；但是它允许我们使用更快的例程来折叠间隙。（Pugixml 使用 memmove，与字符级循环相比，memmove 可以更有效地复制，具体取决于间隙长度和 C 运行时实现。）

图 4.3 - PCDATA 转换期间间隙操作的示例。

优化控制流

pugixml 解析器本身可以被认为是一个递归下降解析器。但是，递归被转换为循环以提高性能。节点游标充当堆栈。当遇到开始标签时，一个新的节点被附加到游标并成为新的游标；当遇到结束标签时，游标被移动到当前游标的父节点。这使得堆栈空间消耗与输入文档无关，这提高了鲁棒性，并避免了潜在的昂贵函数调用。

解析器使用一个调度循环，从流中读取一个字符，读取该字符之后的一个或多个字符（具体取决于第一个字符），以确定标签类型，然后继续解析相关标签的代码。例如，如果第一个字符是 <，我们必须至少读取一个字符才能区分开始标签、结束标签、注释或其他类型的标签。Pugixml 还使用 goto 语句来避免在某些情况下执行调度循环——例如，文本内容解析在流末尾或 < 字符处停止。但是，如果下一个字符是 <，我们不必执行调度循环只是为了再次读取该字符并检查它是否为 <；我们可以直接跳转到执行标签解析的代码。

对于此类代码，有两个重要的优化是分支排序和代码局部性。

在解析器中，代码的不同部分处理各种形式的输入。其中一些 (/例如标签名称或属性解析) 经常执行，而另一些 (/例如 DOCTYPE 解析) 很少执行。即使在代码的一小部分内，不同的输入也具有不同的概率。例如，在解析器遇到一个左尖括号 (<) 之后，下一个最有可能出现的字符是标签名称的字符。下一个最有可能的是 /¹⁰，其次是 ! 和 ?。

考虑到这一点，可以重新排列代码以产生更快的执行速度。首先，所有“冷”代码；也就是说，不太可能执行或不太可能经常执行的代码——在 pugixml 的情况下，这包括所有 XML 内容，除了带属性的元素标签和文本内容——必须从解析器循环中移出到单独的函数中。根据函数的内容和编译器，添加 noinline 等属性，或将额外的函数专门标记为“冷”可能会有所帮助。其想法是将内联到主解析器函数中的代码量限制为热代码。这有助于编译器通过保持控制流图较小来优化函数，并将所有热代码尽可能地放在一起以最大程度地减少指令缓存未命中。

在此之后，在热代码和冷代码中，根据条件概率对您拥有的任何条件链进行排序都是有意义的。例如，以下代码对于典型的 XML 内容来说效率不高

if (data[0] == '<')
{
  if (data[1] == '!') { ... }
  else if (data[1] == '/') { ... }
  else if (data[1] == '?') { ... }
  else { /* start-tag or unrecognized tag */ }
}

一个更好的版本如下所示

if (data[0] == '<')
{
  if (PUGI__IS_CHARTYPE(data[1], ct_start_symbol)) { /* start-tag */ }
    else if (data[1] == '/') { ... }
    else if (data[1] == '!') { ... }
    else if (data[1] == '?') { ... }
    else { /* unrecognized tag */ }
}

在这个版本中，分支按概率从最频繁到最不频繁排序。这最大限度地减少了执行的平均条件测试和条件跳转数量。

确保内存安全

内存安全是解析器的一个重要问题。在任何输入（包括格式错误的输入）上，解析器绝不能读取或写入超出输入缓冲区末尾的内存。实现此目的有两种方法。第一种方法是确保解析器在任何地方都将当前读取位置与结束位置进行比较。第二种方法是使用以 null 结尾的字符串作为输入，并确保解析器相应地处理 null 终止符。Pugixml 使用后者的扩展变体。

额外的读取位置检查会导致明显的性能开销，而 null 终止符通常会自然包含在现有检查中。例如，循环

while (PUGI__IS_CHARTYPE(*s, ct_alpha))
  ++s;

跳过一组字母字符，并在遇到 null 终止符或下一个非字母字符时停止，而无需额外的检查。在任何地方存储缓冲区结束位置也会降低整体速度，因为它通常需要一个额外的寄存器。函数调用也会变得更加昂贵，因为您需要传递两个指针（当前位置和结束位置）而不是一个。

然而，要求以 null 结尾的输入对于库用户来说不太方便：通常 XML 数据被读入一个缓冲区，该缓冲区可能没有空间容纳额外的 null 终止符。从客户端的角度来看，内存缓冲区应该是一个指针和一个没有 null 终止符的大小。

由于内部内存缓冲区必须可变才能使就地解析工作，pugixml 以简单的方式解决了这个问题。在解析之前，它用 null 终止符替换缓冲区中的最后一个字符，并跟踪旧字符的值。这样，它必须考虑最后一个字符的值的地方只是在文档可以结束的地方有效。对于 XML 来说，这样的地方并不多¹¹，所以这种方法的结果是净增益。¹²

这总结了有助于使 pugixml 解析器对各种文档保持快速的最有趣的技巧和设计决策。但是，解析器的最后一个与性能相关的组件值得讨论。

文档对象模型的数据结构

一个 XML 文档是一个树状结构。它包含一个或多个节点；每个节点可以包含一个或多个节点；节点可以表示不同类型的 XML 数据，例如元素或文本；元素节点也可以包含一个或多个属性。

节点数据的每种表示通常都是在内存消耗和各种操作的性能之间进行权衡。例如，语义上，一个节点包含一组子节点；这组节点可以在数据结构中表示。具体来说，这些数据可以存储为数组或链表。数组表示允许快速基于索引的访问；链表表示允许常数时间插入或删除。¹³

Pugixml 选择将节点和属性集合都表示为链表。为什么不使用数组？数组的两个主要优点是快速基于索引的访问（对于 pugixml 来说并不特别重要）和内存局部性（可以通过不同的方式实现）。

通常不需要快速基于索引的访问，因为处理 XML 树的代码要么需要遍历所有子节点，要么需要获取一个由属性值标识的特定节点（例如，“获取具有 ‘id’ 属性等于 ‘X’ 的子节点”。¹⁴ 基于索引的访问在可变的 XML 文档中也很脆弱：例如，添加 XML 注释会改变同一子树中后续节点的索引。

内存局部性取决于分配算法。如果使用正确的算法，如果列表节点是顺序分配的，则链表可以与数组一样有效。（稍后会详细介绍。）

带有存储在数组中的子节点的基本树数据结构（不是 pugixml 使用的）通常如下所示：¹⁵

struct Node {
  Node* children;
  size_t children_size;
  size_t children_capacity;
};

使用链表的基本树数据结构（不是 pugixml 完全使用的）如下所示

struct Node {
  Node* first_child;
  Node* last_child;
  Node* prev_sibling;
  Node* next_sibling;
};

在此，last_child 指针对于支持 O(1) 时间的向后迭代和追加是必要的。

请注意，使用这种设计很容易支持不同的节点类型来减少内存消耗；例如，元素节点需要一个属性列表，而文本节点不需要。数组方法强迫我们将所有节点类型的尺寸保持一致，这会阻止这种优化变得有效。

Pugixml 使用基于链表的方法。这样，节点修改始终是 O(1)。此外，数组方法会强迫我们分配大小不同的块，从几十个字节到单个节点有很多子节点时的兆字节不等；而在链表方法中，只需要为节点结构分配几种不同的尺寸。为固定尺寸的分配设计一个快速分配器通常比为任意分配设计一个快速分配器更容易，这也是 pugixml 选择这种策略的另一个原因。

为了使内存消耗更接近基于数组的方法，pugixml 省略了 last_child 指针，但通过使兄弟列表部分循环，保持对最后一个子节点的访问在 O(1) 时间内可用，方法是使用 prev_sibling_cyclic

struct Node {
  Node* first_child;
  Node* prev_sibling_cyclic;
  Node* next_sibling;
};

此数据结构的组织方式如下

1. first_child 指向节点的第一个子节点，如果节点没有子节点，则指向 NULL。
2. prev_sibling_cyclic 指向节点的左兄弟节点（文档中紧接在节点之前出现在节点父节点中的子节点）。如果节点是最左边的节点（即，如果节点是其父节点的第一个子节点），则 prev_sibling_cyclic 指向节点父节点的最后一个子节点，如果它是唯一的子节点，则指向自身。prev_sibling_cyclic 不能为 NULL。
3. next_sibling 指向节点的右兄弟节点，如果节点是其父节点的最后一个子节点，则指向 NULL。

图 4.4 - 使用部分循环链表表示的示例子树

使用这种结构，以下所有操作都是常数时间的

Node* last_child(Node* node) {
  return (node->first_child) ?
      node->first_child->prev_sibling_cyclic : NULL;
}

Node* prev_sibling(Node* node) {
  return (/node->prev_sibling_cyclic->next_sibling) ?
      node->prev_sibling_cyclic : NULL;
}

基于数组的方法和使用部分循环兄弟列表技巧的链表方法在内存消耗方面变得等效。在 64 位系统上，使用 32 位类型表示大小/容量会使基于数组的节点更小。¹⁶ 在 pugixml 的情况下，链表的其他优势超过了成本。

数据结构到位后，该谈谈拼图的最后一部分——内存分配算法。

基于堆栈的内存分配

一个快速的内存分配器对于 DOM 解析器的性能至关重要。就地解析消除了字符串数据的分配，但 DOM 节点仍然需要分配。还需要分配不同大小的字符串来支持树的变异。保留分配局部性对于树遍历性能很重要：如果连续的分配请求返回相邻的内存块，则在构建期间很容易确保树局部性。最后，销毁速度很重要：除了常数时间的删除之外，能够快速释放为文档分配的所有内存而无需单独删除每个节点，可以显着缩短销毁大型文档所需的时间。

在讨论 pugixml 使用的分配方案之前，让我们讨论一下它可以使用的方案。

由于 DOM 节点有一组小的必需分配大小，因此可以使用基于每个大小的空闲列表的标准内存池。对于这样的池，将存在一个空闲块的单个链表，其中每个块的大小相同。在分配请求期间，如果空闲列表为空，则会分配一个带有块数组的新页面。这些块链接在一起形成一个单链表，然后成为分配器的空闲列表。如果空闲列表不为空，则从列表中删除第一个块并将其返回给用户。释放请求只是将块附加到空闲列表的开头。

这种分配方案非常擅长重用内存——在释放其他节点后分配节点会立即重用内存。但是，添加对将内存页面释放回堆的支持需要对每个页面的已用块进行额外的跟踪。分配的局部性也取决于分配器的先前使用情况，这最终可能会降低遍历性能。

由于 pugixml 支持树变异，因此它需要支持任意大小的分配。目前尚不清楚此分配器是否可以轻松扩展以支持任意大小的分配以及 pugixml 的其他所需功能，而不会影响解析性能。使用类似于 dlmalloc 和其他通用内存分配器中实现的算法的复杂通用分配方案也不是一种选择——这些分配器往往比简单的空闲列表慢一些，更不用说更复杂了。Pugixml 需要一些简单而快速的东西。

事实证明，最简单的分配方案是堆栈分配器。此分配器的工作原理如下：给定一个内存缓冲区和该缓冲区内的偏移量，分配只需要将该偏移量增加分配大小。当然，不可能提前预测内存缓冲区的大小，因此分配器必须能够根据需要分配新的缓冲区。

此代码说明了总体思路

const size_t allocator_page_size = 32768;
struct allocator_page {
  allocator_page* next_page;
  size_t offset;
  char data[allocator_page_size];
};
struct allocator_state {
  allocator_page* current;
};

void* allocate_new_page_data(size_t size) {
  size_t extra_size = (size > allocator_page_size) ?
    size - allocator_page_size : 0;
  return malloc(sizeof(allocator_page) + extra_size);
}

void* allocate_oob(allocator_state* state, size_t size) {
  allocator_page* page = (allocator_page*)allocate_new_page_data(size);
  // add page to page list
  page->next_page = state->current;
  state->current = page;
  // user data is located at the beginning of the page
  page->offset = size;
  return page->data;
}

void* allocate(allocator_state* state, size_t size) {
  if (state->current->offset + size <= allocator_page_size) {
    void* result = state->current->data + state->current->offset;
    state->current->offset += size;
    return result;
  }
  return allocate_oob(state, size);
}

支持大于页面大小的分配很容易。我们只分配一个更大的内存块，但以与处理小页面相同的方式处理它。¹⁷

此分配器非常快。鉴于约束，它可能是最快的分配器。基准测试表明它比空闲列表分配器快，空闲列表分配器必须执行更多操作才能根据页面大小确定正确的列表，并且必须将页面中的所有块链接在一起。我们的分配器还表现出几乎完美的内存局部性。分配不是相邻的唯一情况是分配新页面时。

在小型分配的情况下，此分配器不会浪费内存。但是，可以设计出一种假设的内存分配模式（可能在实践中出现），在这种模式下它确实会浪费内存。交替使用 64 和 65536 的分配大小序列会导致每次调用时分配一个新页面，从而导致 30% 的空间浪费。出于这个原因，此分配器在 pugixml 中的实现行为略有不同：如果分配大于默认页面大小的四分之一，则会为其分配一个完整的页面，并且不会将其添加到页面列表的开头，而是将其添加到第一个条目之后。这样，在大型分配之后发生的小型分配仍然会进入正在进行的页面。

请注意，allocate_oob() 是“冷”代码——也就是说，只有在我们耗尽当前页面时才会执行它，这应该是一个罕见的事件。出于这个原因，明确禁止编译器内联它可以提高性能。¹⁸ 这也意味着在 allocate_oob() 中拥有更复杂的逻辑——例如，以不同方式处理大型分配的逻辑——不会对分配器的整体性能产生任何影响。

最后，由于所有分配都包含在某个页面中，并且分配器将整个页面列表作为状态保留，因此销毁整个页面列表并因此释放所有分配的内存非常容易。这非常快，因为它只触及内存中每个页面的标头。

在基于堆栈的分配器中支持释放

上一节中讨论的实现没有办法释放或重用内存。

有趣的是，对于许多用例来说，这实际上不是什么大问题。由于我们可以在文档销毁时通过移除所有页面¹⁹来释放内存，解析文档或创建新文档不会消耗额外的内存。然而，当我们删除文档的很大一部分，然后继续向文档添加更多节点时，就会出现问题。由于我们从不重复使用内存，峰值内存消耗会变得非常显著。

在保持分配性能的同时实现细粒度重用似乎是不可能的。然而，可以达成一个折衷方案。在分配期间，我们将计算在每个页面中进行的分配次数。然后，释放请求必须获取被销毁指针的页面的引用并减少这个计数器。如果这个计数器达到零，则不再需要该页面，可以将其移除。

为了实现这一点，我们需要知道每个对象是在哪个页面中分配的。这可以在不存储指向页面的指针的情况下实现，但它很困难。²⁰ 因此，pugixml 采用在每个分配旁边存储页面指针的方式。

Pugixml 使用两种不同的方法来减少与在每个分配中存储页面指针相关的内存开销。

第一种方法是在一个指针大小的字段中存储页面指针，该字段还包含一些无关数据的位，这些数据无论如何都需要存储。分配器确保所有页面都对齐到 32 字节，这意味着每个页面指针的最低五位都是零；因此，它们可以用来存储任意数据。五位是一个很好的数字，因为 XML 节点的元数据可以容纳：三位用于节点类型，两位用于指定节点的名称和值是否位于就地缓冲区中。

第二种方法是存储分配元素相对于页面开头的偏移量，这使我们能够通过以下方式获取页面指针的地址

(allocator_page*)((char*)(object) -
    object->offset - offsetof(allocator_page, data))

如果我们的页面大小受限于 2¹⁶ = 65536 字节，则此偏移量适合于 16 位，因此我们可以用 2 字节而不是 4 字节来存储它。Pugixml 对堆分配的字符串使用这种方法。

结果算法的一个有趣特性是它尊重使用分配器的代码所表现出的引用局部性。分配请求的局部性最终导致空间中分配数据的局部性。空间中释放请求的局部性导致成功释放内存。这意味着，在树存储的情况下，删除一个大的子树通常会释放子树使用的大部分内存。

当然，对于某些使用模式，在整个文档被销毁之前，永远不会删除任何内容。例如，如果页面大小为 32000 字节，我们可以进行一百万次 32 字节的分配，从而分配 1000 个页面。如果我们保持每 1000 个对象中的一个保持活动状态并删除其余对象，则每个页面将恰好留下一个对象，这意味着，虽然活动对象的累积大小现在是 1000 ⋅ 32 = 32000 字节，但我们仍然保留所有页面在内存中（消耗 3200 万字节）。这会导致极高的内存开销。但是，这种使用方式极不可能发生，并且该算法的优势超过了 pugixml 的这个问题。

结论

优化软件很难。为了取得成功，优化工作几乎总是涉及低级微优化、高级面向性能的设计决策、仔细的算法选择和调整、在内存、性能、实现复杂度以及更多因素之间取得平衡。Pugixml 是一个库的示例，它需要所有这些方法来提供一个非常快的生产就绪的 XML 解析器，即使为了实现这一点，不得不做出一些妥协。许多实现细节可以适应不同的项目和任务，无论是另一个解析库还是其他完全不同的东西。作者希望所介绍的技巧能够让大家感到有趣，并且其中一些技巧对其他项目有用。