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

信じられないほど速いパース、パート2：遅延パース

· 約20分
Toon Verwaest ([@tverwaes](https://twitter.com/tverwaes)) と Marja Hölttä ([@marjakh](https://twitter.com/marjakh))、パーサー

V8がJavaScriptを可能な限り高速に解析する方法を説明するシリーズの第二部です。第一部では、V8のスキャナを高速化する方法について説明しました。

パースは、ソースコードをコンパイラ（V8ではバイトコードコンパイラのIgnition）が利用できる中間表現に変換するステップです。パースとコンパイルはウェブページのスタートアップの重要なプロセスであり、ブラウザに送られるすべての関数がスタートアップ時にすぐに必要になるわけではありません。開発者が非同期や遅延スクリプトを使用してそのようなコードを遅らせることができますが、それが常に可能とは限りません。また、多くのウェブページでは、特定の機能でのみ使用されるコードが含まれており、ユーザーがそのページを利用する間に一度もアクセスされない可能性があります。

不要なコードを積極的にコンパイルすることには、実際のリソースコストがあります:

  • 必要なコードの利用可能性が遅れるため、CPUサイクルがコードを作成するのに使用されます。
  • コードオブジェクトはメモリを消費します。ただし、バイトコードフラッシングがコードが現在不要であると決定し、それがガベージコレクションされるまでです。
  • トップレベルのスクリプトの実行が終わった時点でコンパイルされたコードはディスクにキャッシュされ、ディスクスペースを占有します。

これらの理由から、すべての主要なブラウザは_遅延パース_を実装しています。各関数の抽象構文木（AST）を生成してからバイトコードにコンパイルする代わりに、パーサーは「プリパース」することで関数を完全にパースすることを避けることができます。プリパーサーへの切り替えを行い、関数をスキップするのに必要な最低限の操作を行うパーサーのコピーです。プリパーサーはスキップされた関数が構文的に有効であることを検証し、外部関数が正しくコンパイルされるために必要なすべての情報を生成します。プリパースされた関数が後で呼び出されると、その時点で完全にパースおよびコンパイルされます。

変数の割り当て​

プリパースを複雑にする主な要因は、変数の割り当てです。

パフォーマンス上の理由から、関数の起動はマシンスタック上で管理されます。例えば、関数gが引数1と2を使用して関数fを呼び出す場合:

function f(a, b) {
  const c = a + b;
  return c;
}

function g() {
  return f(1, 2);
  // `f`の戻り命令ポインターは今ここを指しています
  // (`f`が`return`を呼び出すとき、ここに戻ります)。
}

最初にレシーバー（つまりfのthis値、スラッピーファンクション呼び出しであるためglobalThis）がスタックにプッシュされ、その後呼び出される関数fが続きます。その後、引数1と2がスタックにプッシュされます。その時点で関数fが呼び出されます。呼び出しを実行するには、まずスタックにgの状態を保存します: fの“戻り命令ポインター”（rip; 戻るべきコード）および“フレームポインター”（fp; 戻る時のスタックの状況）が含まれます。その後、fに入り、ローカル変数cおよび必要な一時スペースを割り当てます。これにより、関数の有効範囲が終了したときに使用されたデータは失われます: ただスタックから取り除かれるだけです。

引数a、bとローカル変数cがスタックに割り当てられた関数fへの呼び出しのスタックレイアウト.

この設定の問題は、関数が外部関数で宣言された変数を参照できることです。内部関数はそれが作成された起動の有効範囲外で生き続けることができます:

function make_f(d) { // ← `d`の宣言
  return function inner(a, b) {
    const c = a + b + d; // ← `d`への参照
    return c;
  };
}

const f = make_f(10);

function g() {
  return f(1, 2);
}

上記の例では、innerからmake_fで宣言されたローカル変数dへの参照はmake_fが戻った後で評価されます。これを実現するために、レキシカルクロージャーを持つ言語のVMは、内部関数から参照される変数をヒープ上の“コンテキスト”と呼ばれる構造に割り当てます。

make_fへの呼び出しの際に、引数がinner用に割り当てられたヒープ上のコンテキストにコピーされ、dをキャプチャするためであるスタックレイアウト.

つまり、関数で宣言された各変数について、内側の関数がその変数を参照しているかどうかを確認する必要があります。それによって、変数をスタックに割り当てるべきか、ヒープに割り当てられたコンテキストで割り当てるべきかを決定することができます。関数リテラルを評価するとき、関数のコードと現在のコンテキスト（必要に応じて変数の値を保持するオブジェクト）へのポインタを保持するクロージャを割り当てます。

要するに、準パーサーにおいて少なくとも変数の参照を追跡する必要があります。

ただし、参照だけを追跡すると、参照されている変数を過大評価してしまいます。外部関数で宣言された変数が内部関数の再宣言によってシャドウイングされることがあります。その場合、内部関数の参照は外部宣言ではなく内部宣言をターゲットとします。条件なしで外部変数をコンテキストに割り当てると、パフォーマンスに悪影響を及ぼします。このため、準パーサーを使用して変数割り当てを適切に機能させるには、準パースされた関数が変数参照と宣言の両方を適切に追跡するようにする必要があります。

トップレベルコードはこの規則の例外です。スクリプトのトップレベルは常にヒープに割り当てられます。なぜなら、変数はスクリプト間で可視だからです。適切に機能するアーキテクチャに近づく簡単な方法は、準パーサーを変数追跡なしで実行してトップレベル関数を高速にパースすることと、内部関数には完全なパーサーを使用する（ただし、それをコンパイルしない）ことです。これにより、完全なASTを不必要に構築するため準パースよりは高コストですが、正常に動作させることが可能です。実際、V8はV8 v6.3 / Chrome 63まではこれを行っていました。

準パーサーに変数を教える​

準パーサーで変数の宣言と参照を追跡するのは複雑です。JavaScriptでは、部分式の意味が最初から明確であるとは限らないからです。たとえば、引数dを持つ関数fがあり、その内部にdを参照する可能性のある式を持つ関数gがあるとします。

function f(d) {
  function g() {
    const a = ({ d }

これは、トークンが分割代入式の一部であるため、確かにdを参照する可能性があります。

function f(d) {
  function g() {
    const a = ({ d } = { d: 42 });
    return a;
  }
  return g;
}

また、分割代入の引数dを持つアロー関数となる場合もあります。この場合、fの中のdはgによって参照されません。

function f(d) {
  function g() {
    const a = ({ d }) => d;
    return a;
  }
  return [d, g];
}

初期の準パーサーは、コード共有がほとんどないパーサーのスタンドアロンなコピーとして実装されていました。これが原因で2つのパーサーが時間とともに分岐しました。しかし、パーサーと準パーサーをParserBaseに基づいて再設計し、再帰的テンプレートパターンを採用することで、別々のコピーのパフォーマンス利点を維持しながら共有を最大化しました。この変更により、準パーサーへの完全な変数追跡の追加が大幅に簡素化されました。なぜなら、実装の多くの部分をパーサーと準パーサー間で共有できるからです。

実際には、トップレベル関数においても変数宣言や参照を無視するのは間違いでした。ECMAScript仕様では、スクリプトの最初のパース時に検出すべき様々な種類の変数競合を要求しています。たとえば、同じスコープ内で同じ変数が2回字句変数として宣言されると、それは初期のSyntaxErrorと見なされます。しかし、準パーサーは変数宣言を単にスキップしていたため、誤ってそのコードをプレパース中に許可してしまいました。当時は、性能向上の観点から仕様違反を正当化していました。しかし、準パーサーが変数を適切に追跡するようになり、この型の変数解決関連の仕様違反をパフォーマンスに大きな影響を与えることなく完全に解消しました。

内部関数をスキップする​

前述のように、準パースされた関数が最初に呼び出されるとき、それを完全にパースし、結果のASTをバイトコードにコンパイルします。

// これはトップレベルスコープです。
function outer() {
  // 準パース済み
  function inner() {
    // 準パース済み
  }
}

outer(); // `outer`を完全にパースしてコンパイルするが、`inner`はしない。

関数は直接、内部関数がアクセスする必要がある変数の宣言値を含む外部コンテキストを指します。関数の遅延コンパイルを可能にする（およびデバッガーをサポートする）ために、コンテキストはScopeInfoと呼ばれるメタデータオブジェクトを指します。ScopeInfoオブジェクトは、コンテキストにリストされている変数を記述します。これにより、内部関数をコンパイルする間、変数がコンテキストチェーンのどこに存在するかを計算できます。

ただし、怠惰にコンパイルされた関数自体がコンテキストを必要とするかどうかを計算するには、再度スコープ解決を実行する必要があります。怠惰にコンパイルされた関数内部のネストされた関数が、怠惰な関数によって宣言された変数を参照しているかどうかを知る必要があります。このことを判断するためには、それらの関数を再度解析する必要があります。これはまさにV8がV8 v6.3 / Chrome 63まで行っていたことです。しかし、これは性能面では理想的ではありません。ソースコードのサイズと解析コストの関係を非線形にしてしまうからです。ネストされた関数の数だけ再解析する必要がありました。動的プログラムの自然なネストに加えて、JavaScriptパッカーはしばしば「即時呼び出し関数式」（IIFE）でコードを包むことがあります。このため、ほとんどのJavaScriptプログラムが複数のネスト層を持つことになります。

再解析ごとに関数の解析コストが少なくとも追加されます。

非線型な性能負荷を回避するため、解析中でも完全なスコープ解決を実行します。これにより、後で内部関数を単純に「スキップ」することができ、再解析する必要はありません。一つの方法として、内部関数で参照される変数名を保存することが考えられます。ただし、この方法は保存にコストがかかり、作業の重複を引き起こします。解析中にすでに変数解決を行っているからです。

その代わりに、変数が割り当てられる場所を密なフラグ配列としてシリアル化します。関数を怠惰に解析するとき、変数は準解析器がそれらを見つけた順序で再作成され、メタデータを変数に適用できます。関数がコンパイルされると、変数の割り当てメタデータはもう必要なくなり、ガベージコレクションされます。このメタデータは実際に内部関数を含む関数にのみ必要であるため、すべての関数の大部分がこのメタデータを必要とせず、メモリ負荷は大幅に減少します。

準解析された関数のメタデータを追跡することで内部関数を完全にスキップできます。

内部関数をスキップすることによる性能影響は、内部関数を再解析する負荷と同様に、非線型です。すべての関数を最上位スコープに昇格させるサイトがあります。これらのサイトではネストレベルが常に0であるため、負荷は常に0です。しかし、多くの現代のサイトでは実際に関数が深くネストされています。これらのサイトでは、この機能がV8 v6.3 / Chrome 63で登場したときに大幅な改善が見られました。主な利点は、コードがどれほど深くネストされていてももう関係がなくなったことです。任意の関数は最大でも一度準解析され、一度完全に解析されます1。

メインスレッドとメインスレッド外での解析時間、内部関数スキップ最適化の導入前後。

可能性のある呼び出し関数式​

前述のように、パッカーは通常、モジュールコードを閉包でラップし、それを即座に呼び出すことで単一のファイルに複数のモジュールを結合します。これにより、モジュールはスクリプト内の唯一のコードとして実行されるかのように分離されます。これらの関数は本質的にネストされたスクリプトであり、スクリプトの実行時に即座に呼び出されます。パッカーは通常、即時呼び出し関数式（IIFEs;「イフィー」と発音）を括弧付きの関数として出荷することがあります: (function(){…})()。

これらの関数はスクリプト実行時に即座に必要となるため、このような関数を準解析することは理想的ではありません。スクリプトのトップレベルで実行される際に直ちに関数がコンパイルされる必要があり、関数を完全に解析しコンパイルします。つまり、起動を高速化するために以前行った準解析が、起動にとって不必要な追加コストとなることが保証されているのです。

呼び出される関数を単にコンパイルすればいいではないか、と思うかもしれません。しかし、開発者が関数が呼び出されることに気づくのは通常簡単なのですが、これがパーサーには当てはまりません。パーサーは関数を解析し始める前に、関数を即座にコンパイルするか、コンパイルを遅延するかを決定する必要があります。構文の曖昧さにより、関数の終わりまで単純に高速スキャンすることが難しく、コストはすぐに通常の準解析のコストに類似します。

この理由から、V8は関数を即座に解析しコンパイルするための_可能性のある呼び出し関数式_（PIFEs；「ピフィー」と発音）として認識する2つの単純なパターンを持っています。

  • 関数が括弧付きの関数式である場合、つまり(function(){…})である場合、関数が呼び出されるものと仮定します。このパターンの開始を見た時点で、つまり(functionが見えた時点でこの仮定を行います。
  • V8 v5.7 / Chrome 57以降では、UglifyJSによって生成される!function(){…}(),function(){…}(),function(){…}()のパターンを検出します。この検出は!functionが見えた時点、またはPIFEが直後に続く場合の,functionが見えた時点で開始されます。

V8はPIFEを即座にコンパイルするため、それらはプロファイル指向のフィードバック2として使用でき、ブラウザに起動に必要な関数を知らせます。

V8がまだ内部関数を再解析していた時期、一部の開発者はJS解析が起動時に与える影響が非常に大きいことに気づいていました。パッケージ optimize-js は静的ヒューリスティックスに基づいて、関数をPIFE（Parentheses-Informed Function Expressions）に変換します。このパッケージが作成された当時、V8でのロードパフォーマンスに大きな影響を与えていました。私たちは、optimize-js が提供するベンチマークをV8 v6.1で実行し、最小化されたスクリプトのみを対象にしてこれらの結果を再現しました。

PIFEを積極的に解析およびコンパイルすることで、冷たい起動と温かい起動（最初のページロードと2回目のページロード、解析+コンパイル+実行時間の合計を測定）がわずかに速くなります。ただし、パーサーの大幅な改善により、その利点はV8 v6.1でのものに比べV8 v7.5でははるかに小さくなっています。

しかし、現在では内部関数を再解析しなくなり、かつパーサーがはるかに高速化されたため、optimize-js を使用することで得られるパフォーマンス改善は大幅に減少しています。実際、v7.5のデフォルト設定は、v6.1での最適化されたバージョンよりもすでに遥かに高速です。とはいえ、v7.5でも起動時に必要なコードに対してPIFEを控えめに使用することは依然として理にかなっています。これは、関数が必要であることを早い段階で学習することで解析を回避できるためです。

optimize-js のベンチマーク結果は必ずしも現実世界を正確に反映しているわけではありません。スクリプトは同期的にロードされ、解析+コンパイル時間の全てがロード時間にカウントされます。現実の設定では、スクリプトを <script> タグを使用してロードする可能性があります。これにより、Chromeのプリローダーがスクリプトを評価する前にスクリプトを発見し、メインスレッドをブロックせずにスクリプトをダウンロード、解析、およびコンパイルすることができます。私たちが積極的にコンパイルすることを決定したすべてのものは自動的にメインスレッド外でコンパイルされ、起動時間に対する影響を最小限に抑えるべきです。メインスレッド外でのスクリプトコンパイルを行うことで、PIFE使用の影響が拡大します。

それでも、特にメモリーコストがかかるため、すべてを積極的にコンパイルするのは良い考えではありません:

すべての JavaScriptを積極的にコンパイルすることは、かなりのメモリーコストが伴います。

起動時に必要な関数に括弧を追加することは良い考えです（例えば、起動時のプロファイリングに基づいて）。しかし、単純な静的ヒューリスティックスを適用するような optimize-js のようなパッケージを使用するのはあまり良い考えではありません。例えば、このパッケージは、関数が関数呼び出しの引数である場合、その関数が起動時に呼び出されると仮定します。そのような関数が後に必要とされるモジュール全体を実装している場合、不必要に多くをコンパイルしてしまいます。過剰に積極的なコンパイルはパフォーマンスに悪影響を及ぼします。V8は遅延コンパイルがないと負荷時間が著しく悪化します。さらに、optimize-js の利点の一部は、UglifyJSや他のミニファイアがPIFEではないPIFEから括弧を除去する問題に起因しています。これにより、例えばUniversal Module Definitionスタイルのモジュールに適用される可能性のある有用なヒントが除去されます。これは、おそらくミニファイアが修正すべき問題であり、PIFEを積極的にコンパイルするブラウザで最大のパフォーマンスを得るために必要です。

結論​

遅延解析は、起動を高速化し、必要以上のコードを出荷するアプリケーションのメモリーオーバーヘッドを削減します。変数宣言と参照をプレパーサーで適切に追跡できるようにすることで、正確（仕様に基づく）かつ迅速に解析を行うことが可能です。プレパーサーで変数を割り当てることにより、後でパーサーで利用するための変数割り当て情報をシリアル化することができます。これにより、内部関数を再解析する必要がなくなり、深くネストされた関数の非線形解析挙動を回避できます。

パーサーで認識できるPIFEは、起動時にすぐに必要となるコードの初期プレ解析オーバーヘッドを回避します。慎重なプロファイル誘導によるPIFEの使用、またはパッカーによる使用は、冷たい起動速度を向上させる役立つ手段となります。しかし、単にこのヒューリスティックをトリガーするために関数を括弧で包むことは避けるべきです。これは、より多くのコードを積極的にコンパイルする原因となり、起動パフォーマンスの悪化やメモリー使用量の増加を招きます。

Footnotes​

  1. メモリの理由から、V8ではバイトコードをフラッシュします。しばらく使用されない場合、このコードが後で再び必要になると再解析および再コンパイルを行います。コンパイル中に変数メタデータが消失することを許可しているため、怠惰な再コンパイル時に内部関数を再解析することになります。その時点で内部関数のメタデータを再作成するので、それらの内部関数の内部関数を再解析する必要はもうありません。 ↩

  2. PIFEは、プロファイル情報に基づいた関数式と見なすこともできます。 ↩