如何设计一个快速的编译器？关键的设计选择是什么？

Question

如何设计一个快速的编译器？关键的设计选择是什么？

design-patternsperformancecompiler-theory

10

我想知道如何设计一个编译器，使其编译速度非常非常快。

首先，让我澄清一些问题：

我不是在谈论编译器生成的代码的速度。已经有很多资源可供学习如何优化生成的代码。我找不到的是使编译器本身变快的信息。
我也不感兴趣讨论为什么C++编译器通常比Java编译器慢（例如）。我感兴趣的是可以用什么技术加速任何给定语言的编译器。
我也不想听关于Microsoft的Incredibuild或Unix的distcc之类的分布式编译系统。这些系统不能为您提供更快的编译器，它们只是为您提供了更多的编译器。这当然有用，但这不是我要问的问题。我想知道如何为单个CPU设计一个快速的编译器。
ccache也不是我要找的答案。那是一个允许您完全避免使用编译器的系统，但它并没有使编译器更快。同样，这是有用的；同样，这不是我要问的问题。

我希望我的问题现在非常清楚了。但也许一些历史可以使它更清晰。

C编译器以前真的很慢。然后，在1986年，THINK Technologies推出了Macintosh的Lightspeed C，它几乎可以瞬间编译程序。Lightspeed C比所有其他C编译器都要快得多，几乎没有可比性。（也许Lightspeed C不是第一批新一代闪电般快速编译器中的第一个，但它是我经历过的第一个。Turbo Pascal早在1983年就问世了，但我没有经验，所以我不知道它在速度方面如何比较。）

此后，许多快速编译器已经问世。似乎在20世纪80年代，编译器技术发生了某种飞跃，这正是我试图理解的。那么，这个突破是什么呢？

答案可能很简单：使用像Lightspeed和Turbo这样的IDE，集成编辑器已经将源代码存储在RAM中。如果编译器使用该数据进行操作，则可以消除磁盘I/O，这是任何编译器最慢的部分。如果源代码大小相对于内存大小较小，则这可能是速度提高的非常重要的贡献因素。（在那些日子里，RAM尺寸要小得多，但典型程序的尺寸也比现在小。）

就是这样吗？还是有其他重要的创新 involved ？自那时以来，编译器速度有重要的改进吗？

- Thom Boyer

2

+1 如果正确使用"wicked"作为副词。 - Jon Purdy

6个回答

2

一个问题是你为生成的代码发出了什么。你可以在优化方面投入尽可能多的编译器时间。简单的生成，甚至看起来有点愚蠢，会节省你的时间。当然，当我使用Turbo Pascal和Lightspeed C时，好处在于方便地获取可执行文件，而不是它有多么优化。桌面编译器技术在那个时候严重落后于大型机编译器技术。

Turbo Pascal和Lightspeed C的另一件事是集成。特别是在多任务处理器之前的家用电脑时代，这很棒。与我拥有的第一个C编译器（用于CP/M）不同，我不必在编辑器中进行更改，关闭它，进行编译，链接，然后执行。这可能是你看到的部分：组件的快速执行，无需输入复杂的命令。现在我可以通过在Gnome桌面上运行多个终端来复制这个过程：一个用于vim，一个用于运行gcc，一个用于执行。

除此之外，减少I/O是好的。快速词法分析现在基本上已经解决了，但在那个时候不一定如此。我不确定解析方面，因为我最后一次涉足这个问题是二十年前，所以其他人可以指导你进行快速解析等方面的操作。

- David Thornley

Turbo Pascal（原版）速度极快的另一个因素是其是用汇编语言手工编码的。 - NealB

1

一般来说，手写的自顶向下递归下降语法分析器比类似yacc所构建的基于规则的LALR(k)语法分析器更快，前提是它们被编码得很好。在某些情况下，手写的解析器也可以给出更好的错误信息。

另一方面，使用像yacc这样的工具的一个好理由是，LALR(1)语法分析器能够无歧义地解析比递归下降更多的语言——如果我没记错的话，这等价于LL(1)语言类。而且，使用类似yacc的解析器创建和修订所需的时间可能比手工打造的更少。

与人们一直在讨论的所有其他问题相比，语法分析并不是性能瓶颈。也就是说，在文件IO或AST遍历方面做得不好会对性能造成很大影响——这可能比使用稍微不那么高效的解析器所花费的代价高得多。

然而，我熟悉的真正快速的编译器都使用了手工打造的递归下降解析器。我应该承认，自从几年前我专业地从事编译器以来，已经有一段时间了，但那时它是我日常工作的一部分。

- Alex Blakemore

0

今天，您肯定会让编译器使用其所有可用的内核。我不是在写关于分布式编译的事情，而是关于并行编译的事情——从底层开始设计您的编译器以使用多个内核。一个明显的方法是将编译器的各个阶段进行流水线处理。重写AST当然也可以并行化。

请不要因规则而排除这种方法。您的规则可能会阻止使用浮点单位优化浮点运算，或禁止使用时钟速度高于1GHz的任何处理器。

如果您想为今天的计算机编写快速程序，请为今天的CPU编写程序，而不是昨天的。今天的计算机使用多核CPU。

- High Performance Mark

是的，现代编译器应该使用可用的核心，包括任何GPU。我喜欢你流水线编译器阶段的想法。这些都是好主意，感谢你分享。正如你所说，“被我的‘规则’排除了”吗？是的！这是一个很好的回答，但不是我问的问题。我的问题的核心是：“在1980年代发生了什么，使得编译器变得更快了。”我应该把它作为问题标题。现代编译器使用你们提到的所有想法；它们还使用在1980年代发明的技术——而那就是我缺失的部分。 - Thom Boyer

0

我认为 Turbo Pascal 中的一个重大变化是，在许多以前的编译器/汇编器/链接器中，源代码和目标代码都会存储在磁盘上，编译器/汇编器/链接器的部分也会存储在磁盘上。试图在单个驱动器上同时读取和写入多个文件通常比读取或写入一个文件慢两倍以上。Turbo Pascal 将整个开发系统保留在 RAM 中，并且在许多情况下，源代码或目标代码也会保存在 RAM 中。

在 Commodore 64 的生命周期后期，有一个名为 Fast Assembler 的汇编器，它修补了基本解释器以添加汇编语言操作码和一些新指令。ORG 指令将设置目标代码位置和“传递”标志。如果“传递”标志清除，则每个操作码将通过指令大小增加目标代码位置，但不会生成任何代码，并且不会抱怨超出范围的分支。如果设置了传递标志，则会生成代码。要汇编程序，需要用 for/next 循环将其包围三次，最后一次设置“传递”标志。由于所有内容都保存在 RAM 中，与任何早期汇编器相比，编辑-汇编-测试周期非常快速。

- supercat

0

C++编译器比Java编译器慢，主要是因为它们（通常）生成优化的本地代码，而Java编译器生成不那么优化的字节码，并将最终优化和本地代码生成留给JIT编译器（在运行时执行）。由于严格的优化需要对本地代码有所了解，因此字节码编译器能做的事情有限。

现在，我无法评论Lightspeed（因为我对它一无所知），但在Lattice和Microsoft C（慢）与Borland TurboC（快）的情况下，Borland将所有文件保存在内存中并在那里编译它们（如果您的程序崩溃，可能会导致IDE崩溃，从而丢失未保存的源代码！）。Microsoft的IDE总是将文件保存到磁盘，然后启动一个单独的程序来读取磁盘并编译它。

使用预编译头文件也有助于加速c/C++编译。

另一件有助于加速编译的事情是设计为允许单遍编译的语言。例如，Pascal要求在使用函数之前（而不仅仅是声明，如C++中）定义每个使用的函数（这就是为什么主函数必须在源文件中最后出现的原因）。

- James Curran

请完整阅读问题。你的大部分回答都属于我明确说过不相关的类别。关于内存中文件的观点只是我问题的一部分重复。 - Thom Boyer

1

请注意，C++编译器也较慢，因为解析C++更加困难。我不知道为什么C语言被设计成难以解析，但很可能是无意中做成的。C++无法摆脱这一点，而Java和C#则可以。 - David Thornley

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- artificialidiot · Accepted Answer

采用简单的语法，可以一次性解析。
生成简单的目标代码。如果不直接针对机器代码进行编译，您可以做很多事情。
根本不需要编译。如果您不需要快速执行或主要设计一次性脚本，则不需要浪费时间分析代码。
千万不要试图超越操作系统磁盘/缓存管理。将整个文件映射到内存并像从RAM中读取一样读取它。如果您没有虚拟内存，快速编译是您最不必担心的问题。
避免为AST创建类似XML DOM的臃肿数据结构。您不需要为运算符优先级添加动画效果。而是保留指向映射数据的指针，而不是复制内容。
如果您希望代码运行更快，请对其进行性能分析。永远如此。

补充：

学习不同的解析方式。如果您对自己的解析器编写技能不是非常自信，请使用经过验证的解析器/词法分析器生成工具，例如antlr、lemon等。