使用数据导向设计工程化高性能解析器

# 使用数据导向设计构建高性能解析器 来源：https://www.arshad.fyi/writings/engineering-high-performance-parsers ## 摘要 (https://www.arshad.fyi/writings/engineering-high-performance-parsers#abstract) 解析器通常被当作语法问题来教授，但一旦语法正确，几乎所有性能问题和大部分工程难度都存在于其他地方——即最终树结构在内存中的表示方式。本文描述了我在构建 **Yuku** (https://yuku.fyi/) 时使用的设计方法，这是一个用 Zig 编写的 JavaScript 和 TypeScript 解析器，运行速度比同类已有解析器快数倍。该方法适用于任何原生语言编写的解析器或编译器前端。观点很简单：先设计数据结构，让机器的访问模式决定其形状，那么速度几乎自动提升，而看似无关的问题（内存布局、分配和序列化）也会合并为一个解决方案。 ## 1. 核心理念 (https://www.arshad.fyi/writings/engineering-high-performance-parsers#1-the-single-idea) 解析器的性能早在其首次基准测试之前就已被决定——取决于其树在内存中的布局方式。这就是数据导向设计。从访问模式和硬件出发，推导出表示形式，然后构建其他一切（词法分析器、递归下降解析器、访问者 API）来服务于它。现代硬件有两个事实驱动了整个论点。 1. 一次主存缓存未命中大约花费一百纳秒。一次浮点运算花费不到一纳秒。一个追逐指针的解析器是内存延迟受限的，它在等待加载数据而非进行计算。 2. 通用分配器的调用并非免费，一个每次分配一个节点的解析器要付出数百万次这样的成本，同时将相关对象分散在内存各处。 代价是具体的。一个十万字节的文件大约产生五万个 AST 节点。如果作为单独分配、指针连接的对象，那就是五万次分配、五万次释放，并且后续每次遍历都要在冷内存中追逐指针。而在一个平面数组中，只有几次分配、一次线性扫描和一次释放。这不是常数因子。它改变了曲线的斜率。 ## 2. 直观设计的代价 (https://www.arshad.fyi/writings/engineering-high-performance-parsers#2-the-cost-of-the-obvious-design) 教科书上的 AST 是一个由堆分配的、通过指针连接的结构体组成的树。在原生语言中看起来像这样。 ```zig const Node = union(enum) { binary: struct { op: Op, left: *Node, right: *Node }, call: struct { callee: *Node, args: []*Node }, identifier: struct { name: []const u8 }, // ...每个节点类型一个变体 }; ``` 它是正确的，可读的，但对于机器来说却是错误的形状。考虑它的代价。 - **每个节点的分配**。每个 `*Node` 都是一次分配器调用。对于我们的十万字节文件，那就是数万次调用，每次都会触及分配器元数据。 - **指针追逐**。`left` 和 `right` 指向分配器任意放置的位置。遍历树是一系列不可预测的加载，每次都可能发生缓存未命中。预取器无法帮助，因为地址没有模式。 - **指针开销**。在 64 位目标上，每条边是八个字节。一个有两个子节点的节点仅指针就花费十六字节，通常超过其实际有效载荷。指针还将表示形式固定在一个地址空间中，这使得树无法在不深拷贝的情况下传递给另一种语言。 - **碎片化和释放**。释放树又是数万次调用，而且对象从一开始就不是连续的。不同变体的有效载荷大小差异也很大，因此一个朴素的节点数组必须按最大变体大小来分配，从而在常见的小节点上浪费空间。我们也将解决这个问题。 这些代价没有一个来自语法。它们来自表示形式。所以我们要改变表示形式。 ## 3. 节点作为索引，而非指针 (https://www.arshad.fyi/writings/engineering-high-performance-parsers#3-nodes-as-indices-not-pointers) 第一步是将每个指针替换为指向一个平面节点数组的整数索引。 ```zig pub const NodeIndex = enum(u32) { null = std.math.maxInt(u32), // 通用的"无子节点"哨兵 _, }; ``` `NodeIndex` 是一个 `u32`。它只有指针的一半大小。它不将树固定在一个地址空间中，因此同一个字节在当前进程、序列化文件或另一个语言堆中都是有效的。保留值 `null` 编码了“缺少子节点”，无需单独的可选类型，从而保持有效载荷平坦。 因为数组只增长而不压缩，索引在树的整个生命周期内永远有效。 ``` Tree nodes [ n0 ][ n1 ][ n2 ][ n3 ] ... 一个平面、连续的数组 ^ 子引用只是整数 1 ``` 所有这些内存都由单个区域分配器拥有。解析器在增长节点数组时向区域分配器请求存储空间，当调用者完成时，整个树在一次操作中释放。 ```zig pub fn deinit(self: *const Tree) void { self.arena.deinit(); // 一次释放所有节点、所有列表、所有字符串 } ``` 这就是数据平面与控制平面的区别。设置和销毁区域是控制平面，只发生两次。分配单个节点是数据平面，发生数百万次，因此必须仅仅是索引的递增和偶尔的几何级增长。Yuku 根据源长度估算节点数并预先保留数组，因此追加节点时空间已存在。追加仍然会检查容量，但由于保留已到位，它不会重新分配，因此分配器保持在热路径之外，而边界检查保证了每次写入的安全性。 树是自底向上构建的。一个解析例程先生成其子节点，最后追加自身。追加返回新节点的索引，这个整数就是父节点存储为子节点的内容，取代了朴素设计会使用的指针。 ```zig fn addNode(self: *Tree, node: Node) !NodeIndex { const index: NodeIndex = @enumFromInt(self.nodes.len); try self.nodes.append(self.arena.allocator(), node); return index; } ``` 解析算法本身完全保持普通。优先级攀爬（递归下降的核心）解析左操作数，然后依次折叠每个操作符（当其优先级足够高时），每步创建一个节点。与教科书版本唯一不同的是，`left` 和 `right` 是 `u32` 索引而非指针。 ```zig fn parseExpr(self: *Parser, min_prec: u8) !NodeIndex { var left = try self.parsePrefix(); // 字面量、标识符、括号分组 while (self.current.tag.precedence() > min_prec) { const op = self.current.tag; self.advance(); const right = try self.parseExpr(op.precedence()); // 更紧密绑定的子表达式 left = try self.addNode(.{ .binary = .{ .op = op, .left = left, .right = right } }); } return left; } ``` 数据结构是特殊的部分。在其上运行的算法则不然。 ## 4. 结构体数组与选择节点形状 (https://www.arshad.fyi/writings/engineering-high-performance-parsers#4-struct-of-arrays-and-choosing-a-node-shape) 一个节点逻辑上携带两样东西：说明它是什么的有效载荷，以及说明它在哪里的源码跨度。如果存储为结构体数组，这两者一起移动，任何只读取其中一个的遍历都会将另一个拖入缓存。解决方法是将数组存储为结构体数组。不要使用单一的 `{ payload, span }` 记录数组，而是维护两个平行的列：一个有效载荷列和一个跨度列。只按节点类型进行 switch 的遍历触碰一个密集列。只读取跨度的遍历触碰另一个。相同的索引寻址两者。 ``` 结构体数组 (AoS) 结构体数组的数组 (SoA) [payload|span][payload|span]... payloads: [p0][p1][p2][p3]... spans: [s0][s1][s2][s3]... ^ 读取标签会同时拉入跨度 ^ 读取标签只触碰这一列 作为缓存中的死数据 ``` 现在到了有趣的设计决策：有效载荷列中放什么。有两个好的答案，正确选择取决于消费方是谁。 **最小节点。** 如果解析器是内部编译器前端，没有外部消费者，你可以让节点非常小。存储一个字节的标签，一个指向节点主令牌的索引，以及一个八字节的数据字，它只是两个 `u32` 槽位，其含义完全由标签决定。完全不存储跨度。源位置根据需要从主令牌恢复，只有当实际需要结束位置时才重新词法分析该单个令牌。 ```zig // 最小内部节点：每个字段都是能工作的最小东西 const Node = struct { tag: Tag, // 1 字节：节点种类，也是读取 `data` 的键 main_token: u32, // 此节点依附的令牌，位置可即时获取 data: [2]u32, // 两个字，含义完全取决于 `tag` }; ``` 数据字本身没有类型。标签决定了如何读取它，因此每次访问都通过一个关于 `tag` 的 switch。相同的八个字节对一种节点类型来说是两个子节点索引，对另一种是到共享子节点列表的一个范围，对叶子节点则未使用。 ```zig switch (tree.tag(node)) { // 二元操作：两个字都是子节点索引 .add, .mul => { const left = tree.data(node)[0]; const right = tree.data(node)[1]; }, // 代码块：两个字是到共享子节点索引数组的一个 (start, end) 范围， // 因此块的语句是 extras[start..end] .block => { const range = tree.data(node); const statements = tree.extras[range[0]..range[1]]; }, // 数字字面量：没有子节点，值从令牌文本读取 .number => { const text = tree.tokenText(node.main_token); }, else => {}, } ``` **自描述节点。** Yuku 不是内部前端。它是一个公共解析器，其 AST 是 API，由外部工具从 JavaScript 作为标准 ESTree 树消费。这改变了计算方式。节点必须直接携带自己的跨度，因为在每次查询时通过重新词法分析来恢复位置跨语言边界会很慢，并且有效载荷应该是自描述的，这样对其进行的 switch 是穷举且防错的，而不是一组需要读者记忆的约定。因此 Yuku 对有效载荷使用带标签的联合，并将跨度存储在自己的列中。 ```zig pub const Node = struct { data: NodeData, // 带标签的联合，每个节点类型一个变体，44 字节 span: Span, // { start: u32, end: u32 }, 8 字节 }; ``` 这增加了每个节点的成本，而且这种成本是有意为之。关键不在于一种形状正确而另一种错误，而在于两种形状都是同一个理念——指向平面列的索引——它们只在针对受众进行专业化的程度上有所不同。最小节点专门用于编写它的编译器。自描述节点专门用于需要清晰性、直接跨度以及能廉价跨越语言边界的形状的外部、多语言、工具化受众。你根据消费者证明合理的点来选择频谱上的那个点，并且不比那更慷慨一个字节。 | 设计 | 每节点字节数 | 跨度 | 有效载荷 | 最佳用途 | |------|-------------|------|---------|---------| | 最小节点 | ~13 | 重新计算 | 每标签数据字 | 内部编译器前端 | | 自描述节点 | ~52 | 已存储 | 带标签的联合 | 公共 API 和外部工具 | 还有一种纪律能使任意一种选择随时间推移保持安全。用编译时断言固定大小，这样在一个变体上添加一个看似无害的字段就不会悄无声息地膨胀程序中的每个节点。 ```zig comptime { std.debug.assert(@sizeOf(NodeData) == 44); std.debug.assert(@sizeOf(Node) == 52); } ``` 如果某个更改将联合推到超出预算，构建会立即失败并指出成本。表示形式不再是希望保持小巧的东西，而是编译器强制执行的东西。 ## 5. 可变长度子节点与侧表 (https://www.arshad.fyi/writings/engineering-high-performance-parsers#5-variable-length-children-and-the-side-table) 二元表达式恰好有两个子节点，它们可以内联放置。代码块有任意数量的语句，函数调用有任意数量的参数，联合类型有任意数量的成员。这些不能在一个固定大小的节点中内联，除非将每个节点都按最坏情况设置大小。解决方案是第二个平面数组——一个侧表——容纳所有变长子节点列表，背靠背地打包在一起。拥有列表的节点只存储一个小的描述符——偏移量和长度——到该表中。 ```zig pub const IndexRange = struct { start: u32, len: u32, }; // 在树中： extras: std.ArrayList(NodeIndex), // 所有子节点列表，拼接在一起 pub fn extra(self: *const Tree, range: IndexRange) []const NodeIndex { return self.extras.items[range.start..][0..range.len]; } ``` ``` node.body = IndexRange{ start: 12, len: 3 } extras: ... [ s0 ][ s1 ][ s2 ] ... ^12 ^13 ^14 块的三个语句，连续 ``` 任意长度的列表在拥有节点中只花费八个字节。解析为一个切片，没有间接性，迭代是线性扫描。这个模式在节点具有可变数量关联项的地方反复出现。Yuku 使用完全相同的想法将注释附加到其宿主节点上，使用一个长度为 `node_count + 1` 的前缀和偏移数组，这样节点 `i` 的注释就是偏移 `i` 和偏移 `i + 1` 之间的切片。一个表示技巧被重复使用，而不是为每个特性定制一个结构。 最小节点设计将同一个侧表用于不同的目的。当其八字节数据字不够用时，该字保存一个索引进入侧表，其中拼出了节点的完整字段集。原理相同：将常见、小型、固定的情况内联，将可变情况溢出到由偏移量寻址的共享平坦池中。 ## 6. 临时缓冲区与摊销 (https://www.arshad.fyi/writings/engineering-high-performance-parsers#6-scratch-buffers-and-amortization) 构建子节点列表引发了一个问题：解析器在遇到右括号之前不知道代码块的语句数量，因此它无法预先分配列表大小，但又不能为每个代码块分配一个全新的可增长列表。答案是一组保存在解析器本身上的可重用临时缓冲区。列表被收集到临时缓冲区中，当收集完成时，它一次性刷新到侧表中。然后临时缓冲区被重置（而非释放），因此下一个列表重用相同的内存。 ```zig fn parseBlock(self: *Parser) !IndexRange { const mark = self.scratch.begin(); // 记住当前顶部 defer self.scratch.reset(mark); // 退出时恢复 while (!self.atBlockEnd()) { const stmt = try self.parseStatement(); try self.scratch.append(stmt); } return self.flushToExtras(self.scratch, mark); // 一次批量复制到侧表 } ``` 因为每个调用记录自己的起始标记并重置到该标记，同一个缓冲区可以递归嵌套。在外部代码块内部解析的内部代码块，使用外部代码块区域之上缓冲区的尾部，重置时恢复外部代码块的视图。单个缓冲区服务于整个递归下降过程。Yuku 为不同的递归上下文保留了几个这样的缓冲区，再加上两个通用的，以便单个解析器帧可以同时组装两个列表，例如模板字面量的静态块和插值表达式。 这就是摊销——数据平面的正确做法。昂贵的操作（增长缓冲区）在整个解析过程中只发生几次，而不是每个列表一次。热操作（追加一个子节点）是一次边界检查和一次存储。 ## 7. 无拷贝的字符串 (https://www.arshad.fyi/writings/engineering-high-performance-parsers#7-strings-without-copies) 标识符和字符串字面量无处不在，朴素的方法是将每个词素复制到其自己的堆分配中。对于大文件，这会导致大量小型分配，每个都有分配器开销，并且字符串散布在内存各处。Yuku 将所有字符串存储在一个连续的缓冲区中，通过偏移量和长度引用它们。词法分析器直接从源文件字节中切片（使用 Zig 的切片），解析器仅在需要时复制（例如对于转义序列）。对于标识符，根本不复制：节点只是指向源缓冲区的一个 `[]const u8` 切片。因为源缓冲区在解析过程中保持有效，所以无需分配。字符串字面量如果包含转义，则在输入时被扁平化到字符串缓冲区中，但同样是在一次批量复制中完成。没有针对每个令牌的分配。