V8におけるマップ（Hidden Classes）

V8がどのようにHidden Classesを構築するかを見ていきましょう。主要なデータ構造は以下のとおりです。

Map: Hidden Classそのもの。オブジェクト内の最初のポインタ値であり、そのため、2つのオブジェクトが同じクラスを持っているかどうかを簡単に比較できます。
DescriptorArray: このクラスが持つプロパティの完全なリストとその情報。場合によっては、プロパティ値はこの配列内にあります。
TransitionArray: このMapから兄弟Mapへの「エッジ」の配列。各エッジはプロパティ名であり、「現在のクラスにこの名前のプロパティを追加すると、どのクラスに遷移するか？」と考えるべきです。

多くのMapオブジェクトは、別のオブジェクトへの遷移を1つしか持たない（つまり、それらは「遷移」マップであり、他のものへの途中で使用されるだけである）ため、V8は常に完全なTransitionArrayを作成するわけではありません。代わりに、この「次の」Mapに直接リンクします。システムは、遷移に関連付けられた名前を把握するために、ポイントされているMapのDescriptorArrayを少し探査する必要があります。

これは非常に奥深いテーマです。また、変更される可能性がありますが、この記事の概念を理解していれば、将来の変更も段階的に理解できるはずです。

なぜHidden Classesが必要なのか？ #

確かに、V8はHidden Classesなしでも動作します。その場合、各オブジェクトはプロパティの集合として扱われます。しかし、非常に有用な原則、つまりインテリジェントデザインの原則が見過ごされてしまいます。V8は、開発者がそれほど多くの**異なる**種類のオブジェクトを作成しないと推測します。そして、それぞれの種類のオブジェクトは、最終的には定型的な方法で使用されるようになります。JavaScriptはスクリプト言語であり、事前にコンパイルされる言語ではないため、「最終的にわかる」と言います。そのため、V8は次に何が来るのかを事前に知ることはありません。インテリジェントデザイン（つまり、入力されるコードの背後に意図があるという仮定）を利用するために、V8は監視と待機を行い、構造の感覚を浸透させる必要があります。Hidden Classメカニズムは、これを行うための主要な手段です。もちろん、これは洗練されたリスニングメカニズムを前提としており、これらはインラインキャッシュ（IC）であり、多くのことが書かれています。

これが優れた必要な作業であると確信できたなら、私に従ってください！

例 #

function Peak(name, height, extra) {
  this.name = name;
  this.height = height;
  if (isNaN(extra)) {
    this.experience = extra;
  } else {
    this.prominence = extra;
  }
}

m1 = new Peak("Matterhorn", 4478, 1040);
m2 = new Peak("Wendelstein", 1838, "good");

このコードでは、関数Peakにアタッチされているルートマップ（初期マップとも呼ばれます）から、すでに興味深いマップツリーが得られています。

各青いボックスはマップであり、初期マップから始まります。これは、どういうわけか、プロパティを1つも追加せずに関数Peakを実行できた場合に返されるオブジェクトのマップです。後続のマップは、マップ間のエッジに示されている名前のプロパティを追加した結果です。各マップには、そのマップのオブジェクトに関連付けられたプロパティのリストがあります。さらに、各プロパティの正確な場所が記述されています。最後に、これらのマップの1つ、たとえば、Peak()のextra引数に数値を渡した場合に取得するオブジェクトのHidden ClassであるMap3から、初期マップまでバックリンクをたどることができます。

この追加情報を使用して、もう一度描いてみましょう。注釈（i0）、（i1）は、オブジェクト内フィールドの場所0、1などを意味します。

さて、少なくとも7つのPeakオブジェクトを作成する前にこれらのマップを調べると、**スラック追跡**が発生し、混乱する可能性があります。それについては別の記事があります。さらに7つのオブジェクトを作成するだけで完了です。この時点で、Peakオブジェクトはオブジェクト内に直接追加できない、オブジェクト内に正確に3つのプロパティを持ちます。追加のプロパティは、オブジェクトのプロパティバッキングストアにオフロードされます。これは単なるプロパティ値の配列であり、そのインデックスはマップ（正確には、マップにアタッチされているDescriptorArray）から取得されます。新しい行でm2にプロパティを追加し、マップツリーをもう一度見てみましょう。

m2.cost = "one arm, one leg";

ここに何かを忍び込ませました。すべてのプロパティに「const」という注釈が付いていることに注意してください。これは、V8の観点からは、コンストラクター以降誰も変更していないため、初期化されると定数と見なすことができることを意味します。TurboFan（最適化コンパイラ）はこれを好みます。m2が関数によって定数グローバルとして参照されているとします。フィールドは定数としてマークされているため、m2.costのルックアップはコンパイル時に行うことができます。この記事の後半でこれに戻ります。

プロパティ「cost」はconst p0としてマークされていることに注意してください。これは、オブジェクト内に直接ではなく、**プロパティバッキングストア**のインデックスゼロに格納されている定数プロパティであることを意味します。これは、オブジェクトにこれ以上スペースがないためです。この情報は%DebugPrint(m2)で確認できます。

d8> %DebugPrint(m2);
DebugPrint: 0x2f9488e9: [JS_OBJECT_TYPE]
 - map: 0x219473fd <Map(HOLEY_ELEMENTS)> [FastProperties]
 - prototype: 0x2f94876d <Object map = 0x21947335>
 - elements: 0x419421a1 <FixedArray[0]> [HOLEY_ELEMENTS]
 - properties: 0x2f94aecd <PropertyArray[3]> {
    0x419446f9: [String] in ReadOnlySpace: #name: 0x237125e1
        <String[11]: #Wendelstein> (const data field 0)
    0x23712581: [String] in OldSpace: #height:
        1838 (const data field 1)
    0x23712865: [String] in OldSpace: #experience: 0x237125f9
        <String[4]: #good> (const data field 2)
    0x23714515: [String] in OldSpace: #cost: 0x23714525
        <String[16]: #one arm, one leg>
        (const data field 3) properties[0]
 }
 ...
{name: "Wendelstein", height: 1, experience: "good", cost: "one arm, one leg"}
d8>

4つのプロパティがあり、すべてconstとしてマークされています。最初の3つはオブジェクト内にあり、最後はproperties[0]にあります。これは、プロパティバッキングストアの最初のスロットを意味します。それを見ることができます

d8> %DebugPrintPtr(0x2f94aecd)
DebugPrint: 0x2f94aecd: [PropertyArray]
 - map: 0x41942be9 <Map>
 - length: 3
 - hash: 0
         0: 0x23714525 <String[16]: #one arm, one leg>
       1-2: 0x41942329 <undefined>

追加のプロパティは、突然さらに追加する場合に備えて用意されています。

実際の構造 #

この時点でできることはいくつかありますが、ここまで読んだということはV8がとても好きでなければならないので、私たちが使用する実際のデータ構造、つまりMap、DescriptorArray、TransitionArrayの冒頭で述べたものを描いてみたいと思います。Hidden Classの概念が舞台裏でどのように構築されているかについて、ある程度のアイデアが得られたので、正しい名前と構造を通じて、思考をコードにより密接に結び付けることができます。V8の表現で最後の図を再現してみましょう。最初に、特定のマップのプロパティのリストを保持する**DescriptorArrays**を描画します。これらの配列は共有できます。その鍵は、マップ自体がDescriptorArrayでいくつのプロパティを調べることができるかを知っていることです。プロパティは時間的に追加された順序になっているため、これらの配列は複数のマップで共有できます。次を参照してください。

**Map1**、**Map2**、**Map3**はすべて**DescriptorArray1**を指していることに注意してください。各マップの「descriptors」フィールドの横にある数字は、DescriptorArrayのいくつのフィールドがマップに属しているかを示しています。「name」プロパティのみを知っている**Map1**は、**DescriptorArray1**にリストされている最初のプロパティのみを調べます。一方、**Map2**には「name」と「height」の2つのプロパティがあります。そのため、**DescriptorArray1**の最初と2番目の項目（nameとheight）を調べます。この種の共有により、多くのスペースを節約できます。

当然のことながら、分割がある場所を共有することはできません。「experience」プロパティが追加された場合、Map2からMap4への遷移があり、「prominence」プロパティが追加された場合、Map3への遷移があります。DescriptorArray1が3つのマップ間で共有されていたのと同じ方法で、Map4とMap4がDescriptorArray2を共有していることがわかります。

「実物そっくり」の図から欠けている唯一のものは、この時点ではまだ比喩的なTransitionArrayです。それを変更しましょう。少し整理するために、**バックポインタ**行を削除しました。ツリー内の任意のマップから、ツリーを上に歩くこともできることを覚えておいてください。

この図は研究に値します。**質問：新しいプロパティ「rating」が「height」などのプロパティに進む代わりに「name」の後に追加された場合はどうなりますか？**

**回答**：Map1は、分岐を追跡するために、実際の**TransitionArray**を取得します。プロパティ*height*が追加された場合、**Map2**に遷移する必要があります。ただし、プロパティ*rating*が追加された場合、新しいマップ**Map6**に移動する必要があります。このマップには、*name*と*rating*をメンションする新しいDescriptorArrayが必要です。オブジェクトには、オブジェクトのこの時点で追加の空きスロットがあるため（3つのうち1つだけが使用されます）、プロパティ*rating*にはこれらのスロットの1つが与えられます。

%DebugPrintPtr()の助けを借りて答えを確認し、以下を描きました。

止めてくれと頼む必要はありません。これがそのような図の上限であることがわかります！しかし、パーツがどのように動くのかを感じることができると思います。この偽のプロパティ*rating*を追加した後、*height*、*experience*、*cost*を続けたと想像してみてください。まあ、マップ**Map7**、**Map8**、**Map9**を作成する必要があります。確立されたマップのチェーンの途中でこのプロパティを追加することを主張したため、多くの構造が重複します。その絵を描く気にはなれませんが、送っていただければこのドキュメントに追加します:)。

ダイアグラムを簡単に作成するために、便利な DreamPuf プロジェクトを使用しました。前回のダイアグラムへのリンクがあります。

TurboFan と const プロパティ #

これまでのところ、これらのフィールドはすべて `DescriptorArray` 内で `const` としてマークされています。これを試してみましょう。デバッグビルドで以下のコードを実行します。

// run as:
// d8 --allow-natives-syntax --no-lazy-feedback-allocation --code-comments --print-opt-code
function Peak(name, height) {
  this.name = name;
  this.height = height;
}

let m1 = new Peak("Matterhorn", 4478);
m2 = new Peak("Wendelstein", 1838);

// Make sure slack tracking finishes.
for (let i = 0; i < 7; i++) new Peak("blah", i);

m2.cost = "one arm, one leg";
function foo(a) {
  return m2.cost;
}

foo(3);
foo(3);
%OptimizeFunctionOnNextCall(foo);
foo(3);

最適化された関数 `foo()` の出力が得られます。コードは非常に短いです。関数の最後に次のように表示されます。

...
40  mov eax,0x2a812499          ;; object: 0x2a812499 <String[16]: #one arm, one leg>
45  mov esp,ebp
47  pop ebp
48  ret 0x8                     ;; return "one arm, one leg"!

TurboFan は、`m2.cost` の値を直接挿入するという、生意気なことをしました。これは驚きですね！

もちろん、`foo()` の最後の呼び出しの後、この行を挿入できます。

m2.cost = "priceless";

何が起こると思いますか？一つ確かなことは、`foo()` をそのままにしておくことはできないということです。間違った答えが返されます。プログラムを再実行しますが、最適化されたコードがシステムから削除されたときに通知されるように、フラグ `--trace-deopt` を追加します。最適化された `foo()` の出力の後、これらの行が表示されます。

[marking dependent code 0x5c684901 0x21e525b9 <SharedFunctionInfo foo> (opt #0) for deoptimization,
    reason: field-const]
[deoptimize marked code in all contexts]

すごいですね。

強制的に再最適化を行うと、最適化されたコードほど良くはありませんが、説明してきたマップ構造の恩恵を大きく受けるコードが得られます。ダイアグラムから、プロパティ *cost* は
オブジェクトのバッキングストアのプロパティの最初のプロパティであることを思い出してください。const 指定を失ったかもしれませんが、まだアドレスはあります。基本的に、グローバル変数 `m2` がまだ持っていることを確認するマップ **Map5** を持つオブジェクトでは、次のようにするだけで済みます。

プロパティのバッキングストアを読み込み、
最初の配列要素を読み出します。

見てみましょう。最後の行の下にこのコードを追加します。

// Force reoptimization of foo().
foo(3);
%OptimizeFunctionOnNextCall(foo);
foo(3);

生成されたコードを見てみましょう。

...
40  mov ecx,0x42cc8901          ;; object: 0x42cc8901 <Peak map = 0x3d5873ad>
45  mov ecx,[ecx+0x3]           ;; Load the properties backing store
48  mov eax,[ecx+0x7]           ;; Get the first element.
4b  mov esp,ebp
4d  pop ebp
4e  ret 0x8                     ;; return it in register eax!

なんと。まさに私たちが言ったとおりに起こりました。私たちは理解し始めているのかもしれません。

TurboFan は、変数 `m2` が別のクラスに変更された場合にも、非最適化を行うのに十分なほどスマートです。次のような退屈なコードで、最新の最適化されたコードが再び非最適化されるのを見ることができます。

m2 = 42;  // heh.

ここからどこへ行くか #

多くの選択肢があります。マップの移行。辞書モード（別名「スローモード」）。この分野には多くの探求すべきことがあり、私が楽しんでいるのと同じくらいあなたが楽しんでくれることを願っています。読んでくれてありがとう！