我用 Rust 制作解释器的经验

去年我终于决定学习一些 Rust。 Steve Klabnik 和 Carol Nichols 的官方书很棒，但即使在阅读它并做了一些小代码练习之后，我还是觉得我需要更多的东西来真正理解这门语言。我想从事一个小项目以获得一些实践经验，但我的大部分想法都不太适合 Rust。然后我开始阅读 Bob Nystrom 所著的《Crafting Interpreters》。顾名思义，这本书是关于为一种名为 Lox 的动态语言编写一个解释器。本书分为两部分：第一部分展示了如何使用 Java 实现一个简单的树遍历解释器。第二部分展示了如何实现相同的解释器，但这次使用的是使用 C 的高性能字节码 VM。我在 Clojure 中实现了第一部分，然后我意识到第二部分是尝试 Rust 的完美项目。语言 VM 领域似乎几乎完全由 C/C++ 主导。 VM 对性能非常敏感，通常需要大量的微优化。这个项目似乎是将 Rust 与这些语言进行比较的完美练习。我特别感兴趣的是检查 Rust 是否可以匹配相同的速度，同时提供更好的安全性和人体工程学。免责声明：自从我使用 C/C++ 已经很长时间了，可能超过 15 年了。即便如此，我主要将这些语言用于大学项目或一些开源贡献。在我的整个职业生涯中，我只使用过高级语言。将此帖子视为来自初学者。现在，匹配 Lox 解释器 (clox) 的 C 版本的速度并非易事。虽然许多关于编译器和解释器主题的书籍都专注于解释算法并将性能作为事后的想法，Crafting Interpreters 展示了如何实现一个真正快速的解释器。例如，在一些简单的基准测试中，通常会观察到 clox 比等效的 Python 或 Perl 代码快 2 倍甚至 3 倍。旁注：将此与一粒盐进行比较。 Python 和 Perl 速度较慢的原因是这些语言提供了更大的灵活性，并且会带来性能成本。这在 Wren 的网页 中有更好的解释，这是同一作者的另一种语言，其解释器启发了 clox。所以是的，与 Python 和 Perl 的比较有点橘子和苹果，但这里的要点是，clox 性能非常好并且非常适合生产。当我开始编写 Lox 的 Rust 实现时，我决定坚持使用纯粹安全的代码。 Rust 的主要卖点是它的安全性，但当然你必须坚持语言的安全部分。 Rust 还允许你使用不安全的代码，如果你这样做，我认为没有阻止程序来匹配 C 的速度，尽管这也意味着匹配它的不安全性。从一开始就坚持使用安全代码是有意义的。

我还决定尽可能多地利用 Rust 标准库。关于 Crafting Interpreters 的一个更有趣的事实是它从头开始做所有事情。除了 C 编译器和标准库（非常简单）之外，本书不使用库或解析器生成器或任何工具。每一行代码都在书中，我觉得这绝对是惊人的。所以有一些章节专门展示如何编写动态数组、字符串和哈希映射。鉴于 Rust 的标准库已经有这些并且它们非常优化，我决定使用它们并跳过自定义实现。此外，手动实现这些很可能需要编写不安全的代码。我还想尽可能多地利用 Rust 的高级类型系统。 clox 实现使用可变长度操作码，其中大多数使用一个字节，但有些使用相邻字节来打包参数或数据。在我的实现中，我决定使用枚举来使用固定长度的操作码。 Rust 的 sum 类型使用起来很愉快，因为编译器总是支持你，并在你忘记检查特定情况时警告你。我认为这是人体工程学的巨大进步。开始用 Rust 编写 lox 解释器是轻而易举的。尤其是编译器编写起来很有趣。 Rust 感觉比旧的和古怪的 C 好得多。由于 sum 类型、编译时检查和现成的标准库，VM 的初始部分也非常好写。然而，一旦我研究了更高级的东西，比如闭包和类，事情就开始变得非常棘手。 clox 实现非常自由地使用指针和别名，而 Rust 的别名规则非常严格，借用检查器不允许使用许多模式以确保安全。正因为如此，我花了大量时间寻找解决方法来让借阅检查员满意。旁注：处理借用检查器是 Rust 初学者众所周知的斗争。这就是我在这里花了这么多时间的原因。规则很简单，但出于某种原因，很难在一个大系统中跟踪它们。我经常写大量的重构，认为它们可以解决借用检查器错误，只是为了在重构结束时获得另一个。随着我对语言的体验越多，这种情况发生的频率就越低，但它仍然发生。 Learn Rust With Entirely Too Many Linked Lists 这本书提供了一些很好的例子，说明借用检查器是多么复杂。到目前为止，在我的 Lox 安全 Rust 实现中，最难实现的部分是垃圾收集器。你如何在没有手动内存分配和释放的情况下编写 GC？我花了相当多的时间来试验和尝试不同的方法。我突然想到的一个想法是，也许我可以完全跳过 GC。如果 Rust 在没有 GC 的情况下是内存安全的，也许我可以使用相同的机制为 Lox 做同样的事情。例如，使用引用计数智能指针。但我很快就放弃了这个想法。 Lox 语言没有 Rust 的严格规则；很容易创建循环数据结构，如果使用引用计数来实现会泄漏内存。 GC 在这里是必须的。所以我从 Catherine West 在 RustConf 2018 上的一次非常有趣的演讲中得到了一个想法。在 Rust 世界中处理带有循环的类图结构的一个常见解决方法是使用向量索引作为某种指针。我决定研究一些流行的 crate 的代码，比如以某种方式使用这个概念的 id-arena 和 typed-arena。但是 id-arena 的主要问题是它不支持删除单个对象，因为存在遇到 ABA 问题的风险。当您删除一个对象并随后在某处存在实时引用时重用其插槽时会发生这种情况，然后该引用将指向向量中的错误位置。有办法解决这个问题，比如使用代际竞技场，但这感觉过于复杂。

有一天我意识到一件现在感觉如此明显以至于我几乎羞于承认它的事情：我正在编写一个垃圾收集器，它的主要工作是从程序的活动部分中找到没有引用的对象。这意味着，如果我的 GC 工作正常，我根本不应该担心 ABA 问题，因为 GC 将确保不会有被释放对象的活动引用。考虑到这个想法，我最终为安全 Rust 中的 GC 设计了一个非常简单的设计。它基本上是一个特征对象的向量。每个对象都应该实现一个特性（GcTrace），它具有跟踪对象的方法。此外，还有第二个向量包含墓碑以跟踪已删除的对象。对象的分配意味着将其添加到向量并返回将充当某种指针的索引。释放一个对象意味着将它从向量中交换出来并放置一些占位符，并将索引添加到将在未来分配中重用的墓碑列表中。我没有返回普通整数，而是创建了一个通用包装结构来获得某种类型安全性，这样如果我分配不同类型的对象，结果索引也是不同类型的。这与 id-arena crate 所做的非常相似。这个结果索引是 Copy，这意味着我可以随意传递它，而不会被借用检查器打扰。这也极大地促进了解释器的设计，因为我能够摆脱为取悦借用检查器而添加的许多变通方法，例如使用 RefCell 和 Rc。最后，使用 GC 看起来像这样：然后我可以在任何地方复制和传递这个闭包引用，但是当我真正需要对对象做一些事情时，我可以从垃圾收集器中借用它。例如：这种取消参考的舞蹈有点不符合人体工程学。每次我想使用任何 GC 对象时，我都必须调用 gc.deref()。我想也许我可以实现 Deref 并让 Rust 编译器自动为我做这件事，但这需要每个 GcRef 对象持有对 GC 的引用，并且处理生命周期将是一场噩梦。我也可以让 GC 完全静态，但我什至不知道如何只使用安全的 Rust 来做到这一点，所以我决定忍受它。这种 GC 设计非常简单，但它有很多缺点。其中之一是特征对象和墓碑的向量所需的内存永远不会减少。因此，如果程序突然分配了大量对象，然后这些对象被 GC 释放，则插槽所需的空间将永远保留在那里。另一个缺点与何时运行收集过程有关。 clox 中的 GC 对每次分配都有精确的控制，并且对分配的总字节数进行计数。当此计数达到某个阈值时，收集过程将运行。在我的 Rust GC 中，我无法精确计算分配的字节数，因为对象通常具有动态大小的字段，例如字符串或向量。作为一种解决方法，我向 GcTrace trait 添加了一个 size() 方法来估计对象的大小并使用它来保持分配的字节数。但这只是一个近似值。一旦我完成了 GC，Lox 解释器的其余部分就很容易编写了。我最终得到了一个用 100% 安全的 Rust 代码编写的 Lox 实现，并通过了 Lox 集成测试套件中的 243 个测试。

在拥有一个有效的 Lox 解释器和一个绿色测试套件来验证任何更改之后，是时候开始努力提高性能了。在这一点上，我已经放弃了只用安全的 Rust 来匹配 clox 速度的任何希望。正如我之前提到的，clox 是一个非常快速的实现，它使用了各种技巧来实现这一点。从使用没有任何运行时检查的指针算术到超级棘手的 NaN 装箱。但是，我认为如果我在我的代码库中添加一些不安全的块，我至少可以接近 clox 的速度。当然，第一步是衡量绩效。我决定使用制作解释器存储库中可用的相同基准程序。这种测量方式可能不是最好的，但对于没有任何实际程序的语言来说已经足够了。我还决定手动将基准程序转换为 Python 和 Perl 以进行比较。我期待我的第一个实现会出现一些糟糕的结果，但它们比我预期的要糟糕得多：不仅 Loxido（我的​​实现）通常比 clox 慢几倍，而且在许多情况下，它甚至比 jlox（树用 Java 编写的步行实现）！在最初的震惊之后，我意识到除了开始分析并尽可能地减少这些时间之外别无他法。 perf 的第一次运行向我展示了一个明确的目标，将我的糟糕表现归咎于：其中一个问题与我的 GC 实现以及我取消引用基于索引的指针的方式有关。使用向量索引比常规指针解引用慢。需要进行算术运算来获取元素的地址，但更重要的是，Rust 会始终检查索引是否越界。对于绝大多数用例，这些额外的步骤完全可以忽略不计，但是当您有一个每秒处理约 3.5 亿条指令的 VM，然后您必须对每条指令执行三到四次取消引用时，它就会显示出来。但即便如此，这也不是主要问题。最大的问题是我必须添加一些变通方法来取悦借阅检查员。我将尝试解释这一点：VM 的核心基本上是一个巨大的循环，它增加程序计数器 (PC)，获取下一条指令并运行一个大匹配表达式。 PC 是当前帧的一部分。当前帧有一个闭包对象的引用，闭包对象有一个函数对象的引用，然后函数对象有一个对包含指令的字节码块的引用。在代码中它大致是这样的： loop { let mut frame = self.frames.last_mut().unwrap();让闭包 = self.gc.deref(frame.closure);让函数 = self.gc.deref(closure.function);让块 = &function.chunk;让指令 = chunk.code[frame.ip]; frame.ip += 1;匹配指令 { ... }}

循环的第一部分是导致问题的原因。但是，我真的不需要在每次迭代中都这样做。对于大多数指令，活动帧和字节码块保持不变。当前帧仅在调用函数或当前函数返回时更改。我可以将其存储在局部变量中作为参考，并仅根据这些指令更改它，例如： let mut frame = self.frames.last_mut().unwrap();让闭包 = self.gc.deref(frame.closure);让函数 = self.gc.deref(closure.function);让 mut chunk = &function.chunk;循环 { 让指令 = chunk.code[frame.ip]; frame.ip += 1;匹配指令 { 指令::调用 => { // 更新帧和块 } }} 这将大大提高速度。但是有一个问题：Rust 对此不是很满意。我的实现方式是 GC 拥有创建的每个对象。如果我需要一个对象，我可以借用它，当我借用它时，我也借用了整个 GC。由于 Rust 的别名规则，如果我决定对当前字节码块有一个长期引用，我将永远无法从 GC 可变地借用。因此，这会导致大量的借用检查器投诉。这就是为什么我最终立即归还了每一笔借款。但这意味着大量不必要的取消引用。旁注：我经常遇到的借用检查器的一个类似问题是过程间冲突。 Niko Matsakis 有一篇很好的博客文章解释了这个问题。我很乐意看到 Rust 在这方面有所改进，因为我认为这是初学者的一大难题。我尝试了一些不同的方法来使用安全的 Rust 来解决这个问题，但我在每一种方法上都失败了。这通常令人沮丧，因为它需要长时间的重构，直到最后我才意识到它不起作用。一个更简单的解决方案是使用原始指针而不是引用。这很容易实现，但需要不安全的块来取消引用这两个指针。我最终做到了这一点并且改进是巨大的，一些基准测试占用的时间减少了 74%。这样做之后，我还决定重写 GC 并使引用包装原始指针而不是向量索引。这也需要一些不安全的代码，但它也带来了一些不错的速度改进。更好的是，它让我摆脱了很多样板代码，因为我终于可以使用 Deref。所以，而不是做这样的事情

我离clox的速度还很远，但至少我已经比jlox好，并且非常接近Python和Perl。接下来出现在分析器中的是 HashMap 操作。这在意料之中。像大多数动态语言一样，Lox 大量使用哈希表。它们用于存储全局变量、实习字符串、字段和方法。这方面的任何改进肯定会对解释器的整体性能产生巨大影响。事实上，本书的最后一章专门讨论优化，展示了哈希表代码的微小变化如何允许将基准测试的运行时间缩短多达 42%。那令人印象深刻。最简单的尝试是更改散列算法。 Rust 标准库中的 HashMap 实现默认使用 SipHash，而 clox 使用 FNV。我知道 SipHash 并没有那么快，所以我想我可以用一些简单的胜利来代替它。在 Rust 中，切换哈希函数实现非常容易。只需使用不同的构造函数，其余代码保持不变。我找到了一个实现 FNV 算法的 Rust crate，但我也发现了一个叫做 aHash 的箱子，它声称是“目前 Rust 中最快的、抗 DOS 的哈希”。我两者都试过了，确实 aHash 给出了更好的结果。通过这个微小的变化，我能够将一些基准测试的运行时间缩短多达 45%。这么小的变化真是太神奇了。后来我发现 Rust 编译器使用了另一种称为 fxhash 的哈希算法。尽管 aHash 声称比 fxhash 更快，但鉴于切换算法是多么容易，我还是决定尝试一下。我很惊讶地发现所有基准测试都有改进。在某些情况下，从 aHash 结果中节省了多达 25% 的时间！旁注：不要对这些结果感到非常兴奋。 Rust 默认使用 SipHash 有一个很好的理由。 FNV 和 fxhash 等算法容易受到算法复杂度 DOS 攻击。将它们用于解释器可能不是一个好主意。但考虑到这不是一种现实世界的语言，而且我正在尝试使用 FNV 匹配 clox 速度，我决定暂时忽略这个事实。然而，aHash 声称可以抵抗 DOS，这对于真正的语言来说可能是一个非常有趣的选择。

切换哈希函数的改进非常显着。然而，分析器不断显示出一些由哈希表操作引起的性能瓶颈。我还分析了 clox，我发现哈希操作并没有花那么多时间。我不得不进行更多调查。 Rust 的标准库使用了一种非常复杂的哈希映射实现，称为 HashBrown。这是 Google 的 SwissTables 的一个端口，它是一种用 C++ 编写的高性能哈希映射实现。它甚至使用 SIMD 指令并行扫描多个哈希条目。我怎么能改进呢？这似乎是完全不可能的。所以我决定重新阅读专门用于哈希表的 Crafting Interpreters 一章，看看我是否遗漏了任何技巧。事实确实如此！与通用哈希表实现的 HashBrown 不同，clox 中的哈希表是为非常特定的用例量身定制的。虽然 HashBrown 是通用的，但 clox 的 Table 仅使用 Lox 字符串作为键，使用 Lox 值作为值。 Lox 字符串是不可变的、内嵌的，并且它们可以缓存自己的哈希值。这意味着散列对于每个字符串只发生一次，并且比较与比较两个指针一样快。此外，不处理泛型类型的优势在于可以忽略类型系统边缘情况，例如零大小数据类型。所以我决定咬紧牙关，紧跟 clox 的代码，用 Rust 编写我自己的哈希映射实现。结果非常积极，我能够在大多数基准测试中节省时间，与带有 fxhash 的 HashBrown 相比，在最佳情况下减少了 44%。最后，它也不是很多代码。我的哈希映射实现大约有 200 行，其中大部分是不安全的 Rust。旁注：在编写我自己的哈希表之前，我尝试使用 HashBrown 来模拟与 clox 表相同的特殊条件。例如，我在 GcRef<String> 上实现了 PartialEq 以确保对内部字符串进行比较......