9

我想知道如何设计一个编译非常非常快的编译器。

首先，让我避免对我的问题的一些明显误解：

  1. 我不是在谈论编译器生成的代码的速度。已经有许多资源可用于学习如何优化生成的代码。我很难找到有关使编译器快速的信息。

  2. 我也没有兴趣讨论为什么 C++ 编译器通常比 Java 编译器慢（例如）。我对可以使用哪些技术来加速任何给定语言的编译器感兴趣。

  3. 我也不想听到像 Microsoft 的 Incredibuild 或 Unix 的 distcc 这样的分布式编译系统。这些系统不会给你更快的编译器，它们只是给你更多的编译器。这当然很有用，但这不是我要问的问题。我想知道如何为单个 CPU 设计一个快速编译器。

  4. ccache 也不是我正在寻找的答案。这是一个允许您完全避免使用编译器的系统，但它不会使编译器更快。同样，这很有用；再说一次，这不是我要问的问题。

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

C 编译器过去非常慢。然后，在 1986 年，THINK Technologies 推出了适用于 Macintosh 的 Lightspeed C，它几乎可以立即编译程序。Lightspeed C比所有其他 C 编译器快得多，几乎没有任何可比性。（也许 Lightspeed C 不是新一代闪电般快速的编译器中的第一个，但它是我经验中的第一个。Turbo Pascal 更早 [1983] 出现，但我没有使用它的经验，所以我不知道如何它比较，速度方面。）

从那时起，许多快速编译器已经可用。似乎在 1980 年代编译器技术发生了某种飞跃，这尤其是我想要理解的。突破是什么？

答案可能很简单：使用 Lightspeed 和 Turbo 等 IDE，集成编辑器已经在 RAM 中拥有源代码。如果编译器对这些数据进行操作，它将消除磁盘 I/O，这是所有编译器中最慢的部分。如果源代码大小相对于内存大小较小，那么这可能是提高速度的一个非常重要的因素。（在那些日子里，RAM 大小要小得多，但典型的程序大小也是如此。）

是这样吗？或者是否涉及其他重要的创新？从那时起，编译器速度是否有重大改进？

4

6 回答 6

4
  • 可以一次性解析的简单语法。
  • 简单的目标代码。如果您不直接针对机器代码，您可以摆脱很多事情。
  • 根本不编译。如果您不需要快速执行或主要针对一次性脚本进行设计，则无需浪费时间分析代码。
  • 不要，我再说一遍，不要试图超越你的操作系统磁盘/缓存管理。Mmap 整个该死的文件并像从 RAM 中读取它一样读取它。如果您没有虚拟内存，快速编译是您最不用担心的。
  • 避免为 AST 创建类似于臃肿数据结构的 XML DOM。您不需要为运算符优先级设置动画。保留指向映射数据的指针，而不是到处复制东西。
  • 如果您想要快速分析您的代码。总是。

添加：

  • 学习不同的解析方法。如果您对自己的解析器编写技巧不是非常有信心，请使用经过验证的解析器/词法分析器生成器工具，如 antlr、柠檬等。
于 2010-09-13T20:06:41.080 回答
2

一个问题是您为生成的代码发出了什么。您可以根据需要将尽可能多的编译器时间用于优化。直截了当的一代，甚至看起来有点愚蠢，会节省你的时间。当然，当我使用 Turbo Pascal 和 Lightspeed C 时，整洁的部分是方便地获得可执行文件，而不是优化得有多好。当时，桌面编译器技术严重落后于大型机编译器技术。

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

除此之外，减少 I/O 也很好。快速词法分析在当今本质上是一个已解决的问题，但在当时并不一定如此。我不确定解析，上一次是在二十年前研究过，所以其他人可以指导你进行快速解析等。

于 2010-09-15T17:09:20.147 回答
1

普遍的看法是，手动编码的基于自上而下递归下降的解析器比基于规则的 LALR(k) 解析器（例如由 yacc 构建的）更快——假设它们编码良好。在某些情况下，手动编码的解析器还可以提供更好的错误消息。

OTOH，使用类似 yacc 的一个很好的理由是 LALR(1) 可以明确地解析比递归下降更大的语言类——如果我没记错的话，这相当于 LL(1) 类语言。与手工制作的解析器相比，创建和修改 yacc 样式解析器所需的时间也更少。

与人们一直在讨论的所有其他问题相比，解析是否是性能瓶颈尚不清楚。也就是说，在文件 IO 或 AST 遍历上做得不好会造成很大的伤害——可能比使用效率稍低的解析器所付出的代价要大得多。

仍然是我熟悉的真正快速的编译器使用手工制作的递归下降解析器。我应该承认，自从我专业地与编译器合作以来已经有好几年了，但在某一时刻，这是我日常工作的一部分。

于 2010-09-17T19:24:18.143 回答
0

I think one of the big changes in Turbo Pascal was that on many previous compilers/assemblers/linker, the source code and object code would both be on disk, as would parts of the compiler/assembler/linker. Trying to read and write multiple files at a time on a single drive would often be more than twice as slow as reading or writing one file. Turbo Pascal kept the entire development system in RAM, and in many cases the source or object code would be in RAM as well.

Late in the life of the Commodore 64, there was an assembler called Fast Assembler, which patched the basic interpreter to add assembly-language opcodes and a few new directives. The ORG directive would set an target code location and a "pass" flag. If the "pass" flag was clear, each opcode would bump the target code location by the instruction size but wouldn't generate any code and wouldn't complain about out-of-range branches. If the pass flag was set, code would be generated. To assemble a program, one would surround it with a for/next loop to go through three times, with the "pass" flag set on the last time. Because everything was kept in RAM, the edit-assemble-test cycle was immensely fast compared with any earlier assemblers.

于 2010-10-02T18:58:30.643 回答
0

今天你肯定会让你的编译器使用它所有可用的内核。我写的不是分布式编译而是并行编译——从头开始设计你的编译器以使用多个内核。一种明显的方法是将编译器的各个阶段流水线化。重写 AST 当然也可以并行化

请不要打字，不要告诉我们这种方法被您的“规则”排除在外。您的规则可能会阻止使用浮点单元来优化浮点运算，或者禁止使用时钟速度高于 1GHz 的任何处理器。

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

于 2010-09-15T16:48:58.610 回答
0

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

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

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

有助于加快编译的另一件事是一种旨在允许单遍编译的语言。例如，Pascal 要求在使用之前定义每个曾经使用过的函数（不仅仅是声明，如在 C++ 中）（这就是为什么 main 函数必须在源文件中的最后一个）

于 2010-09-13T20:05:56.803 回答