Articles

エスケープ解析の動作を見る

Posted on

エスケープ解析と呼ばれるコンパイラ解析フェーズを聞いたことがあるかもしれません。 これは、javaオブジェクトの不要な割り当てを削除する集計のスカラー置換と呼ばれる最適化を通知します。 私は、人々はしばしば、この最適化が実際に何をしているのか、そしてそれができることを過小評価していることを誤解していることがわかります。 実際に動作しているのを見ることで、それをよりよく知ることができます。

Context

graalvmコンパイラは、graalvmの一部であり、ホストされた構成でジャストインタイムコンパイル用に構成されているため、エスケープ解析と集計のスカラ置換がどのように適用されるかを示します。 GraalVMコンパイラは、あなたがおそらく慣れている最も一般的なjust-in-timeコンパイラ、HotSpotのC2よりもこの点でより強力です。

この記事でコンパイラと言うたびに、私はjust-in-timeコンパイルを意味しているので、JVMで実行時に発生するコンパイルの種類に注意してください。 私はjavacコンパイラを意味するものではありません。

コンパイル時に使用するデータ構造の1つ、その上位の中間表現を見て、コンパイラがサンプルプログラムをどのように理解するかを示します。 これは、マシンコードへの変換が開始される前に最適化され変換されるJavaプログラムの意味をキャプチャするグラフです。 それはおそらく非常に高度に聞こえるが、私はJavaの経験を持つほとんどの人にとって、コンパイラが何をしているのかを理解するための実際には

この中間表現は、プログラム内のテキストの構文表現である抽象構文木、またはASTとは異なります。 これは、どのメソッドが他のどのメソッドを呼び出すかを示すコールグラフとも異なります。Shopifyの言語実装チームのSeafoamというツールを使用して、Graalからダンプされたデータ構造の図を作成します。 また、Oracle LabsのIdeal Graph Visualizerというツールを使用することもできます。

これは、オブジェクトがコンパイルユニットの外側に表示されているかどうかを検出します(コンパイルユニットは、通常、メソッドとそれにイン)オブジェクトは、返されたり、別のメソッドに引数として渡されたり、フィールドに書き込まれたりすることによって、コンパイル単位の外に表示され

集計のスカラー置換は、エスケープ解析の結果を使用し、コンパイル単位をエスケープしないオブジェクト、または一部のブランチでのみエスケープするオブジ これは、オブジェクト(集計)をローカル変数と同様の単純な値(スカラー)に置き換えます。 これは後でより具体的に見ていきます。

オブジェクト割り当て

doublexyフィールドを保持する単純なVectorクラスで作業します。 コンストラクタ、ゲッター、およびこのVectorが別のオブジェクトに追加された新しいオブジェクトを返すaddメソッドがあります。ループを実行し、

sum

を使用して2つのランダムに生成されたベクトルを合計する

add

メソッドを呼び出すmainメソッドがあります。 ループは、ジャストインタイムコンパイルをトリガーするのに十分なほどコードを熱くするためにあり、ランダム化は、値が効果的に一定であるようにプロフこれをコンパイルして実行しますGRAALVM CE On Java8 20.3.0on macOS ON AMD64. この最適化はコンパイルをもう少し複雑にして理解しにくくするため、on-stack replacementと呼ばれる最適化をオフにします。 次に、Graalの

dump

オプションを使用して、中間表現データ構造をダンプするように依頼します。

エスケープ解析を実行する直前に、Seafoamを使用してコンパイラがsumメソッドをどのように理解しているかを調べることができます。 ファイルsum.bgvには、コンパイラがダンプしたデータ構造が含まれています。

% seafoam sum.bgv:14 render

ここで何を見ているのですか? このグラフは、Graalがコンパイル中にsumメソッドを理解する方法です。 これはJavaコードですが、テキスト表現の制約から解放されています。 操作はノード(ボックス、菱形、楕円形)として表され、操作間の関係はエッジ(矢印)として表されます。 太い赤い矢印は、ある操作が別の操作の前に行われなければならないことを意味します。 薄い矢印は、操作の出力が別の操作への入力として使用されることを意味します。

私たちは、プログラムがテキスト表現の制約から解放されたと述べました。 たとえば、ノード14のadd操作を見てください。 2つのxフィールドから2つの値をロードした後、ノード19のフィールドxに値を格納する前に発生する必要があることはわかっていますが、2つのyフィー Javaのテキストソースコードでは、すべてが1つの線形順序で記述されます。 グラフはこの制約を緩和し、Java言語仕様が実際に必要とする制約のみをエンコードします。 コンパイラは、すべてが実行される最終的な順序を自由に選択できます。

このグラフを読むと、新しいVectorを作成し、2つの入力オブジェクトのxyフィールドをロードし、それらを一緒に追加してから、返す前に作成した新しいVector グラフには、nullチェック、最終的なフィールドバリアなど、実際のコンパイラグラフであるため、いくつかの追加の詳細がありますが、この記事ではそれを短ここで重要なのは、新しいVectorオブジェクトが作成される明確なポイントがあることです。

基本的なスカラー置換

エスケープ解析と集計のスカラー置換が実行された直後に同じ方法を見てみましょう。

% seafoam sum.bgv:15 render

今、グラフは、それがテキストに表示される方法からさらに緩和されています。 代わりにNew Vector操作の我々は今、そのオブジェクトのフィールドの値を取って、オブジェクトを割り当てるために汎用的な操作にそれを分解しています。 ここにはもうStoreFieldはありません。

この特定の方法では、これは有用なものを達成していません–グラフは緩和されていますが、実際に有用な最適化は明らかにされていませんでした。 これは、私たちが実際に割り当てた唯一のオブジェクトは、メソッドを離れるために割り当てる必要があるためです。 エスケープ解析は実行されましたが、オブジェクトはエスケープされたため、集計のスカラー置換はありませんでした。

さらにこれを取るために、3つのVectorオブジェクトを合計するメソッドを見てみましょう。

private static Vector sum(Vector a, Vector b, Vector c) {return a.add(b).add(c);}

エスケープ解析と集計のスカラー置換の前のグラフは、前の方法と同じ構造を持っています。 私たちは2つのNew Vector操作を持っています。 a.add(b)の結果は、最初の新しいオブジェクトに書き込まれ、その後の.add(c)に対して再度読み込まれます。 これがどのように無駄であるかを見ることができます–中間オブジェクトはどこにも格納されていないか、渡されていないため、コンパイルユニットの外には表示されません–では、なぜそれを割り当て、すぐに再度読み出すフィールドをその中に格納するのですか?

エスケープ解析と集計のスカラー置換の後にグラフを見ると、中間体Vectorが完全に削除されていることがわかります。 Allocは1つだけで、2つはありません。 中間オブジェクトのフィールドの集計は、中間StoreFieldおよびLoadFieldを実行せずに、producerとconsumerを直接接続するエッジのスカラー値に置き換えられました。

スカラー置換の有効性

いくつかの例は、この最適化が人々がしばしば想定しているよりも少し強力であることを示します。

Vectorオブジェクトの配列を合計すると、反復ごとに1つのVectorが論理的に作成されます。

private static Vector sum(Vector first, Vector... rest) {Vector sum = first;for (Vector vector : rest) {sum = sum.add(vector);}return sum;}

このグラフはかなり複雑になりましたが、重要な点は、ループ内(太い赤い矢印で形成された円の内側)でNew Vector操作を見ることができることです。)

部分的なエスケープ解析と集計のスカラー置換が実行された後、ループ内にNew Vectorはありません。 返される最後のVectorの最後に単一の割り当てがあり、xyの値は値を累積することによって構築されます(ノード33と92、ノード36と93の周りの小さなループ。)これは、このメソッドの内部ループにメモリが割り当てられなくなったことを意味します。

スタックに割り当てられているコンパイルユニットをエスケープしないオブジェクトについて話すことがあります。 それが誤解である理由はここにあります。 このメソッドは、2つのVectorオブジェクトを合計しますが、xコンポーネントのみを返します。

private static double sumX(Vector a, Vector b) {return a.add(b).getX();}

エスケープ解析が実行される前に、このメソッドは元のsumとまったく同じように見えますが、xフィールドが読み込まれて返されます。 yフィールドは格納されていますが、使用されることはなく、中間のVectorはコンパイル単位をエスケープしません。

オブジェクトがスカラーに置き換えられた後、y値のコンシューマがなかったため、それを生成するコードにはグラフに接続するものがなく、削除されました。

文字通りスタック上にオブジェクトを割り当て、ヒープメモリではなくスタックメモリに同じ形式でオブジェクトを格納する場合、中間のy値を生成する必要があります。 オブジェクトをどこにも割り当てず、代わりにデータフローエッジに置き換えました。

オブジェクトのスタック割り当ては実際にはものであり、標準のHotSpotとC2のために提案されていますが、ここでは簡単にするためには説明しません。

手動最適化

と比較すると、これらのメソッドのいくつかを書き換えて、ローカル変数にxyを蓄積し、中間のVectorオブジェクトを作成しませんか? たとえば、次のようにVectorオブジェクトの配列にsumを書き換えることができます:

このグラフは、実際には、エスケープ分析の前に中間のVectorオブジェクトを使用した合計のグラフよりも効率的です。 ループ内には割り当てはありません。

しかし、エスケープ解析と集計のスカラー置換の後に中間のVectorオブジェクトを使用して前の合計ループを振り返ると、基本的に同じように見えます。 このメソッドを単純な中間オブジェクトVectorを持つ高レベルバージョンから手動で最適化されたバージョンに書き直すことには利点はありませんでした。

(実際にはおそらくあります–手動で最適化されたバージョンはコンパイルが速く、コンパイルされるまで解釈されながらより迅速に実行されます。)

部分エスケープ解析

GraalがC2ではできないことを行うことができ、GraalVMの重要な利点は部分エスケープ解析です。 オブジェクトがコンパイル単位をエスケープするかどうかのバイナリ値を決定する代わりに、オブジェクトがそれをエスケープする分岐を決定し、オブ

この工夫されたメソッドは、二つのVectorオブジェクトを合計し、条件sに基づいて、それをパラメータとしてblackholeという別のメソッドに渡し、エスケープするか、第三のベクトルを追加してから返します。

xに格納されている中間のVectorは最初のブランチでエスケープされますが、2番目のブランチではエスケープされません。

-XX:CompileCommand=dontinline,Vector.blackholeを指定することにより、blackholeがインライン化されないようにします。

部分エスケープ解析が実行される前に、New Vectorforxが両方のブランチに対して実行されていることがわかります。

部分的な脱出分析と集計のスカラー置換の後、中間体New Vectorは終了しました。 代わりに、エスケープするブランチにはAllocオブジェクトがあり、xyの値を参照し、オブジェクトがxyの値をエスケープしない他のブランチでは、直接使

割り当ては、実際に必要とされるブランチのみに移動されました。

うまくいけば、エスケープ解析と集計のスカラー置換が実際に機能することを見ることによって、どのようなものかを理解するのに役立ちます。 また、実際にはスタック割り当てではなく、実際にはそれよりも強力なものであり、GraalVMコンパイラがあなたのために何ができるかを示していること

詳細情報

Graalの部分エスケープ解析アルゴリズムについては、”Partial Escape Analysis and Scalar Replacement for Java”を参照してください。

私はこれらのコンパイラグラフと基本的なGraalグラフの理解でそれらを読む方法についての詳細を書いてきました。

著者:Chris Seaton

ChrisはShopifyの研究者(シニアスタッフエンジニア)であり、Rubyプログラミング言語の研究をしており、マンチェスター大学の訪問者です。

以前はOracle Labs仮想マシン研究グループの研究マネージャーであり、RubyのTruffleRuby実装を主導し、他の言語および仮想マシンプロジェクトに取り組んでいました。 この前、彼はマンチェスターで博士号を取得し、プログラミング言語と不規則な並列性を研究し、ブリストル大学で可変構文と意味論を持つ言語についてMEngを研究した。

暇な時には、彼は女王自身のヨーマンリーのチェシャー-ヨーマンリー戦隊の戦隊長であり、チェシャーの歴史的予備軽騎兵戦隊である。

コメントを残す

メールアドレスが公開されることはありません。