Rust 中的尾调用解释器 – Jimmy Ostler
摘要
Jimmy Ostler 深入探讨了 Rust 中的尾调用解释器，实现并基准测试了多种虚拟机分发技术，包括 switch 分发、子例程线程化和尾调用优化的机器。
暂无内容
查看缓存全文
缓存时间: 2026/08/10 11:33
# Rust 中的尾调用解释器 - Jimmy Ostler
来源：https://lordgoati.us/blog/tail-call/
Rust 中的尾调用解释器 - Jimmy Ostler
---
主页 (https://lordgoati.us/)文章 (https://lordgoati.us/blog/)Ternary (https://lordgoati.us/ternary/)Github (https://github.com/LordGoatius/)**2026 年 8 月 1 日**Jimmy Ostler字数：1636阅读时间：9 分钟
---
最近，我在寻找改进我的`ternary` (https://lordgoati.us/ternary/)项目的方法时，偶然发现了`这篇` (https://noelwelsh.com/posts/understanding-vm-dispatch/)关于不同虚拟机调度风格的文章。我之前听说过尾调用解释，不过我最初的灵感来源花了一些时间才重新找到。不过，这篇文章对 Scala 中几种不同的虚拟机调度风格做了很好的剖析。我决定在 Rust 中实现它们（包括几种与我的项目更相关的变体）作为有趣的实验，并对其进行基准测试以衡量它们的差异。我会介绍 2 个版本——一个旨在模拟 Noel 的 Scala 代码，另一个则旨在利用 Rust 的优势构建一个更复杂、更传统的寄存器机。
## 尾调用
尾调用解释是一种技术，它允许在编译时将某些递归转换为跳转，从而无需分配新的栈帧。这对于函数式语言（如 Scala）保持较小的栈空间极其有用，但大多数编译器都倾向于使用它。如果你想了解更多，我强烈推荐阅读上面 Noel 的精彩文章。在高优化级别下编译时，Rust 也会执行此优化，而不稳定的特性`explicit_tail_calls`允许我们直接告诉编译器执行该优化或报错。
## 栈机（Noel 的机器）
我们能轻松处理的最简单的机器是一个包含 5 条指令的栈机，在 Rust 中表示如下：
``
enum ByteCode {
Lit(f64),
Add,
Sub,
Mul,
Div
}
``
这与 Noel 的 Scala 代码基本相同。由于这是一个栈机，`Lit`（字面量）指令将值压入栈中；算术指令弹出操作数，并将结果值压回栈中。
## 调度
作为对照组，switch 调度是最合理的。我们只需创建一个字节码数组，在一个`match`语句中循环遍历它并执行即可。
``
注意：我决定使用一些奇怪的决策来与 Scala 保持一致。
包括使用 `static mut` 和 `unsafe`，而不是手动创建闭包，
尽管我在某种意义上也确实那么做了。我不赞成用这种方式编写 Rust。
``
### Switch 调度
``
const STACK_SIZE: usize = 32;
// 我们的栈
static mut STACK: &mut [f32] = &mut [0.0; STACK_SIZE];
// 要执行的指令列表
static mut INSTRS: &[Instr] = /* { [Lit(4.0), Lit(3.0)... etc] } */;
// 我们将栈指针和指令指针传递给 `dispatch`
pub fn dispatch(sp: usize, ip: usize) -> f32 {
unsafe {
if ip == INSTRS.len() {
STACK[sp - 1]
} else {
match INSTRS[ip] {
Instr::Lit(value) => {
STACK[sp] = value;
become dispatch(sp + 1, ip + 1)
},
Instr::Add => {
let a = STACK[sp - 2];
let b = STACK[sp - 1];
STACK[sp - 2] = a + b;
become dispatch(sp - 1, ip + 1)
},
Instr::Sub => {
let a = STACK[sp - 2];
let b = STACK[sp - 1];
STACK[sp - 2] = a - b;
become dispatch(sp - 1, ip + 1)
},
Instr::Mul => {
let a = STACK[sp - 2];
let b = STACK[sp - 1];
STACK[sp - 2] = a * b;
become dispatch(sp - 1, ip + 1)
},
Instr::Div => {
let a = STACK[sp - 2];
let b = STACK[sp - 1];
STACK[sp - 2] = a / b;
become dispatch(sp - 1, ip + 1)
},
}
}
}
}
``
这里我们可以看到整个逻辑——一个大型递归函数，每条指令都会调用自身。由于我们使用了`become` (https://github.com/rust-lang/rust/issues/112788)关键字，我们知道递归不会导致栈溢出。这是一个简单直观的策略！这里没有什么太复杂的。
### 子例程调度
接下来我们进行子例程线程化，用其替换 match 语句。我们不再使用枚举，而是必须将指令实现为一个结构体，通过实现`Fn()` (https://doc.rust-lang.org/std/ops/trait.Fn.html)trait 使其可被调用。这意味着我们可以调用动态的`&dyn Fn()`，而无需关心底层结构体是什么。
我们的字节码现在看起来像这样（为简洁起见省略了部分内容）：
``
// 现在，我们的指令是 `&dyn Fn()`，因此我们可以使用动态分发
// 来调用不同的指令，而无需知道它们是什么。
static mut INSTRS: &[&dyn Fn() -> ()] = /*[&Lit, &Add... etc]*/;
static mut SP: usize = 0;
const STACK_SIZE: usize = 32;
static mut STACK: &mut [f32] = &mut [0.0; STACK_SIZE];
struct Lit(f32);
struct Add;
struct Sub;
struct Mul;
struct Div;
impl Fn<()> for Lit {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
STACK[SP] = self.0;
SP += 1;
}
}
}
impl Fn<()> for Add {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a + b;
SP -= 1;
}
}
}
impl Fn<()> for Sub {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a - b;
SP -= 1;
}
}
}
impl Fn<()> for Mul {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a * b;
SP -= 1;
}
}
}
impl Fn<()> for Div {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a * b;
SP -= 1;
}
}
}
pub fn dispatch(ip: usize) -> f32 {
unsafe {
if ip == INSTRS.len() {
STACK[SP - 1]
} else {
INSTRS[ip]();
become dispatch(ip + 1)
}
}
}
``
当然，我可以移除全局变量，要么将它们作为字节码数据的一部分，要么将它们作为变量传递。一个相当简单的技巧是让每个函数传递并返回所有必要的值。这种技术同样受益于尾调用优化，因此我们不必担心函数传递的开销。此外，我们可以使用普通函数并增加一个稍微复杂的解码阶段，但对于*这部分*，我希望尽可能与 Scala 版本保持一致。
### 间接调度
接下来，Noel 讨论了间接线程化。这种技术保留了 match 语句，但我们不是直接返回并通过递归循环。相反，我们使用*间接递归*。这意味着操作调用 dispatch 函数，而不是返回后由函数自身调用自己。
理论上，这会少一次函数返回，并允许函数调用开销被尾调用优化消除。在 Rust 中，这看起来像这样。
``
pub enum ByteCode {
Lit(f32),
Add,
Sub,
Mul,
Div
}
static INSTRS: &[ByteCode] = ...;
static mut SP: usize = 0;
static mut IP: usize = 0;
const STACK_SIZE: usize = 32;
static mut STACK: &mut [f32] = &mut [0.0; STACK_SIZE];
pub fn dispatch(instr: ByteCode) -> f32 {
match instr {
ByteCode::Lit(val) => lit(val),
ByteCode::Add => add(),
ByteCode::Sub => sub(),
ByteCode::Mul => mul(),
ByteCode::Div => div(),
}
}
fn lit(val: f32) -> f32 {
unsafe {
STACK[SP] = val;
SP += 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
dispatch(INSTRS[IP])
}
}
}
fn add() -> f32 {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a + b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
dispatch(INSTRS[IP])
}
}
}
fn sub() -> f32 {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a - b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
dispatch(INSTRS[IP])
}
}
}
fn mul() -> f32 {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP * 2] = a - b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
dispatch(INSTRS[IP])
}
}
}
fn div() -> f32 {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP * 2] = a / b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
dispatch(INSTRS[IP])
}
}
}
``
这里我们还利用 return 返回最终值。到目前为止，我最喜欢这一个，部分原因是它避免了我在子例程线程化中使用的更复杂的虚分发。这主要是因为我以 Rust`Fn()`trait 并不真正适合的方式使用了它们，因为允许这样使用它们的特性仍然不稳定。
这引出了最后一个问题。如果我们组合这些技术会怎样？我们从操作内部进行调度，但使用一个`dyn Fn()`数组。这意味着几个好处：每条指令一次函数调用，并且没有 match 语句。虽然情况各不相同，但这在某些微架构的某些方面可能更友好，同时函数调用次数最少，为 1（这取决于你的虚拟机架构，但重要的是每个操作直接调用下一个操作）。
### 直接调度
这就引出了直接调度。我们暂时回到将对象作为字节码（for now），让每个操作调度下一个操作。结果在我的机器上成为了性能最佳的变体。它看起来大致像这样：
``
static mut INSTRS: &[&dyn Op] = ...;
static mut SP: usize = 0;
static mut IP: usize = 0;
const STACK_SIZE: usize = 32;
static mut STACK: &mut [f32] = &mut [0.0; STACK_SIZE];
pub trait Op: Fn() -> f32 {}
impl Op for Lit {}
impl Op for Sub {}
impl Op for Add {}
impl Op for Mul {}
impl Op for Div {}
struct Lit(f32);
struct Add;
struct Sub;
struct Mul;
struct Div;
impl Fn<()> for Lit {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
STACK[SP] = self.0;
SP += 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
INSTRS[IP]()
}
}
}
}
impl Fn<()> for Add {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a + b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
INSTRS[IP]()
}
}
}
}
impl Fn<()> for Sub {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a - b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
INSTRS[IP]()
}
}
}
}
impl Fn<()> for Mul {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a * b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
INSTRS[IP]()
}
}
}
}
impl Fn<()> for Div {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a * b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
INSTRS[IP]()
}
}
}
}
``
## 结果
这种技术完全没有独立的`dispatch`函数，这意味着要开始计算，你只需调用指令指针位置处的指令即可。所有这些实验在我的机器上得出了以下结果：
``
test bench::direct ... bench: 24.59 ns/iter (+/- 0.50)
test bench::indirect ... bench: 55.32 ns/iter (+/- 1.21)
test bench::subroutine ... bench: 79.93 ns/iter (+/- 1.18)
test bench::switch ... bench: 59.39 ns/iter (+/- 2.16)
``
直接调度是明显的赢家，这并不太令人惊讶，因为它充分利用了尾调用的能力，同时不像其他递归技术那样做那么多额外工作。间接调度似乎有大约 2 倍的开销，这意味着多一次函数调用的开销并不一定很小。不过我们在这里需要小心——这些数字非常小，我们应该警惕编译器所做的优化，尤其是（在这种情况下）它完全掌握了我们打算执行的指令信息。尽管如此，这些技术的数字似乎与我们预期的一致，而且它们之间的相互关系在现代硬件上似乎也反映了这一点。
## 进一步实验
虽然这些技术直接从 Scala 翻译成某种非正统的 Rust 代码非常酷，但它们并不是我的 ternary VM 应该采用的风格。首先，我的 VM 往往更像真实硬件，因为我的目标是模拟某种假想的理论三进制硬件，这意味着需要更复杂的解码步骤和寄存器。因此，我创建了一个极其有限的小型 16 位寄存器机，以便在更接近我最终用例的条件下进行测试。
该机器很简单：
``
pub struct Machine {
regs: [u16; 16],
instrs: [Instr; 256],
ip: usize,
}
pub enum Op {
Halt = 0b0000,
Add = 0b0001,
Sub = 0b0010,
Mul = 0b0011,
Div = 0b0100,
Bgt = 0b0101,
Bleq = 0b0110,
}
``
``
指令编码：
12 8 4 0
┌─────┬────┬────┬────┐
│ IMM │ R1 │ RD │ OP │
└─────┴────┴────┴────┘
``
这不是世界上最革命性的东西，但足以测试一个简单的寄存器机。
### Switch 调度
Switch 调度与预期差不多，只是包含一个更大的解码阶段。此外，我们将指令指针内化到机器中，避免了上一阶段不幸的`static mut`。我们也可以将指令指针作为递归参数内化到`run`函数中，但在这种情况下这不太可能产生影响（这是我目前在我的 ternary VM 中使用的方法，不过在我最终确定之前可能应该做更多测试）。
``
pub fn run(machine: &mut Machine) {
loop {
let instr = machine.instrs[machine.ip];
let rd = instr.rd() as usize;
let r1 = instr.r1() as usize;
let rdv = machine.regs[rd];
相似文章
C语言中的尾调用优化相对较新
LWN的一条评论讨论了C语言编译器中尾调用优化相对较新的实现，引用了历史上的局限性，并指出现代的GCC和Clang现已支持该优化，这对解释器实现有潜在好处。
来自未来的 RISC-V 解释器
Rust 编写的 RISC-V 解释器的更新，支持模块化、no_std、编译时执行，并严格符合规范，同时利用了众多 Rust nightly 版本的特性。
Rust类型系统中的Lisp
一个嵌入在Rust trait系统中的Lisp解释器，支持在编译时进行递归函数、闭包和延续传递风格。
突破 RISC-V 模拟的极限
这篇博客文章探讨了如何通过在非 RISC-V 机器上使用提前重编译器来加速 RISC-V 执行，该重编译器通过尾调用连接基本块，并利用 Clang 的 preserve_none 调用约定，作为 Axiom 的 OpenVM 项目的一部分。
Rust 函数重载：实验性呼吁
Rust 项目正在 nightly Rust 构建中实验函数重载，以通过新的 #[rustc_splat] 属性增强 FFI 绑定，特别是与 C++ 的互操作性，提供更人性化的调用语法。