• ホーム
• 最新
• プラットフォームとしてのGraalVM
• 言語実装フレームワーク

コンパイルキューに対するTruffleのアプローチ

バージョン21.2.0から、Truffleはコンパイルキューイングに対する新しいアプローチを採用しています。このドキュメントでは、このアプローチの動機と概要を説明します。

コンパイルキューとは？ #

ゲストコードの実行中、各Truffleの呼び出しターゲットは、実行された回数と、それらの実行中に発生したループ反復回数（つまり、ターゲットの「呼び出しおよびループカウント」）をカウントします。このカウンターが特定のしきい値に達すると、呼び出しターゲットは「ホット」と見なされ、コンパイルがスケジュールされます。これがゲストコードの実行に与える影響を最小限に抑えるために、ターゲットをコンパイルする必要があるという概念は、コンパイルタスクとして具体化され、コンパイルキューに入れられてコンパイルを待ちます。Truffleランタイムは、キューからタスクを取得し、指定された呼び出しターゲットをコンパイルする複数のコンパイラスレッド（--engine.CompilerThreads）を生成します。

Truffleのコンパイルキューの最初の実装は、単純なFIFOキューでした。このアプローチには、ゲストコード実行のウォームアップ特性に関して重要な制限があります。つまり、すべての呼び出しターゲットがコンパイルするのに等しく重要ではありません。目標は、より多くの実行時間を占めるターゲットを特定し、それらを最初にコンパイルして、より早くより良いパフォーマンスを達成することです。呼び出しターゲットは、カウンターが特定のしきい値に達するとコンパイルのためにキューに入れられるため、FIFOキューは、そのしきい値に達した順にターゲットをコンパイルします。実際には、これは実際の実行時間と相関しません。

次の簡単なJavaScriptの例を考えてみましょう。

function lowUsage() {
    for (i = 0; i < COMPILATION_THRESHOLD; i++) {
        // Do something
    }
}

function highUsage() {
    for (i = 0; i < 100 * COMPILATION_THRESHOLD; i++) {
        // Do something
    }
}

while(true) {
    lowUsage();
    highUsage();
}

lowUsage関数とhighUsage関数の両方が、最初の実行時でも十分な呼び出しおよびループカウントのしきい値に達しますが、lowUsage関数が最初に達します。FIFOキューを使用すると、この例が示すように、より早くより良いパフォーマンスを達成するためにhighUsage関数を最初にコンパイルする必要があるにもかかわらず、lowUsage関数を最初にコンパイルすることになります。

コンパイルキューのトラバース #

Truffleの新しいコンパイルキューは、一般的に「トラバースコンパイルキュー」と呼ばれ、ターゲットのコンパイル順序を選択する際に、より動的なアプローチを採用しています。コンパイラスレッドが次のコンパイルタスクを要求するたびに、キューはキュー内のすべてのエントリをトラバースし、最も優先度の高いものを選択します。

タスクの優先度は、いくつかの要因に基づいて決定されます。

まず、最初の層コンパイル（つまり、最初の層のタスク）用にスケジュールされたターゲットは、常に2番目の層のタスクよりも高い優先度を持ちます。これの根拠は、インタープリターでコードを実行する場合と、最初の層でコンパイルされたコードで実行する場合のパフォーマンスの違いが、1層と2層でコンパイルされたコードの違いよりもはるかに大きいということです。つまり、これらのターゲットをより早くコンパイルすることで、より多くのメリットが得られます。また、最初の層のコンパイルは通常、時間がかからないため、1つのコンパイラスレッドが、1つの2層コンパイルを完了するのにかかる時間で、複数の最初の層コンパイルを完了できます。このアプローチは、特定のシナリオではパフォーマンスが低下することが示されており、今後のバージョンで改善される可能性があります。

同じ層の2つのタスクを比較する場合、最初にそれらのコンパイル履歴を考慮し、以前に高いコンパイラ層でコンパイルされたタスクを優先します。たとえば、呼び出しターゲットが最初に最初の層でコンパイルされ、何らかの理由で無効化され、再度最初の層のコンパイルのためにキューに入れられた場合、以前にコンパイルされたことがない他のすべての最初の層ターゲットよりも優先されます。その理由は、以前にコンパイルされた場合、明らかに重要であり、無効化によって必要以上にペナルティを課すべきではないからです。

最後に、前の2つの条件で2つのタスク間の優先度を区別できない場合は、より高い「重み」を持つタスクを優先します。重みは、ターゲットの呼び出しとループカウントと時間の関数です。これは、ターゲットの呼び出しとループカウントに、過去1ミリ秒でその呼び出しとループカウントが増加した速度を掛けたものとして定義されます。ターゲットの呼び出しとループカウントを実行に費やされた時間の代理として使用すると、このメトリックは、その呼び出しターゲットの実行に費やされた合計時間と、その時間の最近の増加とのバランスを取ることを目的としています。これにより、以前は「ホット」だったが現在はあまり実行されていないターゲットと比較して、現在「非常にホット」なターゲットに優先度が高まります。

パフォーマンス上の理由から、タスクの重みはキャッシュされ、1ミリ秒の間再利用されます。キャッシュされた値が1ミリ秒より古い場合は、再計算されます。

トラバースコンパイルキューは、バージョン21.2.0以降はデフォルトでオンになっており、--engine.TraversingCompilationQueue=falseを使用して無効にできます。

動的コンパイルしきい値 #

トラバースコンパイルキューの問題の1つは、最新の重みを取得し、最も優先度の高いタスクを選択するために、キュー内のすべてのエントリをトラバースする必要があることです。キューのサイズが妥当な範囲にとどまる限り、これには大きなパフォーマンスへの影響はありません。これは、妥当な時間内に常に最も優先度の高いタスクを選択できるようにするために、キューが無限に成長しないようにする必要があることを意味します。

これは、「動的コンパイルしきい値」と呼ぶアプローチによって実現されます。簡単に言うと、動的コンパイルしきい値とは、コンパイルしきい値（各呼び出しターゲットの呼び出しおよびループカウントをコンパイルするかどうかを決定する際に比較するしきい値）が、キューの状態に応じて時間の経過とともに変化する可能性があることを意味します。キューが過負荷になっている場合は、コンパイルしきい値を上げて、コンパイルタスクの数を減らすことを目指します。つまり、ターゲットはコンパイルがスケジュールされるためには「よりホット」である必要があります。一方、キューが空に近い場合は、コンパイルしきい値を下げて、より多くのターゲットをコンパイルするようにスケジュールできます。つまり、コンパイラスレッドはアイドル状態になる危険性があるため、「あまりホットでない」ターゲットでもコンパイルするようにしましょう。

しきい値のこの変更を「スケーリング」と呼びます。しきい値は、実際には、scale関数によって決定される「スケールファクター」を掛けただけであるためです。スケール関数は、キューの「負荷」を入力として受け取ります。これは、キュー内のタスク数をコンパイラスレッド数で割ったものです。キュー内のタスクの生の数は、コンパイルのプレッシャーがどれだけあるかの良い指標ではないため、意図的にコンパイラスレッドの数を制御しています。たとえば、平均的なコンパイルに100ミリ秒かかり、キューに160個のタスクがあると仮定します。16個のスレッドを持つランタイムは、すべてのおタスクを約10 * 100ミリ秒、つまり1秒で完了します。一方、2つのコンパイラスレッドを持つランタイムは、約80 * 100ミリ秒、つまり8秒かかります。

スケール関数は、3つのパラメーターによって定義されます。--engine.DynamicCompilationThresholdsMinScale、--engine.DynamicCompilationThresholdsMinNormalLoad、およびDynamicCompilationThresholdsMaxNormalLoadです。

--engine.DynamicCompilationThresholdsMinScaleオプションは、しきい値をどれだけ低くスケーリングするかを定義します。デフォルト値は0.1で、コンパイルしきい値がデフォルト値の10％未満にスケーリングされることはないことを意味します。実際には、定義によりscale(0) = DynamicCompilationThresholdsMinScaleまたはデフォルト値の場合scale(0) = 0.1を意味します。

--engine.DynamicCompilationThresholdsMinNormalLoadオプションは、コンパイルしきい値がスケーリングされない最小負荷を定義します。これは、キューの負荷がこの値よりも大きい限り、ランタイムはコンパイルしきい値をスケールダウンしないことを意味します。実際には、定義によりscale(DynamicCompilationThresholdsMinScale) = 1またはデフォルト値の場合scale(10) = 1を意味します。

--engine.DynamicCompilationThresholdsMaxNormalLoadオプションは、コンパイルしきい値がスケーリングされない最大負荷を定義します。これは、キューの負荷がこの値よりも小さい限り、ランタイムはコンパイルしきい値をスケールアップしないことを意味します。実際には、定義によりscale(DynamicCompilationThresholdsMaxScale) = 1またはデフォルト値の場合scale(90) = 1を意味します。

これまで、scale関数を3点で定義しました。それらの点の間にあるすべての値について、scale関数はそれらの2つの点を結ぶ直線です。これは、最小負荷と最大通常負荷の間のすべての値に対して、スケール関数が定義により1であることを意味します。0と最小通常負荷の間の値については、scale関数は最小スケールと1の間で線形に増加します。この関数の傾きをsとして定義しましょう。次に、関数の残りのドメイン、つまり最大通常負荷よりも大きい値については、scaleを点(DynamicCompilationThresholdsMaxNormalLoad, 1)を通る傾きsの線形関数として定義します。

以下は、スケール関数のASCIIアートプロットであり、どのように定義されているかを説明する必要があります。

          ^ scale
          |
          |                                            /
          |                                           /
          |                                          /
          |                                         /
          |                                        /
          |                                       /
        1 |..... ________________________________/
          |     /.                               .
          |    / .                               .
          |   /  .                               .
          |  /   .                               .
          | /    .                               .
MinScale >|/     .                               .
          |      .                               .
          |_______________________________________________________> load
         0       ^                               ^
              MinNormalLoad                   MaxNormalLoad

動的しきい値は、トラバースコンパイルキューでのみ機能し、バージョン21.2.0以降はデフォルトでオンになっています。これらは、--engine.DynamicCompilationThresholds=falseで無効にできます。