Writing a Fast Compiler
Writing a Fast Compiler
Writing a Fast Compiler 编写快速编译器
2024-02-04 I’m going to describe the various tricks I used to write fast compilers for my programming languages. By fast compilation, I mean compiling at least 500.000 lines of code per second (excluding blank lines and comments) on a single CPU core. 2024-02-04 我将介绍我为自己的编程语言编写快速编译器时所使用的各种技巧。所谓的“快速编译”，是指在单核 CPU 上每秒至少能编译 50 万行代码（不包括空行和注释）。
Does it Matter? 这重要吗？
You may argue that compilation time is not important. After all, once released, who cares that a program took hours to build; as users, we only want it to work and to work fast. It’s like complaining that the last Pixar movie took days for the final rendering. However it can severely affect the development cycle and make developers angry. It’s 2024 and I can see that the most common complaint for Rust is still its compilation time. The speed also affects the design of the compiler: when my biggest program is less than 100K SLOC and I can compile 500K SLOC per second I don’t really have to worry about separate compilation since a complete build takes less than 200ms. And this is good since separate compilation can be tricky with genericity. 你可能会说编译时间并不重要。毕竟，程序一旦发布，谁会在乎它花了几个小时构建呢？作为用户，我们只希望它能运行且运行得快。这就像抱怨皮克斯的最新电影花了几天时间进行最终渲染一样。然而，编译时间会严重影响开发周期并让开发者感到恼火。现在是 2024 年，我发现人们对 Rust 最常见的抱怨仍然是它的编译时间。编译速度也会影响编译器的设计：当我最大的程序不到 10 万行代码（SLOC）且我每秒能编译 50 万行时，我真的不需要担心增量编译（separate compilation），因为完整构建只需不到 200 毫秒。这很好，因为在涉及泛型时，增量编译可能会很棘手。
Designing a Language for Fast Compilation 为快速编译而设计语言
If you’re writing a compiler for an existing language, e.g. C++, you have no control here, you’ll have to deal with an LL(k) grammar, a preprocessor and a terrible module system. Conversely, if you’re writing a compiler for your own programming language, careful design choices can help a lot. I’ve always used a context free grammar that can be easily parsed with a simple recursive descent parser. If a syntax is easy to parse by the computer it will be also easy to parse by a human. A simple syntax will also make the development of independent tools easier (static analyzer, formating tools, refactoring, syntax highlighting, …). 如果你是在为现有的语言（例如 C++）编写编译器，你对此无能为力，你必须处理 LL(k) 文法、预处理器和糟糕的模块系统。相反，如果你是在为自己的编程语言编写编译器，仔细的设计选择会大有裨益。我一直使用上下文无关文法，这种文法可以通过简单的递归下降解析器轻松解析。如果一种语法易于计算机解析，那么它对人类来说也易于理解。简单的语法也会使独立工具（静态分析器、格式化工具、重构工具、语法高亮等）的开发变得更容易。
General Rules 通用规则
Minimizing Code and Memory Access 最小化代码和内存访问
Less code to execute and less memory access usually means faster execution. While modern architectures don’t make this principle strictly true, it is still a good rule to follow. I avoid copying data as much as possible. Many languages use zero-terminated strings. I prefer to use a pair of (start_pointer, size) or (start_pointer, end_pointer) instead: it allows for instance to refer to any sub-string directly from the input buffer without having to do a copy. 更少的执行代码和更少的内存访问通常意味着更快的执行速度。虽然现代架构并不完全遵循这一原则，但这仍然是一个值得遵循的好规则。我尽可能避免复制数据。许多语言使用以零结尾的字符串。我更喜欢使用一对 (start_pointer, size) 或 (start_pointer, end_pointer) 来代替：例如，这允许直接从输入缓冲区引用任何子字符串，而无需进行复制。
Reducing Memory Usage 减少内存使用
The less memory I use, the more it will fit in cache. Ordering variables in structs carefully can significantly reduce the size of these structs, especially in 64 bits because of alignment constraints. Combining multiple flags in an integer saves memory but it also allows to perform multiple tests at once just by using a mask. C bitfields are useful here. Using bytes or bitfields for enums. 我使用的内存越少，它就越能装入缓存。仔细排列结构体中的变量可以显著减小结构体的大小，特别是在 64 位架构下，因为存在对齐约束。将多个标志位合并到一个整数中不仅节省内存，还允许仅通过掩码一次性执行多个测试。C 语言的位域在这里很有用。对于枚举，可以使用字节或位域。
Optimizing the Common Path 优化常规路径
A lot of work in the compiler is to check for errors but a program has usually no error or very few ones. Therefore the code must be optimized considering that errors are exceptionals. If an error requires two conditions to be met, I evaluate the fastest one first so the second one will never be evaluated. I don’t compute something needed only for an error reporting until an actual error is detected. 编译器中很大一部分工作是检查错误，但程序通常没有错误或只有极少数错误。因此，代码必须在假设错误是异常情况的前提下进行优化。如果一个错误需要满足两个条件，我会先评估计算速度最快的一个，这样第二个条件就永远不会被评估。在检测到实际错误之前，我不会计算仅用于错误报告所需的内容。
Memory Management: Using Memory Regions 内存管理：使用内存区域
A memory region is a contiguous block of memory where parts can be allocated but not de-allocated (the entire region must be de-allocated). The allocation consists just in advancing a pointer, and eventually creating a new region when the region is full. It makes allocations extremely fast. The de-allocation is also extremely fast since all objects of a region are freed at once. This kind of memory management fits very well with a compiler: a single region can be used for a compilation unit. In practice I use 3 regions: one to store the AST, one to store the program objects and one for the code generation so I can get rid of the AST during code generation. However when compiling functions, there are lot of temporary objects created, mainly dictionary of names for each lexical scope. To handle this I create pools of regions: instead of creating and destroying regions I pick one from a pool and put it back to the pool when finished. Resizable arrays and open addressing hashtables are not suitable data structures for memory regions since they need a lot of de-allocations and re-allocations. To store lists of elements, when possible I count the elements first and then I allocate a fixed size array, when it’s not possible I just use a link-list. To handle hash tables which are heavily used for names, I use separate chaining instead of open-addressing. It eliminates re-allocation of arrays but it requires to carefully choose the size of the hash: the global namespace will need a bigger hash table than the inner scope of a function. 内存区域是一块连续的内存，其中的部分可以被分配但不能被单独释放（必须释放整个区域）。分配操作仅仅是移动指针，当区域满时创建一个新区域。这使得分配速度极快。释放操作也非常快，因为区域内的所有对象会一次性被释放。这种内存管理方式非常适合编译器：一个编译单元可以使用一个区域。在实践中，我使用 3 个区域：一个用于存储 AST，一个用于存储程序对象，一个用于代码生成，这样我可以在代码生成期间丢弃 AST。然而，在编译函数时，会创建大量临时对象，主要是每个词法作用域的名称字典。为了处理这个问题，我创建了区域池：我不再创建和销毁区域，而是从池中取出一个，用完后再放回池中。可变大小数组和开放寻址哈希表不适合内存区域，因为它们需要大量的释放和重新分配。为了存储元素列表，如果可能，我会先计算元素数量，然后分配一个固定大小的数组；如果无法计算，我就使用链表。为了处理大量用于名称存储的哈希表，我使用拉链法（separate chaining）而不是开放寻址法。这消除了数组的重新分配，但需要仔细选择哈希表的大小：全局命名空间需要的哈希表比函数内部作用域的更大。
Lexical Analyzer: Identifiers as Numbers 词法分析器：将标识符视为数字
CPUs are not designed to work with strings, they are designed to work with fixed size integers. Comparing two strings needs additional access to two memory regions. Hashing a string is slow. An important part of the compilation process is to find which entity is associated to an identifier. If the identifier is stored as a string, it will be slow. The compiler does not need to know the content of an identifier except to present it to the user when an error occurs or to store it in a debug symbol table in the object file. It only needs to test equality between identifiers, so it can work internally with an integer assigned for each distinct identifier. Since the lexer already needs to do a lookup in a dictionary for keywords, the additional cost to convert an identifier into a unique integer during lexical analysis is very small. CPU 不是为处理字符串而设计的，它们是为处理固定大小的整数而设计的。比较两个字符串需要额外访问两个内存区域。对字符串进行哈希处理很慢。编译过程的一个重要部分是找出与标识符关联的实体。如果标识符以字符串形式存储，速度会很慢。编译器不需要知道标识符的内容，除非是在发生错误时向用户展示，或者将其存储在目标文件的调试符号表中。它只需要测试标识符之间的相等性，因此可以在内部为每个不同的标识符分配一个整数。由于词法分析器已经需要在字典中查找关键字，因此在词法分析期间将标识符转换为唯一整数的额外成本非常小。
The following source code func main(args) if args.size < 2 will produce this flow of lexical units:
以下源代码 func main(args) if args.size < 2 将产生以下词法单元流：
type = keyword, value = Keyword.func type = identifier, value = 1 type = openParen type = identifier, value = 2 type = closeParen type = newline type = keyword, value = Keyword.if type = identifier, value = 2 type = point type = identifier, value = 3 … where: 1 corresponds to main, 2 to args and 3 to size. 其中：1 对应 main，2 对应 args，3 对应 size。
Optimizing the Syntax Analysis 优化语法分析
I use a simple classic… 我使用一种简单的经典……