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个函数调用。快速地。