AST の解釈と比較して、VM を使用した実行の高速化に役立つ可能性がある、いくつかの最適化方法または一般的なバイトコード設計に興味があります。
2 に答える
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 では数百レベルの再帰しか許可されていませんでした。
おそらく、 llvm "opt" ツールが提供するさまざまな方法を見ることができます。これらはバイトコードからバイトコードへの最適化であり、ツール自体が特定の最適化を適用する利点を分析します。