V8 の Inline Caches と Hidden Class について

動的型付けの仕組み

JavaScript のコンパイラーである V8 は C++ で書かれていますが、JSILというOSSの Inline Caches の説明を参照したため仕組みの部分については、C# での説明になってしまいました。仕組みとしては同じはずですのでご容赦ください。

JavaScript は動的型付けの言語であるため、動的に型を決めることができるように内部的に Variant Generic Interface を実装しています。これは共変性という性質を持つもので、戻り値が同じ型であれば再代入可能である性質です。C#のドキュメントまたはこちらのサイトがわかりやすかったです。

Variant Generic Interface の曖昧さ

上記で説明した Variant Generic Interface は実装によっては曖昧さを含んでしまいます。

例えば以下のように実装した場合、どの型が正しいのか判別できずに意図しない結果になる可能性があります。

// Simple class hierarchy.
class Animal { }
class Cat : Animal { }
class Dog : Animal { }

// This class introduces ambiguity
// because IEnumerable<out T> is covariant.
class Pets : IEnumerable<Cat>, IEnumerable<Dog>
{
    IEnumerator<Cat> IEnumerable<Cat>.GetEnumerator()
    {
        Console.WriteLine("Cat");
        // Some code.
        return null;
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        // Some code.
        return null;
    }

    IEnumerator<Dog> IEnumerable<Dog>.GetEnumerator()
    {
        Console.WriteLine("Dog");
        // Some code.
        return null;
    }
}

class Program
{
    public static void Test()
    {
        IEnumerable<Animal> pets = new Pets();
        pets.GetEnumerator();
    }
}

C#ドキュメントからコードを引用しました。

このコードを読むと、GetEnumeratorメソッドを持つ Interface があり、それぞれが Generic によって型を決定しています。さらにここでは Variant Generic Interface によって、多少曖昧な型でも、コンパイルエラーは起こりません。そのため、実行時にどの Interface のメソッドが実行されるのか分からない状態になってしまっています。

JavaScript(V8) への影響

JavaScriptは動的型付け言語であるため、この曖昧さに対して実行時に対処しなければなりません。JavaScriptはこの問題に対して、全ての候補を調べるという方法でどのプロパティを参照するのかを決定しています。この方法では、実行がかなり遅くなってしまいます。そのため、JavaScriptでは Inline Caches(ICs) という方法を使って、一度決定した型を次に使い回すという方法で高速化を測っています。こちらのページに C# で実行した場合、ICs が有効の場合、無効の場合のベンチマークの計測結果が載っています。

Hidden Class とは

Hidden Class はオブジェクトを宣言した時に必ず作られるもので、メモリ上のプロパティのオフセット(メモリ上の位置)を動的に決めるための方法です。静的型付け言語であればコンパイル時に事前にオフセットの位置を決めて、そこから値を参照することができるのですが、動的型付け言語である JavaScript は事前にコンパイルすることができないので Hidden Class を使って動的にメモリ上のオフセットの位置を更新しています。

例えば以下のようなコードがあった時に、p1とp2は異なる Hidden Class を持ちます。Hidden Class は **値が代入される度に変わり、**アップデートされます。アップデートされた時はメモリ上のオフセットを動かして、新しいオフセットへと更新します。そのため、p1.aの位置 => p1.bの位置へと更新されていきます。この時にp2ではp2.b => p2.aの順番で値が代入されてしまっているため、同じルートでオフセットの位置を辿ることができません。そのため、今回のケースではp1とp2で代入の順番が異なっているため、異なる Hidden Class が生成されてしまいます。

function Point(x, y) {
    this.x = x;
    this.y = y;
}

var p1 = new Point(1, 2);
p1.a = 5;
p1.b = 6;

var p2 = new Point(3, 4);
p2.b = 7;
p2.a = 8;

Hidden Class についての詳しい説明はこちらの記事がわかりやすかったです。

Inline Caches とは

Inline Caches について具体的な例を示します。

getX関数があったとして、引数oはプロパティxを持ちます。この場合、引数oは呼び出し時に Hidden Class を作り、オブジェクトをメモリ上にキャッシュします。

function getX(o) {
	return o.x;
}

// 型を決めて、Hidden Class を生成し、メモリ上にキャッシュされる
getX({ x: 'test1' });

最初の呼び出し時に引数oはキャッシュされているので2回目の呼び出しからはキャッシュされた値が使われます。

// 2回目の呼び出しではキャッシュを使うので、型の処理が不要になる
getX({ x: 'test2' });

しかしここで、異なる Hidden Class を生成してしまうとキャッシュが利用できなくなる

// プロパティyはメモリ上に存在しないのでキャッシュを利用できない
getX({ y: 'abc' });

そのため、出来るだけ Hidden Class を再利用するように実装することで runtime の速度を少しでも改善することができます。

JavaScript でどのように動くのか

上記のようにキャッシュされた関数呼び出しの情報は、オブジェクトへのアクセスを容易にします。最初に述べたとおり、JavaScript は動的型付け言語であるため、渡された Object が何の型なのか最初から分からないため、プロパティを調査します。しかし、キャッシュすることによって、調査の必要がなくなり、スムーズにプロパティにアクセスできるようになります。

つまり、オブジェクトへのルックアップを減らし、パフォーマンスを向上させるためには、オブジェクトのプロパティが変更されないことが重要になります。

オブジェクトが変更されていないことを保証するために Hidden Class を使って値が変更されていないことを保証します。この Hidden Class のプロパティが変更されていない時のみ、プロパティを調査する処理を省き、プロパティへのアクセスを高速にすることができます。

JavaScriptの最適化

ここまでの説明をまとめると、V8 では Object が作成される度に、Hidden Class が作成され、型情報をキャッシュしていることがわかります。そしてこの型情報を元にプロパティの呼び出しを効率的に行っており、Inline Caches も Hidden Class の型に基づいて関数を効率的に呼び出すようにキャッシュしています。

このことを踏まえると以下のことを意識してコードを書く必要がありそうです。

• Hidden Class が異なってしまい、最適化されたコードが共有されなくなってしまうため、同じ順番でインスタンス化する
• 動的に値を追加することは Hidden Class を強制的に変更し、処理を遅くするため、出来るだけ constructor で初期化するようにする
• Inline Caches によって最適化が施されるため、繰り返し使うようなメソッドは、1つのメソッドを使うようにする
• このような性質のため、Reduxのような頻繁にオブジェクトを変更するような作業は少し重い作業になります。そのため、Reduxではオブジェクトを浅くすることを推奨しています。浅い方がコピーのスピードが早く、ポインタを効率的に動かすことができるからです。

まとめ

JavaScript(V8) がどのように処理しているのかを知ることで、コンパイラの気持ちを考えてコードが書くことができるようになったと思います。しかし、まだまだ知らないことがありそうなので今後も少しずつ調べてまとめていたらと思います。

また JavaScript は動的型付け言語であるために、記事にあるようなことを意識するのは少し難しいですが、最初から型で固定してしまえば、意識しなくてもある程度パフォーマンスの良いコードを書けるようになるのかなと思いました。つまり TypeScript がパフォーマンスの面でも重要なのかなと感じました。

最後まで読んでいただきありがとうございました。

何か間違っているところがあれば、教えていただけると嬉しいです。

参考

• Optimizing dynamic JavaScript with inline caches - https://github.com/sq/JSIL/wiki/Optimizing-dynamic-JavaScript-with-inline-caches
• How JavaScript works: inside the V8 engine + 5 tips on how to write optimized code - https://blog.sessionstack.com/how-javascript-works-inside-the-v8-engine-5-tips-on-how-to-write-optimized-code-ac089e62b12e
• V8のHidden Classの話 - https://engineering.linecorp.com/ja/blog/detail/232/
• JavaScript engine fundamentals: Shapes and Inline Caches - https://mathiasbynens.be/notes/shapes-ics
• Redux FAQ: Performance - https://github.com/reduxjs/redux/blob/master/docs/faq/Performance.md#do-i-have-to-deep-clone-my-state-in-a-reducer-isnt-copying-my-state-going-to-be-slow