编译语言的优势与尽早执行构建后的AST相比是什么？

Question

编译程序生成机器码的好处/缺点与仅从源代码构建AST并在遍历树时执行操作相比有何优劣之处？

在一种方式中选择而不是另一种方式，是否有特定的原因？

- kjh

Answer 1

解释AST的速度通常比运行执行相同任务的机器码要慢得多，一般会慢20倍左右。

其中的优点是AST生成速度更快，因此需要比大多数编译器生成代码的时间要短。由于整个代码生成阶段可以被忽略，所以AST解释器也往往比编译器简单。

因此，如果您有一个不进行重型计算的程序，使用解释器将启动更快。另一方面，如果您有一个程序在一个稀缺的循环环境中经常或持续运行，则最好使用编译器。

一些编程环境（例如许多LISP）包括解释器用于开发代码，因为它支持快速的调试周期和编译器用于生成速度较快的代码的生产。其中一些系统允许自由混合解释和编译代码，这本身就是非常有趣的。

编译成字节码是一个折中方案：编译速度比机器码更快，但执行速度比AST快。尽管如此，现代字节码解释器通常会在程序运行时“即时”将其编译为本机代码。例如，Sun的HotSpot JVM的名称源于此，它将Java字节码中的“热点”编译为本机代码以在运行时加速程序。

回答评论中的问题

上文提到的20倍是一个参考数字，因为很少有现代语言系统使用纯AST解释器（重要例外是命令shell，但它们大多是很久以前开发的，速度基准测试不常见）。他们太慢了。我的背景是lisp解释器。我实现过一些。例如，这里有一组Scheme基准测试 。易于选择与AST解释器相对应的列。如果需要，我可以从ACM Digital Library archive 中发布更多类似的内容。

另一个粗略的基准测试：Perl使用高度优化的AST解释器。在我的机器上紧密循环中添加10百万个浮点数需要大约7秒钟。编译后的C代码（gcc -O1）需要大约1/20秒。

评论者以添加4个变量作为示例。分析忽略了查找成本。解释器和编译器之间的一个明显分界线是符号的预计算地址或帧偏移量。在“纯”解释器中没有这些东西。因此，在运行时环境（通常是哈希表）中添加4个数字需要4次查找，至少需要100条指令。在良好的编译代码中，在x86上添加4个整数只需要2个指令和一个存储结果的指令。

在“纯”AST解释器和编译机器码之间有许多不同的阴影。根据语言的不同，可能可以将符号偏移编译进AST中。这有时被称为“快速链接”。该技术通常将速度提高了2倍或更多。然后有像Python、PHP、Perl、Ruby 1.9+这样的“编译成字节码并执行”的系统。它们的字节码实际上是线程化代码（操作码可能导致非常复杂的事情发生），因此它们比机器码更接近AST。然后有以上提到的JIT字节码解释器。

重点是，纯AST解释器的20倍是一个极端，而机器码则是另一个极端。在中间存在许多变体，每个变体都有优缺点。

- Gene

---

20是从哪里得来的（即您能提供引用吗）？我很好奇，因为因子似乎大不相同：w+x+y+z -> load, add, add, add，但(load (add (add (add)))) -> load node、load value、add、load node、load value、add、load node、load value、add、load node、load value、add，可能会有许多缓存未命中。我有一种感觉，这将比20倍的时间更长。另一方面，x=y -> load x、store y，但(store (load)) -> load node、load value、load node、store value，远少于20倍（或者由于缓存未命中，再次增加）。 - Sebastian Mach

@phresnel 一个好问题。我在我的帖子中添加了一些信息。 - Gene

Answer 2

编译的另一个优点是比直接即兴解释要容易得多，这一点尚未提及。通常，未经处理的源语言不太适合直接解释，将其简化为更简单的语言将有助于更高效和直接的解释。例如，语言可能具有词法作用域，每次对变量或函数参数进行解引用时都需要名称查找。但一个简单的转换过程，枚举变量并插入隐式存储管理结构，将使解释变得更简单、更高效——数组访问比文本键哈希表快得多。另一个例子是闭包处理—— lambda提升处理比任何可能的即兴方法都更简单。

解释平坦的“字节码”比树形结构要容易得多。有许多公认的优化技术（例如线程代码）可用于字节码解释器，而AST遍历解释器注定会非常缓慢。

另外，除非你必须进行一些重量级的优化（如死代码消除、常量折叠、寄存器分配、有效指令调度），编译非常简单，可以分成显然容易的小步骤。另一方面，任何非平凡语言的简单解释总是复杂的，不能被简单和明显地分解。

- SK-logic