optimization - 高效解释器中使用了哪些操作码调度策略？

Question

哪些技术可以促进高效的操作码调度以实现快速解释器？是否有一些技术只能在现代硬件上运行良好，而其他技术由于硬件的进步而不再运行良好？必须在易于实施、速度和可移植性之间做出哪些权衡？

我很高兴 Python 的 C 实现终于超越了switch (opcode) {...}操作码分派的简单实现，转为作为编译时选项的间接线程，但我不太高兴他们花了 20 年才到达那里。也许如果我们在 stackoverflow 上记录这些策略，下一种语言会变得更快。

score 14 · Accepted Answer

有许多关于不同类型调度的论文：

M. Anton Ertl 和 David Gregg，Optimizing Indirect Branch Prediction Accuracy in Virtual Machine Interpreters，2003 年 ACM SIGPLAN 编程语言设计和实现会议论文集 (PLDI 03)，第 278-288 页，加利福尼亚州圣地亚哥，2003 年 6 月.

M. Anton Ertl 和 David Gregg，高效虚拟机解释器在现代架构上的行为，第 7 届欧洲并行计算会议论文集（Europar 2001），第 403-412 页，LNCS 2150，曼彻斯特，2001 年 8 月。

石云和在他的博士论文中提供了一个很好的总结。

score 6 · Accepted Answer

在你开始任何事情之前，请检查Lua。

它很小 (150Kb)，纯 ANSI C，适用于任何具有 C 编译器的东西。非常快。

最重要的是 - 源代码干净易读。值得一试。

score 4 · Accepted Answer

间接线程是一种策略，其中每个操作码实现都有自己JMP的下一个操作码。Python 解释器的补丁看起来像这样：

add:
    result = a + b;
    goto *opcode_targets[*next_instruction++];

opcode_targets将语言字节码中的指令映射到操作码实现的内存位置。这更快，因为处理器的分支预测器可以对每个字节码做出不同的预测，switch这与只有一条分支指令的语句相比。

编译器必须支持计算的 goto 才能工作，这主要意味着 gcc。

直接线程类似，但在直接线程中，操作码数组被替换为指向操作码实现的指针，如下所示：

goto *next_opcode_target++;

这些技术之所以有用，是因为现代处理器是流水线的，并且必须在错误预测的分支上清除它们的流水线（慢）。处理器设计人员进行了分支预测以避免经常清理管道，但分支预测仅适用于更有可能采用特定路径的分支。

score 3 · Accepted Answer

3

即时编译就是其中之一。

于 2009-02-04T14:28:30.997 回答

score 1 · Accepted Answer

一个巨大的胜利是以中间形式存储源代码，而不是在执行期间重做词法分析和解析。

这可以从仅存储令牌到 Forth 风格的线程代码一直到 JIT 编译。

score 0 · Accepted Answer

基准测试是一种在给定平台上快速做任何事情的好技术。测试，改进，再测试，改进。

我不认为你能得到更好的答案。制作口译员有很多技巧。但我给你一个提示，不要做权衡，选择你真正需要的东西并追求那些目标。

score 0 · Accepted Answer

我发现一篇关于线程解释器实现的博客文章很有用。

作者描述了基于 GCC 标签的线程，以及如何在 Visual Studio 中使用内联汇编器来实现这一点。

结果很有趣。他报告说使用 GCC 时性能提高了 33%，但令人惊讶的是，Visual Studio 内联汇编实现慢了 3 倍！

score -1 · Accepted Answer

问题有点模糊。但是，您似乎在询问是否要编写解释器。

解释器通常使用传统的解析组件：词法分析器、解析器和抽象语法树 (AST)。这使设计人员能够阅读和解释有效的语法，并构建具有相关运算符、参数等的命令树结构。

一旦采用 AST 形式，整个输入就会被标记化，解释器可以通过遍历树开始执行。

有很多选择，但我最近使用ANTLR作为解析器生成器，它可以构建各种目标语言的解析器，包括 C/C++ 和 C#。

8 回答 8