optimization - 让解释器执行得更快

Question

我创建了一个简单语言的解释器。它是基于 AST 的(更准确地说，是一种不规则的异构 AST)，访问者执行和评估节点。然而我注意到它与“真正的”解释器相比非常慢。为了进行测试，我运行了以下代码:

i = 3
j = 3
has = false
while i < 10000
     j = 3
     has = false
     while j <= i / 2
          if i % j == 0 then
              has = true
          end
          j = j+2
     end
     if has == false then
          puts i
     end
     i = i+2
end

在 ruby​​ 和我的解释器中(只是原始地查找素数)。 Ruby 在 0.63 秒内完成，而我的解释器则超过 15 秒。

我在 C++ 和 Visual Studio 中开发解释器，因此我使用分析器来查看最耗时的部分:评估方法。 50% 的执行时间用于调用抽象求值方法，然后该方法会转换传递的表达式并调用正确的 eval 方法。像这样的事情:

Value * eval (Exp * exp)
{
   switch (exp->type)
   {
   case EXP_ADDITION:
        eval ((AdditionExp*) exp);
        break;

    ...
   }
}

我可以将 eval 方法放入 Exp 节点本身，但我想保持节点干净(Terence Parr 在他的书中谈到了有关可重用性的内容)。

此外，在求值时，我总是重建 Value 对象，该对象存储求值表达式的结果。实际上 Value 是抽象的，并且它具有不同类型的派生值类(这就是我使用指针的原因，以避免返回时对象切片)。我认为这可能是缓慢的另一个原因。

如何使我的解释器尽可能优化？我应该从 AST 创建字节码，然后解释字节码吗？ (据我所知，它们可能会更快)

如果有助于理解我的问题，这里是来源:src

注意:我还没有进行任何错误处理，因此非法语句或错误只会卡住程序。 (也对愚蠢的“错误消息”感到抱歉:))

语法非常简单，当前执行的文件位于 OTZ1core/testfiles/test.txt(这是主要查找器)中。

我很感激我能得到的任何帮助，我在编译器和解释器方面确实是初学者。

Answer 1

加速的一种可能性是使用函数表而不是具有动态重新键入的开关。您对 typed-eval 的调用至少要经历一层，也可能是几层间接。如果您通过名称来区分类型化函数并为它们提供相同的签名，则可以将指向各种函数的指针打包到一个数组中并通过类型成员进行索引。

value (*evaltab[])(Exp *) = {  // the order of functions must match
    Exp_Add,                   // the order type values
    //...
};

那么整个开关就变成了:

evaltab[exp->type](exp);

1 次间接，1 次函数调用。快。