Oxc

构建 JavaScript 编译器的性能追求 ​

原文发布于 https://rustmagazine.org/issue-3/javascript-compiler/

关于性能 ​

在编写 Rust 两年后，性能已成为我根深蒂固的准则——它归结为减少内存分配和减少 CPU 周期。

然而，如果对问题领域不了解或不知道潜在的解决方案，要实现最佳性能是很困难的。

在下面的章节中，我将带你了解我的性能和优化之旅。我偏好的学习方式是研究、尝试和试错的结合，因此以下章节将按此方式组织。

解析 ​

Oxc 是一个标准的编译器，包括抽象语法树（AST）、词法分析器和递归下降解析器。

抽象语法树（AST） ​

编译器的第一个架构设计是其 AST。

所有 JavaScript 工具都在 AST 层面工作，例如：

  • Linter（如 ESLint）检查 AST 中的错误
  • Formatter（如 prettier）将 AST 打印回 JavaScript 文本
  • Minifier（如 terser）转换 AST
  • Bundler 连接不同文件中 AST 之间的所有 import 和 export 语句

如果 AST 不够友好，构建这些工具将会很痛苦。

对于 JavaScript，最常用的 AST 规范是 estree。 我的第一个 AST 版本复制了 estree：

rust
pub struct Program {
    pub node: Node,
    pub body: Vec<Statement>,
}

pub enum Statement {
    VariableDeclarationStatement(VariableDeclaration),
}

pub struct VariableDeclaration {
    pub node: Node,
    pub declarations: Vec<VariableDeclarator>,
}

在 Rust 中，声明一棵树相对简单，因为涉及到使用结构体和枚举。

内存分配 ​

我在编写解析器时使用这个版本的 AST 工作了几个月。有一天我决定对其进行性能分析。分析器显示程序花费了大量时间调用 drop。

💡 AST 的节点通过 Box 或 Vec 在堆上分配，它们被单独分配，因此按顺序依次释放。

有没有解决方案可以缓解这个问题？

在编写解析器时，我研究了其他一些用 Rust 编写的 JavaScript 解析器，主要是 ratel 和 jsparagus。

这两个解析器都用生命周期注解声明它们的 AST，

rust
pub enum Statement<'ast> {
    Expression(ExpressionNode<'ast>),
}

并且它们都有一个名为 arena.rs 的配套文件。

我不理解它的作用，所以我忽略了它们，直到我开始阅读它们对内存竞技场的使用：bumpalo 和 toolshed。

总之，内存竞技场预先以块或页的形式分配内存，并在竞技场释放时一起释放。AST 在竞技场上分配，因此释放 AST 是一个快速操作。

另一个附带的好处是，AST 以特定顺序构造，树的遍历也遵循相同顺序，在访问过程中产生线性内存访问。这种访问模式将非常高效，因为所有附近的内存都会以页的形式读入 CPU 缓存，从而实现更快的访问时间。

不幸的是，对于 Rust 初学者来说，使用内存竞技场可能具有挑战性，因为所有数据结构和相关函数都需要通过生命周期注解进行参数化。我花了五次尝试才将 AST 分配到 bumpalo 中。

将 AST 改为内存竞技场带来了大约 20% 的性能提升。

枚举大小 ​

由于 AST 的递归性质，我们需要以一种避免"无间接递归"错误的方式定义类型：

error[E0072]: recursive types `Enum` and `Variant` have infinite size
 --> crates/oxc_linter/src/lib.rs:1:1
  |
1 | enum Enum {
  | ^^^^^^^^^
2 |     Variant(Variant),
  |             ------- recursive without indirection
3 | }
4 | struct Variant {
  | ^^^^^^^^^^^^^^
5 |     field: Enum,
  |            ---- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
  |
2 ~     Variant(Box<Variant>),
3 | }
4 | struct Variant {
5 ~     field: Box<Enum>,

有两种方法可以解决这个问题。要么在枚举变体中装箱枚举，要么在结构体字段中装箱。

我在 2017 年的 Rust 论坛上发现了同样的问题：有没有更好的方式来表示抽象语法树？

Aleksey (matklad) 告诉我们要装箱枚举变体以保持 Expression 枚举较小。但这是什么意思？

事实证明，Rust 枚举的内存布局取决于其所有变体的大小，其总字节大小取决于最大的变体。例如，以下枚举将占用 56 字节（1 字节用于标签，48 字节用于载荷，8 字节用于对齐）。

rust
enum Enum {
    A, // 0 字节载荷
    B(String), // 24 字节载荷
    C { first: String, last: String }, // 48 字节载荷
}

在典型的 JavaScript AST 中，Expression 枚举包含 45 个变体，Statement 枚举包含 20 个变体。如果枚举变体没有装箱，它们将占用超过 200 字节。这 200 字节需要到处传递，而且每次我们进行 matches!(expr, Expression::Variant(_)) 检查时都要访问，这对性能来说不是很缓存友好。

因此，为了使内存访问高效，最好装箱枚举变体。

perf-book 描述了如何查找大类型的额外信息。

我还复制了限制小枚举大小的测试。

rust
#[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
#[test]
fn no_bloat_enum_sizes() {
    use std::mem::size_of;
    use crate::ast::*;
    assert_eq!(size_of::<Statement>(), 16);
    assert_eq!(size_of::<Expression>(), 16);
    assert_eq!(size_of::<Declaration>(), 16);
}

装箱枚举变体带来了大约 10% 的加速。

Span ​

有时，我们可能不会意识到更小的内存占用是可能的，直到我们花额外的时间检查数据结构。

在这个例子中，所有 AST 节点的叶子都包含一个称为"span"的小数据结构，用于存储源文本的字节偏移量，由两个 usize 组成。

rust
pub struct Node {
    pub start: usize,
    pub end: usize,
}

有人指出我可以安全地将 usize 改为 u32 以减少峰值内存，因为超过 u32 的文件是 4GB。

改为 u32 在大文件上提升了多达 5% 的性能。

字符串和标识符 ​

在 AST 内部，人们可能会尝试使用对源文本的字符串引用来表示标识符名称和字符串字面量。

rust
pub struct StringLiteral<'a> {
    pub value: &'a str,
}

pub struct Identifier<'a> {
    pub name: &'a str,
}

但不幸的是，在 JavaScript 中，字符串和标识符可以有转义序列，即 '\251'、'\xA9' 和 '©' 对于版权符号是相同的。

这意味着我们必须计算转义值并分配一个新的 String。

字符串驻留 ​

当有大量堆分配的字符串时，可以使用一种称为字符串驻留的技术，通过只存储每个不同字符串值的一个副本来减少总内存。

string-cache 是 servo 团队发布的一个流行且广泛使用的库。最初，我在 AST 中使用 string-cache 库来处理标识符和字符串。解析器在单线程中的性能很快，但当我开始实现 linter 时，有多个解析器与 rayon 并行运行，CPU 利用率大约只有所有核心的 50%。

经过分析，一个名为 parking_lot::raw_mutex::RawMutex::lock_slow 的方法出现在执行时间的顶部。我对锁和多核编程了解不多，但全局锁从一开始就很奇怪，所以我决定移除 string-cache 库以实现完整的 CPU 利用率。

从 AST 中移除 string-cache 将并行解析的性能提高了大约 30%。

string-cache ​

半年后，在处理另一个性能关键项目时，string-cache 库再次出现。它在并行文本解析期间阻塞了所有线程。

我决定研究 string-cache 的作用，因为这次我在阅读 Mara Bos 的书 Rust Atomics and Locks 后做好了准备。

以下是锁周围的相关代码。请注意，这段代码是八年前 2015 年编写的。

rust
pub(crate) static DYNAMIC_SET: Lazy<Mutex<Set>> = Lazy::new(|| {
    Mutex::new({

// ... 在另一个地方
let ptr: std::ptr::NonNull<Entry> =
    DYNAMIC_SET.lock().insert(string_to_add, hash.g);

所以这很直接。每次插入字符串时它都会锁定数据结构 Set。由于这个例程在解析器中被频繁调用，其性能受到同步的负面影响。

现在让我们看看 Set 数据结构 看看它做了什么：

rust
pub(crate) fn insert(&mut self, string: Cow<str>, hash: u32) -> NonNull<Entry> {
    let bucket_index = (hash & BUCKET_MASK) as usize;
    {
        let mut ptr: Option<&mut Box<Entry>> = self.buckets[bucket_index].as_mut();

        while let Some(entry) = ptr.take() {
            if entry.hash == hash && *entry.string == *string {
                if entry.ref_count.fetch_add(1, SeqCst) > 0 {
                    return NonNull::from(&mut **entry);
                }
                entry.ref_count.fetch_sub(1, SeqCst);
                break;
            }
            ptr = entry.next_in_bucket.as_mut();
        }
    }
    debug_assert!(mem::align_of::<Entry>() >= ENTRY_ALIGNMENT);
    let string = string.into_owned();
    let mut entry = Box::new(Entry {
        next_in_bucket: self.buckets[bucket_index].take(),
        hash,
        ref_count: AtomicIsize::new(1),
        string: string.into_boxed_str(),
    });
    let ptr = NonNull::from(&mut *entry);
    self.buckets[bucket_index] = Some(entry);

    ptr
}

看起来它正在寻找一个桶来存储字符串，如果字符串不在桶中就插入它。

💡 这是线性探测吗？如果是线性探测，那么这个 Set 就是一个没有明说的 HashMap。 💡 如果这是一个 HashMap，那么 Mutex<HashMap> 就是一个并发哈希表。

虽然当我们知道要寻找什么时解决方案似乎很明显，但我花了一个月才弄清楚这一点，因为我没有意识到这个问题。当很明显这只是一个并发哈希表时，将 Mutex 应用到桶上而不是整个哈希表是一个清晰且合乎逻辑的解决方案。在实现这个更改的一小时内，我提交了一个拉取请求，并对结果感到满意 😃。

https://github.com/servo/string-cache/pull/268

值得一提的是，字符串驻留是 Rust 社区内的一个战场。例如在这篇博文中展示的，有单线程库如 string-interner、lasso、lalrpop-intern、intaglio 和 strena。

由于我们正在并行解析文件，一个选择是使用多线程字符串驻留库，如 ustr。然而，在对 ustr 和增强版的 string-cache 进行性能分析后，很明显性能仍然低于预期，与我下面要解释的方法相比。

对性能不佳的一些初步猜测是：

  • 哈希——驻留器需要对字符串进行哈希以进行去重
  • 间接访问——我们需要从"远处"的堆读取字符串值，这对缓存不友好

字符串内联 ​

所以我们回到了必须分配大量字符串的初始问题。幸运的是，如果我们看看我们正在处理什么样的数据，这个问题有一个部分解决方案：短的 JavaScript 变量名和一些短字符串。有一种称为字符串内联的技术，我们将字符串的所有字节存储在栈上。

本质上，我们想要以下枚举来存储我们的字符串。

rust
enum Str {
    Static(&'static str),
    Inline(InlineReprensation),
    Heap(String),
}

为了最小化枚举的大小，InlineRepresentation 应该与 String 大小相同。

rust
#[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
#[test]
fn test_size() {
    use std::mem::size_of;
    assert_eq!(size_of::<String>(), size_of::<InlineReprensation>());
}

Rust 社区中有许多 crate 旨在优化内存使用。这是社区内的另一个战场。最流行的是

每个 crate 都有独特的特性和实现内存优化的方法，在选择使用哪个时会有各种权衡和考虑。例如 smol_str 和 flexstr 的克隆是 O(1)。flexstr 可以存储 22 字节，smol_str 和 smartstring 可以存储 23 字节，compact_str 在 64 位系统上可以存储 24 字节。

https://fasterthanli.me 对这个主题有深入探讨。

将 String 改为 compact_str::CompactStr 大幅减少了内存分配。

词法分析器 ​

Token ​

词法分析器（也称为分词器）的工作是将源文本转换为称为 token 的结构化数据。

rust
pub struct Token {
    pub kind: Kind,
}

为了便于使用，token 类型在 Rust 中通常定义为枚举。枚举的变体保存每个 token 的相应数据。

rust
pub enum Kind {
    // 关键字
    For,
    While,
    ...
    // 字面量
    String(String),
    Num(f64),
    ...
}

这个枚举目前使用 32 字节，词法分析器经常需要构造数百万个这种 token Kind。每次构造 Kind::For 或 Kind::While 时，它必须在栈上分配 32 字节的内存。

一个聪明的改进方法是将枚举变体拆分，将 Kind 保持为单字节，并将值移到另一个枚举中，

rust
pub struct Token<'a> {
    pub kind: Kind,
    pub value: TokenValue
}

pub enum TokenValue {
    None,
    String(String),
    Num(f64),
}

由于我们控制所有解析代码，我们需要保证安全，始终将相应的 token 值与其类型对应。

虽然 32 字节的 TokenValue 已经很小了，但它仍可能对性能产生负面影响，因为它频繁分配。

让我们看看 String 类型，看看我们能发现什么，通过在代码编辑器中使用"转到定义"，我们将经过 String -> Vec -> RawVec：

rust
pub struct String {
    vec: Vec<u8>,
}

pub struct Vec {
    buf: RawVec<T, A>,
    len: usize,
}

pub struct RawVec {
    ptr: Unique<T>,
    cap: usize,
    alloc: A,
}

如广告所说，String 只是 u8 的 Vec，而 Vec 有长度和容量字段。由于我们永远不会修改这个字符串，在内存使用方面的优化是去掉容量字段，改用字符串切片（&str）。

rust
pub enum TokenValue<'a> {
    None,
    String(&'a str),
    Num(f64),
}

TokenValue 变成 24 字节。

虽然使用字符串切片而不是 TokenValue 中的 String 会减少内存使用，但它确实有添加生命周期注解的缺点。这可能导致借用检查器的问题，并且生命周期注解会传播到代码库的其余部分，使我们的代码在一定程度上难以管理。我 8 个月前输掉了借用检查游戏，但最终赢了。

在合理的情况下，我们总是可以使用不可变数据的拥有版本而不是引用。例如用 Box<str> 替代 String，用 Box<[u8]> 替代 Vec<u8>。

总之，我们总是可以想出技巧来保持数据结构小，这有时会给我们带来性能提升。

Cow ​

我在研究 jsparagus 的代码时第一次遇到术语 Cow，它有一个称为 AutoCow 的基础设施。

我模糊地理解代码在做什么。当 JavaScript 字符串被分词时，当遇到转义序列时它会分配一个新字符串，否则返回原始字符串切片：

rust
fn finish(&mut self, lexer: &Lexer<'alloc>) -> &'alloc str {
    match self.value.take() {
        Some(arena_string) => arena_string.into_bump_str(),
        None => &self.start[..self.start.len() - lexer.chars.as_str().len()],
    }
}

这很聪明，因为 99.9% 的时间它不会分配新字符串，因为转义字符串很少。

但术语 Cow 或"写时克隆智能指针"对我来说从来没有意义。

Cow 类型是一个提供写时克隆功能的智能指针：它可以封装并提供对借用数据的不可变访问，并在需要修改或所有权时懒克隆数据。该类型设计为通过 Borrow trait 与一般借用数据一起工作。

如果你是 Rust 新手（像我一样），那么这个描述就没有帮助（我仍然不理解它在说什么）。

有人指出clone-on-write 只是这个数据结构的一个用例。更好的名称应该是 RefOrOwned，因为它是一个包含拥有数据或引用的类型。

SIMD ​

当我浏览旧的 Rust 博客时，宣布 Portable SIMD 项目组引起了我的注意。我一直想玩 SIMD，但从来没有机会。经过一些研究，我发现了一个可能应用于解析器的用例：Daniel Lemire 的你能多快地从字符串中删除空格？。原来这以前就做过，在一个叫 RapidJSON 的 JSON 解析器中，它使用 SIMD 删除空白。

最终在 portable-SIMD 和 RapidJSON 代码的帮助下，我不仅设法跳过空白，还设法跳过多行注释。

这两个更改将性能提高了几个百分点。

关键字匹配 ​

在性能分析的顶部，有一个热代码路径占总执行时间的约 1 - 2%。

它尝试将字符串匹配到 JavaScript 关键字：

rust
fn match_keyword(s: &str) -> Self {
    match s {
        "as" => As,
        "do" => Do,
        "if" => If,
        ...
        "constructor" => Constructor,
        _ => Ident,
    }
}

添加 TypeScript 后，有 84 个字符串需要我们匹配。经过一些研究，我发现了 V8 的一篇博客极快解析，第 1 部分：优化扫描器，它详细描述了其关键字匹配代码。

由于关键字列表是静态的，我们可以计算一个完美哈希函数，为每个标识符最多给出一个候选关键字。V8 使用 gperf 计算这个函数。结果从长度和前两个标识符字符计算哈希，找到单个候选关键字。我们只在该关键字的长度与输入标识符长度匹配时才将标识符与关键字比较。

所以快速哈希加上整数比较应该比 84 次字符串比较更快。但我们尝试了又一次都没有成功。

事实证明，LLVM 已经优化了我们的代码。通过在 rustc 上使用 --emit=llvm-ir，我们找到相关代码：

switch i64 %s.1, label %bb6 [
  i64 2, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit.i"
  i64 3, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit280.i"
  ...
], !dbg !191362

%s 是字符串，%s.1 是其长度……它在字符串长度上分支！编译器比我们要聪明 😃。

（是的，我们对此太认真了，以至于开始看 LLVM IR 和汇编代码。）

后来，@strager 发布了一个非常有教育意义的 YouTube 视频比 Rust 和 C++ 更快：完美的哈希表，讨论这个话题。视频教会了我们一种系统性的方法来推理微调性能问题。

最后，我们得出结论，简单的关键字匹配对我们来说已经足够，因为它只占性能的约 1 - 2%，在花了几天时间后不值得再努力——Rust 没有我们构建这个完美哈希表所需的所有组件。

Linter ​

Linter 是一个分析源代码问题的程序。

最简单的 linter 访问每个 AST 节点并检查规则。可以使用访问者模式：

rust
pub trait Visit<'a>: Sized {
    // ... 很多访问函数

    fn visit_debugger_statement(&mut self, stmt: &'a DebuggerStatement) {
        // 报告错误
    }
}

父指针树 ​

通过使用访问者很容易沿 AST 向下遍历，但如果我们要向上遍历树来收集一些信息怎么办？

这个问题在 Rust 中特别难以解决，因为不可能在 AST 的节点上添加指针。

让我们暂时忘记 AST，专注于具有节点有指向其父节点指针属性的通用树。要构建通用树，每个树节点需要是相同类型 Node，我们可以通过使用 Rc 引用它们的父节点：

rust
struct Node {
    parent: Option<Rc<Node>>,
}

如果需要修改，使用这种模式很繁琐，而且性能不佳，因为节点必须在不同时间释放。

更高效的解决方案是使用 Vec 作为其后备存储并使用索引作为指针。

rust
struct Tree {
    nodes: Vec<Node>
}

struct Node {
    parent: Option<usize> // 索引到 `nodes`
}

indextree 是这个任务的一个好库。

回到我们的 AST，我们可以通过让节点指向一个包装每种 AST 节点的枚举来构建 indextree。我们称之为非类型化 AST。

rust
struct Node<'a> {
    kind: AstKind<'a>
}

enum AstKind<'a> {
    BlockStatement(&'a BlockStatement<'a>),
    // ...
    ArrayExpression(&'a ArrayExpression<'a>),
    // ...
    Class(&'a Class<'a>),
    // ...
}

最后缺少的一块是在访问者模式内有构建这棵树的回调。

rust
pub trait Visit<'a> {
    fn enter_node(&mut self, _kind: AstKind<'a>) {}
    fn leave_node(&mut self, _kind: AstKind<'a>) {}

    fn visit_block_statement(&mut self, stmt: &'a BlockStatement<'a>) {
        let kind = AstKind::BlockStatement(stmt);
        self.enter_node(kind);
        self.visit_statements(&stmt.body);
        self.leave_node(kind);
    }
}

impl<'a> Visit<'a> for TreeBuilder<'a> {
    fn enter_node(&mut self, kind: AstKind<'a>) {
        self.push_ast_node(kind);
    }

    fn leave_node(&mut self, kind: AstKind<'a>) {
        self.pop_ast_node();
    }
}

最终的数据结构变成 indextree::Arena<Node<'a>>，其中每个 Node 有一个指向 AstKind<'a> 的指针。可以调用 indextree::Node::parent 来获取任何节点的父节点。

制作这个父指针树的好处是，它可以方便地访问 AST 节点而不需要实现任何访问者。Linter 变成对 indextree 中所有节点的简单循环：

rust
for node in nodes {
    match node.get().kind {
        AstKind::DebuggerStatement(stmt) => {
        // 报告错误
        }
        _ => {}
    }
}

完整示例在这里提供。

乍一看，这个过程可能显得缓慢和低效。然而，通过内存竞技场访问类型化 AST 并将指针推入 indextree 是高效的线性内存访问模式。当前的基准测试表明这种方法比 ESLint 快 84 倍，所以对我们的目的来说肯定足够快。

并行处理文件 ​

Linter 使用 ignore crate 进行目录遍历，它支持 .gitignore 并添加额外的忽略文件如 .eslintignore。

这个 crate 的一个小问题是它没有并行接口，ignore::Walk::new(".") 没有 par_iter。

相反，需要使用原语

rust
let walk = Walk::new(&self.options);
rayon::spawn(move || {
    walk.iter().for_each(|path| {
        tx_path.send(path).unwrap();
    });
});

let linter = Arc::clone(&self.linter);
rayon::spawn(move || {
    while let Ok(path) = rx_path.recv() {
        let tx_error = tx_error.clone();
        let linter = Arc::clone(&linter);
        rayon::spawn(move || {
            if let Some(diagnostics) = Self::lint_path(&linter, &path) {
                tx_error.send(diagnostics).unwrap();
            }
            drop(tx_error);
        });
    }
});

这解锁了一个有用的功能，我们可以在单个线程中打印所有诊断，这引出了本文的最后一个话题。

打印很慢 ​

打印诊断很快，但我在这个项目上工作了这么长时间，每次在大型 monorepo 上运行 linter 时打印数千条诊断消息感觉就像永恒。所以我开始搜索 Rust GitHub issues 并最终找到了相关的：

总之，println! 调用每次遇到换行符都会锁定 stdout，这称为行缓冲。要使打印更快，我们需要选择块缓冲，这在这里文档化。

rust
use std::io::{self, Write};

let stdout = io::stdout(); // 获取全局 stdout 实体
let mut handle = io::BufWriter::new(stdout); // 可选：将该句柄包装在缓冲区中
writeln!(handle, "foo: {}", 42); // 如果你关心错误，在这里添加 `?`

或者获取 stdout 上的锁。

rust
let stdout = io::stdout(); // 获取全局 stdout 实体
let mut handle = stdout.lock(); // 获取其上的锁
writeln!(handle, "foo: {}", 42); // 如果你关心错误，在这里添加 `?`

© 2026 VoidZero Inc. and Oxc contributors.