メインコンテンツまでスキップ

V8正規表現の改善

· 約9分
Patrick ThierとAna Peško、正規表現に関する意見を持つ正規表現擁護者

デフォルト設定では、V8は初回実行時に正規表現をネイティブコードにコンパイルします。JITなしのV8の作業の一環として、正規表現用のインタープリターを導入しました。正規表現を解釈することにはメモリ使用量が少ないという利点がありますが、パフォーマンスの低下を伴います。このブログ投稿では、正規表現を解釈する利点を活かしつつ、欠点を軽減する方法を説明します。

RegExpの段階的向上戦略​

正規表現において「両方の世界の最高」を利用したいと考えています。そのためには、まずすべての正規表現をバイトコードにコンパイルし、それを解釈します。この方法では、多くのメモリを節約でき、全体的に（そして新しい高速インタープリターを使用して）パフォーマンス低下は受け入れ可能です。同じパターンの正規表現が再び使用された場合、それを「ホット」とみなし、ネイティブコードに再コンパイルします。この時点から、できるだけ高速に実行を続けます。

V8の正規表現コードには、呼び出されるメソッドやグローバル/非グローバルの正規表現の違い、そして高速パスを利用するか遅いパスを利用するかによって、多くの異なる実行経路があります。そのため、段階的向上の決定を可能な限り集中させたいと考えています。V8のRegExpオブジェクトにticksフィールドを追加し、ランタイム時に特定の値に初期化されます。この値は、コンパイラーに段階的向上する前に正規表現が解釈される回数を表しています。正規表現が解釈されるたびに、ticksフィールドが1ずつ減少します。CodeStubAssemblerで書かれた組み込み関数で、すべての正規表現に対して実行時にticksフラグを確認します。ticksが0に達すると、正規表現をネイティブコードに再コンパイルする必要があることが分かり、ランタイムにジャンプしてそうします。

正規表現が異なる実行経路を持つ可能性があることについて言及しました。引数として関数を持つグローバル置換の場合、ネイティブコードとバイトコードの実装は異なります。ネイティブコードは事前にすべての一致を格納する配列を期待し、バイトコードは1回の一致を処理します。このため、このユースケースでは常に積極的にネイティブコードへ段階的向上することを決定しました。

RegExpインタープリターの高速化​

ランタイムのオーバーヘッドを削減​

正規表現が実行される際には、CodeStubAssemblerで書かれた組み込み関数が呼び出されます。この組み込み関数は以前、JSRegExpオブジェクトのコードフィールドに直接実行可能なJITtedネイティブコードが含まれているかどうかを確認し、そうでない場合はランタイムメソッドを呼び出してRegExpをコンパイルする（またはJITなしのモードで解釈）ようにしていました。JITなしモードでは、正規表現の実行ごとにV8のランタイムを通過しなければならず、これはJavaScriptコードとC++コードの間で実行スタックを切り替える必要があるため非常に高価です。

V8 v7.8では、RegExpコンパイラーが正規表現を解釈するためのバイトコードを生成する際、生成されたバイトコードに加えてJSRegExpオブジェクトのコードフィールドにインタープリターへのトランポリンを格納するようになりました。この方法により、インタープリターはランタイムを経由せずに直接組み込み関数から呼び出されるようになりました。

新しいディスパッチ方法​

以前のRegExpインタープリターは単純なswitchベースのディスパッチ方法を使用していました。この方法の主な欠点は、次に実行するバイトコードをCPUが予測するのが非常に困難であり、多くの分岐予測ミスが発生し、実行速度が低下することです。

V8 v7.8ではディスパッチ方法をスレッド化コードに変更しました。この方法により、CPUの分岐予測機能が現在実行中のバイトコードに基づいて次のバイトコードを予測できるようになり、予測ミスが減少します。さらに詳しく説明すると、ディスパッチテーブルを使用し、各バイトコードIDとバイトコードを実装するハンドラーのアドレスとの間のマッピングを格納します。V8のインタープリターIgnitionもこのアプローチを使用しています。ただし、IgnitionとRegExpインタープリターとの大きな違いは、IgnitionのバイトコードハンドラーはCodeStubAssemblerで書かれているのに対し、RegExpインタープリター全体はC++でcomputed gotos（clangでもサポートされているGNU拡張）を使用して書かれていることです。これはCSAよりも読みやすく保守しやすいです。computed gotosをサポートしていないコンパイラーの場合、以前のswitchベースのディスパッチ方法に戻ります。

バイトコードの覗き見最適化​

バイトコードのピープホール最適化について話す前に、動機付けとなる例を見てみましょう。

const re = /[^_]*/;
const str = 'a0b*c_ef';
re.exec(str);
// → マッチ 'a0b*c'

このシンプルなパターンに対して、正規表現コンパイラーは各文字に対して実行される3つのバイトコードを生成します。高レベルでは次のようなものです。

  1. 現在の文字を読み込む。
  2. 文字が '_' と等しいかどうかをチェックする。
  3. 等しくない場合、現在の位置を進めて文字列を評価し、goto 1 を実行する。

私たちの文字列では、非一致の文字が見つかるまで17のバイトコードを解釈します。ピープホール最適化のアイデアは、複数のバイトコードの機能を組み合わせる新しい最適化されたバイトコードに置き換えることです。この例では、goto によって暗黙的に作成されたループを新しいバイトコードで明示的に処理することができるため、単一のバイトコードで全ての一致する文字を処理し、16回のディスパッチを節約できます。

この例は作り上げられたものですが、ここで説明されるバイトコードのシーケンスは実際のウェブサイトで頻繁に発生します。実際のウェブサイトを分析し、最も頻繁に遭遇したバイトコードシーケンスに対して新しい最適化されたバイトコードを作成しました。

結果​

図1：異なるティアアップ値でのメモリ節約

図1は、Facebook、Reddit、Twitter、Tumblrのブラウジングストーリーに対する異なるティアアップ戦略のメモリに及ぼす影響を示しています。デフォルトはJITコードのサイズで、その後使用する正規表現コードのサイズ（ティアアップしない場合のバイトコードサイズ、ティアアップする場合のネイティブコードサイズ）が1、10、100のティックで初期化された場合のものです。最後に、すべての正規表現を解釈した場合の正規表現コードのサイズがあります。これらの結果やその他のベンチマークを使用して、ティックが1に初期化された状態でティアアップをオンにすることを決定しました。つまり、一度正規表現を解釈してからティアアップを行います。

このティアアップ戦略により、実際のサイトでV8のヒープコードサイズを4〜7%、実効サイズを1〜2%削減することができました。

図2：正規表現のパフォーマンス比較

図2は、このブログ投稿1で説明されているすべての改善がRexBenchベンチマークスイートに及ぼす正規表現インタープリターのパフォーマンスへの影響を示しています。参考までに、JITコンパイルされた正規表現のパフォーマンス（ネイティブ）も示されています。

新しいインタープリターは古いものより最大2倍高速で、平均して約1.45倍高速です。ほとんどのベンチマークでJIT化された正規表現のパフォーマンスに非常に近づいており、唯一の例外がRegex DNAです。このベンチマークでインタープリターがJIT化された正規表現よりも遅い理由は、使用される長い文字列（約300,000文字）によるものです。ディスパッチのオーバーヘッドを最小限に削減しましたが、1,000文字以上の文字列ではオーバーヘッドが積み重なり、実行が遅くなります。長い文字列にはインタープリターが非常に遅いため、これらの文字列のために積極的にティアアップするヒューリスティックを追加しました。

結論​

V8 v7.9（Chrome 79）からは、正規表現を積極的にコンパイルする代わりにティアアップを行います。そのため、以前はJITのないV8でのみ使用されていたインタープリターが、現在はどこでも使用されるようになりました。その結果、メモリを節約することができます。この戦略を可能にするためにインタープリターの速度を向上させました。しかし、これは終わりではありません—将来的にさらに多くの改善が期待されています。

インターンシップ中に私たちを支援してくれたV8チームの皆さんに、この場を借りて感謝したいと思います。本当に素晴らしい経験でした！

Footnotes​

  1. ここで示されている結果にはすでにV8 v7.8のリリースノートで説明された正規表現の改善も含まれています。 ↩