Clever Geek Handbook

Llst内部デバイス、パート3。JITの魔法、または仮想マシンを50倍高速化する方法

XKCD 303

前の記事で 、 humbugと私は、メソッドの実行方法とその内容によって計算速度がどのように変化するかを示しました。 これで、仮想マシンの内部を見て、これがどのように、なぜ起こるのかを理解できます。



先ほど、 Smalltalk言語 、またはLittle Smalltalkのマイクロ実装に精通しました。 言語の構文、メモリ内のオブジェクトを表現するための形式、および基本的な命令のセットを理解しました。 これで、SmalltalkとLLVMの相互作用の問題に近づきます（このため、一連の記事全体が考案されました）。



これで、JITコンパイラで何が行われるかを正確に理解するために必要な知識ベースがすべて揃いました。 この記事では、SmalltalkバイトコードがLLVM IRコードに変換される方法、コードがコンパイルおよび実行される方法、およびプログラムによる解釈よりも高速に動作する理由を学習します。 最もせっかちな人は、数字と忍び寄るラインのあるシェルキャスト（ 1回と2回 ）を見ることができます（スクロールの可能性を忘れないでください）。





はじめに



TRIZと常識のありふれた考察の両方は、私たちに次のことを教えてくれます：





これらの原則は人間関係をはるかに超えており、幅広い分野で応用されています。 コンピューターサイエンスを含む。 多くは、 キャッシュを使用する利点を理解しています。 怠zyなコンピューティングのことを聞いた人もいます。 しかし、無意味でむさぼる官僚主義の時代に直面した反例で、誰もが出会いました。



また、JITコンパイラーには、上記の考慮事項と多くの共通点があります。 私たちのプロジェクトも例外ではありません。 従来の方法でコードが実行される方法と、パフォーマンスを改善するためにコードで何ができるかを確認します。



仮想マシンと実際のプロセッサーの違い



Smalltalk仮想マシンはスタック指向です。



  1. 操作を実行すると、オペランドがスタックにプッシュされます。
  2. 実行された操作により、必要な数のオペランドがスタックから削除されます。
  3. 結果はスタックの最上部にプッシュバックされ、次の操作のオペランドとして使用できます。


このアプローチの利点は、仮想マシンのコードがシンプルであり、一連の計算を簡単に実装できることです。 もちろん欠点もありますが、その主な点は、値を操作したり、スタックに値を配置したり、スタックから値を削除したりして、マシンが値に対して何らかのアクションを実行できるようにすることです。 自分で判断する： 前の記事 （ Collection>>sort:



説明した例では、値をスタックに繰り返しプッシュしてすぐに値を抽出し、Arrayクラスのインスタンスにコピーしてから、オブジェクトをスタックに再び配置します（ markArgumentsはこれを行います） ）



もちろん、これはすべて理由があります。 マシンの積み重ねられた構成により、複雑な操作を導入することなく、アクションのシーケンスを非常に簡単に記録できます。 たとえば、括弧を使用して算術式を計算する場合、スタックは中間値の一時的なストレージとして使用されます。 太古から、工学計算機はこれらの原則に従って、 逆ポーランド記法を使用して設計されてきました。



ただし、最新のプロセッサアーキテクチャの観点から見ると、Smalltalkは非常に不便です。 ほとんどの操作はメモリを使用して実行されます。 局所性の原則は維持されません（オブジェクトはすべて互いに遠く離れたヒープに散在しています）。 新しいオブジェクトが絶えず生成されているため、ガベージコレクションが行われ、次の大量のメモリがシャッフルされます。 すべてのメモリ操作は間接的に処理されます。 最後に、多数の小さなメソッドにより、レジスタを適切に割り当てることができなくなります。



大衆の最新のプロセッサは登録されています。 レジスタはRAMよりもはるかに高速に動作するため、レジスタを直接操作することでより高いパフォーマンスを期待できます。 大量のデータキャッシュが存在すると、メモリへのアクセスのコストを大幅に削減できます（ローカリティの原理に従います）が、以下に示すように、メモリ操作自体をレジスタに移動するのではなく、メモリ操作自体の数を根本的に削減することにより、主に成功を達成します。



したがって、プロセッサでSmalltalkコードを効率的に実行するには、スタックロジックをレジスタに変換する方法を見つける必要があります。



コンパイラーJIT値スタック



LLVMの中間コード表現はSSA表記を使用します。 この表記では、慣れている形式の変数はありません。 すべての計算はグラフです。 各計算結果（ノード）に名前を割り当てて、この名前を以降の計算で使用できます（2つのノードをリンクします）。 さらに、指定された名前がその値を変更できない場合（同じ名前への値の再割り当ては許可されません）。 名前は、それが発表されたプログラム（およびデータ）内のそのポイントのみを参照します。 まだメモリを操作する必要がある場所では、alloca命令が使用されます。これは、要求されたサイズのメモリ領域と、読み込みおよび書き込みのロードおよびストア命令をそれぞれ割り当てます。



前述のソート方法からleft



変数を初期化するのに必要なSmalltalkバイトコードに再び注目しましょう。 

 "left <- List new" 0023 PushLiteral 4 0024 MarkArguments 1 0025 SendMessage new 0026 AssignTemporary 0 0027 DoSpecial popTop


別の例、同じメソッドからのブロックの開始： 

 0037 PushArgument 1 "criteria" 0038 PushTemporary 3 "x" 0039 PushTemporary 2 "mediane" 0040 MarkArguments 3 0041 SendMessage value:value: "  " 0042 DoSpecial branchIfFalse 52


また、どちらの場合も、多数の単純なメモリ操作が実行されることは明らかです。 基本的なプッシュ命令は、アセンブラー命令のペアに変換できます。 スタックの最上部のインデックスをシフトすることにより変数のインデックスを別の領域にシフトすることにより、あるメモリ領域からポインタをコピーするだけです（そしてオブジェクト構造へのポインタのみを使用します）。



IRコードでの上記のアイデアの「正面」実装は、次のようになります。 

 define void @pushValueToStack(%TContext* %context, i32 %index, %TObject* %value) { %stackPointer = getelementptr inbounds %TContext* %context, i32 0, i32 4 %stack = load %TObjectArray** %stackPointer %stackObject = bitcast %TObjectArray* %stack to %TObject* call %TObject** @setObjectField(%TObject* %stackObject, i32 %index, %TObject* %value) ret void } define %TObject** @setObjectField(%TObject* %object, i32 %index, %TObject* %value) { %fieldPointer = call %TObject** @getObjectFieldPtr(%TObject* %object, i32 %index) store %TObject* %value, %TObject** %fieldPointer ret %TObject** %fieldPointer } define %TObject** @getObjectFieldPtr(%TObject* %object, i32 %index) { %fields = getelementptr inbounds %TObject* %object, i32 0, i32 2 %fieldPointer = getelementptr inbounds [0 x %TObject*]* %fields, i32 0, i32 %index ret %TObject** %fieldPointer }


はい、動作し、ネイティブコードに変換されると、インタープリターの同様の実装よりも高速になります。 ただし、このようなJIT VMの全体的なパフォーマンスは驚くほど低くなります。 問題は、メモリ操作自体がなくなっていないことです。 単純に低レベルのコードに移植し、ソフトウェアVMの「ラッパー」を取り除きました。



仮想マシンを実際に高速化するには、提供されているLLVM機能、つまりSSAを豊富な最適化パスとともに使用する必要があります。



pushおよびmarkArgument命令の目的を思い出すと、ここのスタックは特定の値（引数、リテラル、定数、または一時変数）を、対応するプッシュ命令の位置によって決定される引数の配列内の対応するセルに関連付けるためにのみ使用されることが明らかになります。



SSA表記により、スタックをバイパスしてこれを直接行うことができます。 必要なのは、引数の配列に入れるために準備したオブジェクトを「記憶」し、すぐに将来の使用場所にコピーすることです。 LIFOの原則に従って、保存されている値にも順番にアクセスするため、スタックを使用してリンクを保存するのが妥当です。 この値スタックは存在し、コンパイル時にのみ使用されます。 すでに生成された「正しい」コードが実行されます。



この原則は非常にうまく機能するため、JITバージョンのメソッドは通常のコンテキストスタックをまったく使用しません。 JITコードでコンテキストを作成するときにも初期化されず、これは送信するメッセージごとに 1つの割り当てを差し引いたものです。



したがって、最適化されたメッセージ送信のために次のアルゴリズムを取得します。

  1. オブジェクトをコンテキストスタックにプッシュする （ push ）代わりに、メモリから変数に値をロードし（ load ）、コンパイラーの値スタックに置きます。
  2. markArgumentsステートメントを処理し、引数のオブジェクトを作成してから、値スタックから要素を順次削除し、作成された引数の配列のスロットの行にそれらを格納します。
  3. sendMessageハンドラースタブを呼び出します 。


4つのメモリ操作（値の読み込み 、スタックへの値の格納 、スタックからの値の読み込み 、引数配列のフィールドへの格納）の代わりに、2つ（値の読み込みと配列への格納）だけを残したことがわかります。



LLVMに精通している人は、オプティマイザパスによって外部の支援なしでそのような空のメモリ操作が効果的に削除されることに反対するかもしれません。 実際、最も単純な場合、これはそうです。 しかし、生成する必要がある実際のコードは、はるかに複雑に見えます。 これは主に、ガベージコレクターの正しい動作を保証するために特別なマーカーと値への参照を追加する必要があるためです。



メソッドと機能



動作すると、仮想マシンはイメージから各メソッドのJITバージョンを作成します。 メソッドと機能的に同等ですが、ネイティブプロセッサの命令で既に実装されています。 JIT関数は、まだ送信されていないメッセージを最初に送信したときに作成されます。 たとえば、メッセージList>>sort:



firstを送信すると、メッセージハンドラが見つかります。これはCollection>>sort:



メソッドです（ List



クラスにはsort:



メソッドはありませんが、 Collection



から継承されるため）。 その後、仮想マシンは同じ名前のJIT関数を見つけようとしますが、見つけられません。 JITコンパイラが呼び出され、 Collection>>sort:



メソッドの本体を通じて、同等の関数が作成されます。 次に、この関数は、通常のメッセージ用と同じパラメーターで呼び出されます。 次回送信すると、コンパイラは呼び出されず、メソッドの既存のバージョンが使用されます。



メッセージを送信する



前回の記事で思い出したように、仮想マシンにメッセージを送信するには、次のものが必要です。



  1. スタックから値を削除し、引数の配列を作成します（ markArgumentsの個別のステップとして実行されます ）。
  2. メッセージを処理する階層内のメソッドを見つけます。
  3. コンテキストオブジェクトを作成し、フィールドに入力します。
  4. 新しいコンテキストの実行に切り替えます。


この段階では、仮想マシンにはオブジェクトのタイプに関する情報がないため、宛先メソッドの検索手順に影響を与えることはできません。 具体的には、この情報は呼び出し時にのみ利用可能であり、オブジェクトの将来のタイプを予測するために使用することはできません。 したがって、メッセージ検索エンジンは同じままで、モジュールに登録されているsendMessage()



システム関数を使用して呼び出されます。 この機能を使用すると、JITコードからソフトウェアVMにアクセスし、メッセージ宛先を見つけるように依頼できます。 次に、制御は見つかったメソッドのJITバージョンに転送されます。



ソフトウェアVMは、他のメモリがないため、ヒープ上にのみすべてのオブジェクトを作成します。 JIT VMの場合、いくつかのオブジェクトをスタックに配置することにより、メモリのオーバーヘッドを大幅に削減できます。 そのようなオブジェクトは次のとおりです。





これらのオブジェクトの存続期間はメソッド自体の実行時間よりも短くないため（常にアクティブなコンテキストからリンクされているため）、スタックに配置できます。 メソッドを終了すると、スタックは前のフレームに折りたたまれ、使用中のメモリが自動的に解放されます。 厳密に言えば、スタックとヒープのメモリ割り当ての速度はほぼ同じです。 そことそこの両方で、割り当てられたメモリのサイズにポインタを移動し、結果の値を返すだけです。 しかし、大量の場合、これはガベージコレクションの必要性につながり、すでにかなりの時間がかかります。 これが頻繁に発生するほど、スタックオプションはより効率的に機能します。



統計



JITコンパイラの理想的な最終結果は、次のように表すことができます。





RBIを達成する方法の主な問題は、呼び出しごとのオブジェクトのタイプの不確実性です。 既に知っているCollection >> sortメソッドをもう一度考えてみましょう。 



 sort: criteria | left right mediane | (self size < 32) ifTrue: [ ^ self insertSort: criteria ]. mediane <- self popFirst. left <- List new. right <- List new. self do: [ :x | (criteria value: x value: mediane) ifTrue: [ left add: x ] ifFalse: [ right add: x ] ]. left <- left sort: criteria. right <- right sort: criteria. right add: mediane. ^ left appendList: right




使用される変数のタイプはどうですか？ 実行コンテキストと呼び出しコードがなければ、明確なことは言えません。 これは、Smalltalkの長所と短所の両方です。 このコードは、下位クラスに関係なく同等に効率的に機能するため、強力です。 リストと配列の両方を等しくソートします。 コンパイル段階で最適化を行うことができず、オブジェクト型の知識に依存しているため、弱い。



最適に近い結果を得ることができるトリッキーなプランがあります。 そして、彼の名前はコール統計です。 プログラムが実行されると、sendMessageハンドラーが呼び出されます。このハンドラーは、メインの作業に加えて、メッセージの送信に関与するクラスの統計も補充します。



プログラムの過程でクラス階層が変化しないと仮定して、条件の代わりに直接呼び出しを挿入できます。 残念なことに、ここでの厳しい現実には驚きがあります。 たとえば、統計を収集すると、次の結果が得られました。10回の連続した呼び出しから、変数がクラスString



ことが10回判明しました。 しかし、これは次回にそうなるという意味ではありません。 オブジェクトのコレクションを歩くと、さまざまなクラスに出会えます。 最後に、 String



インスタンスを返すために使用されたメソッドでさえ、単に星が形成されたためにパラメータが設定されたため、突然nilを返すことがありました。



したがって、呼び出しの統計情報を持っている場合でも、変数の型が既知のいずれかであることが判明した場合、この段階でできることは直接呼び出しを挿入することです。 実際には、これは、パッチャーがオブジェクトのクラスをチェックし、対応する関数に制御を移すスイッチブロックを挿入するという事実につながります。



型推論



将来的には、Hindley-Milnerアルゴリズムと追加のヒューリスティックを使用して、完全な型推論を行う予定です。 次に、変数の型が完全に推測された場所で、チェックなしで直接呼び出しを行うことができます。 これは、呼び出したコードに呼び出されたメソッドを完全にインライン化するパフォーマンスと機能に非常によく影響します。



たとえば、上記のCollection>>sort:



メソッドを見ると、注意深い読者は、変数left



とright



常にList



クラスのインスタンスによって初期化されることに気付くかもしれません。 仮想マシンは、次の考慮事項からこれを理解できます。



  1. left



    変数は、 List new



    式の結果に初期化されます。
  2. 式List new



    はパラメーターを使用せず、固定アクションオブジェクト（ List



    ）を持ちます。
  3. List



    オブジェクトへの#new



    メッセージの送信は、 List>>new



    によって処理されます
  4. List>>new



    メソッドは、式super new



    結果を返します
  5. 現在のコンテキストでは、 List super



    、つまりCollection



  6. Collection



    オブジェクトへの#new



    メッセージの送信は、 Object>>new



    によって処理されます
  7. Object>>new



    メソッドには、既知のクラス（公理）のオブジェクトを常に返すプリミティブ7が含まれます。


さらに、式は逆の順序で折りたたまれ、「 left



の変数はList



クラスのオブジェクトによって初期化されます」というステートメントにつながります。



変数のクラスleft



とright



を知っていれば、メソッドの残りの部分も最適化できます。 操作#add:



#sort:



、および#appendList:



は、追加の条件なしで直接メソッド呼び出しを使用してコンパイルされます。



実際、型の完全な推論は私たちにとって望ましいですが、必須ではありません。 変数の型は呼び出しごとに変わらないことを知るだけで十分です。 そして、最初にメッセージを送信したときの状態を正確に調べます。 全体として、プログラム実行中の型チェックを排除し、コード量を削減し、オプティマイザーの手を離すことができます。



編集



この時点まで読んだことがあるが 、 LLVMが何であるかについてほとんど知らない人のために、Habréの多くの非常に良い投稿、またはLLVMとLLVM言語リファレンスマニュアル へのHackerの紹介を読むことをお勧めします。 もちろん、英語で。



そのため、LLVMは命令のチェーンの形式で記述されたIR表現を入力で受け取ります。 命令は、 基本ブロックと呼ばれるエンティティに編成されます 。 このようなユニットの特徴は、1つの入力と1つの出力しかないことです。 これは、作業の便宜上、意図的に行われます。 制御を転送する命令を除き、命令はブロック内に配置できます。 つまり、条件付きジャンプ、リターン、スロー、およびキャッチ命令をブロックの途中に置くことはできません（例外をスローしない場合、関数呼び出しは許可されます）。 それでもこれが必要な場合、この場所のブロックは2つに分割されるため、問題の命令（LLVM用語ではターミネーターと呼ばれます ）は前半の末尾にあります。 したがって、機能全体は一連の基本ブロックとそれらの間の遷移で構成されます（遷移命令自体はアドレスではなく、制御を転送するブロックの識別子で動作します）。



私たちのタスクは、メソッドのバイトコードを読み取り、それをIRコードで再作成し、遷移ロジックを保持し、最終的に機能的に同等なものを取得することです。 もちろん、これは単語ごとにバイトコードから操作を繰り返す必要があるという意味ではありませんが、正確性を確保する必要があります。



最初の問題は、メソッドのバイトコードが1つの配列にまとめて書き込まれることです。 当然、基本的なブロックはなく、すべての遷移アドレスは、配列の先頭からのオフセットシステムに記録されます。 したがって、最初に必要なことは、遷移命令のオフセットとベースブロック間の対応を構築することです。 これは、バイトコードを事前に渡すことで行われます（ MethodCompiler.cppのscanForBranchesメソッド）



メソッドの将来のブロックの「魚」を手にし、指示を「詰め込む」ことから始めます。 スタッフィング自体は順番に行われます。 メソッドの最初から、Smalltalk命令を対応するIRコードの操作に変換します。 プッシュ命令は直接エンコードされないことを思い出してください。代わりに、必要な保留中のアクションを説明するTDeferredValue構造体（ TStackValueも参照 ）を値スタックに配置します。 次に、コードでスタックからそのような値を削除する操作に出くわすと、保留中のアクションを実行し、既に使用可能な実際の名前を取得します。 大半の場合、アクションは数命令だけ延期されるため、コード内の操作の実際の位置は変わりません。 実際、中間値（またはコンテキストスタックの使用）を必要とせずに、コード内の2つの場所の論理バインディングがあります。 現在のコードの値の転送がどのように正確に実装されるかは、LLVMによってすでに決定されています。



たとえば、バイトコードで次の場合： 

 "left <- List new" 0023 PushLiteral 4 0024 MarkArguments 1 0025 SendMessage new 0026 AssignTemporary 0 0027 DoSpecial popTop


...この部分をコンパイルするとき、アクションのシーケンスは次のようになります。



  1. 「スタックに4番目のリテラルを置く」遅延操作を作成します。
  2. markArgumentsステートメントでは、スタックから値を取得する必要があります。 これにより、保留中の操作が実行されます。名前lit0



    作成し、 lit0



    リテラルの配列から4番目の要素を読み取る操作をlit0



    ます。 この名前は、現在のベースユニットの値のスタックに配置します。
  3. 1つの要素の配列を作成し、それをargs0



    という名前でargs0



    ます。 . , , ( lit0



    ). , : args0[0] = lit0



    .
  4. sendMessage, args0



    . ( , ).
  5. temp0, . temp0



    .
  6. ( popTop ).




一見怖いですが、実際には、これらすべてがほんの数個のアセンブラー命令でまとめられます。特に、引数の配列を作成するとき、必要なメモリ操作のみを残しました。リテラルを読み取り、配列に書き込み、メッセージを送信し、結果を一時変数に書き込みます。



同じ操作セットのソフトウェアVMは、スタックを操作するときにメモリの読み取りと書き込みを繰り返し実行する必要があります。値をコンテキストスタックにプッシュしてすぐに値を取得し、引数の配列に書き込みます。彼女は再び作成された引数の配列へのポインタをスタックに置き、それをスタックから引き出し、メッセージを送信するときにそれを使用します。その結果は数秒間だけスタックに置かれます。最新のプロセッサと大胆なデータキャッシュでも。



私たちの国では、引数の配列でさえヒープ上に作成されませんが、ストリームへの呼び出しの実際のスタックに配置されます。したがって、配列の割り当てと充填は迅速に行われます。最も重要なことは、IRで動作するLLVMは、直接見られないが適切と考えるあらゆる種類の最適化を自由に実行できることです。



たとえば、同じtemp値が連続して2回使用される場合があります。次に、値を再読み取りする代わりに、LLVMは以前の名前を使用できます（これが結果に影響しない場合）。そして、そのような些細な事柄がたくさんあります。



...コンパイラ値スタックをローカルで使用するオプションを検討しました。ただし、移行操作が開始されると、事態はさらに複雑になります。



すべてのプッシュ操作現在の基本単位の値のローカルスタックで実行されます。スタック操作は非ローカルにすることができます。この場合、値は遷移階層の上位のブロックから削除されます。たとえば、2つの基本ブロックXとYがあります。ブロックXは操作pushTemporary 0



とbranch , Y. , Y markArguments 1



, . , Y . , Y X, . .



Y X 1 ..X n , φ- , SSA. X i , , . , .



, MethodCompiler::TJitContext::popValue() JITCompilation.txt .





, , « ». , , . Collection>>sort:



, . , , .



, . , , . , .



, . , 10% , , — . , :







branch , Y. , Y markArguments 1



, . , Y . , Y X, . .



Y X 1 ..X n , φ- , SSA. X i , , . , .



, MethodCompiler::TJitContext::popValue() JITCompilation.txt .





, , « ». , , . Collection>>sort:



, . , , .



, . , , . , .



, . , 10% , , — . , :







branch , Y. , Y markArguments 1



, . , Y . , Y X, . .



Y X 1 ..X n , φ- , SSA. X i , , . , .



, MethodCompiler::TJitContext::popValue() JITCompilation.txt .





, , « ». , , . Collection>>sort:



, . , , .



, . , , . , .



, . , 10% , , — . , :









More articles:


All Articles