抽象语法树（AST）的生命周期与内存管理实践

本文深入探讨抽象语法树（AST）在编译器中的核心作用，对比不同编程语言（C++、Rust、Java/C#）中AST的内存管理策略，包括共享指针、唯一指针和变体类型的实现方式，并分析性能优化与内存布局的权衡实践。

抽象语法树的生命与时代

你已抵达计算机编程的涅槃境界。你的旅程带你走过许多路径，包括相信上帝用LISP编写了宇宙，但现在你心中真理昭然：所有问题都可以通过再写一个编译器来解决。

确实如此。即使我们即将迎来的人工智能霸主也不过是编译器，正如传说预言。你为革命性DeFi平台编写的智能合约？它终将在某个时刻经过编译器处理。

既然我们已经确定每个程序至少应包含一个编译器（如果还没有的话），让我们谈谈如何编写编译器。事实证明，这是个相当庞大的话题，我不太可能在这篇博客文章的边距中容纳对这个主题的全面论述。相反，我将专注于抽象语法树（AST）的主题。

过去，我曾致力于一个将LLVM位码转换为Clang AST的反编译器，这使我对AST形成了自己的见解。这些是学校里不会教你的东西，比如：AST的API应该是什么样子？它应该如何布局在内存中？从零开始设计组件时，我们必须考虑超越其单纯功能性的方面——我想你可以称这些方面为"语用学"。让我们探讨其中一些方面，这样如果你将来需要处理AST，就可以跳过更令人困惑的部分，直接解决更关键的问题！

什么是AST？

就其本身而言，AST并不是编译器中非常有趣的部分。它们主要是将我们作为输入接收的可怕字符流转换为更易于后续编译器操作的格式。然而，AST的设计方式在处理编译器时会产生重要影响。让我们探究一下如何实现。

管理不可管理之物

如果你在使用像C#或Java这样的托管语言，这些语言带有垃圾收集器和非常面向对象的类型系统，你的AST节点很可能看起来像这样：

1
2
3
4
5
6
7
8

class Expr {}
class IntConstant : Expr {
    int value;
}
class BinExpr : Expr {
    public Expr lhs;
    public Expr rhs;
}

这样很好——它能很好地达到目的，模型也很清晰：由于所有内存都由运行时管理，节点的所有权并不那么重要。最终，这些节点不会去任何地方，直到所有人都使用完毕并且GC确定它们不再可达。

（顺便说一句，我将在整篇文章中做这类示例；它们不意味着可编译，只是为了提供我正在讨论的内容的一般概念。）

然而，我在处理编译器时通常不使用C#或Java。我是个C++守旧派，意味着我喜欢随时保持我的"footguns"上膛待发：因为没有垃圾收集器来清理我留下的烂摊子，我需要深入思考谁拥有每一个节点。

让我们尝试模仿托管情况下的做法。

天真方法 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

struct Expr {
    virtual ~Expr();
};
struct IntConstant : Expr {
    int value;
};
struct BinExpr : Expr {
    std::shared_ptr<Expr> lhs;
    std::shared_ptr<Expr> rhs;
};

C++中的共享指针使用引用计数（有人可能认为这是一种自动垃圾收集的形式），这意味着最终结果类似于我们在Java和C#中的情况：每个节点保证至少保持有效，直到持有对其引用的最后一个对象存活。

前一句中的"至少"是关键：如果这是一个抽象语法图而不是抽象语法树，我们会很快发现自己处于节点被困在脱离物质现实的生死边缘的情况，一系列节点相互指向形成一个循环，永远等待其他节点死亡，然后才能找到永恒的安息。

再次强调，这纯粹是学术上的可能性，因为树按定义是无环的，但仍然需要记住这一点。

我不太了解Rust，但我的理解是，大致相当于上述布局的代码会这样写：

1
2
3
4

enum Expr {
    IntConstant(i32),
    BinExpr(Arc<Expr>, Arc<Expr>)
}

使用这种表示法时，你的编译器通常会持有一个对根节点的引用，这导致整个节点金字塔保持站立。一旦该引用消失，其余节点也会随之消失。

不幸的是，由于使用原子引用计数器，每个指针都会引入额外的计算和内存消耗。从技术上讲，在Rust示例中可以通过使用Rc而不是Arc来避免"原子"部分，但在C++中没有等效物，我的示例也不会很好地工作。根据我的经验，完全摆脱每个节点持有引用计数的仪式是相当容易的，而是决定采用更有纪律的所有权方法。

“反向金字塔"方法 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

struct Expr {
    virtual ~Expr();
};
struct IntConstant : Expr {
    int value;
};
struct BinExpr : Expr {
    std::unique_ptr<Expr> lhs;
    std::unique_ptr<Expr> rhs;
};

使用唯一指针使我们无需跟踪何时释放内存，同时不增加引用计数的开销。虽然多个节点不可能拥有对同一节点的拥有引用，但仍然可以通过解引用唯一指针并存储引用来表达循环数据结构。这（非常）粗略地等同于在共享指针中使用std::weak_ptr。

就像在天真方法中一样，销毁AST的根节点将导致所有其他节点随之销毁。不同之处在于，在这种情况下我们保证这会发生，因为每个子节点都由其父节点拥有，并且不可能有其他拥有引用。

我相信这种表示法大致相当于这个Rust片段：

1
2
3
4

enum Expr {
    IntConstant(i32),
    BinExpr(Box<Expr>, Box<Expr>)
}

题外话：改进API

我们非常接近我称之为理想表示的东西，但我喜欢做的一件事是使我的数据结构尽可能不可变。

如果我要在实际代码库中实现BinExpr，它可能看起来像这样：

1
2
3
4
5
6
7
8
9

class BinExpr : Expr {
    std::unique_ptr<Expr> lhs, rhs;
public:
    BinExpr(std::unique_ptr<Expr> lhs, std::unique_ptr<Expr> rhs)
        : lhs(std::move(lhs))
        , rhs(std::move(rhs)) {}   
    const Expr& get_lhs() const { return *lhs; }
    const Expr& get_rhs() const { return *rhs; }
};

这向我表明了几件事：

  • 节点是不可变的
  • 节点不能为null
  • 节点不能移动；它们的所有者是固定的

移除安全措施

下一步是看看如何通过移除我们迄今为止使用的一些安全措施来改进事情，而不会完全搬起石头砸自己的脚。我不会提供如何在Rust中实现这些方法的片段，因为上次我在公司的Slack频道中询问如何做到这一点时，我收到的回复是"不要”、“为什么要这样做？“和"有人请叫保安”。这不应该令人惊讶，因为AST基本上是一个带有额外步骤的链表，而Rust讨厌链表。

到目前为止，总体思路是节点拥有其他节点。这使得安全处理AST变得相当容易，因为节点是自包含的。

如果我们决定将节点的所有权转移给其他实体呢？毕竟，拥有某种ASTContext对象是相当合理的，我们可以假设它处理节点的生命周期，类似于Clang中发生的情况。

让我们先改变Expr节点的外观：

1
2
3
4

struct BinExpr : Expr {
    const Expr& lhs;
    const Expr& rhs;
};

现在我们为所有节点创建一个存储：

1
2
3
4

vector<unique_ptr<Expr>> node_storage;
auto &lhs = node_storage.emplace_back(make_unique<IntConstant>(...));
auto &rhs = node_storage.emplace_back(make_unique<IntConstant>(...));
auto &binexp = node_storage.emplace_back(make_unique<BinExpr>(*lhs, *rhs));

很好！node_storage现在是所有节点的所有者，我们可以迭代它们而无需进行树遍历。事实上，去看看关于Carbon编译器设计的这个演讲，大约37分钟处：如果你保持创建节点的模式可预测，最终会得到一个已经按后序遍历顺序排序的存储容器！

主题变奏

现在让我们从Rust的书中借用一个技巧：我迄今为止一直在使用的Expr类是通过继承实现多态性的老派案例。虽然我确实相信继承有其地位，并且在许多情况下应该是首选解决方案，但我确实认为AST是区分联合（discriminated unions）是正确选择的地方之一。

Rust将区分联合称为enum，而C++17称它们为std::variant。虽然实质相同，但人体工程学不同：Rust在语法中对它们有一流支持，而C++让用户进行模板元编程技巧才能使用它们，即使他们不一定意识到这一点。

我对使用variant而不是继承最感兴趣的一个特性是，它将我们的AST对象变成"值类型”，允许我们直接存储Expr对象，而不必通过引用或指针进行间接操作。这一点稍后会很重要。

这种模型解锁的另一个特性是，我们免费获得了访问者模式的实现，并且可以弄清楚某个值持有哪种节点，而不必发明自己的动态类型转换系统。看看你，LLVM。还有Clang。还有MLIR。

脱离常规

让我们回顾一下我之前做的一个例子：

1
2
3
4

vector<unique_ptr<Expr>> node_storage;
auto &lhs = node_storage.emplace_back(make_unique<IntConstant>(...));
auto &rhs = node_storage.emplace_back(make_unique<IntConstant>(...));
auto &binexp = node_storage.emplace_back(make_unique<BinExpr>(*lhs, *rhs));

有一件事让我困扰：双重间接和非连续内存分配。想想这种存储机制的内存布局是什么样的：向量将有一块连续的内存块用于存储指向所有节点的指针，然后每个指针将有一个与节点大小相关的内存块，如前所述，每种节点的大小各不相同。

这意味着我们的节点，即使顺序分配，也有可能最终分散在各处。他们说早期优化是万恶之源，但为了耗尽我袖中的所有技巧，我将继续展示一种避免这种情况的方法。

让我们开始做我之前说过要做的事情，为节点使用variant：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

struct IntConstant;
struct BinExpr;
using Expr = std::variant<IntConstant, BinExpr>;

struct IntConstant {
    int value;
};
struct BinExpr {
    Expr &lhs;
    Expr &rhs;
};

现在每个节点都有相同的大小，我们终于可以将它们连续存储在内存中：

1
2
3
4
5

std::vector<Expr> node_storage;
node_storage.reserve(max_num_nodes);
auto &lhs = node_storage.emplace_back(IntConstant{3});
auto &rhs = node_storage.emplace_back(IntConstant{4});
auto &binexp = node_storage.emplace_back(BinExpr{lhs, rhs});

你看到那个node_storage.reserve调用了吗？那不是优化——这是这个机制的绝对承重部分。

我想明确表示，这里发生的事情是C++招致仇恨的那种事情。这是一把众所周知的手枪，如果你选择使用它，它将绑在你的臀部指向你的脚，完全上膛，准备在你任何时候忘记它存在时炸掉你的腿。

我们在这种情况下使用reserve的原因是，我们希望确保我们可能用于存储节点的所有内存都是预先分配的，这样当我们使用emplace_back将节点放入其中时，我们保证该内存块不会被重新分配和更改地址。（如果发生这种情况，任何包含对其他节点引用的节点最终将指向垃圾，恶魔将从你的鼻子中飞出来。）

使用vector和reserve当然不是唯一的方法：如果你要使用的最大节点数在编译时已知，使用std::array也是有效的。

啊，是的，max_num_nodes。你如何计算这将是多少？这个问题没有单一的好答案，但你可以找到合适的启发式方法。例如，假设你正在解析C：我能想到的最小语句可能看起来像a;，或者更极端地说，只是a。我们可以推断，如果我们想极其安全，我们可以分配存储空间，节点数量等于我们正在解析的源代码中的字符数。考虑到大多数程序不会接近这种病态行为水平，可以预期大部分内存将被浪费。不幸的是，我们不能通过简单的shrink_to_fit调用来轻松回收浪费的内存，因为这可能导致重新分配。

你可以在那种情况下使用的技术，或者在你绝对无法避免分配额外内存的情况下，实际上是进行AST的深度克隆，访问每个节点并在新容器中精心创建新的对应物。

当这样存储AST节点时，要记住的一件事是，每个节点的大小现在将等于最大可表示节点的大小。我认为这并不那么重要，因为无论如何你应该尝试保持所有节点尽可能小，但仍然值得思考。

当然，可能你实际上不需要从AST中榨取最后一滴性能和内存效率，你可能愿意用其中一些来换取一些易用性。我可以想到三种实现这一目标的方法：

  1. 使用std::list
  2. 使用std::deque
  3. 使用索引而不是原始指针

让我们逐一探讨这些选项。

使用std::list而不是std::vector

不要。说得够多了。

好吧，好吧。我会详细说明。

在RAM的"随机访问"部分还不是谎言且内存访问模式无关紧要的时代，链表是好的。使用链表存储节点只是取消了我们为优化布局所做的所有努力。

使用std::deque而不是std::vector

这种方法已经更好了！由于我们主要只是将节点附加到节点存储容器的末尾，并且由于双端队列保证这样做是可能的而不会使任何现有内容的地址失效，这看起来是一个很好的折衷方案。

不幸的是，内存布局不再完全连续，但你可能不在乎这一点。不过，如果你使用微软的STL，你前面还有更大的问题。

使用索引而不是原始指针

这个想法是，你不是存储子节点的指针，而是存储该节点在向量内的索引。这又在画面中添加了一层间接性，你现在还必须弄清楚这个索引指的是哪个向量？你在每个节点中存储对向量的引用吗？这有点浪费。你全局存储它吗？如果你问我，这有点令人不快。

离别思考

我已经写了很多，但几乎没有触及设计者在编写编译器时必须做出的决策的表面。我谈到了如何在内存中存储AST，但没有说你想在AST中存储什么。

在这个令人振奋的概述中， overarching主题是编译器有很多超越解析的内容，构建编译器所需的所有抽象想法都需要在某个时候具体化，而你如何做到这一点的细节很重要。我还觉得有义务提到在玩这种游戏时应该记住的两条格言：过早优化是万恶之源，并且始终分析你的代码——很可能你的代码库包含更容易摘取的果实，你可以先摘取这些果实，然后再决定微调AST存储。

有趣的是，本文中展示的大多数技术在使用托管语言时都不容易访问。这是否意味着所有这些并不真正重要，或者用那些语言编写的编译器（我想到的是，例如，Roslyn）留下了性能？如果是这样，那种性能的重要性是什么？

最后，我希望这篇文章能开始关于编译器和类似编译器工具内部的讨论：这些通常高度复杂的软件表面下隐藏着什么？很容易找到关于编译一般思想的材料——标记化、解析、寄存器分配——但关于人们在编写需要以快速和内存高效的方式处理大型代码库的程序时提出的巧妙想法却较少。如果有人有战争故事要分享，我想听听！

如果你喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News

comments powered by Disqus
© 2020 - 2025 qife
使用 Hugo 构建
主题 Stack 由 Jimmy 设计
本站总访问量次 本站访客数人次