究極に高速な解析、第1部：スキャナーの最適化
JavaScriptプログラムを実行するには、まずソーステキストをV8が理解できる形式に処理する必要があります。V8は、ソースを抽象構文木（AST）というプログラム構造を表すオブジェクトのセットに解析することから始めます。このASTはIgnitionによってバイトコードにコンパイルされます。この解析+コンパイルフェーズの性能は重要です。V8はコンパイルが終わるまでコードを実行することができないからです。このブログ記事のシリーズでは、解析に焦点を当て、V8で超高速のパーサーを実現するための取り組みについて説明します。
実際には、このシリーズはパーサーよりも1つ前の段階から始まります。V8のパーサーは、スキャナーによって提供される「トークン」を消費します。トークンとは、単一の意味を持つ文字列、識別子、++のような演算子など、1文字または複数文字のブロックです。スキャナーは、基盤となる文字ストリームの連続した文字を組み合わせることでこれらのトークンを構築します。
スキャナーはUnicode文字のストリームを消費します。これらのUnicode文字は常にUTF-16コードユニットのストリームからデコードされます。さまざまなエンコーディングのためにスキャナーやパーサーを分岐させたり専用化したりするのを避けるため、単一のエンコーディングのみがサポートされており、JavaScript文字列のエンコーディングであり、ソース位置がそのエンコーディングに基づいて提供される必要があるため、UTF-16が選択されました。UTF16CharacterStreamは、基盤となるLatin1、UTF-8、またはUTF-16エンコーディングに対して、V8がChromeから受け取る（Chromeはネットワークから受け取る）UTF-16の（場合によってはバッファされた）ビューを提供します。複数のエンコーディングをサポートすることに加えて、スキャナーと文字ストリームの分離により、ネットワーク経由でまだデータの一部しか受信していない場合でも、完全なソースが利用可能であるかのように透明にスキャンできるようになります。
スキャナーと文字ストリームの間のインターフェースは、次のUTF-16コードユニットを返すか、入力の終わりを示すために-1を返すメソッドUtf16CharacterStream::Advance()です。UTF-16ではすべてのUnicode文字を単一のコードユニットでエンコードすることはできません。基本多言語面外の文字は、サロゲートペアと呼ばれる2つのコードユニットとしてエンコードされます。ただし、スキャナーはUnicode文字を操作するので、この低レベルのストリームインターフェースをScanner::Advance()メソッドでラップし、UTF-16コードユニットを完全なUnicode文字にデコードします。現在デコードされた文字はバッファに格納され、Scanner::ScanString()](https://cs.chromium.org/chromium/src/v8/src/scanner.cc?rcl=edf3dab4660ed6273e5d46bd2b0eae9f3210157d&l=775)などのスキャンメソッドによって取得されます。
スキャナーは、JavaScript内の最長曖昧文字列列1である最大4文字の先読みを基に、特定のスキャナーメソッドまたはトークンを選択します。その後、ScanStringなどのメソッドが選択されると、そのトークンの残りの文字を消費し、次にスキャンされるトークン用にトークンの一部ではない最初の文字をバッファします。ScanStringの場合、それはエスケープシーケンスをデコードしながら、スキャンされた文字をLatin1またはUTF-16としてエンコードされたバッファにコピーします。
空白
トークンは、改行、スペース、タブ、単一行コメント、多行コメントなど、さまざまな種類の空白によって区切ることができます。一種類の空白の後で別の種類の空白が続く場合があります。空白は、2つのトークン間で改行を引き起こした場合に意味を持ち、自動セミコロン挿入を引き起こす可能性があります。そのため、次のトークンをスキャンする前に、すべての空白がスキップされて改行が発生したかどうかが追跡されます。実際のJavaScriptの本番コードはほとんどが縮小されているため、多文字空白はめったに使われません。そのため、V8はそれぞれの種類の空白を等しくスキャンし、通常のトークンであるかのように処理します。例えば、最初のトークン文字が/で、次にもう一つの/が続く場合、V8はこれを単一行コメントとしてスキャンし、その結果Token::WHITESPACEを返します。そのループは他のトークンを見つけるまで単純にトークンのスキャンを続けます。つまり、次のトークンが空白に続かない場合、空白を明示的にチェックすることなく、すぐに関連するトークンスキャンを開始します。
しかしながら、ループ自体はスキャンされたトークンごとにオーバーヘッドを追加します。それには、スキャンしたばかりのトークンを検証するための分岐が必要です。スキャンしたばかりのトークンがToken::WHITESPACEである可能性がある場合のみループを続ける方が良いでしょう。それ以外の場合、ループからすぐに抜け出すべきです。これを実現するために、ループ自体を別のヘルパーメソッドに移動し、トークンがToken::WHITESPACEでないことが確実な場合すぐに返すようにします。このような変更は非常に小さく見えるかもしれませんが、スキャンされたトークンごとのオーバーヘッドを削減します。これは特に、句読点のような非常に短いトークンに対して違いを生みます。
識別子のスキャン
最も複雑でありながら最も一般的なトークンは、識別子トークンです。これは主にJavaScriptで変数名などに使用されます。識別子はUnicode文字のID_Startプロパティから始まり、オプションでID_Continueプロパティを持つ文字列が続きます。Unicode文字がID_StartまたはID_Continueプロパティを持つかどうかの確認は非常にコストがかかります。文字とそのプロパティ間のキャッシュマッピングを挿入することで、これを少し高速化することができます。
ただし、ほとんどのJavaScriptソースコードはASCII文字で書かれています。ASCII範囲の文字では、a-z、A-Z、$および_のみが識別子開始文字です。ID_Continueにはさらに0-9が含まれます。我々は各128のASCII文字について、その文字がID_StartまたはID_Continue文字であるかどうかを示すフラグ付きテーブルを構築することで識別子スキャンを高速化します。スキャン中の文字がASCII範囲内である場合、このテーブルの対応するフラグを調べ、一つの分岐でプロパティを確認します。文字がID_Continueプロパティを持たない最初の文字が現れるまで、その文字は識別子の一部と見なされます。
この投稿で取り上げたすべての改善により、識別子スキャン性能の違いは以下の通りになります:
長い識別子のスキャンが速くなるのは直感に反するかもしれません。識別子の長さを増やすことで性能が向上するのではないかと思われるでしょう。長い識別子のスキャンがMB/sの観点で単純に速い理由は、非常にタイトなループ内に長く滞在し、パーサーに戻る必要がないためです。ただし、アプリケーションの性能の観点から重要なのは、完全なトークンがどれだけ速くスキャンできるかです。次のグラフは、おおよそのトークン長に対する秒間のトークン数を示しています:
ここで、短い識別子を使うことでアプリケーションのパース性能が向上することがはっきりと示されています。我々は一秒間により多くのトークンをスキャンすることが可能です。つまり、MB/sが速く見えるサイトは単純に情報密度が低く、実際には一秒間に生成されるトークンが少なくなっています。
縮小された識別子の内部化
すべての文字列リテラルと識別子はスキャナーとパーサー間の境界で重複除去されます。パーサーが文字列または識別子の値を要求すると、可能なリテラル値ごとに一意の文字列オブジェクトが返されます。これは通常、ハッシュテーブル検索を必要とします。JavaScriptコードはしばしば縮小されているため、V8は単一のASCII文字列に対して簡単な検索テーブルを利用します。
キーワード
キーワードは言語によって定義された識別子の特別なサブセットです。例えば、if、else、functionなどです。V8のスキャナーは識別子とは異なるトークンをキーワードに対して返します。識別子をスキャンした後、その識別子がキーワードかどうかを認識する必要があります。JavaScriptのすべてのキーワードは小文字のa-zのみを含むため、ASCII文字がキーワード開始および続行可能な文字かどうかを示すフラグを保持します。
フラグに基づいて識別子がキーワードである可能性がある場合、その識別子の最初の文字を切り替えることでキーワード候補のサブセットを見つけることができます。識別子の最初の文字の数の方がキーワードの長さよりも多いので、後続の分岐を減らすことができます。各文字に対して、キーワードの可能な長さに基づいて分岐し、長さも一致する場合のみ識別子をキーワードと比較します。
より良い方法は、完全ハッシュと呼ばれるテクニックを使用することです。キーワードのリストが静的であるため、各識別子に対して最大1つの候補キーワードを与える完全ハッシュ関数を計算できます。V8では、この関数を計算するためにgperfを使用しています。結果は、長さと最初の2つの識別子文字からハッシュを計算し、単一の候補キーワードを検索します。そのキーワードの長さが入力識別子の長さと一致する場合にのみ、識別子をキーワードと比較します。これにより、特に識別子がキーワードでない場合に、判断に必要な分岐が少なくて済むため、速度が向上します。
サロゲートペア
前述のように、スキャナーはUTF-16でエンコードされた文字ストリーム上で動作しますが、Unicode文字を消費します。補助平面内の文字は識別子トークンにのみ特別な意味を持ちます。たとえば、そのような文字が文字列に含まれる場合、文字列の終了を意味しません。単独のサロゲートもJSでサポートされており、単にソースからコピーされます。そのため、必要になるまでサロゲートペアを結合することを避け、Unicode文字ではなくUTF-16コードユニットに直接スキャナーを動作させる方が良いのです。文字列をスキャンしているとき、サロゲートペアを探したり結合したり、その後文字列を構築するために文字を再分割する必要はありません。スキャナーがサロゲートペアに対処する必要があるのは、トークンスキャンの開始時に、他の何とも認識できない文字の場合のみ、結合して結果が識別子の開始かどうかを確認する時です。同様に、非ASCII文字を扱う識別子スキャンの遅い経路で結合する必要があります。
AdvanceUntil
スキャナーとUTF16CharacterStreamの間のインターフェースは、状態の多い境界を持っています。このストリームはバッファ内の自分の位置を追跡し、消費されたコードユニットごとに位置を進めます。スキャナーは、受信したコードユニットをバッファにため込み、その後その文字を要求したスキャンメソッドに戻ります。そのメソッドはバッファされた文字を読み取り、その値に基づいて処理を続行します。この設計はレイヤリングをきれいに保ちますが、非常に遅いです。昨年秋、インターンのFlorian Sattlerが、このレイヤリングの利点を保持しつつ、ストリーム内のコードユニットへのアクセスを大幅に高速化する改良インターフェースを考案しました。テンプレート化された関数AdvanceUntilは、特定のスキャンヘルパーに特化し、ストリーム内の各文字に対してヘルパーを呼び出し、ヘルパーがfalseを返すまで繰り返します。これにより、スキャナーが抽象化を壊すことなく基礎データに直接アクセスできるようになります。これにより、EndOfInputに対処する必要がなくなり、スキャンヘルパー関数が実際に簡素化されます。
AdvanceUntilは、大量の文字を消費する必要があるスキャン関数の速度を向上させるのに特に有用です。これは、以前示した識別子を高速化するためだけでなく、文字列2やコメントにも使用されています。
結論
スキャンの性能は、パーサーの性能の基盤となります。私たちはスキャナーを可能な限り効率的に調整しました。その結果、全体的な改善が見られ、単一トークンスキャンの速度が約1.4倍、文字列スキャンが1.3倍、複数行コメントスキャンが2.1倍、識別子スキャンが長さに応じて1.2～1.5倍向上しました。
しかし、スキャナーだけでできることには限りがあります。開発者としては、プログラムの情報密度を高めることで解析性能をさらに向上させることができます。最も簡単な方法は、ソースコードを最小化し、不要な空白を削除し、可能な限り非ASCII識別子を避けることです。理想的には、これらのステップはビルドプロセスの一環として自動化され、コード作成時に気にする必要がなくなります。