用 64 位字替换 Rust 枚举使我的解释器速度提升 17%

# 用64位字替代Rust枚举使我的解释器性能提升17% 来源：https://pointersgonewild.com/2026-08-25-replacing-a-rust-enum-with-a-64-bit-word/ 本篇博文是关于我构建和优化Plush（https://github.com/maximecb/plush）语言解释器与虚拟机的系列文章的第六篇。前一篇是《加速Plush垃圾回收器》（https://pointersgonewild.com/2026-08-17-speeding-up-the-plush-garbage-collector/）。在上一篇文章中，我解释了几项简单的更改如何让复制式垃圾回收器的速度提升超过16倍，并将一百万个对象的回收时间缩短至约7毫秒。我纯粹为了优化而优化Plush乐在其中，但我也怀有让这门语言足够快、能够实时渲染3D动画的目标，尽管它是解释型语言。Plush是一门动态类型语言，与Python、JavaScript、Ruby、Lua和Lox同属一个家族。这类动态语言的特性是类型附加于值而非变量，因此为了在程序中传递值，解释器通常需要一个能表示该语言中所有可能值的`Value`类型。 在Plush的原始版本中，我使用了一个普通的Rust标记枚举。这很棒，因为Rust让使用标记枚举变得非常便捷，我们可以用`match`语句将不同的`Value`子类型分派到不同的处理逻辑： ``` // 旧的Rust Value类型，作为标记枚举 enum Value { Undef, // 未初始化的变量或字段，读取会触发错误 Nil, False, True, Int64(i64), Float64(f64), String(*const Str), // 不可变字符串 HostFn(&'static HostFn), // 宿主虚拟机暴露的函数 Fun(FunId), // 非闭包的Plush函数 Closure(*mut Closure), // 捕获变量的闭包 Cell(*mut Value), // 闭包捕获的可变变量 Object(*mut Object), // 类实例 Array(*mut Array), // JS/Python风格的数组/列表 ByteArray(*mut ByteArray), // 快速原始字节数组（如帧缓冲区） Dict(*mut Dict), // JS/Python风格的字典 Class(ClassId), } ``` 如上所示，即使我仍将其视为玩具语言，Plush也拥有多种不同的值类型。该语言有对象（即类实例），其访问效率很高，但它也有JS/Python风格的字典，使得JSON式的语法成为可能。此外还有两种不同的数值类型：`Int64`和`Float64`。我做出这个选择是因为，虽然JavaScript表面上将所有数字都视为双精度浮点数，但JS引擎实际上会在后台追踪哪些是整数，这一直让我有些困扰。 但这里最遗憾的事情并非枚举变体的数量，而是这个枚举的总宽度达到了16字节（128位）。每个枚举变体只需要64位，Rust生成的枚举标签也只需要8位，但由于内存对齐约束，Rust可能需要为每个值使用整整128位。这可能看起来没什么大不了，但如果你有一个包含大量值的数组，那么这个数组内部最终会充满许多空闲、浪费的字节。这就是那种会让虚拟机工程师夜里哭醒的事情。 一段时间以来，我一直在思考，是否可以设计一种更高效的低位标记方案，使`Value`类型能够放入64位以内。这里有一个[经典的技巧](https://www.chiark.greenend.org.uk/doc/sbcl/sbcl-internals/Type-tags.html)，它基于这样一个事实：在64位系统中，堆对象地址通常对齐到8字节边界，这意味着地址的最低3位必须为零。这意味着你本质上可以“窃取”这些位来打包额外信息。你也可以借用整数值的最低两位，前提是假设整数值极少需要用到完整的64位范围，因为作为参考，`2^64 ≈ 1.84 * 10^19`，这是一个极其巨大的数值。如果你有一个变量表示例如文本文件的行数、游戏中的敌人数量或其他任何数值量，它几乎不可能达到这个值。在一个现代CPU上，如果执行类似`for (uint64_t i = 0; i < UINT64_MAX; ++i)`的循环，这个循环可能需要十多年才能执行完。 更复杂的标记方案显然能减少内存使用，但也意味着我们需要引入位运算来判断一个值是整数、指针还是浮点数。我们还需要额外的位运算来解包某些值以进行操作。这意味着CPU需要执行额外的指令。一位经验丰富的虚拟机工程师曾告诉我，聪明的做法是为整数设置零作为标记位，因为这样，两个移位后的整数相加或相减仍然可以直接使用`add`或`sub`机器指令。然而，浮点数的打包和解包更为复杂，需要多条指令。我曾有点担心性能影响，需要牺牲内存效率来换取一点性能损失。 但事实证明，我的担忧完全是多余的，正如我们将在本文后面看到的。 ## 一种高效的低位标记方案 Claude和我共同设计并迭代了这个值的表示，具体见[此源文件](https://github.com/maximecb/plush/blob/6b71f8c4bbf7cf234c289ee2b979f16195daead1/src/value.rs)。它完美地包装在一个Rust新类型中，内部是`u64`。如你所见，它提供了许多便捷方法，弥补了丢失Rust枚举所带来的不便。大多数方法都标记为始终内联（always inline）以保证性能，因为它们在解释器循环中无处不在。 下图更详细地说明了值的表示结构： **带标记的值表示。**（https://pointersgonewild.com/2026-08-25-replacing-a-rust-enum-with-a-64-bit-word/value-repr.svg）*带标记的值表示。* 我最终采用的低位标记方案编码了5种不同类型的值：定长整数（fixnums）、浮点数（flonums）、立即数（immediates）和两种指针。定长整数是适合62位范围的有符号整数。浮点数是使用自标记方案编码的浮点值（稍后详述）。立即数是诸如`nil`、`true`、`false`、`undef`、函数和类ID，以及可以从Plush调用的、用Rust编写的宿主函数。在Plush中，你可以用美元符号前缀调用宿主函数，例如`$read_file(file_name)`。立即数有一个5位的子标签来指示它是哪种立即数。之所以是5位，因为在现代CPU上，对最低字节进行8位比较只是一条指令，这意味着如果需要，我们可以在一条指令中同时比较子标签和标记位。 在此表示中有两种指针的原因是，我想要让值之间的相等比较变得快速。这很常见，因为你可能有循环条件、if语句中的指针比较等。Plush中的大多数值使用简单的引用相等性进行比较，但我选择对字符串进行结构相等性比较，以便以后有可能使用[字符串驻留（string interning）](https://en.wikipedia.org/wiki/String_interning)表。这就像JS，两个值相同的字符串是相等的。 浮点数也需要特殊处理，因为它们有一个符号位，并且`+0.0`必须与`-0.0`相等。简单的实现方式是使用标记中的一个位（我选择了位索引1）来表明两个值是否可以直接用一条比较指令进行比较。这允许我们有一个快速路径，使用单个机器比较指令来比较整数、指针、句柄以及`true`、`false`、`nil`和`undef`这样的小立即常量。 这里有一些细微之处，因为某些指针类型（字符串对象）不能使用直接指针相等性进行比较。此外，如果整数或浮点值超出我们能装入带标记值的范围，我们必须分配一个堆对象来装箱这个值。这意味着我们最终可能会有两个值相等的浮点数，它们由不同的堆对象表示，但这些值使用`==`运算符比较时必须测试为相等。 如果Plush最终获得JIT编译器，那么为`if (p != nil)`生成的代码可能如下所示。这里没有慢路径，因为没有任何被结构比较的值可能等于`nil`： ``` ; x0 = 被测试的值 ; nil 是立即数 0x05 cmp x0, #5 b.eq .ELSE_BRANCH ; 如果相等则跳转到else分支 ``` ## 高效的定长整数操作 如前所述，适合62位定长整数范围的整数值，其最低两位设置为00，并存储为`n << 2`。因此，加法、减法、比较以及位运算与/或/异或可以直接在带标记的字上进行。64位溢出恰好也是结果不再适合62位的情况，这意味着我们可以使用标准的机器指令来检查溢出（在x86-64上是`jo`，在ARM64上是`bvs`）。 对于像`i < n`这样的循环计数器比较，ARM64机器代码可以如下所示。检查两个值都是整数的成本是3条机器指令： ``` ; `i < n` 的快速路径，5条指令 ; x0 = i, x1 = n orr x2, x0, x1 ; 组合两个操作数 tst x2, #3 ; 两个操作数都是定长整数吗？ b.ne .Lslow_lt ; 浮点数、装箱数字和字符串走这条路径 cmp x0, x1 ; 比较定长整数，`00`标记位无关紧要 b.ge .LOOP_EXIT ; 有符号比较，定长整数是62位有符号数 ``` 两个定长整数相加的快速路径如下所示。Rust编译器在实践中可能无法组合两个标签，但JIT编译器可以轻松做到，甚至可以在拥有有关值类型的额外运行时信息的情况下完全移除类型检查，在这种情况下，加法将像C整数加法一样高效： ``` ; 定长整数加法的快速路径 ; 快速路径5条指令 ; x0 = a, x1 = b，两个带标记的Value ; 定长整数是 n << 2，所以它的低两位是 00 orr x2, x0, x1 ; 组合两个标签，这样一次测试就覆盖了一对 tst x2, #3 ; 两个操作数都是定长整数吗？ b.ne .Lslow adds x0, x0, x1 ; (a << 2) + (b << 2) == (a + b) << 2 b.vs .Loverflow ; 有符号溢出恰好是62位溢出 ; x0 已经包含带标记的结果。输入过程中没有解标签 ; 输出过程中也不需要重新标签 ``` ## 自标记浮点数表示 在带标记值的系统中，标记浮点值有很多种方式。其中最著名的方案之一是[NaN装箱（NaN boxing）](https://craftinginterpreters.com/optimization.html#nan-boxing)，据我所知，它至今仍在Firefox JavaScript引擎中使用。NaN装箱利用了这样一个事实：当一个双精度浮点数的11位指数位全部设置为1且其尾数非零时，它就被视为[NaN（非数字）](https://en.wikipedia.org/wiki/NaN)。任何满足此条件的位模式，无论字的其余部分持有何物，都会被读作NaN。对于64位双精度数，这意味着有52位尾数位可用作存储任何类型数据的有效载荷，实际中是51位，因为实现通常为静默NaN保留最高位。《Crafting Interpreters》一书还提到，你可以将最高位符号位用作额外标签。 这是一个巧妙的技巧，其优势在于你可以“免费”（或多或少）获得双精度操作，无需标记或解标签。缺点是其他类型的操作会受到一点性能损失。实际情况是，典型的JavaScript、Python或Ruby程序并不做太多浮点运算，更多的是整数和指针操作。对于Plush，我决定研究其他可能与低位标记配合使用的浮点数标记途径。我已经知道一种可能的方法是窃取IEEE双精度数的一些指数位。双精度数能表示的范围巨大无比，最大可表示值约为`1.8 * 10^308`。有理由认为，计算机程序中通常看到的大多数值从未接近该范围，因此，如果我们窃取几个指数位，我们将得到一个较小、但仍然巨大的带标记浮点数可表示范围。我们无法装入该范围的双精度数，可以简单地进行堆分配，但这应该几乎不需要发生。 在我研究如何高效实现这一点的过程中，我偶然发现了一篇相当近期的关于[浮点自标记（Float Self-Tagging）](https://arxiv.org/pdf/2411.16544)的论文，作者是Olivier Melançon、Manuel Serrano和Marc Feeley。他们提出的方案对高位进行旋转，使其最终处于标签位位置，在添加一个偏移值（bias value）后，低位会变成我们想要的特定标签。这很巧妙，意味着我们不需要移位、掩码或其他任何操作。最棒的是，带标签的浮点值也可以表示次正规数、无穷大甚至NaN，而无需堆装箱，这非常方便，因为这些值在某些计算中确实会出现。 在我的装箱方案中，我选择了一个偏移值，使得最低两位最终为`10`。位索引1中的那个`1`表示双精度数不能直接进行相等比较。神奇的是，我们只丢失了两位指数，并保留了完整的尾数精度，这意味着在浮点表示中没有丢失任何有效数字。 **使用自标记对浮点数进行装箱和标记，来自Float Self-Tagging (arXiv:2411.16544)。**（https://pointersgonewild.com/2026-08-25-replacing-a-rust-enum-with-a-64-bit-word/flonum.svg）*使用自标记对浮点数进行装箱和标记，来自Float Self-Tagging (arXiv:2411.16544)。* 两个浮点数相加比两个定长整数相加成本更高，因为我们确实需要做一些额外的工作来撤销和重新标记： ``` ; 快速路径18条指令，BIAS已经在寄存器中 ; x0 = a, x1 = b，两个带标记的Value ; x9 = BIAS, 0x6810_0000_0000_0000，一次性物化 and x2, x0, #3 ; 隔离a的标签位 and x3, x1, #3 ; 和b的标签位 cmp x2, #2 ; 浮点数的低两位是10 ccmp x3, #2, #0, eq ; 仅当a是浮点数时才检查b b.ne .Lslow ror x2, x0, #4 ; 撤销旋转 sub x2, x2, x9 ; 撤销偏移，留下IEEE 754位 fmov d0, x2 ror x3, x1, #4 sub x3, x3, x9 fmov d1, x3 fadd d0, d0, d1 ; 实际的f64加法 fmov x2, d0 ; 回到位模式 add x2, x2, x9 ; + BIAS ror x0, x2, #60 ; 向左旋转4位：ARM64只能向右旋转 and x3, x0, #3 ; 隔离结果的标签位 cmp x3, #2 ; 标签是否落在10上，或者这个值需要装箱？ b.ne .Lbox ``` 上面机器代码片段的最后几条指令测试最低两位是否最终为`10`。如果没有，这意味着我们得到的值属于编码未覆盖的两个狭窄的幅度范围。在实践中这应该极其罕见，但如果确实发生，我们有一个慢路径，简单地分配一个堆装箱然后继续。在Plush中，我使用的是一个bump分配器，因此堆装箱实际上也相当快。 ## 对内存使用的影响 我有一组Plush的综合基准测试。其中一些是微基准测试，旨在测试某个特定特性的性能，另一些则更宽泛一些。例如，`fib`是递归斐波那契数微基准测试（Marc Feeley的最爱）；它主要测试函数调用和解释器吞吐量。`binary_tree`基准测试同时包含递归函数调用和对象属性访问，以及指针追踪和遍历堆分配的对象。`mlp`基准测试是一个朴素实现的多层神经网络，包含大量浮点运算。我还有一个`sha256`计算和经典的`nbody`天体模拟。最近，我还添加了一个三角形光栅化基准测试（此处未显示），以了解我在Plush中能用3D图形做到什么程度（https://www.youtube.com/watch?v=ElwU9PAvpRM）。