JavaScriptエンジンの最適化(2) – Hidden class, Inline Caching

1. Prototype vs Class

JavaScriptは基本的にクラスがありません。その代わり、プロトタイプという概念があり、「オブジェクト間の継承」を実装できます。すべてがオブジェクトとして扱われるため、見方を変えると、JavaScriptは他のクラス基盤の言語よりもOOP言語に近いとも言えますが、実際にプロトタイプを既存概念のクラスよりも効果的に使えるかは疑問があります。

JavaScriptはプロトタイプ基盤の言語のため、クラス基盤の言語とは異なり、コンパイラの立場から特に注意すべきことがあります。

フィールド構造

クラス基盤の言語の場合、同じクラスに属するオブジェクトは、すべて同じフィールド構造を持ちます。したがって、オブジェクトの特定のメンバ変数にアクセスするとき、どのような変数にアクセスするか、メモリのどの位置を参照すればよいか、実行前に把握することができます。

たとえば、Aというクラスのオブジェクトは、x、yというフィールドを持ち、Aタイプのオブジェクトを作成するとき、変数xはAが格納された位置の0番offset、変数yはAが格納された位置の1番offset、とあらかじめ決めておくと、コンパイルしたときに、axにアクセスすれば[a+offset(x)]、ayにアクセスすれば[a+offset(y)]のメモリの値を読み込むようにアドレスの値に置換してコードを生成できます。

継承の場合も、継承されたものが親クラスのメンバ変数をなくすことはないので、追加されたものを後ろに付けると問題は発生しません。(もちろん、メンバ関数の場合はポリモーフィズムがあるため、別の話になります。)

 

(出典:Google V8 – Hidden classes)

上図は、クラス基盤の言語とJavaScriptの違いをよく表しています。クラス基盤の言語(左)は、オフセット値だけですべてのメンバ変数にアクセスできますが、JavaScript(右)は実行途中にフィールド構造が変更される可能性があるため、基本的には[プロパティ名+値]のセットをすべてのオブジェクトが保持する必要があります。たとえば、オブジェクトを100個作ったとして、100個すべてのフィールド構造を持っていても、いつ変更されるか分からないので、当該テーブルを持ち続けなければなりません。重複表示されるメンバ変数名をすべて保持しているため、メモリは当然のことながら、パフォーマンスにも問題が生じます(この部分は後述します)。

2. Hidden classes

これらの問題を見事に解決するのが、hidden classという概念です。たとえJavaScriptにクラスがなくても、エンジンの内側に隠されたクラスの概念を置くことで最適化を図ります。


上図は、WebKitのJavaScriptCoreエンジンのhidden class関連の内部データ構造です。簡単に表現すると、JSCellはオブジェクトを保存するデータ構造で、Structureはhidden classデータ構造です。(上図は2009年頃の旧バージョンのコードを参考にしたものですが、2016年現在も大きく変わっていません。)

JSCellだけを見ると既存のクラス基盤言語の方法とよく似ています。実際のプロパティ値のみ格納し、代わりに自分が(現在)所属しているhidden classに対するポインタを保持します。

構造は少し複雑ですが、m_propertyTableは、現在hidden classにあるオブジェクトがどのようなフィールド構造を持ち、それぞれのフィールドがどのオフセットに保存されているかを表すテーブルです。オブジェクトのメンバ変数を参照するときに、このテーブルを参照することで、どの位置の値を読めばよいか調べることができます。

フィールド構造を実行時に変更できるという要件を満たすのが、m_transitionTableです。途中でオブジェクトのフィールド構造が変化する場合、このテーブルを参照して、オブジェクトが他のhidden classに移動したり、新規に生成されます。

左上のコードでa.y = 2の部分が実行された後、hidden classが上図のように形成されますが、その過程は次のとおりです。

  • フィールドがないオブジェクトは、[Structure 0]を参照する。
  • aにxフィールドを追加、[Structure 1]が生成され、プロパティテーブルにx(offset = 0)が追加される。
  • [Structure 0]のトランジションテーブルにxが追加される。以降、[structure 0]を指すオブジェクトでxというフィールドが追加されると、トランジションテーブルを参照して、[Structure 1]に移動する。
  • a.y = 2が実行され、yというフィールドを追加しようとする。xの時と同様に、[Structure 2]を作成し、[Structure 1]にyが追加される場合についたリンクを作成する。
  • 最終的にaは[Structure 2]を指しているので、xにアクセスするときはoffset 0番を、yにアクセスするときはoffset 1番を持って使用すればよい。

ここで、最後のコードであるvar b = new foo(3)が実行されると以下のような状態になります。

  • bが最初に作られて[Structure 0]を指し、xプロパティが追加される。
  • [Structure 0]のトランジションテーブルを見ると、xが追加される時のリンクがあるので、bのhidden classを[Structure 1]に変更する。
  • b.yを追加する場合、[Structure 2]を指すように変更される。
  • b.zを追加する場合、新規に[Structure 3]を作成して、[Structure 1]のトランジションテーブルにzが追加される。

3.パフォーマンスの問題

hidden classを使えば同じフィールドを持つオブジェクトが多くなった場合、メモリは確かにセーブできます。しかし、実際のフィールドにアクセスして値を取得するには、オブジェクト -> hidden class -> プロパティテーブル -> プロパティの比較- > [オブジェクト+オフセット]の位置にアクセスというプロセスが必要になります。

hidden classがなくても、プロパティの比較段階を経る必要があるため、実際はhidden classにアクセスするオーバーヘッドだけが追加されることになります。1つの追加動作ですが、それがフィールドアプローチであれば、全体的なパフォーマンスに大きな影響を及ぼすことになります。

4. Inline Caching

オブジェクトフィールドにアクセスするときにhidden classを使用する場合、最終的に私たちが取得したいものは、アクセスしようとするフィールドのオフセット値です。簡単に言えば、インラインキャッシュは、このオフセット値をキャッシュします。

インラインキャッシュこそJavaScriptエンジンの最適化の哲学を最もよく表す方法ですが、それには次の2つの仮定がベースになっています。

  • 動的言語とはいえ、実際は変わらない方が多い
  • 性能を迅速化するため、ループを狙う

オブジェクトのフィールド構造が実行時に変更されることがありますが、実際のところ頻繁には発生せず、またループの中で変化することもほとんどありません。この仮定が正しければ、インラインキャッシュは高い効率を見せるはずです。実際にベンチマークを回すと、インラインキャッシュの適用有無で非常に大きな違いを見せました。

上図は、JavaScriptCore bytecodeの1つであるput_by_id、すなわちオブジェクトのフィールドに値を書き込むときに生成されるネイティブコードです。
簡単にみると

  • 最初の実行時はキャッシュされた値がないので、slow case(ハンドラ関数、非効率的)で実行する。このとき訪問したオフセット値とhidden class(structure)をconstant pool領域にキャッシュする。
  • 次に同じフィールドにアクセスするとき、キャッシュされたstructureと現在のオブジェクトが指すstructureのアドレス値を比較する。
  • 同一の場合、キャッシュされたプロパティのオフセットが有効であることを意味するので、下のコード(青色の領域)を実行してフィールドに値を格納する。
  • 異なる場合、フィールド構造が変わったことを意味するので、オフセット値が無効になる。この場合、slow caseに移動して再キャッシュしたり、キャッシュを放棄するように変更する。

実際に適用された例を見てみましょう。

for (var i=0; i<10; i++) {
   arr[i].x = i;
}

上記の.xの部分でinline cachingが行われます。最初のiteration(i = 0)では、キャッシュされた値がないため、slow caseで実行され、arr[0]のstructureとarr[0].xのオフセット値がキャッシュされます。2回目からはキャッシュされたオフセット値をすぐに使用できるため、クラス基盤の言語と同じ性能を見せることになります。

ただしこれは、arr[1]からarr[9]までのすべてのフィールド構造を持つことで成立します。したがって、異なるフィールド構造を持つオブジェクトがarrに混ざっていたり、arrにあるオブジェクトに新しいxフィールドを追加するために作成したコードであった場合には、インラインキャッシュの恩恵を全く享受できません。(むしろ損害を被ります。)

最初の実行ですぐにキャッシュすると述べましたが、正確には第2実行からキャッシュされます。最初に実行されたコードは一度だけ実行される可能性が高く、2回実行されたコードは、以降も続けて実行される確率が高いからです。(これもコンパイラの最適化分野においてよく適用される基本仮定です。)つまり、一度だけ実行されるコードはキャッシュをしたところであまり意味がありません。

5.結論

インラインキャッシュを有効にするには、ループ内でフィールドにアクセスするオブジェクトが、すべて同じhidden classを指す必要があります。ループの中間でオブジェクトのフィールド構造を変更するのはよくありませんが、実際にこのように実装することはほとんどないでしょう。そのため、私たちが注意すべきは、上述の例のように配列内のオブジェクトに反復してアクセスするとき、1つの配列の中にすべてのフィールド構造を持つ(同じhidden classを持つ)オブジェクトだけを入れてアクセスするようにする程度です。

性能のよいJavaScriptのプログラムを作成したいなら、JavaScriptを静的な言語と見做して使うとよいでしょう。動的な特性を最大限に活用してパワフルで素晴らしいコードを作成することもありますが、そこには常に性能という対価が伴うことを留意する必要があります。

TOAST Meetup 編集部

TOASTの技術ナレッジやお得なイベント情報を発信していきます
pagetop