LINE株式会社は、2023年10月1日にLINEヤフー株式会社になりました。LINEヤフー株式会社の新しいブログはこちらです。 LINEヤフー Tech Blog

Blog


V8のHidden Classの話

この記事はLINE Advent Calendar 2017の19日目の記事です。

JavaScriptの気持ちを知りたい

こんにちは、LINE FukuokaのフロントエンドエンジニアのYoneharaです。

そろそろクリスマスですね。フロントエンドエンジニアのみなさん、苦しんでいますか?私は苦しんでいます。2017年も暮れようというのに、いまだにブラウザやJavaScriptの気持ちが分からず、ユーザーに思うような快適なUXが提供できないことがあるからです。

JavaScriptの気持ち。ただ幸いなことに、我々はかなりの程度、それを分析的に知ることができます。GoogleやMozillaが自身のJavaScriptエンジンのコードを公開し、随所でそのアーキテクチャを解説してくれており、また豊富なトレーシング・プロファイリングの手段が用意されているからです。

今回の記事では、みなさんおなじみのChromeに採用されているV8というJavaScriptエンジンの、Hidden Classという最適化のための1つの仕組みをのぞいてみたいと思います。

動的型付け言語の辞書の実装には制約がある

JavaScriptは動的型付け言語です。つまり実行時にその状況に応じて型が決まるのですが、このことはオブジェクトのプロパティにアクセスする速度という点では不利になり得ます。静的型付けの言語を使い、かつ可変長配列などの動的な型を使わないのであれば、理論上は、あるプロパティ(あるいは構造体のメンバ)のメモリ上のオフセットをコンパイル時に決定できるはずです。したがって、宣言時にオフセット値をどこかに保存しておき、各プロパティの値を知りたいときにそれをそのまま使えばいいということになります。

一方で型が動的に決まる場合、プロパティのメモリ上のオフセットをコンパイル時に決定することはできません。宣言時とアクセス時ではプロパティの型や順番が異なっている可能性があるからです。したがって、宣言時のオフセット値からは値を参照できず、何も対策をしないのであれば、そのつどプロパティを探し当てる必要があります(Dynamic Lookup)。JavaScriptのようにオブジェクトが辞書であるとするなら、その実装方法に依存したコストがプロパティの読み取り時に発生します。

V8はいかにしてDynamic Lookupを回避するのか

しかし、V8ではある方法を使ってDynamic Lookupを回避しています。それがHidden Classです。端的に言えば、プロパティが変化したときに、それぞれそのプロパティのオフセットをアップデートして保持する手法です。

Hidden Classは次のような性質を持っています。

  • あるオブジェクトは必ず1つのHidden Classを参照する。
  • Hidden Classは各プロパティについてメモリ上のオフセットを保持している。
  • 動的に新しいプロパティが作られる、または既存のプロパティが削除されたり型が変わったりするときは別のHidden Classが新しく作られ、それらは既存のプロパティに加え新しいプロパティのオフセットを保持する。
  • Hidden Classはそのプロパティへの操作と、それに対応して遷移すべきHidden Classへの参照を持つ。
  • 新しいプロパティが作られるとき、現在のHidden Classの遷移条件を調べ、合致していれば指定のHidden Classにオブジェクトの参照を遷移させる。

これを元に、Hidden Classの生成の過程を見ていきましょう。あるオブジェクトが作られるとき、必ずHidden Classが作られます。したがって、以下のコードが実行されるとHidden Classが作られ、objはそれに関連付けられます。

var obj = {};

この段階のHidden Classを慣習に習ってC0と呼ぶことにします。このとき、Hidden Classはまだ何の情報も持っていません。objがプロパティを持っていないからです。

次に、オブジェクトを生成した後にobj.xが代入されたとします。

var obj = {};
obj.x = 1;

このとき、また新しいHidden Classが作られます(C1)。このHidden Classはxのオフセット値を持ちます。そしてobjはC0を参照していましたが、これがC1に切り替わります。さらにここが面白いところですが、C0に「xを追加したときはC1に遷移(Transition)する」という条件と遷移先の情報が加わります。

今度は、obj.yが代入されました。

var obj = {};
obj.x = 1;
obj.y = 1;

このときもまた新しいHidden Classが作られ(C2)、objに対応するHidden ClassがC2に変わります。C1にyのオフセット値を追加するわけではありません。そして同様に、C1に「yを追加したときはC2に遷移する」という情報が加わります。

このようなHidden Classのチェーンができた後、例えばobj.yに対するアクセスがあったとします。その場合、objがひも付いているHidden Classを探し(ここではC2)、そのHidden Classに書かれているyのオフセットを使って値を参照することになります。

これがHidden ClassによってDynamic Lookupを回避する基本的な仕組みです。

Transitionの条件の概念によって、Hidden Classは効率的になる

先の節で「C0にtransitionの条件が記載される」と書きました。これをもう少し深く説明します。

例えばこのようなJavaScriptがあるとします。

function Person(name) {
  this.name = name;
}

var foo = new Person("yonehara");
var bar = new Person("suzuki");
console.log(bar.name);

var foo = new Person("yonehara");を実行し終わった時点では、以下の情報が存在し、fooはC1を参照しています。

  • Hidden Class C0
    • プロパティのオフセットなし
    • nameを加えたときはC1に遷移する」という条件
  • Hidden Class C1
    • xのオフセット値

次にbarが作られますが、その過程でbarがC0を参照したとき、すでにそこには「nameを加えたときにはC1に遷移する」という条件が書かれています。それに従って、barは次にnameを加えるとき、新しいHidden Classを作るのではなくC1を参照し、自分自身をひも付けます。

こうして無駄なHidden Classを増やさず、効率的にオフセットを保持するという目的を達成しています。

Hidden Classが同じかどうか、Chromeで確かめてみよう

Hidden Classが同じかどうか確かめる方法があります。V8のデバッガ兼シェルであるd8を使う方法もありますが、もっと簡単にChromeのデベロッパーツールで確認できます。

Chromeを開き、以下の手順を試してみてください。

  1. デベロッパーツールを開く。
  2. 以下のコードをコンソールで実行する。
function Person(name) {
  this.name = name;
}

var foo = new Person("yonehara");
var bar = new Person("suzuki");
  1. Snapshotをとる。
  2. Memoryタブ内で「Person」を検索する。

これで、上記のコードを実行した直後のメモリの状態を見ることができます。

encoder layer

上のSnapshotでわかるように、"map"という項目の右端のidが同じですね。実は、Hidden Classはコード上ではMapと呼ばれています。したがって、このidが一致するなら参照するHidden Classは同じです。

では、barに別のプロパティを加えてみましょう。理論上は、fooは新しいHidden Classを参照し、今までのHidden Classは新しいHidden Classへの参照を持つようになるはずです。

function Person(name) {
  this.name = name;
}

var foo = new Person("yonehara");
var bar = new Person("suzuki");
foo.job = "frontend";

もう一度Snapshotをとってみましょう。

encoder layer

両者のmapのidが別になりました。つまり、違うHidden Classを参照しているということです。mapの下にはtransitionがあり、残念ながら条件までは分かりませんが、barが参照しているHidden Classは内部的にfooのHidden Classへの参照を持っていることも確認できました。

Hidden Classが同じであることは、その後の最適化の条件になる

Hidden Classという概念は普段表には出てきませんが、プロパティの値を参照する速度を落とさない工夫の1つであることがわかりました。本来は、このHidden Classを1つの足がかりにして、Inline Cachingという別の最適化処理が走ります。

Inline Cachingというのは特にV8に固有の手法ではなく、古くからある、値や関数などの結果を状況に応じてキャッシュする手法です。Hidden Classがあるとはいえ保持するオフセットを使ってメモリを参照する作業は残っていますが、その作業がHot、つまり同じ条件で何度も繰り返されるのであれば、結果をキャッシュして返そうというコンセプトがInline Cachingです。

Inline Cachingについても詳しく書きたかったのですが……残念ながら調べる時間が少し足りませんでした。また次回にしたいと思います。

明日はhuydxさんによる「レイテンシーを計算する技術の話」です。お楽しみに!