WebkitがES6の機能を完備 : RegExpを例に、パフォーマンスのための取り組みを詳解する

r202125の時点で、JavaScriptCoreがECMAScript6(ES6)言語仕様にある新機能の全てをサポートしました。ES6のあらゆる新しい機能が最新のWebKit NightlySafari Technology Previewで入手できます。モジュールの実装はありますが、Web用のAPIはまだできあがっていません。ES6で、JavaScript言語には非常に多くの優れた機能が追加され、JavaScriptCoreの開発に関わる人たちはJavaScriptの未来に興奮しています。新しいES6の機能を単に実装するだけでなく、ずば抜けたパフォーマンスを確実に実現しようと一生懸命です。しかしながら、今回は違う観点から論じます。とはいえ、ES6の機能の開発においては上記と同様に重要な点について、つまり、現在あるES5のWebサイト・アプリケーションと同じパフォーマンスを維持する方法についての話です。

ES6におけるRegExpの変更点

ES6ではJavaScriptの正規表現に、信じがたいほどの量のカスタマイズ性が加わりました。Symbolプロパティのメソッドを使って、String.prototype関数による引数RegExpの扱い方を開発者がカスタマイズできるのです。例えば、String.prototype.match()は、マッチングの実行に当たってSymbol.matchプロパティを最初の引数の中で使おうとします[1]。デフォルトで、RegExp.prototypeにはString.prototypeオペレーション(Symbol.replaceSymbol.searchSymbol.matchなど)それぞれに相当する関数がありますが、開発者が振る舞いをカスタマイズしたければ変えることができます。加えて、さらに重要なのは、ES6では、flagsglobalexecといった全てのRegExpプロパティにRegExp.prototype関数それぞれがアクセスまたはコールする方法を指定しているということです。もし、これらの新しい機能を何も考えずに実装してしまうと、機能性を高めたい開発者の要求を満たすものの、高い機能を求めないWebページ上ではパフォーマンスを犠牲にしてしまいます。

JavaScriptCore Virtual Machine(VM)の目標の1つは、「開発者が、使わない機能に関するコストを払うことはない」というのを保証することです。RegExp関数の場合は、「現在あるWebページでRegExpのコードのパフォーマンスに影響を与えてはならない」というのが目標になります。同じパフォーマンスを維持するために、JavaScriptCoreでは関数とゲッタのルックアップと実行を、避けることができなくてはなりません。例えば、JavaScriptCoreによって「String.prototype.match()に対する全ての呼び出しには、matchに関連するプロパティ(Symbol.matchexecglobalUnicode)を一切オーバーライド/改変しないRegExpオブジェクトが渡される」ということを保証できれば、match()をより速くて特化した実装で実行できます。こういうプロパティは変わっていないという知識があれば、特化した実装によって、無駄を含む可能性を持った要素のあるプロパティのルックアップを避けることができ、RegExpオブジェクトからmatch関数が直接必要とする全ての情報をロードできます。これにより、特化した実装がexec関数をインライン化することもできます。

JavaScriptCore VMは、各ティアが段階的に最適化を進めるマルチティアエンジンのデザインを使っています。JavaScriptCoreの最上位のティアは、コードの振る舞いについて推論し、他のやり方では実現できない最適化を可能にしています。JavaScriptCoreのティア構造についてのより詳しい情報は過去の投稿で確認できます[2][3]。私たちの作るエンジンの最適化ティアでは、RegExpオブジェクト上のプロパティについて推論するために、目立った影響を伴わずにこれらのプロパティをルックアップする方法が必要でした。

そのために、TryGetByldという新しいバイトコードが追加されました。これは、識別子で通常のプロパティをルックアップするバイトコードであるGetbyldに似た動きをします。もし、プロパティに値がセットされていないか、通常の値(JavaScriptには[].lengthのような特殊な効果を持つ特殊なプロパティが幾つかありますが、それらは除きます)がセットされている場合、TryGetByldは適切な値を返します。その他の場合には、プロパティがアクセサならTryGetByldは内部のGetterSetterオブジェクトを返しますが、これは想定された元々の値になぞらえたものです。アクセサは関連づけられたゲッタとセッタを持っているので、GetterSetterオブジェクトはVMが利用するこれらの関数を備えた内部オブジェクトということになります。それだけで、TryGetByldがES6の振る舞いに関連したパフォーマンスの問題を解決することはありません。というのも、TryGetByldは「その値はVMの期待する値である」ということを明らかにするために動くからです。しかしながら、コードがVMの最適化コンパイラへかけられるにつれて、下位のティアのTryGetByldから収集された情報によって、特化したコードの実行に必要なチェックのほとんど全てを取り除くことができます。

Structures

TryGetByldがいかに最適化されるかについての詳細に踏み込む前に、Structuresの概念を理解することが有益でしょう。Structures(shapeやmapとも称されます)の概念についてよく分かっている人は読み飛ばして次のセクションへ行っても構いません。StructuresはSmalltalkやSelf言語の最適化[4]として80年代に始まったものなので、オブジェクトにおけるプロパティのメモリレイアウトを表す方法だということです。JavaScriptにおいてオブジェクトにプロパティを格納する率直なやり方は、あらゆるオブジェクトを「識別子から対応する値/アクセサへのハッシュマップ」にすることです。ハッシュマップの利用は動作こそするものの、オブジェクトの普通の使われ方については利点がありません。JavaScriptでオブジェクトを生成する際には、いくつかのプロパティを追加するようなコンストラクタをコールするのが一般的です。ほとんどの場合、同じ関数によって作られたオブジェクトは同じプロパティのセットを共有するものです。Structureはこういったオブジェクト間の類似性をうまく利用する方法です。下記を見てみましょう。

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

let p1 = new Point(1, 2);
let p2 = new Point(3, 4);

p1p2は異なる値ではありますが、どちらも同じように初期化されます。つまり、new Point()をコールすると新たに空のオブジェクトであるoが割り当てられます。プロパティxがそのオブジェクトに追加され、プロパティyが続いて追加されます。上記の例では、コードがthis.xiに割り当てると、oという単体のStructure上のプロパティxのルックアップによってVMが起動します。oは最初は空のオブジェクトなので、プロパティを持たないあらゆるノーマルなオブジェクトによって共有される最初のStructuresを持っています。この単体Structureはプロパティxへのエントリを持っていません。それゆえ、エントリの追加が必要です。

Structureはイミュータブルであるため、オブジェクトにxプロパティを追加するには、VMはそのオブジェクトのStructureを、そのオブジェクトの既存の全プロパティだけでなくxのエントリも持つ別のStructureに置き換える必要があります。このStructureの置き換えを、私たちはtransitionと呼んでいます。新しいプロパティの追加以外にも、transitionが必要となる操作はいろいろあります。例えば、プロパティの削除、(Object.defineOwnPropertyによる)プロパティの属性の変更、プロトタイプの変更などです。

新しいプロパティを追加するためにStructure transitionを実行する度に、VMはまず、同じStructureを共有している他のオブジェクトに、これから追加するプロパティと同じ識別子のプロパティが追加されているかどうかを確認します。そのようなStructureが存在する場合は、そのStructureが再利用されます。もし存在しない場合は、新しいStructureが割り当てられ、その新しいStructureに現在のStructureの全プロパティをコピーした後で新しいプロパティを追加します。その後、私たちはオブジェクトのStructureのポインタを新しいStructureに変更します。

JavaScriptCoreでは、オブジェクトのプロパティは、Butterflyと呼ばれる配列のようなオブジェクトに格納されます。Butterflyは、オブジェクトによって指定されます。Structureは、識別子からButterfly内のオフセットへのハッシュマップを保持しており、そのオフセットの位置にプロパティの値が格納されています。新しいプロパティの追加は、次の空いているオフセットが与えられるだけで遂行されます。VMは新しいStructureを完全に初期化した後、元のStructureに、「同じ識別子を追加する新しいプロパティtransitionをする場合、新しいStructureを再利用する」という印をつけます。

image

例えば上の図は、new Point(3, 4)を呼び出すまでの各行で、Pointインスタンスがどのようにtransitionを行うかを示しています。新しいプロパティが追加される度に、Pointインスタンスは、そのStructureを取り換えて、Butterflyに新しいオフセットを追加します。ここで注目してほしいのは、プロパティxが追加される時、Structure 1にはStructure 2へのtransitionがマークされていることです。同様に、プロパティyが追加される時は、Structure 2にはStructure 3へのtransitionがマークされています。次にまたPointインスタンスが作成され、初期化されると、それは同じStructure 1、2、および3を再利用し、最初のPointインスタンスと同じレイアウトのButterflyを持つことになります。

Structureを使う利点は、大きく2つあります。1つ目の利点は、メモリ量をかなり節約することができることです。もしプログラムがStructureを使わずに何千ものPointを割り当てる場合、Pointそれぞれが、そのプロパティのハッシュテーブルを持つ必要があります。一方、Structureを使う場合は、プロパティをマップするためにメモリを一定量だけ使いますが、各オブジェクトに必要なのは、プロパティの配列だけです。2つ目の利点は、同じプロパティを持つオブジェクトは同じプロトタイプを持つことが多いので、JavaScriptCoreは、オブジェクト1つ1つにプロトタイプへのポインタを格納する代わりに、これらのオブジェクトが共有するStructureにプロトタイプポインタのコピーを1つ格納するだけでいいということです。下の図は、Setインスタンスオブジェクトのプロトタイプチェーンの様子を表しています。Structureの2番目の利点の方が、恐らく重要ですが、この利点は、Structureを共有する各オブジェクトが、同じプロパティレイアウトのButterflyを持っていることに由来しています。JavaScriptCoreはこのことを利用して、エンジン全体のさまざまな最適化を実行します。

image

Object Property ConditionsとAdaptive Watchpoints

TryGetByIdは、GetByIdが利用しているのと同じインラインキャッシュシステム(過去のブログ記事を参照)を共有しているので、TryGetByIdはGetByIdが持っている最適化を全て利用することができます。オブジェクト自体に置かれているプロパティ(自身のプロパティともいう)をキャッシュする場合、インラインキャッシュは比較的簡単です。最初のアクセスの後、次に続く全てのアクセスを高速にするためにVMが行うべきことは、Structureおよびプロパティのオフセットを伴う命令を幾つか再パッチするだけです。この次にGetById/TryGetByIdが実行される際、プログラムは、新しいオブジェクトが前回と同じStructureを持っているかどうかの確認を行います。持っている場合、VMは、オフセットを見つけるためにStructure上のハッシュテーブルをルックアップしなくても、キャッシュされたオフセットからプロパティをロードすることができます。オブジェクトのStructureがVMの把握しているものかどうか確認することを、Structureチェックといい、さまざまな目的に使用されます。

ES6の全てのRegExpの新たな変更の場合と同様に、プロトタイプからプロパティをロードすることは、かなり難しい問題です。Structureチェックは、Structureが求められるプロパティを持っていないオブジェクトであることを保証しますが、そのオブジェクトのプロトタイプがそのプロパティを同じように持っているか、持っていないかということは保証しません。Safari 9.0のリリース以降、プロトタイプのインラインキャッシュは、Object Property ConditionsとAdaptive Watchpointsという2つの新しい概念の追加により、さらに一層強力になりました。特に、Object Property ConditionsとAdaptive Watchpointsにより、時にはJavaScriptCoreはプロパティのアクセスのための最適化コードで、全てのヒープロードとほぼ全てのStructureチェックを完全に取り除くことができます。

Object Property Conditions

プロトタイプチェーン上でプロパティをルックアップする際、幾つかのヒープアクセスを確認する制約条件がObject Property Conditions(OPC)です。Object Property Conditionsは、その名前が示すように、オブジェクトとそのオブジェクト上の条件(condition)を保持しています。GetById/TryGetByIdが使うプロパティの条件はPresence、Absence、Equivalenceの3種類です。PresenceとAbsenceは単純です。Presenceは、OPCのオブジェクトが指定された識別子のプロパティを持っていることを表します。一方、AbsenceはOPCのオブジェクトがその識別子のプロパティを持っていないことを表します。Equivalenceのwatchpointについては、もう少し後でお話しします。あるプロパティについてGetById/TryGetByIdすることを考えましょう。そのプロパティを持つプロトタイプとベースオブジェクトの間のプロトタイプチェーンがありますが、そのプロトタイプチェーン内のオブジェクトそれぞれにOPCが存在する必要があります。要求されたプロパティを持つオブジェクトがプロトタイプチェーンに1つも存在しない時は、プロトタイプチェーンのあらゆるオブジェクト上にOPCが存在している必要があります。

function foo() {
   let r = new Set();
   console.log(r.toString());
}

上に示した例で、新しく作成されたSetインスタンスオブジェクトから、toStringプロパティを素早くロードしたいのであれば、2つのOPCと1つのStructureチェックを持っている必要があります。1つ目のOPCでは、Object.prototypetoStringプロパティのPresence条件を保持していることを示します。また2つ目のOPCでは、Set.prototypetoStringプロパティのAbsence条件を保持していることを示します。これらの条件とStructureチェックでGetById/TryGetByIdインラインキャッシュは、Object.prototype.toStringの現在の値を直接ロードすることができます。ストラクチャはオブジェクトのプロトタイプとそのオブジェクトがtoStringプロパティを持たないということの両方を表しているので、Structureチェックは1回で十分であることに留意してください。

image

Adaptive Watchpoints

OPCが、作成された時に有効であったからといって、この状態が後まで続くということを意味するわけではありません。古いプロパティを取りやめようと、プログラマが以前に存在したプロパティを削除したり、プロトタイプチェーン上に同じ識別子を有するプロパティを追加したりすることは十分にあり得ることです。ここでAdaptive Watchpointの登場です。VMがあるオブジェクトに対してOPCを作成する時はいつでも、その条件のオブジェクトのStructureに結びつけるためのAdaptive Watchpointを作成し、その条件が有効であり続けることを保証します。監視中のオブジェクトのStructureを持つオブジェクトが一度でもtransitionすると、Adaptive Watchpointが起動します。Adaptive Watchpointは、一旦動き出せば、そのOPCが監視中のオブジェクト上で未だ有効かどうかを調べます。もしtransitionが監視中のオブジェクト上にあり、かつOPCが無効であるなら、その条件に依存するコードは全て破棄されます。そうでなければ、Adaptive Watchpointは、それ自体を監視中のオブジェクトの新しいStructureへ再配置します。下の図は、Setインスタンスオブジェクト上のtoStringプロパティをルックアップする際に、Adaptive WatchpointとObject Property Conditionsがプロトタイプチェーンとどのように情報をやり取りするのかを示しています。

image

一旦、あるコードがJavaScriptCoreの最適化コンパイラの1つと結びついたら、VMは前述したEquivalence条件の利用を開始します。Equivalence条件は本質的により強いPresence条件です。それは、プロパティ”p“がオブジェクト上に存在しているだけでなく、”p“が特定の値を持つということも表します。最適化コンパイラは、GetById/TryGetByIdは定数を返すことがあるということを知っているので、それ以外の方法では実現できない非常にたくさんの最適化を行うことができます。

VMは、コードの一部と最適化コンパイラを結びつけるので、下位のティアで各GetById/TryGetByIdが示したケースを調べます。どのケースも同じプロトタイプのオブジェクト上のPresence条件からロードすると分かれば、VMはそのPresence条件をEquivalence条件に変更しようと試みます。Equivalence条件が有効なままであることを確かめるために、Equivalence条件を保持しているAdaptive Watchpointは、条件のプロパティの既存の値を置き換える監視中のオブジェクトに格納するプロパティは全く無いことを保証する必要があります。監視中のオブジェクトへの格納毎にチェックをすると多大なコストが発生しますが、実際には、プロトタイプオブジェクトへの格納はとてもまれで、最適化コンパイラにおける利得の方がはるかに大きいという傾向があります。

JavaScriptCoreがプロパティのロードを最適化する方法を理解したところで、TryGetByIdを正規表現のパフォーマンスを向上させるのに利用できる理由を見てみましょう。ほとんどのコードはRegExp.prototypeオブジェクト上のプロパティを変更しないので、VMは通常、Equivalence条件を用いて、関連のあるプロパティ上のTryGetByIdを全て定数に変更することができます。そして、最適化コンパイラは、専用のコードの前のプレチェックが全て不要であるということを認識し、それらを取り除くことができます。前に示したString.prototype.matchの例で、Symbol.matchRegExp.prototype.execRegExp.prototype.globalRegExp.prototype.unicodeのどれもが無効にできなかったチェックを取り除くことができました。結果として生じる最適化コードは、その引数のRegExpオブジェクトのStructureチェックを一度、実行する必要があるだけです。そして、その後は高速な専用のコードに直接進むことができます。

まとめ

JavaScriptCoreのチームはES6の新しい機能の全てにとても興奮しています。そして、開発者がそこから多くの恩恵を得られると思っています。今後も、それらの機能の高速化を続けます。また進めていく過程で、さらに多くの記事を投稿するつもりです。今のところ、WebKit nightlyやSafari Technology PreviewでES6機能の最新の実装を確かめることができます。いつものように、ご意見や、遭遇した問題やバグについてお知らせください。