4

我对一些优化方法或通用字节码设计感兴趣，与解释 AST 相比，它们可能有助于加快使用 VM 的执行速度。

4

2 回答 2

8

AST 解释与字节码的主要胜利是操作调度成本，对于高度优化的解释器来说，这开始成为一个真正的问题。“调度”是用于描述开始执行操作（例如算术、属性访问等）所需的开销的术语。

一个相当正常的基于 AST 的解释器看起来像这样：

class ASTNode {
    virtual double execute() = 0;
}

class NumberNode {
    virtual double execute() { return m_value; }
    double m_value;
}

class AddNode {
    virtual double execute() { return left->execute() + right->execute(); }
}

因此，为简单的事情执行代码1+1需要 3 个虚拟调用。虚拟呼叫非常昂贵（在事物的宏伟计划中），因为拨打电话的多重间接方式，以及首先拨打电话的一般成本。

在字节码解释器中，你有一个不同的调度模型——而不是虚拟调用，你有一个执行循环，类似于：

while (1) {
    switch (op.type) {
        case op_add:
            // Efficient interpreters use "registers" rather than
            // a stack these days, but the example code would be more
            // complicated
            push(pop() + pop());
            continue;
        case op_end:
            return pop();
    }
}

与本机代码相比，这仍然具有相当昂贵的调度成本，但比虚拟调度快得多。您可以使用名为“computed goto”的 gcc 扩展来进一步提高性能，它允许您删除 switch 调度，从而将总调度成本降低到基本上单个间接分支。

除了提高调度成本之外，基于字节码的解释器比 AST 解释器有许多额外的优势，主要是因为字节码能够像真机一样“直接”跳转到其他位置，例如想象这样的代码片段：

while (1) {
    ...statements...
    if (a)
        break;
    else
        continue;
}

要在每次执行语句时正确实现这一点，您需要指出执行是要停留在循环中还是停止，因此执行循环变为：

while (condition->execute() == true) {
    for (i = 0; i < statements->length(); i++) {
        result = statements[i]->execute();
        if (result.type == BREAK)
            break;
        if (result.type == CONTINUE)
            i = 0;
    }
}

随着您添加更多形式的流量控制，此信令变得越来越昂贵。一旦添加了异常（例如，可能在任何地方发生的流控制），您甚至需要在基本算术的中间检查这些东西，从而导致开销不断增加。如果您想在现实世界中看到这一点，我鼓励您查看 ECMAScript 规范，其中他们根据 AST 解释器描述了执行模型。

在字节码解释器中，这些问题基本上消失了，因为字节码能够直接表达控制流，而不是通过信号间接表达，例如。continue只是简单地转换为跳转指令，并且只有在实际命中时才能获得该成本。

最后，根据定义，AST 解释器是递归的，因此必须防止溢出系统堆栈，这对您可以在代码中递归的程度施加了非常严格的限制，例如：

1+(1+(1+(1+(1+(1+(1+(1+1)))))))

在解释器中（至少）有 8 级递归——这可能是一个非常大的成本；旧版本的 Safari（SquirrelFish 之前）使用 AST 解释器，因此 JS 只允许几百级递归，而现代浏览器允许 1000 级递归。

于 2010-08-27T23:29:12.560 回答
1

也许您可以查看llvm “opt” 工具提供的各种方法。这些是字节码到字节码的优化，工具本身将分析应用特定优化的好处。

于 2010-08-27T23:16:48.517 回答