10

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

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

4

8 回答 8

14

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

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 月。

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

此外,几年前有人发现了一种新技术,它是有效的 ANSI C。

于 2009-07-29T16:10:59.490 回答
6

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

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

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

于 2009-02-04T14:36:51.103 回答
4

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

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

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

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

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

goto *next_opcode_target++;

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

于 2009-02-04T16:01:06.583 回答
3

即时编译就是其中之一。

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

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

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

于 2009-02-04T15:05:15.337 回答
0

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

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

于 2009-02-04T14:58:34.727 回答
0

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

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

http://abepralle.wordpress.com/2009/01/25/how-not-to-make-a-virtual-machine-label-based-threading/

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

于 2010-11-11T17:33:01.840 回答
-1

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

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

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

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

于 2009-02-04T15:14:28.253 回答