単相性はどれほど便利ですか？

JavaScriptのパフォーマンスとブログの投稿では、 単相コードの重要性が強調されることがよくありますが、通常、単相/多相とは何か、なぜ重要なのかについては明確な説明がありません。 私自身のスピーチでさえ、信じられないほどのハルクの二分法に帰着することがよくあります。 2種類の悪い！」 パフォーマンスに関するアドバイスを求められると、ほとんどの場合、モノモーフィズムとは何か、ポリモーフィズムはどこから来て、何が悪いのかを説明するように頼まれます。

「多型」という言葉自体が多くの意味を持っているという事実によって、状況は複雑になっています。 古典的なオブジェクト指向プログラミングでは、ポリモーフィズムは、基本クラスの動作をオーバーライドできる子クラスの作成に関連付けられています。 Haskellプログラマーは、代わりにパラメトリック多相性について考えるでしょう。 ただし、JavaScriptパフォーマンスレポートで警告されるポリモーフィズムは、関数呼び出しのポリモーフィズムです 。

このメカニズムを非常に多くの方法で説明したので、ようやく集まってこの記事を書きました。今では即興ではなく、単にリンクを張ることができます。

_{私はまた、物事を説明する新しい方法を試みました-短い漫画の形で仮想マシンのコンポーネントの相互作用を描いています。 さらに、この記事では、重要ではない、冗長である、または直接関連していないと見なした詳細については説明しません。}

ダミーの動的検索

簡単にするために、主にJavaScriptのプロパティへの最も基本的な呼び出し（以下のコードのoxなど）を検討します。 同時に、ここで説明していることはすべて、プロパティまたは算術演算子の呼び出しであるかどうかにかかわらず、 動的バインディングを使用するすべての操作に適用され、JavaScriptだけでなく適用できることを理解することが重要です。

 function f(o) { return ox } f({ x: 1 }) f({ x: 2 }) 

Interpretators LLCの優秀なポジションについてインタビューを受け、JavaScript仮想マシンのプロパティにアクセスするためのメカニズムを考えて実装するように求められます。 最も平凡で単純な答えは何でしょうか？

ECMAScript仕様（ECMA 262）から既製のJSセマンティクスを取得し 、英語の単語の[[Get]]アルゴリズムの単語をC ++、Java、Rust、Malbolge、または使用する他の言語に書き換えるよりも簡単なものを見つけるのは難しいインタビューのために。

一般的に、ランダムなJSインタープリターを開くと、次のようなものが表示される可能性が高くなります。

 jsvalue Get(jsvalue self, jsvalue property_name) { // 8.12.3    [[Get]] } void Interpret(jsbytecodes bc) { // ... while (/*    */) { switch (op) { // ... case OP_GETPROP: { jsvalue property_name = pop(); jsvalue receiver = pop(); push(Get(receiver, property_name)); // TODO(mraleph):    strict mode,    8.7.1  3. break; } // ... } } } 

これはプロパティ呼び出しを実装する絶対に正しい方法ですが、1つの重大な欠点があります。最新のJS仮想マシンと比較して、実装が非常に遅いです。

インタプリタは健忘症に悩まされます。プロパティにアクセスするたびに、プロパティを検索するための一般化されたアルゴリズム全体を実行する必要があります。 彼は以前の試みからは学ばず、毎回最高額を支払わざるを得ません。 したがって、パフォーマンス指向の仮想マシンはプロパティアクセスを異なる方法で実装します。


ここで、すでに見たオブジェクトに関する情報を取得して、それを同様のオブジェクトに適用できるようになったら！ 理論的には、これにより、一般的なアルゴリズムではなく、特定の形状のオブジェクトに最も適したアルゴリズムを使用することで、多くの時間を節約できます。

ランダムオブジェクト内のプロパティの検索は時間がかかる操作であるため、一度実行して、オブジェクトの形式をキーとして使用して見つかったパスをキャッシュすることをお勧めします。 次回同じ形状のオブジェクトに出会ったとき、最初から計算するよりもはるかに高速にキャッシュからパスを取得することが可能になります。

この最適化手法は、 インラインキャッシングと呼ばれ、 以前にそれについてすでに書いています。 この記事では、実装の詳細については説明しませんが、これまで言及しなかった2つの重要な点に注意します。他のキャッシュと同様に、インラインキャッシュにはサイズ （特定の時点でキャッシュされるアイテムの数）と容量 （アイテムの最大数、キャッシュできます）。

例に戻ります。

 function f(o) { return ox } f({ x: 1 }) f({ x: 2 }) 

oxインラインキャッシュにはいくつのエントリがありますか？

{x: 1}と{x: 2}は同じ形状（ 隠されたクラスと呼ばれることもある）であるため、答えは1です。monomorphicと呼ぶのはこのキャッシュ状態です。

_{モノ（ "one"）+モーフ（ "form"）}






しかし、異なる形状のオブジェクトで関数fを呼び出すとどうなりますか？

 f({ x: 3 }) //  ox    f({ x: 3, y: 1 }) //  ? 

オブジェクト{x: 3}と{x: 3, y: 1}は形状が異なるため、キャッシュには{x: *}用と{x: *, y: *}用の2つのエントリが含まれています。 操作はポリモーフィズムレベル2でポリモーフィックになりました。

さまざまな形状のオブジェクトをfに転送し続けると、インラインキャッシュの容量制限に達するまでポリモーフィズムのレベルが増加します（たとえば、V8では、プロパティにアクセスするための容量制限は4になります）。 その後、キャッシュはメガモーフィック状態になります。

 f({ x: 4, y: 1 }) // ,  2 f({ x: 5, z: 1 }) // ,  3 f({ x: 6, a: 1 }) // ,  4 f({ x: 7, b: 1 }) //  

キャッシュが制御不能に成長するのを防ぐために、メガモーフィック状態が必要であり、本質的には「フォームが多すぎるため、さらに追跡するのは無意味です」という意味です。 V8仮想マシンでは、メガモーフィック状態のキャッシュは引き続き何かをキャッシュできますが、ローカルではなくグローバルハッシュテーブルにキャッシュできます。 サイズは固定されており、衝突が発生した場合、値は上書きされます。




理解度をテストするための小さな演習：

 function ff(b, o) { if (b) { return ox } else { return ox } } ff(true, { x: 1 }) ff(false, { x: 2, y: 0 }) ff(true, { x: 1 }) ff(false, { x: 2, y: 0 }) 

1. ff関数で宣言されているインラインプロパティアクセスキャッシュはいくつですか？
2. 彼らはどのような状態ですか？

パフォーマンスへの影響

この段階で、さまざまなインラインキャッシュ状態のパフォーマンスが明らかになります。

• 毎回キャッシュから値にアクセスすると、単相が最速です（ ONE TYPE GOOD！ ）
• 多態性-キャッシュ値間の線形検索
• Megamorphic-グローバルハッシュテーブルへのアクセス。 最も遅いキャッシュオプションですが、キャッシュミスよりも高速です
• キャッシュミスは、キャッシュにないフィールドへのアピールです。 ランタイムへの切り替えと最も一般的なアルゴリズムの使用に料金がかかります

実際、これは真実の半分に過ぎません：直接的なコードアクセラレーションに加えて、インラインキャッシュは全能の最適化コンパイラーのサービスでスパイとしても機能します。これは遅かれ早かれ、コードをさらに高速化します。

仕様と最適化

インラインキャッシュは、次の2つの理由で単独で最大のパフォーマンスを提供することはできません。

• 各インラインキャッシュは独立して動作し、ネイバーについては何も知りません
• 各インラインキャッシュはミスする可能性があるため、ランタイムを使用する必要があります。最終的には、一般化された副作用を伴う一般化された操作であり、戻り値のタイプでさえ不明であることがよくあります。

 function g(o) { return ox * ox + oy * oy } g({x: 0, y: 0}) 

上記の例では、7つのインラインキャッシュがあります.xに2つ、 .yに2つ、 * 2つ、 + 1つです。 それぞれが独立して動作し、オブジェクトがキャッシュされたフォームに準拠しているかどうかをチェックします。 +演算子の算術キャッシュは、両方のオペランドが数値であるかどうかをチェックしますが、これは*演算子キャッシュの状態から推測できます。 さらに、V8には数値の内部表現がいくつかあるため、これも考慮されます。

JSの一部の算術演算には、固有の特定のタイプがあります。たとえばa | 0 a | 0常に32ビット整数を返し、 +aは単なる数字ですが、他のほとんどの操作ではそのような保証はありません。 このため、JS用のAOTコンパイラーを作成するのは非常に困難です。 JSコードを事前に一度コンパイルする代わりに、ほとんどのJS仮想マシンにはいくつかの実行モードがあります。

たとえば、V8は最初にすべてを通常のコンパイラでコンパイルし、すぐに実行を開始します。 後で、頻繁に使用される関数は最適化を使用して再コンパイルされます。 一方、Asm.jsは暗黙的なタイプの操作を使用し、その助けを借りて、静的型付けを使用したJavascriptの非常に厳密に限定されたサブセットを記述します。 そのようなコードは、アダプティブコンパイルを推測することなく、起動前でも最適化できます。

コードを「ウォームアップ」するには、次の2つの目的が必要です。

• 起動遅延を削減：最適化コンパイラは、コードが十分に使用されている場合にのみオンになります
• インラインキャッシュは、オブジェクトのフォームに関する情報を収集します。

上記のように、人々のJavaScriptコードには通常、完全に静的に入力してAOTコンパイルするのに十分な情報が含まれていません。 JITコンパイラは、プログラムの動作を推測し、特定の仮定の下でのみ適切な最適化コードを生成する必要があります。 つまり、最適化された関数で使用されるオブジェクトを知る必要があります。 幸運なことに、これはまさにインラインキャッシュが収集する情報です。

• 単相キャッシュには、「タイプA のみが表示されました」と表示されます
• ポリモーフィックキャッシュには、「タイプA ₁ 、...、A _N しか見ていません 」
• メガモーフィックキャッシュ：「はい、たくさん見ました...」

最適化コンパイラは、インラインキャッシュによって収集された情報を分析し、そこから中間表現 （ IR ）を構築します。 IR命令は通常、JSでの操作よりも具体的で低レベルです。 たとえば、 .xプロパティにアクセスするためのキャッシュが{x, y}形式のオブジェクトのみを見た場合、コンパイラはオブジェクトへのポインタから固定オフセットで値を受け取るIR命令を生成できます。 もちろん、着信オブジェクトにこの最適化を使用することは安全ではないため、コンパイラはその前に型チェックも追加します。 型チェックは、オブジェクトの形状と予想される形状を比較し、それらが異なる場合、最適化されたコードを実行できません。 代わりに、最適化されていないコードが呼び出され、そこから実行が継続されます。 このプロセスは最適化解除と呼ばれます 。 最適化が解除される唯一の理由は、タイプの不一致だけではありません。 また、32ビット数の算術演算が「シャープ化」され、前の演算の結果がオーバーフローを引き起こした場合、または存在しない配列インデックスarr[idx] （範囲外、隙間のある疎配列など）にアクセスした場合にも発生します。 。）。


上記の欠点を解消するには最適化が必要であることが明らかになります。

最適化されていないコード	最適化されたコード
各操作には未知の副作用があり、完全なセマンティクスを実装します。	コードの特殊化は不確実性を排除または制限し、副作用は厳密に知られています（たとえば、オフセットによるプロパティの呼び出しにはそれらがありません）
各操作は独自に行われ、独立して学習し、経験を隣人と共有しません	操作は、一緒に最適化される低レベルのIR命令に分解され、冗長性が排除されます。

もちろん、特定の形式のオブジェクト用にIRを構築することは、最適化チェーンの最初のステップにすぎません。 中間表現が形成されると、コンパイラはそれを数回調べて、不変式を検出し、余分な部分を切り取ります。 このタイプの分析は通常、プロシージャの範囲に制限されており、コンパイラーは各呼び出しで考えられる最悪の副作用を考慮することを余儀なくされます。 呼び出しは、指定されていない操作で非表示にできることに注意してください。たとえば、 +演算子はvalueOfを呼び出すことができ、プロパティにアクセスするとそのゲッターメソッドが呼び出されます。 したがって、最初の段階で操作を指定できなかった場合、オプティマイザーの後続のすべてのパスはその操作でつまずきます。

冗長な命令の最も一般的なタイプの1つは、同じオブジェクトが同じ形状であることを常にチェックすることです。 これは、最初の中間表現が上記の例から関数g探す方法です。

  CheckMap v0, {x,y} ;; shape check v1 Load v0, @12 ;; load ox CheckMap v0, {x,y} v2 Load v0, @12 ;; load ox i3 Mul v1, v2 ;; ox * ox CheckMap v0, {x,y} v4 Load v0, @16 ;; load oy CheckMap v0, {x,y} v5 Load v0, @16 ;; load oy i6 Mul v4, v5 ;; oy * oy i7 Add i3, i6 ;; ox * ox + oy * oy 

ここでは、変数v0オブジェクトの形状が4回チェックされますが、チェックの間に変更を引き起こす可能性のある操作はありません。 気配りのある読者は、 v2とv5ロードも冗長であることに気付くでしょう。コードが上書きされないためです。 幸いなことに、その後のグローバル番号付けのパスにより、これらの指示が削除されます。

 ;;   CheckMap v0, {x,y} v1 Load v0, @12 i3 Mul v1, v1 v4 Load v0, @16 i6 Mul v4, v4 i7 Add i3, i6 

上記のように、これらの命令間に副作用のある操作がなかったために、これらの命令を削除することが可能になりました。 ダウンロードv1とv2間に呼び出しがあった場合、 v0のオブジェクトの形状を変更できると想定する必要があるため、 v2の形式の確認は必須です。

操作が単相ではない場合、コンパイラは上記の例と同じ「フォームの検証と具体化された操作」の束を単純にとることはできません。 インラインキャッシュには、いくつかのフォームに関する情報が含まれています。 それらのいずれかを使用して、それだけを結び付けると、残りはすべて最適化解除につながりますが、これは望ましくありません。 代わりに、コンパイラは決定木を構築します 。 たとえば、 oxプロパティにアクセスするインラインキャッシュがフォームA、B、Cのみにox場合、展開された構造は次のようになります（これは擬似コードです。実際、 制御フローグラフが構築されます）。

 var o_x if ($GetShape(o) === A) { o_x = $LoadByOffset(o, offset_A_x) } else if ($GetShape(o) === B) { o_x = $LoadByOffset(o, offset_B_x) } else if ($GetShape(o) === C) { o_x = $LoadByOffset(o, offset_C_x) } else { //  ox   A, B, C //   ,  **     $Deoptimize() } //     ,  o   //   - A, B  C.     , //   

モノモーフィックコールには、ポリモーフにはない非常に便利なプロパティが1つあります。副作用を伴う次の操作まで、オブジェクトの形状が変更されないことが保証されます。 ポリモーフィック処理は、「オブジェクトがいくつかの形式の1つを持っている」という弱い保証のみを提供し、最適化はほとんどできません（最適な場合、最後の比較と最適化解除のブロックを削除することは可能ですが、V8はそれを行いません）。

一方、V8は、フィールドがすべてのフォームで同じオフセットにある場合、効果的な中間表現を形成できます。 この場合、ポリモーフィックフォーム検証が使用されます。

 // ,       A, B  C -   $TypeGuard(o, [A, B, C]) //  ,        var o_x = $LoadByOffset(o, offset_x) 

2つのポリモーフィックチェックの間に副作用のある操作がない場合、モノモーフィックチェックの場合のように、2番目のポリモーフィックチェックも不要として削除できます。

インラインキャッシュがオブジェクトの可能な形式についてコンパイラに情報を渡すと、コンパイラはグラフ内で不適切に分岐することにより、各オブジェクトに対して何をすべきかを判断できます。 この場合、わずかに異なるグラフが生成され、最終的には最適化解除ではなく、一般化された操作が行われます。

  var o_x if ($GetShape(o) === A) { o_x = $LoadByOffset(o, offset_A_x) } else if ($GetShape(o) === B) { o_x = $LoadByOffset(o, offset_B_x) } else if ($GetShape(o) === C) { o_x = $LoadByOffset(o, offset_C_x) } else { //  ,    ox . //      //   : o_x = $LoadPropertyGeneric(o, 'x') // ^^^^^^^^^^^^^^^^^^^^    } //       "" //    ,   //    

場合によっては、コンパイラは操作を指定するという考えを完全に放棄する場合があります。

• 効果的に具体化する方法はありません
• 操作はポリモーフィックであり、コンパイラは決定ツリーの構築方法を知りません（これは以前にarr[i]ポリモーフィック呼び出しで発生しましたが、すでに修正されています）
• 操作をインスタンス化できる型に関する情報はありません（コードが実行されたことがない、ガベージコレクターがフォームに関する収集された情報を削除したなど）

これらの（かなりまれな）場合、コンパイラは中間表現の一般化バージョンを生成します。

パフォーマンスへの影響

その結果、次のことができます。

• 単相操作は最も簡単に最適化され、オプティマイザーにアクションの余地を与えます。 ハルクが言うように-「 鉄に近いタイプ！ 」
• フォーム検証を必要とする低レベルのポリモーフィズム、または単相よりも遅い決定ツリーを使用した操作：
  
  • 決定木は実行の流れを複雑にします。 コンパイラが型情報を配布し、不要な命令を削除することはさらに困難です。 条件付きツリーの遷移も、ロードされたサイクルに陥ると、パフォーマンスを損なう可能性があります。
  • ポリモーフィックフォームチェックは最適化をそれほど妨げず、いくつかの冗長な命令を削除できますが、モノモーフィックな命令よりも遅くなります。 パフォーマンスへの影響は、プロセッサが条件分岐をどの程度処理するかによって異なります。
• メガモーフィックまたは高度なポリモーフィックな操作はまったく指定されておらず、中間表現では呼び出しが行われ、CPUの最適化とパフォーマンスに対するすべての結果が生じます。

_{翻訳者のメモ：著者はマイクロベンチマークへのリンクを提供しましたが、サイト自体は機能しなくなりました。}

非共有

この記事があまりにも広範にならないように、意図的にいくつかの実装の詳細には触れませんでした。

フォーム

フォーム（または非表示のクラス）の配置方法、計算方法、オブジェクトへの割り当て方法については説明しませんでした。 一般的なアイデアは、AWP2014での 以前の記事またはプレゼンテーションから入手できます。

JS仮想マシンの「フォーム」の概念そのものがヒューリスティックな近似であることを覚えておく必要があります。 人の視点から見た場合、2つのオブジェクトの形状は同じであっても、機械の視点から見ると異なる場合があります。

 function A() { this.x = 1 } function B() { this.x = 1 } var a = new A, b = new B, c = { x: 1 }, d = { x: 1, y: 1 } delete dy // a, b, c, d -     V8 

JSのオブジェクトは辞書として気楽に実装されているため、ランダムポリモーフィズムを適用できます。

 function A() { this.x = 1; } var a = new A(), b = new A(); //   if (something) { ay = 2; //  a      b } 

意図的な多型

作成されたオブジェクトの形状を変更できない多くの言語（Java、C＃、Dart、C ++など）では、ポリモーフィズムもサポートされています。 インターフェイスに基づいて特定の実装に応じて実行されるコードを記述する機能は、非常に重要な抽象化メカニズムです。 静的に型付けされた言語では、ポリモーフィズムは同様の方法でパフォーマンスに影響します。

当然のことながら、JVMはインラインキャッシュを使用してinvokeinterfaceおよびinvokevirtualを最適化しinvokevirtual 。

すべてのキャッシュが同じように役立つわけではありません。

一部のキャッシュはオブジェクトの形式に基づいていない、および/または他のキャッシュよりも容量が少ないことに留意してください。 たとえば、関数呼び出しのインラインキャッシュには、初期化されていない、単相、または大形の3つの状態しかありません。 関数を呼び出すためにオブジェクトの形状は重要ではありませんが、関数オブジェクト自体はキャッシュされるため、中間のポリモーフィック状態はありません。

  function inv(cb) { return cb(0) } function F(v) { return v } function G(v) { return v + 1 } inv(F) // - ,   F inv(G) // -   

関数がinv最適化され、インラインキャッシュが単相状態にある場合、オプティマイザーは関数の本体を呼び出しの場所に埋め込むことができます（これは、頻繁に呼び出される場所の短い関数にとって特に重要です）。キャッシュがメガモーフィック状態にある場合、オプティマイザーはどの関数のどのボディを埋め込むことができるかを知らないため、一般化された呼び出し演算子は中間表現のままになります。

一方、次の形式のメソッドの呼び出しom(...)プロパティ参照のように機能します。メソッド呼び出しのインラインキャッシュは、中間のポリモーフィック状態を持つこともできます。 V8仮想マシンは、プロパティと同じ方法で、そのような関数への呼び出しを単相、多相、さらにはメガモルフィック形式で埋め込むことができます。唯一の制限があります：メソッドはオブジェクトの形式で含まれる必要があります。

_{実際、om(...)一度に2つのインラインキャッシュを使用します。1つはプロパティをロードし、もう1つは関数を直接呼び出すために使用します。関数の上記の例のように、2番目には2つの状態しかありませんcb。したがって、その状態は呼び出しの最適化中に無視され、プロパティにアクセスするインラインキャッシュの状態のみが使用されます。}

  function inv(o) { return o.cb(0) } var f = { cb: function F(v) { return v }, }; var g = { cb: function G(v) { return v + 1 }, }; inv(f) inv(f) // -   , //     f inv(g) //    ,   //  f    g 

上記の例fでgは、形状が異なることは予想外のように思われるかもしれません。これは、関数をオブジェクトプロパティに割り当てると、V8は（可能であれば）オブジェクト自体ではなくオブジェクトのフォームにアタッチしようとするためです。上記の例でfはformが{c: F}あり、フォーム自体はクロージャーを参照しています。このフォームの前のすべての例には、特定のプロパティの存在の兆候のみが含まれていました。この場合、その値は保持され、フォームはJavaやC ++などの言語のクラスに似たものになります。

もちろん、後でプロパティを別の関数で上書きすると、V8はクラスとメソッドの関係とは見えなくなると見なし、フォームが変更されます。

 var f = { cb: function F(v) { return v }, }; //  f  {cb: F} f.cb = function H(v) { return v - 1 } //  f  {cb: *} 

V8がオブジェクトのフォームをどのように構築および維持するかについては、別の大きな記事を書く価値があります。

プロパティへのパスの表現

この時点で、プロパティにアクセスするインラインキャッシュはox、クラス内の形状やオフセットを比較する辞書のようDictionary<Shape, int>です。実際、そのような表現は深さを伝えません。プロパティは、プロトタイプチェーン内のオブジェクトの1つに属している場合や、アクセスメソッドを持つ場合があります。明らかに、ゲッターセッターを持つプロパティは、データを持つ通常のプロパティよりも特定性が低いと見なされます。

たとえば、オブジェクトo = {x: 1}は、仮想マシンのメソッドを使用して、プロパティが特別な非表示スロットに値をロードおよび保存するオブジェクトとして表すことができます。

 // ,  o = { x: 1 } var o = { get x () { return $LoadByOffset(this, offset_of_x) }, set x (value) { $StoreByOffset(this, offset_of_x, value) } // /    //     JS- }; $StoreByOffset(o, offset_of_x, 1) 

_{ところで、プロパティはDart VMでほぼこのように実装されています。}

このように見れば、Dictionary<Shape, Function>フォームをアクセサー関数と比較することで、インラインキャッシュがフォームに表示される可能性が高くなります。オフセットのある素朴な表現とは異なり、プロトタイプチェーン、ゲッターセッター、ES6のプロキシオブジェクトのプロパティを記述することができます。

準単相条件

V8の一部のインラインキャッシュには、premonomorphicと呼ばれる別の状態があります。一度だけアクセスされるキャッシュのコードをコンパイルしません。あまり知られていない実装機能であるため、この条件については言及しませんでした。

最終的なパフォーマンスのヒント

最高のパフォーマンスのヒントは、デイルカーネギーの本「How to Stop Worrying and Start Living」のタイトルから引用できます。

実際、多型を心配することは通常無意味です。代わりに、通常のデータを使用してコードを実行し、プロファイラーでボトルネックを探します。JSに関連する場合は、コンパイラーが生成する中間表現を確認する必要があります。

そして、ロードされたサイクルの途中で、名前の下に命令が表示されるXYZGenericか、何かが属性でマークされている場合changes [*]（つまり、「すべてを変更する」）、それから（そしてその後のみ）心配し始めることができます。