如何使用字节码来优化动态语言的执行时间？

Question

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

Answer 1

AST解释与字节码的主要胜利是运营调度成本,对于高度优化的解释器,这开始成为一个真正的问题."Dispatch"是用于描述开始执行操作(例如算术,属性访问等)所需的开销的术语.

一个相当普通的基于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扩展来进一步改进perf,它允许您删除交换机调度,从而将总调度成本降低到基本上单个间接分支.

除了提高调度成本之外,基于字节码的解释器还具有许多优于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(pre-SquirrelFish)使用了AST解释器,因此JS只允许几百个级别的递归,而现代浏览器只允许1000个递归.