🐊 🤽🏼 🤶🏼 Llst内部パート2またはLittle Smalltalk + LLVM =♥ 🏴‍☠️ ➿ 🤚🏽

みなさんこんにちは！ humbugとともに、 Low Level Smalltalk （LLST）シリーズの3番目の記事に注目してください。この記事が、珍しいプログラミング言語の~~自転車~~愛好家だけでなく、 LLVMのような素晴らしいものに興味がある人にとっても興味深いものになることを願っています。

私たちのプロジェクトの目標は、バイトコードレベルでLittle Smalltalkと互換性のある独自の仮想マシンを作成することです。主な違いは、異種アーキテクチャです。LLVMコードをIRコードに変換することにより、バイトコードをプログラムで実行し、低レベルのプロセッサ命令にコンパイルできます。もちろん、2番目の方法では、より高いパフォーマンスを実現し、利用可能なコンピューティングリソースを最適な方法で使用できます。

しかし、最初に最初に...

バージョン0.2の新機能

前の記事で説明した以前のバージョンと比較すると、多くの変更点があります。

リストを表示

readlineライブラリを接続しました。これで、コマンドラインを簡単に編集できます。以前に入力したコマンド（Ctrl + R）の履歴と、Tabキーのオートコンプリートがありました。一般に、すべては通常のシェルと同じように機能します。
ファイルを操作するプリミティブが追加され、イメージがディスクに書き込まれます。これで、新しいVMでも元のVMとほぼ同じことができます。
スケジューラクラスに基づいてプリミティブマルチタスク（グリーンスレッド）を実装しました。計画-完全なマルチスレッド。
テストは、その後のデバッグを大幅に簡素化するオブジェクトを使用した基本操作用に作成されました。テストは素晴らしいです！
ヒープオブジェクトhptr<>へのポインタを修正しました。以前は、外部リストstd::list<> 、現在はリストがスタックスペースに保持されています。これだけで、ソフトウェアVMが2回加速されました。
ブランチ37では、ネイティブAPIスケッチが作成されます。これにより、将来、ラッパーやその他の松葉杖なしでネイティブメソッドを完全に便利に作成できるようになります。メソッドは、Smalltalkからの同等のエンティティの構造を記述する同じクラスの「インプレース」で実装されます。ここ、ここ、ここで例を見ることができます。
既存のBakerに基づいて、世代別GCを実装しようとしました。実際、すべての違いは、ヒープの半分の役割と、世代間のリンクのリストの格納にあります。したがって、迅速に組み立てる場合は、若い世代のみを調べて、そこから古い世代から参照されているオブジェクトを取得する必要があります。コードは記述されていますが、まだデバッグされていません。
Flex / Bisonを使用してImageBuilderをゼロから書き直す作業が開始されました。継承されたユーティリティには多くの問題があります。パラメータを渡すことはできず、通常のエラー出力はありません。イメージコードの文字のペアを変更すると「神秘的な」クラッシュが発生します。たとえば、コメントなどを削除するときの同じ「神秘的な」生活。さらに、場合によっては、ユーティリティは誤ったバイトコードを生成します。もちろん、そのように生きることは不可能なので、リメイクすることにしました。現時点では、Little Smalltalkの文法は完全に記述されています。言語構成体自体に加えて、プライマリブートストラップイメージの構築に使用される制御コマンドもあります。
ドメイン名を取得してGitHubに移動しました。リポジトリがllst.orgで利用可能になりました。トラッカーにも注意してください。

さて、今、最も興味深いもの：

SmalltalkバイトコードのLLVM IRコードへの変換を実装しました。そして、これは、メッセージを送信するときに、その場で行われます。つまり、最初の呼び出しでは、メソッドコードの変換とコンパイル（ミリ秒）に時間がかかりますが、後続の呼び出しは既にネイティブに行われます。
余分な組み込み関数llvm.gcrootを削除する追加のパスを実装して、メモリアクセスの回数を減らします（そしてもちろん、速度を上げます）。
メッセージの送信とメソッドの「ホットスポット」に関する統計が収集されます。これは、後続の最適化の基礎です。
最後に、「ホット」メソッドの修正が実装されました。これは、収集された統計に基づいて、直接呼び出しの導入、キャッシュのバイパス、クラステーブルの検索によってメソッドを変更します。これにより、パイプラインとプロセッサ遷移予測を最適な方法で使用でき、パフォーマンスにプラスの影響を与えます。

現在、最適化された最適化されたホットコードは、実行されるコードに応じて、以前のバージョンのソフトウェアVMと比較して2〜100倍高速に実行されます。悪くない、私には思える。まだ開発の余地がありますが。実際、複雑なグラフ分析と型推論を必要としない最も単純な最適化が行われています。自由に時間を過ごしたいなら、もっと壮大なことができます。

それはどのように見えますか

呼び出し統計を知ることでコードを高速化する方法を見てみましょう。前の記事で説明した既知の並べ替えアルゴリズムと、メッセージ処理の速度を評価できるベンチマークのテストを実行します。バージョンをローカルにインストールする場合は、githubのリポジトリの説明にあるUsageとLLVMの項目を読んだ後、コンパイル済みバージョンをインストールするか、ソースからコンパイルすることをお勧めします。

ベンチマークから始めましょう：

 loopBenchmark | sum | sum <- 0. 1 to: 100000 do: [ :x | sum <- sum + 1 ]. ^sum

この「悪意のある」コードは、変数のsum 10万回の小さなコードを追加します。もちろん、出口で同じ10万を取得する必要があります（または、VMがゴミ箱に移動できます）。

そして、実行の結果は次のとおりです。

多くのブナ

 $ ./llst Image read complete. Loaded 5442 objects Soft run: 60 Cold jit run: 46 Hot jit run: 28 JIT Runtime stat: Messages dispatched: 200006 Objects allocated: 200004 Blocks invoked: 200002 Block cache hits: 199999 misses 3 ratio 100.00 % Message cache hits: 400004 misses 6 ratio 100.00 % Hot methods: Hit count Method name 200000 Block>>value: (0 sites) 2 Number>>to:do: (1 sites) value: (index 20, offset 109) class hits: (Block 200000) 2 Undefined>>loopBenchmark (1 sites) to:do: (index 15, offset 73) class hits: (SmallInt 2) 2 Block>>value (0 sites) Patching active methods that have hot call sites Recompiling method for patching: Number>>to:do: Patching Number>>to:do: ...done. Verifying ...done. Recompiling method for patching: Undefined>>loopBenchmark Patching Undefined>>loopBenchmark ...done. Verifying ...done. Optimizing Number>>to:do: ...done. Verifying ...done. Optimizing Undefined>>loopBenchmark ...done. Verifying ...done. Compiling machine code for Number>>to:do: ...done. Compiling machine code for Undefined>>loopBenchmark ...done. All is done. Patched cold jit run: 12 Patched hot jit run: 9 JIT Runtime stat: Messages dispatched: 200010 Objects allocated: 400008 Blocks invoked: 400004 Block cache hits: 399998 misses 6 ratio 100.00 % Message cache hits: 400006 misses 10 ratio 100.00 % Hot methods: Hit count Method name 200000 Block>>value: (0 sites) 4 Block>>value (0 sites) 2 Undefined>>loopBenchmark (0 sites) 2 Number>>to:do: (1 sites) value: (index 20, offset 109) class hits: (Block 200000) 2 Undefined>>loopBenchmark (1 sites) to:do: (index 15, offset 73) class hits: (SmallInt 2) ===-------------------------------------------------------------------------=== ... Statistics Collected ... ===-------------------------------------------------------------------------=== 2 adce - Number of instructions removed 2 branchfolding - Number of block tails merged 2 branchfolding - Number of dead blocks removed 1 cgscc-passmgr - Maximum CGSCCPassMgr iterations on one SCC 31 codegen-dce - Number of dead instructions deleted 63 codegenprepare - Number of GEPs converted to casts 9 codegenprepare - Number of blocks eliminated 114 codegenprepare - Number of memory instructions whose address computations were sunk 47 codegenprepare - Number of uses of Cast expressions replaced with uses of sunken Casts 313 dagcombine - Number of dag nodes combined 0 dse - Number of other instrs removed 12 dse - Number of stores deleted 54 gvn - Number of blocks merged 2 gvn - Number of instructions PRE'd 125 gvn - Number of instructions deleted 2 gvn - Number of loads PRE'd 37 gvn - Number of loads deleted 265 inline - Number of functions inlined 271 inline-cost - Number of call sites analyzed 263 instcombine - Number of dead inst eliminated 1 instcombine - Number of dead stores eliminated 67 instcombine - Number of instructions sunk 492 instcombine - Number of insts combined 159 isel - Number of blocks selected using DAG 7667 isel - Number of times dag isel has to try another path 101 jit - Number of bytes of global vars initialized 5310 jit - Number of bytes of machine code compiled 12 jit - Number of global vars initialized 239 jit - Number of relocations applied 3 jit - Number of slabs of memory allocated by the JIT 1 loop-simplify - Number of pre-header or exit blocks inserted 3 machine-licm - Number of hoisted machine instructions CSEed 11 machine-licm - Number of machine instructions hoisted out of loops 73 machine-sink - Number of machine instructions sunk 6 memdep - Number of block queries that were completely cached 11 memdep - Number of fully cached non-local ptr responses 43 memdep - Number of uncached non-local ptr responses 784 pei - Number of bytes used for stack in all functions 1 phi-opt - Number of dead PHI cycles 15 phielim - Number of atomic phis lowered 31 pre-RA-sched - Number of loads clustered together 48 reassociate - Number of insts reassociated 29 regalloc - Number of cross class joins performed 251 regalloc - Number of identity moves eliminated after coalescing 92 regalloc - Number of identity moves eliminated after rewriting 7 regalloc - Number of instructions deleted by DCE 4 regalloc - Number of instructions re-materialized 1 regalloc - Number of interferences evicted 251 regalloc - Number of interval joins performed 11 regalloc - Number of new live ranges queued 683 regalloc - Number of original intervals 369 regalloc - Number of registers assigned 1 regalloc - Number of registers unassigned 3 regalloc - Number of rematerialized defs for spilling 4 regalloc - Number of rematerialized defs for splitting 3 regalloc - Number of spilled live ranges 2 regalloc - Number of splits finished 4 simplifycfg - Number of blocks simplified 2 twoaddrinstr - Number of instructions aggressively commuted 2 twoaddrinstr - Number of instructions commuted to coalesce 4 twoaddrinstr - Number of instructions promoted to 3-address 30 twoaddrinstr - Number of two-address instructions 14 x86-codegen - Number of floating point instructions 1414 x86-emitter - Number of machine instructions emitted ->

ここで重要なのは5行です。

 Soft run: 60 Cold jit run: 46 Hot jit run: 28 Patched cold jit run: 12 Patched hot jit run: 9

最初の行は、ソフトウェアVMを使用したメソッドの実行です。最も遅い方法：トリックなし、コードは命令ごとに非常に正確に実行されます。このモードは、コードに変更を加えないため、デバッグに適しています。また、コマンドラインを解析するときにイメージに組み込まれたコンパイラーによって使用されます。

2行目はJITコールドランです。このメソッドは、機能的に同等のIRコードに変換され、プロセッサ命令にコンパイルされ、既に直接実行されています。この段階ですでにいくつかの最適化が行われていますが、これについては後で説明します。メソッドのコンパイルを考慮しても、総実行時間は純粋な実行よりも短いことがわかります。これは常にそうではありません。多くの場合、複雑なメソッドの場合、最初の実行に約100ミリ秒の時間がかかる場合がありますが、その後にゲインが得られます。同じモードでは、呼び出しに関する統計が蓄積されます（呼び出しハンドラが呼び出されるたびに、コンパイルされたメソッドが起動されます）。

3行目はホットランです。すでにJITに馴染みのあるメソッドが呼び出されるため、既製のコンパイル済みコードが含まれます。オーバーヘッドなし-キャッシュ内のメソッドの存在を確認し、関数を直接呼び出します。結果は明らかです。

4行目は、パッチャーの「コールド」実行と、統計がこのイベントの実行可能性を示す直接呼び出し（直接）の配置です。この場合、ボディ全体が関数からスローされ（新たに再コンパイルされます）、パッチャーはパスします。パッチャーが直接呼び出しで置き換える必要がある命令を見つけることができるように、完全な再コンパイルが必要です。問題は、パスを最適化した後（およびGCのコードを準備した後）、メソッドの本体が認識できないほど変更される可能性があることです。これらすべての操作の後、IRコードは実際のプロセッサ命令にコンパイルされ、その後実行されます。

5行目は、パッチが適用され最適化されたメソッドのホットランです。繰り返しますが、トリックなしでそれを行うだけです。

これらはパイです...値を外挿すると、1秒あたり約1200万ブロックが私のマシンで処理されます。この定数から、処理されたメッセージの数の推定値を取得できます。 Number>>to:do:メソッドに対応するJITコードでは、次のメッセージ送信と同等の3つの操作が実行されます。

< #to:do:ループ条件）内で< counterオブジェクトを送信します。
#value:ブロックオブジェクトへ（ブロック呼び出し）;
sumオブジェクト（ループ本体）に+を送信します。

一定の3,600万を取得します。これは、1秒あたりに送信されるメッセージの数を上から概算すると見なすことができます。

同時に、これは制限速度からはほど遠い。たとえば、 whileTrue:コンストラクトを使用してベンチマークの本文を書き換える場合whileTrue:

 loopBenchmark | sum | sum <- 0. [ sum < 1000000 ] whileTrue: [ sum <- sum + 1 ]. ^sum

次に、 100万回の実行の結果（10万回ではなく、定数に注意してください）は次のようになります。

 Soft run: 197 Cold jit run: 13 Hot jit run: 4

この場合、1秒あたり約8.1×10 ⁸メッセージ、または197/4の加速が約50倍になります。これは、コンパイルされたバージョンにメッセージ送信の実際の操作が含まれていないためです。 whileTrue:遷移を伴う線形の命令セットに展開されます。すべての演算は、算術演算を直接含む、実行の個別の分岐がある数値に対して行われます。

パッチャーを使用した実行の結果は、ホットJITの実行の結果と変わりません。メッセージの送信がないため、収集できる統計情報がなく、JIT関数への直接呼び出しで置き換えることができるソフトウェアVMへの呼び出しがないことを意味します。

もちろん、VMのパフォーマンスに関しては、あらゆる種類のベンチマーク（特に整数のベンチマーク）に非常に注意する必要があります。これらの数値は、実行された最適化の大まかな評価にのみ使用され、平均してコードの実行が速くなったことを示す指標としてのみ使用されます。

もちろん、ここでは最適化のためのほぼ理想的な条件があるため、実数は少なくなります。ループと算術はネイティブコード全体にコンパイルされます。直接分岐命令の存在は、プロセッサ分岐予測子を最適に使用します;キャッシュのミスは少し少なくなります。したがって、最適化されていないバージョンと比較して増加し、各パッケージについてハンドラースタブに移動する必要があり、キャッシュを確認して、メッセージに実際に対処する必要があるユーザーを理解します。ヒットの99％を考慮しても、貴重なプロセッサクロックがこれに費やされます。

ソートテストでは、より控えめな結果が表示されます。

 Soft run: 48 Cold jit run: 140 Hot jit run: 25 Patched cold jit run: 7 Patched hot jit run: 6

完全な結論

 Preparing test data ...done Soft run: 48 Cold jit run: 140 Hot jit run: 25 JIT Runtime stat: Messages dispatched: 210613 Objects allocated: 17746 Blocks invoked: 43006 Block cache hits: 43001 misses 5 ratio 99.99 % Message cache hits: 369520 misses 51704 ratio 87.73 % Hot methods: Hit count Method name 44061 Link>>next (0 sites) 35102 MetaObject>>in:at:put: (0 sites) 27775 Link>>value (0 sites) 25778 Block>>value:value: (0 sites) 17746 Class>>new (0 sites) 17356 MetaLink>>value:next: (3 sites) new (index 3, offset 7) class hits: (MetaLink 17356) in:at:put: (index 11, offset 31) class hits: (MetaLink 17356) in:at:put: (index 18, offset 72) class hits: (MetaLink 17356) 17226 Block>>value: (0 sites) 15619 List>>add: (1 sites) value:next: (index 5, offset 13) class hits: (MetaLink 15619) 1999 List>>isEmpty (1 sites) = (index 4, offset 9) class hits: (SmallInt 1999) 1999 SmallInt>>= (0 sites) 1867 List>>insert:onCondition: (10 sites) isEmpty (index 3, offset 7) class hits: (List 1867) add: (index 10, offset 27) class hits: (List 130) value (index 33, offset 166) class hits: (Link 10419) value:value: (index 40, offset 210) class hits: (Block 10419) next (index 48, offset 268) class hits: (Link 1481) value:next: (index 50, offset 286) class hits: (MetaLink 1481) value:next: (index 57, offset 21) class hits: (Link 1481) next (index 68, offset 8) class hits: (Link 8938) value:next: (index 81, offset 24) class hits: (MetaLink 256) next: (index 83, offset 9) class hits: (Link 256) 1481 Link>>value:next: (0 sites) 392 List>>size (0 sites) 390 MetaList>>new (2 sites) new (index 4, offset 9) class hits: (MetaCollection 390) in:at:put: (index 12, offset 34) class hits: (MetaList 390) 384 Link>>next: (0 sites) 262 Collection>>sort: (13 sites) size (index 3, offset 7) class hits: (List 262) insertSort: (index 12, offset 34) class hits: (List 132) popFirst (index 21, offset 88) class hits: (List 130) new (index 26, offset 126) class hits: (MetaList 130) new (index 31, offset 158) class hits: (MetaList 130) value:value: (index 42, offset 219) class hits: (Block 15359) add: (index 49, offset 279) class hits: (List 8207) add: (index 56, offset 12) class hits: (List 7152) do: (index 59, offset 31) class hits: (List 130) sort: (index 64, offset 64) class hits: (List 130) sort: (index 70, offset 19) class hits: (List 130) add: (index 76, offset 4) class hits: (List 130) appendList: (index 81, offset 24) class hits: (List 130) 260 Link>>do: (2 sites) value (index 18, offset 72) class hits: (Link 260) value: (index 20, offset 82) class hits: (Block 260) 260 List>>do: (1 sites) do: (index 9, offset 25) class hits: (Link 260) 132 Collection>>insertSort: (4 sites) isEmpty (index 3, offset 7) class hits: (List 132) new (index 16, offset 55) class hits: (MetaList 130) insert:onCondition: (index 27, offset 130) class hits: (List 1867) do: (index 30, offset 143) class hits: (List 130) 130 List>>popFirst (3 sites) value (index 14, offset 43) class hits: (Link 130) next (index 19, offset 76) class hits: (Link 130) - (index 25, offset 111) class hits: (SmallInt 130) 130 SmallInt>>- (0 sites) 130 List>>appendList: (7 sites) firstLink (index 8, offset 21) class hits: (List 2) size (index 13, offset 40) class hits: (List 2) next (index 36, offset 181) class hits: (Link 8207) next (index 43, offset 234) class hits: (Link 8079) firstLink (index 54, offset 3) class hits: (List 128) next: (index 56, offset 12) class hits: (Link 128) size (index 61, offset 49) class hits: (List 128) 130 List>>firstLink (0 sites) 2 Collection>>sort (1 sites) sort: (index 10, offset 27) class hits: (List 2) 2 Block>>value (0 sites) ===-------------------------------------------------------------------------=== ... Statistics Collected ... ===-------------------------------------------------------------------------=== 2 adce - Number of instructions removed 14 branchfolding - Number of block tails merged 6 branchfolding - Number of branches optimized 5 branchfolding - Number of dead blocks removed 1 cgscc-passmgr - Maximum CGSCCPassMgr iterations on one SCC 38 codegen-dce - Number of dead instructions deleted 220 codegenprepare - Number of GEPs converted to casts 2 codegenprepare - Number of blocks eliminated 151 codegenprepare - Number of memory instructions whose address computations were sunk 123 codegenprepare - Number of uses of Cast expressions replaced with uses of sunken Casts 854 dagcombine - Number of dag nodes combined 250 dce - Number of insts removed 194 dse - Number of other instrs removed 158 dse - Number of stores deleted 51 gvn - Number of blocks merged 353 gvn - Number of instructions deleted 6 gvn - Number of loads PRE'd 277 gvn - Number of loads deleted 862 inline - Number of functions inlined 862 inline-cost - Number of call sites analyzed 1085 instcombine - Number of dead inst eliminated 69 instcombine - Number of instructions sunk 2540 instcombine - Number of insts combined 194 isel - Number of blocks selected using DAG 18193 isel - Number of times dag isel has to try another path 461 jit - Number of bytes of global vars initialized 12042 jit - Number of bytes of machine code compiled 25 jit - Number of global vars initialized 375 jit - Number of relocations applied 2 jit - Number of slabs of memory allocated by the JIT 15 llst - Number of removed loads from gc.root protected pointers <<<<<< 222 llst - Number of removed roots <<<<<< 4 machine-cse - Number of common subexpression eliminated 1 machine-licm - Number of hoisted machine instructions CSEed 14 machine-licm - Number of machine instructions hoisted out of loops 71 machine-sink - Number of machine instructions sunk 10 memdep - Number of block queries that were completely cached 81 memdep - Number of fully cached non-local ptr responses 84 memdep - Number of uncached non-local ptr responses 2792 pei - Number of bytes used for stack in all functions 9 phielim - Number of atomic phis lowered 2 phielim - Number of critical edges split 36 pre-RA-sched - Number of loads clustered together 23 reassociate - Number of insts reassociated 21 regalloc - Number of cross class joins performed 250 regalloc - Number of identity moves eliminated after coalescing 124 regalloc - Number of identity moves eliminated after rewriting 6 regalloc - Number of instructions deleted by DCE 1 regalloc - Number of interferences evicted 248 regalloc - Number of interval joins performed 21 regalloc - Number of new live ranges queued 1240 regalloc - Number of original intervals 891 regalloc - Number of registers assigned 1 regalloc - Number of registers unassigned 6 regalloc - Number of rematerialized defs for spilling 4 regalloc - Number of rematerialized defs for splitting 6 regalloc - Number of spilled live ranges 4 regalloc - Number of splits finished 13 simplifycfg - Number of blocks simplified 3 twoaddrinstr - Number of instructions re-materialized 43 twoaddrinstr - Number of two-address instructions 40 x86-codegen - Number of floating point instructions 2697 x86-emitter - Number of machine instructions emitted Patching active methods that have hot call sites Recompiling method for patching: MetaLink>>value:next: Patching MetaLink>>value:next: ...done. Verifying ...done. Recompiling method for patching: List>>add: Patching List>>add: ...done. Verifying ...done. Recompiling method for patching: List>>isEmpty Patching List>>isEmpty ...done. Verifying ...done. Recompiling method for patching: List>>insert:onCondition: Patching List>>insert:onCondition: ...done. Verifying ...done. Recompiling method for patching: MetaList>>new Patching MetaList>>new ...done. Verifying ...done. Recompiling method for patching: Collection>>sort: Patching Collection>>sort: ...done. Verifying ...done. Recompiling method for patching: Link>>do: Patching Link>>do: ...done. Verifying ...done. Recompiling method for patching: List>>do: Patching List>>do: ...done. Verifying ...done. Recompiling method for patching: Collection>>insertSort: Patching Collection>>insertSort: ...done. Verifying ...done. Recompiling method for patching: List>>popFirst Patching List>>popFirst ...done. Verifying ...done. Recompiling method for patching: List>>appendList: Patching List>>appendList: ...done. Verifying ...done. Recompiling method for patching: Collection>>sort Patching Collection>>sort ...done. Verifying ...done. Optimizing MetaLink>>value:next: ...done. Verifying ...done. Optimizing List>>add: ...done. Verifying ...done. Optimizing List>>isEmpty ...done. Verifying ...done. Optimizing List>>insert:onCondition: ...done. Verifying ...done. Optimizing MetaList>>new ...done. Verifying ...done. Optimizing Collection>>sort: ...done. Verifying ...done. Optimizing Link>>do: ...done. Verifying ...done. Optimizing List>>do: ...done. Verifying ...done. Optimizing Collection>>insertSort: ...done. Verifying ...done. Optimizing List>>popFirst ...done. Verifying ...done. Optimizing List>>appendList: ...done. Verifying ...done. Optimizing Collection>>sort ...done. Verifying ...done. Compiling machine code for MetaLink>>value:next: ...done. Compiling machine code for List>>add: ...done. Compiling machine code for List>>isEmpty ...done. Compiling machine code for List>>insert:onCondition: ...done. Compiling machine code for MetaList>>new ...done. Compiling machine code for Collection>>sort: ...done. Compiling machine code for Link>>do: ...done. Compiling machine code for List>>do: ...done. Compiling machine code for Collection>>insertSort: ...done. Compiling machine code for List>>popFirst ...done. Compiling machine code for List>>appendList: ...done. Compiling machine code for Collection>>sort ...done. All is done. Patched cold jit run: 7 Patched hot jit run: 6

ここで、どのように、そしてどのように最適化されるかについていくつかの言葉を言う必要があります。まず、パッチャーはメソッドの機能のみを渡します。ブロックは最適化されないままです。次に、メッセージ送信操作ごとにArrayクラスのインスタンスが作成され、メッセージ引数が配置されます。これにも時間がかかります。最後に、現在、インライン化メソッドは実際には使用されていません。これは、ユーティリティ関数（後で説明します）といくつかの簡単な構造のみに関係します。これにより、さらなる最適化の可能性は尽きることはない、と結論付けることができます。

コンパイルプロセス中およびプログラム実行中に何が起こるかをより詳細に理解するには、仮想マシンの内部キッチンを理解する必要があります。今何をしますか。

Smalltalk仮想マシン

仮想マシンはオブジェクトを操作します。操作は、オブジェクト間でメッセージを交換し、オブジェクトの背後にあるゴミを一掃することに削減されます。実際、仮想マシンが行う唯一の深刻な操作は、メッセージの送信です。他のすべては、何らかの形で、同じ前提に帰着します。

マシンがこれを行う方法を理解するには、まずSmalltalkオブジェクトとは何かを理解する必要があります。

オブジェクト

次の構造により、オブジェクトを簡素化できます。

 struct TObject { TSize size; TClass* klass; union { TObject* fields[0]; uint8_t bytes[0]; }; };

各オブジェクトには、オブジェクトのサイズとそのクラスへのポインターが記録される見出しがあります。以下は、他のオブジェクトへのポインタを含むオブジェクトフィールドです。もちろん、クラスもフィールドもオブジェクトであるため、同じ構造で表されます。

Smalltalkのすべてのオブジェクトは4バイトの倍数です。このサイズはゼロオフセットで格納され、下位2ビットは特別な役割を果たします。バイナリ（B）および間接（I）フラグが格納されます。フラグBは、オブジェクトがバイナリであることを意味します。つまり、通常のオブジェクトのフィールド用に予約された場所に未加工のバイトセットを格納します。このようなオブジェクトは、たとえば、ライン（インスタンスString）です。インスタンスに保存されているメソッドバイトコードByteArray、これもバイナリオブジェクトです。バイナリオブジェクトには、常にバイトが複数の長さまで埋め込まれます。フラグIは、既に処理されたオブジェクトをマークするためにヒープを通過するときに、ガベージコレクターによって使用されます。

したがって、オブジェクトのサイズに対して30ビットが残ります。通常のオブジェクトの場合、サイズはフィールド（4バイトの倍数）、バイナリの場合-バイトで計算されます。両方のオブジェクトには同じ既知の見出しがあるため、合計サイズではそのサイズは考慮されません。

SmallInt

すべてのオブジェクトは、4バイトで整列されたメモリに配置されます。したがって、アドレスの下位2ビットは常に0になります。この事実は、オブジェクトのフィールドに最大31ビット長の数値を直接格納するために使用されます。この場合、記録された数値は2倍され（左に1ビットシフト）、下位ビットは1に設定されます。仮想マシンはこの最適化を認識し、フィールドにアクセスするすべての場所で、オブジェクトポインターが実際に格納されているかどうかを確認しますまたは、この情報は数字として解釈する必要があります。

この点は、システムの他の部分に対して完全に透過的であることに注意することが重要です。アプリケーションプログラマは、何が、どこに、どのように保存されているかを知る必要はありません。たとえば、コンソールでコマンドを記述し1 class、期待される応答を取得することは完全に合法ですSmallInt、画像内のこの単位はまさにそのような「オブジェクト」によって表されますがSmallInt。

この小さなトリックは、バイナリ表現よりも1ビットだけ多くを使用して数値を書き込むため、消費されるメモリの量を大幅に削減できます。ボクシングが使用される場合、各番号に対して、4バイトのオブジェクトポインターに加えて、ヘッダーの別の8バイトと実際のデータの4バイトが格納されます。最善の選択肢ではないようです。

メッセージ

前の記事ですでに説明したように、メッセージはレシーバーオブジェクト、セレクター、パラメーターセットです。メッセージの送信と関数の呼び出しの重要な違いは、最後の瞬間まで誰が実際にメッセージを処理するかわからないことです。オブジェクトのみが知られています-メッセージの受信者。

メッセージの送信は、メッセージを処理できるクラスの階層内の検索から始まります。検索は、オブジェクトの直接のクラスから、階層を上って、最大で実行されます。Object。大量のメモリアクセスを行う必要があるため、これはかなり高価な操作であると言わなければなりません。したがって、検索結果はキャッシュされます。したがって、完全な検索は一度だけ実行する必要があります。メソッドキャッシュがフラッシュされるのは、次のガベージコレクション（メソッドオブジェクトが移動する可能性がある）と次のメソッドが追加または削除される（階層に影響する）場合の2つだけです。ガベージコレクション中のキャッシュの定期的なクリーニングを考慮しても、ヒットの割合は非常に高いまま（約99％）であるため、メソッドの検索に費やされる時間は平均的には重要ではないと考えられます。

オブジェクト'Hello world'（クラスインスタンスString）にメッセージを送信する場合の検索の様子を見てみましょう#isNil。

検索は次のように実行されます。

hash(String, #isNil);
, ;
, String :
methods , ( Dictionary ) .
: ;
;
;
, , , ; ;
, :
( nil ), 4;
, .

メソッドがクラス階層で一度も見つからなかった場合、仮想マシンは、#doesNotUnderstand:処理されることが保証される（少なくとも実際のものではObject）オブジェクトにメッセージを送信します。場合によっては、クラスはこのメッセージを意図的にインターセプトして特定の目標を達成します。たとえば、プロキシオブジェクトはこれを実行でき、メッセージは有効なアドレスに配信されます。

上記のメッセージの場合はString>>isNil、検索文字列は、次のようになります。
String→ Array→ Collection→ Magnitude→ Object。

メソッドが見つかった後、仮想マシンはコンテキストオブジェクトを作成してデータを入力し、メソッドに進みます。

コンテキスト

コンテキストの概念は、メッセージを送信する操作と密接にリンクしています。

x86などの従来のプロセッサアーキテクチャには、コールスタックの概念が存在します。関数が呼び出されると、戻りアドレスとともに渡されたパラメーターがスタックにプッシュされ、その後関数本体への遷移が実行されます。それぞれ関数を終了すると、スタックの最上部から戻りアドレスが削除されます。スタック上の各関数には、スレッドが開始されてから現在の関数呼び出しまでの遷移の「階層」全体が存在することがわかります。

Smalltalkでは、すべてが異なって行われます。単一の呼び出しスタックはありません。代わりに、メッセージが送信されるたびにコンテキストオブジェクトが生成されます。、この特定のパッケージに関連する情報を保存します。メソッド本体自体を実行する場合、仮想マシンは同じオブジェクトを使用します。これは次のようなものです。

 struct TContext : public TObject { TMethod* method; TObjectArray* arguments; TObjectArray* temporaries; TObjectArray* stack; TInteger bytePointer; TInteger stackTop; TContext* previousContext; };

方法 -ここでは、メッセージを処理する以前の方法を発見したオブジェクトへのポインタを置きました。
arguments-質量（インスタンスArray）へのポインターがここに格納され、渡された引数が保存されます。
temporaries-一時メソッド変数のストレージ。特に、| |メソッドヘッダー内の文字の間に書き込まれるもの。
stack — . . . , . .
bytePointer — ; IP . . .
stackTop — .
previousContext-ここでは、メッセージが送信されたメソッドから、親コンテキストのみが保存されます。現在のメソッドから値を返すと、その値は親スタックの一番上に配置されます。

いつでも、コンテキストにはメソッド実行の現在の状態に関するすべての情報があります。これにより、メソッドの実行を簡単に中断して（たとえば、割り当てられたティック数の有効期限が切れた後）、後で戻ることができます。たとえば、継続の実装など、エキゾチックなユースケースがまだあります。

方法

メソッドは、次の形式のオブジェクトで表されます。

 struct TMethod : public TObject { TSymbol* name; TByteObject* byteCodes; TSymbolArray* literals; TInteger stackSize; TInteger temporarySize; TClass* klass; TString* text; TObject* package; };

name-メソッドの実際の名前、またはこの名前のシンボルへのポインター。
byteCodes — ByteArray , - .
literals — . : , , . , .
stackSize — (. TContext::stack), .
temporarySize — , . .
klass — , .
text — .
パッケージはこのメソッドのカテゴリです。ユーザーインターフェイスに表示されるメソッドのリストをフィルター処理するように設計されています。現在使用されていません。

メソッドオブジェクトは、プライマリイメージがImageBuilderを使用してソースimageSource.stからコンパイルされ、結果のイメージファイルに保存されるときに形成されます。また、コマンドラインからコマンドを実行すると、1回限りのメソッドが作成されます。実際、コマンドラインテキストはメソッドの本文として解釈され、通常の方法でコンパイルされて呼び出されます。

このようにします。メソッドの本体にUndefined>>mainコードがあります：

 [ command <- String readline: '->'. command notNil ] whileTrue: [ command isEmpty ifFalse: [ command doIt printNl ] ]

まず、readlineライブラリを使用して、コマンドラインを取得します。次に、メッセージが文字列オブジェクトに送信され#doIt、その結果が画面に表示されます。メソッド自体は#doIt次のとおりです。

 doIt | method | method <- Undefined parseMethod: 'doItCommand ^ ' + self. ^ method notNil ifTrue: [ ^ Context new perform: method withArguments: (Array new: 1) ]

すべての魔法は、ここでイメージテキストに実装されたコンパイラを使用して、Undefined>>parseMethod:ソーステキスト#doItCommandからメソッドオブジェクトを形成するメソッドで作成されます。Smalltalkは、Smalltalk自体で書かれたコンパイラを使用して独自のメソッドをコンパイルします。Smalltalkはイメージの不可欠な部分です。この瞬間はとても面白いと思います。

メソッドオブジェクトが作成されると、コンテキストオブジェクトが作成されて呼び出され、作成されたメソッドが実行されます。新しいメソッドはどのクラスのメソッドリストにも追加されていないため、実行時（次のガベージコレクションまで）にのみ存在します。

仮想マシンの指示

仮想マシンは、メソッドのフレームワーク内でのみ命令を実行できます。コードメソッドの外側には存在しません。命令は、クラスインスタンスのbyteCodesフィールドに格納されますMethod。さらに、インスタンス自体には、コンテキストオブジェクトを初期化するときにも使用される追加情報が含まれています（上記を参照）。

この記事はすでに大きく成長しているため、ここではバイトコードを表現するための形式について詳しく説明しません。1つの命令が1バイトまたは2バイトを占有できることに注意してください。

値スタックの説明

オブジェクトの1つを値スタックの一番上にプッシュするプッシュ命令もあります。命令コードとともに、整数パラメーターも指定されます。これは、対応するデータ構造からオブジェクトを選択するためのインデックスとして解釈されます。

pushArgument-現在のコンテキストの引数の配列からの引数。
pushInstance-現在のオブジェクトのフィールド。
pushTemporary-現在のコンテキストの変数の配列からの一時変数。
pushLiteral-このメソッドのリテラルの定数配列からのリテラル。

少し異なる動作をする他の2つの特別なプッシュ命令があります。

pushConstant — : SmallInt , 0-9 , nil , true false , Undefined , True False .
pushBlock — Block , - , . bytePointer .

また、いくつかの逆の操作があります。次の操作を使用すると、スタックから値を削除せずにフィールドと一時変数の値を変更できます。フィールドと変数は、オプションの整数パラメーターによってもインデックス化されます。

assignInstance-現在のオブジェクトフィールドの値をスタックの一番上に割り当てます。
assignTemporary-一時変数にスタックの一番上にある値を割り当てます。

引数とリテラルは両方ともメソッド呼び出しの一部として定数と見なされるため、それらの割り当て操作は存在しません。スタックから値を削除するために、別の操作（popTop）が提供されます。これについては、以下で説明します。

移行手順

もちろん、移行手順があります：

branchIfTrue — bytePointer , true .
branchIfFalse — , false .
branch — .

メッセージ送信手順は普遍的であり、どこにでも適用できますが、場合によっては、専用の実装を使用して処理を高速化します。そのような特殊なケースは、単項およびバイナリメッセージを送信する操作です。個別のsendUnary命令とsendBinary命令が提供されます。通常のメッセージはsendMessageによって送信されます。

メッセージを送信すると、引数がスタックにプッシュされ、その後markArguments Nステートメントが呼び出されます。スタックからN個の値を削除し、それらからオブジェクトを形成しますArray。次に、このオブジェクトへのポインタはスタックの一番上に戻ります。これは、作成されたコンテキストオブジェクトの引数フィールドを初期化するときに使用されます。

返品手順

遅かれ早かれ、何らかの方法でメソッドから戻る必要があります。これは、復帰指示を使用して行われます。主なものはstackReturnです。これは、スタックから値を削除して呼び出しコンテキストに渡し、メソッドの現在のコンテキストを停止します。

Smalltalkで任意の値を返すことに加えて、結果としてselfを返すことが非常に頻繁に必要です。したがって、このような操作用に独立したselfReturnステートメントが用意されています。

最後のreturnステートメントはblockReturnです、指で説明するのはかなり難しいです。基本的な考え方は、制御は親コンテキストにではなく、現在実行中のブロックの宣言を含むメソッドの親コンテキストに転送されます。この動作は、他の言語の例外スローメカニズムと比較できます。プログラムの特別な状況でのみ発生し、一般的なケースではプログラムの「通常の」実行に関係しない例外とは対照的に、blockReturnは仮想マシンの観点からは完全に通常の操作であり、一般的なコードで使用できます。

これは例を使用して表示するのが最も簡単です。これはメソッドテキストです。Collection>>at:ifAbsent:

 at: value ifAbsent: exceptionBlock self do: [ :element | element = value ifTrue: [ ^element ] ]. ^exceptionBlock value

^elementネストされたブロック自体の式は、blockReturnステートメントを使用してコンパイルされます。実際には、ブロックは現在のメソッドでは実行されませんが、より深いため、これが必要です。メソッドCollection>>at:ifAbsent:はmethodを呼び出し、Collection>>do:パラメーターとして外部ブロックを渡します。このメソッドは、コレクションの各要素をCollection>>do:呼び出しBlock>>value:て、パラメーターをブロックに渡します。そして、内部にBlock>>value:あるのはプリミティブ番号8だけで、これはすでにブロックコードの実行につながります。したがって、コードブロックは、戻り値を実行するために必要であることを決定するelementには、プログラムとそうであろう命令含まblockReturn先頭に制御を移し、超えてはCollection>>at:ifAbsent:メッセージの結果として目的の値を返す。ブロックの本体に立っている

すべての演算子^がblockReturnステートメントに変換されるわけではないことに注意してください。コンパイラは可能な限り、コードをより単純な命令に分解しようとします。実行メソッドの本体にブロックを埋め込み、ブロックの呼び出しを単純な命令遷移に置き換えます。この場合、blockReturnもstackReturnまたはselfReturnに置き換えられます。

特別な指示

上記の指示に加えて、いくつかの補助的な指示があります。これらには、popTopおよびdup命令が含まれます。1つ目は、プッシュ命令の1つを使用して（またはメッセージ送信の結果として仮想マシン自体によって）スタックの先頭から値を削除するだけです。通常、popTopはassignInstanceまたはassignTemporary命令の後に使用され、スタックから不要になった値を削除します。dup

命令は、名前から推測できるように、スタック上の値を複製し、まったく同じものを次に配置します。Smalltalkコンパイラは、この命令を使用して、条件付きの複雑な式を解析します。

メソッド実行

上記のように、実行はコンテキストオブジェクトの作成から始まります。その後、仮想マシンは最初の命令のバイトコードを抽出してデコードします。その後、マシンは、メッセージの送信またはジャンプ命令のいずれかに遭遇するまで、命令を1つずつ実行し始めます。メソッドの実行は、returnステートメントの1つが見つかるとすぐに終了します。

前回の記事ですでにおなじみのコレクションのソート方法に基づいて、メソッドの実行とJITコンパイラの動作を追跡します。

 ->Collection viewMethod: #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

そのような方法をコンパイルした結果は、指示書全体です。作業のロジックの詳細な説明はこの記事の範囲を超えているため、バイトコードを見て、どの部分が何に対応するかを理解してみてください。これは実際にはそれほど難しくありません。従来のアセンブラとは異なり、ここでは命令は非常に均一かつ一貫して使用されます。最初に、値スタックに将来の呼び出しのための引数が入力されます。次に、markArgumentsを使用して、特定のメッセージ送信操作ですでに使用されている引数の配列がそれらから形成されます。さて、移行の指示はこのすべての怒りを制御します。読みやすくするために、1つの前提に関連する命令ブロックを空白行で削除し、コメントを提供しました。

 ->Collection methods at: #sort:; disassemble "  " 0000 PushArgument 0 "    self" 0001 MarkArguments 1 0002 SendMessage size 0003 PushLiteral 1 "  1        32" 0004 SendBinary < " " 0005 DoSpecial branchIfFalse 16 "     " "  :" 0008 PushArgument 0 0009 PushArgument 1 0010 MarkArguments 2 0011 SendMessage insertSort: 0012 DoSpecial stackReturn 0013 DoSpecial branch 17 "   :" 0016 PushConstant nil " " 0017 DoSpecial popTop "mediane <- self popFirst" 0018 PushArgument 0 0019 MarkArguments 1 0020 SendMessage popFirst 0021 AssignTemporary 2 0022 DoSpecial popTop "left <- List new" 0023 PushLiteral 4 0024 MarkArguments 1 0025 SendMessage new 0026 AssignTemporary 0 0027 DoSpecial popTop "right <- List new" 0028 PushLiteral 6 0029 MarkArguments 1 0030 SendMessage new 0031 AssignTemporary 1 0032 DoSpecial popTop "self do: ..." 0033 PushArgument 0 0034 PushBlock " " 0037 PushArgument 1 "criteria" 0038 PushTemporary 3 "x" 0039 PushTemporary 2 "mediane" 0040 MarkArguments 3 0041 SendMessage value:value: "  " 0042 DoSpecial branchIfFalse 52 "left add: x" 0045 PushTemporary 0 0046 PushTemporary 3 0047 MarkArguments 2 0048 SendMessage add: 0049 DoSpecial branch 56 "right add: x" 0052 PushTemporary 1 0053 PushTemporary 3 0054 MarkArguments 2 0055 SendMessage add: 0056 DoSpecial stackReturn 0057 MarkArguments 2 0058 SendMessage do: 0059 DoSpecial popTop "  left" 0060 PushTemporary 0 0061 PushArgument 1 0062 MarkArguments 2 0063 SendMessage sort: 0064 AssignTemporary 0 0065 DoSpecial popTop "  right" 0066 PushTemporary 1 0067 PushArgument 1 0068 MarkArguments 2 0069 SendMessage sort: 0070 AssignTemporary 1 0071 DoSpecial popTop "right add: mediane" 0072 PushTemporary 1 0073 PushTemporary 2 0074 MarkArguments 2 0075 SendMessage add: 0076 DoSpecial popTop "  " 0077 PushTemporary 0 0078 PushTemporary 1 0079 MarkArguments 2 0080 SendMessage appendList: " " 0081 DoSpecial stackReturn "( )" 0082 DoSpecial popTop 0083 DoSpecial selfReturn

おわりに

...一般に、この記事でSmalltalk仮想マシンの内部デバイスについて説明したかったのはこれだけです。物語の形式には簡潔さが求められますが、理解を損なうためにこれを行うべきではありません。私はなんとか妥協点を見つけることができたと思います。

Smalltalkイメージでオブジェクトがどのように見えるか、数字がどのように表現されるか、メッセージを送信して適切なクラスを検索するアルゴリズムを理解し、コンテキストオブジェクトとは何かを学びました。最後に、仮想マシンの基本的な命令に精通し、既知のソート方法のコードと、コンパイラによって変換される命令を調べました。

では次の記事、SmalltalkメソッドをLLVMが理解できる中間IRコードにコンパイルする際のJITの問題について説明します。次に、実際のプロセッサ命令にコンパイルされます。メソッドのバイトコードを分析し、それらを最適な方法でIRに変換するために必要なことを理解しようとします。

最後に、小さな調査：

Llst内部パート2またはLittle Smalltalk + LLVM =♥