如何构建高性能动态语言解释器

# 如何构建一个高性能的动态语言解释器 来源：https://zef-lang.dev/implementation 本文旨在介绍如何将我为娱乐而创建的动态语言 Zef（https://zef-lang.dev/index.html）中一个*极其简单*的 AST 遍历解释器进行优化，使其性能足以与 Lua、QuickJS 和 CPython 等主流方案相媲美。 ## 为什么这么做？ 大多数关于提升语言实现速度的文章，关注的都是当底层基础已经稳固时的工作，比如编写又一个 JIT（即时编译器）或者微调一个已经很完善的垃圾回收器。我已经写过不少（https://webkit.org/blog/3362/introducing-the-webkit-ftl-jit/）（https://webkit.org/blog/5852/introducing-the-b3-jit-compiler/）文章（https://webkit.org/blog/6161/locking-in-webkit/），讨论了（https://webkit.org/blog/7122/introducing-riptide-webkits-retreating-wavefront-concurrent-garbage-collector/）针对（https://webkit.org/blog/7536/）成熟 JS 运行时（https://webkit.org/blog/10308/speculation-in-javascriptcore/）的各种优化。本文则不同。它关注的是从零开始的情况：你距离编写 JIT 还很遥远，且 GC 也不是你最头疼的问题。本文将介绍的技术易于理解——*没有 SSA、没有 GC、没有字节码、也没有机器码*——**但它们能带来高达 16 倍的性能提升**（如果算上尚未完成的 Yolo-C++ 移植版，可达 *67 倍*），使我的微型解释器性能跻身于 QuickJS、CPython 和 Lua 的竞争行列。本文将重点介绍以下技术： - 值的表示方式（Value representation）。 - 内联缓存（Inline caching）。 - 对象模型（Object model）。 - 观察点（Watchpoints）。 - 基础常识优化（Grinding through common sense optimizations）。 ## 评估方法 为了评估优化进度，我创建了一个名为 ScriptBench（https://zef-lang.dev/scriptbench1.html）的基准测试套件。该套件将经典的编程语言基准测试移植到了 Zef： - Richards（https://www.cl.cam.ac.uk/%7Emr10/Bench.html）（操作系统调度器） - DeltaBlue（约束求解器） - N-Body（物理模拟） - Splay（二叉树测试） 这些基准测试也已广泛移植到其他多种语言中。我找到了它们现有的 JavaScript、Python 和 Lua 版本。对于 Splay 测试，由于缺乏现成的 Python 和 Lua 移植版，我使用 Claude 进行了移植。所有实验均在配备 32GB 内存的 Intel Core Ultra 5 135U 处理器上运行 Ubuntu 22.04.5 系统进行。Fil-C++ 版本为 0.677。Lua 5.4.7 使用 GCC 11.4.0 编译。QuickJS-ng 0.14.0 取自 QuickJS 的 GitHub Release 页面（https://github.com/quickjs-ng/quickjs/releases/download/v0.14.0/qjs-linux-x86_64）。CPython 3.10 则是 Ubuntu 自带的版本。所有实验结果均取 30 次随机交错运行的平均值。**需要明确的是：在本文的大部分章节中，我会比较用 Fil-C++ 编译的我自己的解释器与其他开发者使用 Yolo-C 编译器编译的对比项。** ## 目录 本文首先简要描述原始的重哈希表依赖、基于 AST 遍历的 Zef 解释器，随后按顺序详细介绍我在实现 16.6 倍加速过程中所采用的各项优化。 | Implementation | vs Zef Baseline | vs Python 3.10 | vs Lua 5.4.7 | vs QuickJS-ng 0.14.0 | |---|---|---|---|---| | Zef Baseline (https://zef-lang.dev/implementation#baseline) | 1x faster | 35.448x slower | 79.588x slower | 22.562x slower | | Zef Change #1: Direct Operators (https://zef-lang.dev/implementation#1-directops) | 1.175x faster | 30.161x slower | 67.716x slower | 19.196x slower | | Zef Change #2: Direct RMWs (https://zef-lang.dev/implementation#2-directrmws) | 1.219x faster | 29.081x slower | 65.291x slower | 18.509x slower | | Zef Change #3: Avoid IntObject (https://zef-lang.dev/implementation#3-avoidintobject) | 1.23x faster | 28.82x slower | 64.705x slower | 18.343x slower | | Zef Change #4: Symbols (https://zef-lang.dev/implementation#4-symbols) | 1.456x faster | 24.338x slower | 54.643x slower | 15.491x slower | | Zef Change #5: Value Inline (https://zef-lang.dev/implementation#5-valueinline) | 1.497x faster | 23.673x slower | 53.15x slower | 15.067x slower | | Zef Change #6: Object Model and Inline Caches (https://zef-lang.dev/implementation#6-objectmodel-and-ic) | 6.818x faster | 5.199x slower | 11.674x slower | 3.309x slower | | Zef Change #7: Arguments (https://zef-lang.dev/implementation#7-arguments) | 9.047x faster | 3.918x slower | 8.798x slower | 2.494x slower | | Zef Change #8: Getters (https://zef-lang.dev/implementation#8-getters) | 9.55x faster | 3.712x slower | 8.333x slower | 2.362x slower | | Zef Change #9: Setters (https://zef-lang.dev/implementation#9-setters) | 9.874x faster | 3.59x slower | 8.06x slower | 2.285x slower | | Zef Change #10: callMethod inline (https://zef-lang.dev/implementation#10-callmethodinline) | 10.193x faster | 3.478x slower | 7.808x slower | 2.213x slower | | Zef Change #11: Hashtable (https://zef-lang.dev/implementation#11-hashtable) | 11.758x faster | 3.015x slower | 6.769x slower | 1.919x slower | | Zef Change #12: Avoid std::optional (https://zef-lang.dev/implementation#12-avoidoptional) | 11.963x faster | 2.963x slower | 6.653x slower | 1.886x slower | | Zef Change #13: Specialized Arguments (https://zef-lang.dev/implementation#13-specializedargs) | 12.39x faster | 2.861x slower | 6.423x slower | 1.821x slower | | Zef Change #14: Improved Value Slow Paths (https://zef-lang.dev/implementation#14-valueslowpaths) | 13.642x faster | 2.598x slower | 5.834x slower | 1.654x slower | | Zef Change #15: Deduplicated DotSetRMW::evaluate (https://zef-lang.dev/implementation#15-dedupdotsetrmw) | 13.609x faster | 2.605x slower | 5.848x slower | 1.658x slower | | Zef Change #16: Fast sqrt (https://zef-lang.dev/implementation#16-sqrt) | 13.824x faster | 2.564x slower | 5.757x slower | 1.632x slower | | Zef Change #17: Fast toString (https://zef-lang.dev/implementation#17-tostring) | 14.197x faster | 2.497x slower | 5.606x slower | 1.589x slower | | Zef Change #18: Array Literal Specialization (https://zef-lang.dev/implementation#18-arrayliterals) | 15.351x faster | 2.309x slower | 5.184x slower | 1.47x slower | | Zef Change #19: Value callOperator Optimization (https://zef-lang.dev/implementation#19-valuecalloperator) | 16.344x faster | 2.169x slower | 4.87x slower | 1.38x slower | | Zef Change #20: Better C++ Configuration (https://zef-lang.dev/implementation#20-cppoptions) | 16.639x faster | 2.13x slower | 4.783x slower | 1.356x slower | | Zef Change #21: No Asserts (https://zef-lang.dev/implementation#21-noasserts) | 16.646x faster | 2.13x slower | 4.781x slower | 1.355x slower | | Zef in Yolo-C++ (https://zef-lang.dev/implementation#yolo) | 66.962x faster | 1.889x faster | 1.189x slower | 2.968x faster | ## 原始 Zef 解释器 原始的 Zef 解释器（https://zef-lang.dev/source-viewers/baseline.html）在编写时几乎未考虑性能问题。仅做了两项与性能相关的决策： - **值的表示方式**（https://zef-lang.dev/source-viewers/baseline.html#value.h）是一个 64 位标记值（tagged value），可容纳 double、32 位整数或`Object*`。Double 通过偏移量`0x1000000000000`来表示（这一技术我从 JavaScriptCore 中学到；文献中常称之为 NuN 标记法）。整数和指针直接使用原生类型表示，这里我依赖于“没有任何指针的值会低于`0x100000000`”这一事实（这是一个有风险的假设，但你可以通过架构限制强制其为真；注意，如果担心这点，本可以用高位标记`0xffff000000000000`来表示整数）。这使得数字运算的快速路径变得极其简单（只需一次位测试即可判断是否为数字及其类型）。更重要的是，这完全避免了数字类型的堆分配。**如果你正从零开始构建解释器，从一开始就做好基本值表示的决策非常重要，因为后期再改会极其困难！***对于实现动态类型语言，32 位或 64 位标记值是一个标准的起点。* - 我选择了某种 C++。选择一种最终能够支撑语言实现中逐渐演变的各种优化技术的语言至关重要，而 C++ 正是其中之一。我不会选择 Java，因为底层优化的天花板太低。我也不会选择 Rust，因为垃圾回收语言需要一个包含全局可变状态和循环引用的堆表示（尽管如果你愿意多语言混合开发，可以用 Rust 编写解释器的部分模块；或者如果你的项目不介意大量`unsafe`代码，也可以用 Rust）。 我也犯了许多从性能工程角度看并不明智的临时决策： - 我使用了 Fil-C++（https://fil-c.org/）。这确实让我推进得极快——例如，我免费获得了垃圾回收器。这也意味着我零时间调试内存安全问题（Fil-C++ 会附带清晰的堆栈跟踪和大量诊断信息报告内存违规）或未定义行为（Fil-C++ 本身消除未定义行为）。然而，Fil-C++ 通常会导致约 4 倍的开销，所以我一开始就背负了这 4 倍的性能劣势，再加上后续提到的其他非最优选择。 - **递归 AST 遍历解释器**。解释器实现为一个虚拟的`Node::evaluate`方法（https://zef-lang.dev/source-viewers/baseline.html#node.h:20），并在多处被重写。 - **到处使用字符串**。例如，`Get` AST 节点（https://zef-lang.dev/source-viewers/baseline.html#get.h）持有一个`std::string`来描述要获取的变量名，且每次访问变量时都会使用该字符串。 - **到处使用哈希表**。当`Get`执行时，该字符串被用作`std::unordered_map`（https://zef-lang.dev/source-viewers/baseline.html#context.cpp:43-45）的键，该映射存储着变量值。 - **层层递归的作用域链遍历**（https://zef-lang.dev/source-viewers/baseline.html#context.cpp:51-60）（https://zef-lang.dev/source-viewers/baseline.html#userobject.cpp:43-50）。Zef 允许几乎所有构造嵌套，嵌套会产生闭包；例如，类 A 嵌套在函数 F 中，F 嵌套在类 B 中，B 又嵌套在函数 G 中，这意味着类 A 的成员函数可以访问 A 的字段、F 的局部变量、B 的字段以及 G 的局部变量。原始解释器通过在 C++ 中对可查询不同作用域对象的函数进行递归来实现此功能。尽管如此，这些**糟糕的决策**也让我能用极少的代码实现一个相当复杂的语言解释器。其中最大的模块显然是**解析器**（https://zef-lang.dev/source-viewers/baseline.html#parse.cpp）。其余部分则简单清晰。 **该解释器比 CPython 3.10 慢 35 倍，比 Lua 5.4.7 慢 80 倍，比 QuickJS-ng 0.14.0 慢 23 倍。让我们看看通过实施一系列优化能取得多大的进展！** ## 优化 #1：直接调用运算符 第一次优化（https://zef-lang.dev/diff-viewers/1-directops.html）是让解析器为每个运算符生成独立的 AST 节点，而不是使用带有运算符名称的`DotCall`节点。在 Zef 中，以下代码： `` a + b `` 等价于： `` a.add(b) `` 因此，原始解释器会将`a + b`解析为以`b`为参数的`DotCall(a, "add")`（https://zef-lang.dev/source-viewers/baseline.html#parse.cpp:584）。这导致了执行缓慢，因为每次数学运算都需要查找运算符的方法名字符串： - `DotCall`会将该字符串传递给`Value::callMethod`（https://zef-lang.dev/source-viewers/baseline.html#dotcall.h:34）。 - `Value::callMethod`会通过多次字符串比较进行级联分发（https://zef-lang.dev/source-viewers/baseline.html#value.cpp:212-249）。 通过此项优化，我们让解析器创建了（https://zef-lang.dev/diff-viewers/1-directops.html#parser.cpp:584）`Binary<>`（https://zef-lang.dev/source-viewers/1-directops.html#binary.h）和`Unary<>`（https://zef-lang.dev/source-viewers/1-directops.html#unary.h）节点。借助一些模板和 Lambda 技巧，这些节点为每个运算符提供了独立的`Node::evaluate`虚函数重写。这些调用会直接进入对应运算符的`Value`快速路径（https://zef-lang.dev/source-viewers/1-directops.html#value.cpp:23-199）。因此，现在执行`a + b`会调用`Binary::evaluate`，随后调用`Value::add`。 **此次变更带来了 17.5% 的性能提升。**此时，Zef 的速度比 CPython 3.10 慢 30 倍，比 Lua 5.4.7 慢 67 倍，比 QuickJS-ng 0.14.0 慢 19 倍。* ## 优化 #2：直接调用读改写操作符 (RMWs) 在上一次优化中，我们通过避免基于字符串比较的分发机制让运算符变快。但这一改动并没有影响*所有*运算符！那些运算符的读改写（RMW）形式，例如： `` a += b `` 仍然依赖基于字符串的分发。因此，第二次优化（https://zef-lang.dev/diff-viewers/2-directrmws.html）是让解析器为每种 RMW 情况（https://zef-lang.dev/diff-viewers/2-directrmws.html#rmw.h）生成独立的节点（https://zef-lang.dev/diff-viewers/2-directrmws.html#parse.cpp:745-750）。 在这里发生的过程是：解析器通过`makeRMW`虚函数调用，请求 LValue 节点将自己替换为 RMW 节点： - Get（https://zef-lang.dev/diff-viewers/2-directrmws.html#get.h:26）：对应变量的获取，即单纯的`id` - Dot（https://zef-lang.dev/diff-viewers/2-directrmws.html#dot.h:24）：对应`expr.id` - Subscript（https://zef-lang.dev/diff-viewers/2-directrmws.html#subscript.h:24）：对应下标访问，即`expr[index]` 这些虚函数调用均使用`SPECIALIZE_NEW_RMW`（https://zef-lang.dev/source-viewers/2-directrmws.html#rmw.h:14-34）宏来创建模板特化形式： - SetRMW（https://zef-lang.dev/source-viewers/2-directrmws.html#setrmw.h）：对应`id += value` - DotSetRMW（https://zef-lang.dev/source-viewers/2-directrmws.html#dotsetrmw.h）：对应`expr.id += value` - SubscriptRMW（https://zef-lang.dev/source-viewers/2-directrmws.html#subscriptrmw.h）：对应`expr[index] += value` 需要注意的是，虽然其余运算符的特化（来自更改 #1）使用 Lambda 来分派到相应的`Value`运算符函数，但对于 RMW，我们使用了枚举。这是一个务实的选择，因为我们需要在许多地方传递该枚举，以处理可能通过三种不同途径（get、dot 和 subscript）到达 RMW 的事实。所有的封装最终都落脚于`Value::callRMW<>`（https://zef-lang.dev/source-viewers/2-directrmws.html#value.h:150-171）模板函数，由它来分发实际的 RMW 运算符调用。 **此次变更带来了 3.7% 的性能提升。**此时，Zef 的速度比 CPython 3.10 慢 29 倍，比 Lua 5.4.7 慢 65 倍，比 QuickJS-ng 0.14.0 慢 18.5 倍。*我们现在比起步阶段快了 1.22 倍。* ## 优化 #3：避免 IntObject 检查 `Value`的快速路径（https://zef-lang.dev/source-viewers/2-directrmws.html#value.cpp:23-199）存在一个小问题：它们使用了`isInt()`（https://zef-lang.dev/source-viewers/2-directrmws.html#value.h:62-65），该方法内部调用了`isIntSlow()`（https://zef-lang.dev/source-viewers/2-directrmws.html#value.cpp:281-284），后者又会发起对`Object::isInt()`（https://zef-lang.dev/source-viewers/2-directrmws.html#object.h:23）的虚函数调用，用于检查我们处理的是否真的是整型。 之所以会出现这种情况，是因为原始解释器中的 Zef 值表示包含四种不同的情况： 1. 带标签的 int32 值。 2. 带标签的 double 值。 3. 无法用 int32 表示的 int64 对应的 IntObject。 4. 其他所有对象。 在 IntObject 的情况下，`Value` 仍然负责所有整数方法的派发，因为这允许解释器只需维护一套数学运算符的实现（且该实现始终位于 `Value` 中）。 这项简单的优化（https://zef-lang.dev/diff-viewers/3-avoidintobject.html）使得`Value`的快速路径仅考虑 int32 和 double（https://zef-lang.dev/diff-viewers/3-avoidintobject.html#value.cpp:25-201），并将所有`IntObje