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 拡張機能を使用してパフォーマンスをさらに向上させることができます。これにより、スイッチ ディスパッチを削除でき、ディスパッチ コストの合計を基本的に単一の間接分岐に削減できます。

ディスパッチ コストの改善に加えて、バイトコード ベースのインタープリターには、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 インタープリターを使用していたため、最新のブラウザーで許可されている 1000 レベルに対して、JS では数百レベルの再帰しか許可されていませんでした。

于 2010-08-27T23:29:12.560 に答える
1

おそらく、 llvm "opt" ツールが提供するさまざまな方法を見ることができます。これらはバイトコードからバイトコードへの最適化であり、ツール自体が特定の最適化を適用する利点を分析します。

于 2010-08-27T23:16:48.517 に答える