構文ハイライトの最適化

2017年2月8日 - Alexandru Dima

Visual Studio Codeバージョン1.9には、私たちが取り組んできたクールなパフォーマンス改善が含まれており、その経緯をお話ししたかったのです。

TL;DR VS Code 1.9では、TextMateテーマが作者の意図に忠実に表示され、より高速に、より少ないメモリ消費でレンダリングされます。

構文ハイライト

構文ハイライトは通常、2つのフェーズで構成されます。ソースコードにトークンが割り当てられ、次にテーマによってそれらがターゲットにされ、色が割り当てられ、ほら、ソースコードが色付きでレンダリングされます。これは、テキストエディタをコードエディタに変える唯一の機能です。

VS Code（およびMonaco Editor）でのトークン化は、上から下へ、1パスで1行ずつ実行されます。トークナイザは、トークン化された行の終わりにいくつかの状態を保存でき、それが次の行をトークン化する際に渡されます。これは、TextMate文法を含む多くのトークン化エンジンで使用されているテクニックで、ユーザーが編集を行う際に、エディタがごく一部の行だけを再トークン化することを可能にします。

ほとんどの場合、行に入力するとその行だけが再トークン化されます。トークナイザが同じ終了状態を返し、エディタは後続の行に新しいトークンがないと仮定できるためです。

まれに、行に入力すると、現在の行とそれ以下のいくつかの行の再トークン化/再描画が発生します（等しい終了状態が検出されるまで）。

過去のトークンの表現方法

VS Codeのエディタのコードは、VS Codeが存在するずっと前から書かれていました。それは、Internet ExplorerのF12ツールを含むさまざまなMicrosoftプロジェクトで、Monaco Editorの形で出荷されていました。私たちが持っていた要件の1つは、メモリ使用量を削減することでした。

以前は、手書きでトークナイザーを作成していました（TextMate文法をブラウザで解釈する実用的な方法はありませんでした。今日でもそうですが、それは別の話です）。以下の行の場合、手書きのトークナイザーから次のトークンが生成されます。

tokens = [
  { startIndex: 0, type: 'keyword.js' },
  { startIndex: 8, type: '' },
  { startIndex: 9, type: 'identifier.js' },
  { startIndex: 11, type: 'delimiter.paren.js' },
  { startIndex: 12, type: 'delimiter.paren.js' },
  { startIndex: 13, type: '' },
  { startIndex: 14, type: 'delimiter.curly.js' }
];

このトークン配列を保持するにはChromeで648バイトが必要であり、このようなオブジェクトを格納することはメモリの観点から非常にコストがかかります（各オブジェクトインスタンスは、そのプロトタイプやプロパティリストなどを指すスペースを予約する必要があります）。現在のマシンには多くのRAMがありますが、15文字の行に648バイトを格納するのは許容できません。

そこで当時、トークンを格納するためのバイナリ形式、つまりVS Code 1.8まで使用されていた形式を考案しました。トークンタイプが重複することを考慮し、ファイルごとに個別のマップに収集し、次のような処理を行いました。

//     0        1               2                  3                      4
map = ['', 'keyword.js', 'identifier.js', 'delimiter.paren.js', 'delimiter.curly.js'];
tokens = [
  { startIndex: 0, type: 1 },
  { startIndex: 8, type: 0 },
  { startIndex: 9, type: 2 },
  { startIndex: 11, type: 3 },
  { startIndex: 12, type: 3 },
  { startIndex: 13, type: 0 },
  { startIndex: 14, type: 4 }
];

次に、`startIndex` (32ビット) と `type` (16ビット) を、JavaScriptの数値が持つ53ビットの仮数部の48ビットでエンコードします。トークン配列は最終的にこのように見え、マップ配列はファイル全体で再利用されます。

tokens = [
  //       type                 startIndex
  4294967296, // 0000000000000001 00000000000000000000000000000000
  8, // 0000000000000000 00000000000000000000000000001000
  8589934601, // 0000000000000010 00000000000000000000000000001001
  12884901899, // 0000000000000011 00000000000000000000000000001011
  12884901900, // 0000000000000011 00000000000000000000000000001100
  13, // 0000000000000000 00000000000000000000000000001101
  17179869198 // 0000000000000100 00000000000000000000000000001110
];

このトークン配列を保持するにはChromeで104バイトかかります。要素自体は56バイト（7 x 64ビットの数値）しかかからないはずで、残りはv8が配列と一緒に他のメタデータを保存しているか、またはバッキングストアを2の累乗で割り当てていることが原因だと考えられます。しかし、メモリの節約は明らかであり、1行あたりのトークン数が増えるほど改善されます。私たちはこのアプローチに満足しており、以来この表現方法を使用しています。

注: トークンを格納するよりコンパクトな方法があるかもしれませんが、バイナリ検索可能な線形形式で格納することは、メモリ使用量とアクセス性能の点で最良のトレードオフとなります。

トークン <-> テーマのマッチング

私たちはブラウザのベストプラクティスに従い、スタイルをCSSに任せるのが良い考えだと考えました。そこで、上記の行をレンダリングするときは、`map`を使ってバイナリトークンをデコードし、次のようにトークンタイプを使ってレンダリングしました。

  <span class="token keyword js">function</span>
  <span class="token">&nbsp;</span>
  <span class="token identifier js">f1</span>
  <span class="token delimiter paren js">(</span>
  <span class="token delimiter paren js">)</span>
  <span class="token">&nbsp;</span>
  <span class="token delimiter curly js">{</span>

そして、テーマをCSSで記述しました（例えばVisual Studioテーマ）。

...
.monaco-editor.vs .token.delimiter          { color: #000000; }
.monaco-editor.vs .token.keyword            { color: #0000FF; }
.monaco-editor.vs .token.keyword.flow       { color: #AF00DB; }
...

それは非常にうまくいき、どこかでクラス名を切り替えるだけで、すぐに新しいテーマがエディターに適用されました。

TextMate 文法

VS Codeのリリース時には、手書きのトークナイザーが10個ほどあり、そのほとんどはWeb言語向けでしたが、汎用デスクトップコードエディタとしては明らかに不十分でした。そこで登場したのが、トークン化ルールを記述的に指定する形式であるTextMate文法で、これは数多くのエディタで採用されています。しかし、TextMate文法は手書きのトークナイザーとはまったく異なる動作をするという問題がありました。

TextMate文法は、begin/end状態やwhile状態を使用することで、複数のトークンにまたがるスコープをプッシュできます。以下は、JavaScript TextMate文法での同じ例です（簡潔にするために空白を無視しています）。

VS Code 1.8におけるTextMate文法

スコープスタック全体を通してセクションを作成すると、各トークンは基本的にスコープ名の配列を取得し、トークナイザからは次のようなものが返されます。

tokens = [
  { startIndex: 0, scopes: ['source.js', 'meta.function.js', 'storage.type.function.js'] },
  { startIndex: 8, scopes: ['source.js', 'meta.function.js'] },
  {
    startIndex: 9,
    scopes: [
      'source.js',
      'meta.function.js',
      'meta.definition.function.js',
      'entity.name.function.js'
    ]
  },
  {
    startIndex: 11,
    scopes: [
      'source.js',
      'meta.function.js',
      'meta.parameters.js',
      'punctuation.definition.parameters.js'
    ]
  },
  { startIndex: 13, scopes: ['source.js', 'meta.function.js'] },
  {
    startIndex: 14,
    scopes: [
      'source.js',
      'meta.function.js',
      'meta.block.js',
      'punctuation.definition.block.js'
    ]
  }
];

すべてのトークン型が文字列であり、私たちのコードは文字列配列を扱う準備ができていませんでした。トークンのバイナリエンコーディングへの影響は言うまでもありません。そこで、次の戦略を使用してスコープの配列を単一の文字列に「近似」することにしました。

• 最も具体的でないスコープ（つまり、`source.js`）を無視する。これはほとんど価値がなかったため。
• 残りの各スコープを`"."`で分割する。
• ユニークな部分を重複排除する。
• 残りの部分を安定ソート関数でソートする（辞書順ソートとは限らない）。
• 部分を`"."`で結合する。

tokens = [
  { startIndex: 0, type: 'meta.function.js.storage.type' },
  { startIndex: 9, type: 'meta.function.js' },
  { startIndex: 9, type: 'meta.function.js.definition.entity.name' },
  { startIndex: 11, type: 'meta.function.js.definition.parameters.punctuation' },
  { startIndex: 13, type: 'meta.function.js' },
  { startIndex: 14, type: 'meta.function.js.definition.punctuation.block' }
];

*: 私たちがやっていたことは全く間違っており、「近似」というのはそれに対する非常に丁寧な言葉です:)

これらのトークンは「収まり」、手動で記述されたトークナイザと同じコードパス（バイナリエンコードされる）に従い、同じようにレンダリングされました。

<span class="token meta function js storage type">function</span>
<span class="token meta function js">&nbsp;</span>
<span class="token meta function js definition entity name">f1</span>
<span class="token meta function js definition parameters punctuation">()</span>
<span class="token meta function js">&nbsp;</span>
<span class="token meta function js definition punctuation block">{</span>

TextMate テーマ

TextMateテーマは、特定のスコープを持つトークンを選択し、色、太字などのテーマ情報を適用するスコープセレクタと連携します。

以下のスコープを持つトークンが与えられた場合

//            C                     B                             A
scopes = ['source.js', 'meta.definition.function.js', 'entity.name.function.js'];

以下は、ランク順（降順）に並べられた一致するシンプルなセレクタです。

観察: `entity` は `meta.definition.function` に勝ります。なぜなら、より具体的なスコープ（それぞれ `A` と `B`）に一致するからです。

観察: `entity.name` は `entity` に勝ります。なぜなら、どちらも同じスコープ (`A`) に一致しますが、`entity.name` は `entity` よりも具体的だからです。

親セレクタ

事態をさらに複雑にするために、TextMateテーマは親セレクタもサポートしています。以下に、シンプルなセレクタと親セレクタの両方を使用した例をいくつか示します（ここでもランク順降順にソートされています）。

観察: `source entity` は `entity` に勝ります。なぜなら、どちらも同じスコープ (`A`) に一致しますが、`source entity` は親スコープ (`C`) にも一致するからです。

観察: `entity.name` は `source entity` に勝ります。なぜなら、どちらも同じスコープ (`A`) に一致しますが、`entity.name` は `entity` よりも具体的だからです。

注: スコープを除外する3番目の種類のセレクタもありますが、ここでは説明しません。私たちはこの種類のサポートを追加していませんし、実際にはほとんど使用されていないことに気づきました。

VS Code 1.8におけるTextMateテーマ

Monokaiテーマのルールを2つ紹介します（ここでは簡潔にするためにJSON形式で、オリジナルはXML形式です）。

...
// Function name
{ "scope": "entity.name.function", "fontStyle": "", "foreground":"#A6E22E" }
...
// Class name
{ "scope": "entity.name.class", "fontStyle": "underline", "foreground":"#A6E22E" }
...

VS Code 1.8では、「近似された」スコープに一致させるため、以下の動的なCSSルールを生成していました。

...
/* Function name */
.entity.name.function { color: #A6E22E; }
...
/* Class name */
.entity.name.class { color: #A6E22E; text-decoration: underline; }
...

そして、「近似された」スコープと「近似された」ルールをCSSにマッチングさせるように任せていました。しかし、CSSのマッチングルールはTextMateセレクタのマッチングルールとは異なり、特にランキングに関しては異なります。CSSのランキングは一致したクラス名の数に基づいていますが、TextMateセレクタのランキングにはスコープの具体性に関する明確なルールがあります。

そのため、VS CodeのTextMateテーマは「まあまあ」に見えましたが、決して作者の意図通りではありませんでした。時には違いは小さいものでしたが、時にはこれらの違いがテーマの雰囲気を完全に変えてしまうこともありました。

いくつかの星が並ぶ

時間の経過とともに、私たちは手書きのトークナイザーを段階的に廃止してきました（最後のHTML用トークナイザーはわずか数ヶ月前です）。そのため、今日のVS Codeでは、すべてのファイルがTextMate文法でトークン化されています。Monaco Editorの場合、ほとんどのサポート言語でMonarch（TextMate文法と本質的に似ていますが、より表現力豊かでブラウザで実行できる記述的トークン化エンジン）の使用に移行し、手動トークナイザー用のラッパーを追加しました。総合的に見ると、これは新しいトークン化形式をサポートするために、3つのトークンプロバイダー（TextMate、Monarch、および手動ラッパー）を変更する必要があることを意味し、10個以上ではありません。

数ヶ月前、私たちはVS Codeコアにあるトークンタイプを読み取るすべてのコードをレビューし、それらのコンシューマーが文字列、正規表現、またはコメントのみを気にしていることに気づきました。たとえば、括弧一致ロジックは、スコープに`"string"`、`"comment"`、または`"regex"`を含むトークンを無視します。

最近、社内パートナー（Monaco Editorを使用しているマイクロソフト内の他のチーム）から、Monaco EditorでIE9とIE10のサポートが不要になったという承諾を得ました。

おそらく最も重要なのは、エディタの最も投票された機能がミニマップのサポートであることです。合理的な時間でミニマップをレンダリングするには、DOMノードやCSSマッチングを使用することはできません。おそらくキャンバスを使用することになり、各トークンの色をJavaScriptで知る必要があるので、それらの小さな文字を適切な色で描画できます。

おそらく最大のブレークスルーは、トークンがテーマに一致する場合や、括弧一致が文字列をスキップする場合にのみ効果を発揮するため、トークンもそのスコープも保存する必要がないと気づいたことです。

最後に、VS Code 1.9の新機能

TextMateテーマの表現

非常にシンプルなテーマは次のようになります。

theme = [
  {                                  "foreground": "#F8F8F2"                           },
  { "scope": "var",                  "foreground": "#F8F8F2"                           },
  { "scope": "var.identifier",       "foreground": "#00FF00", "fontStyle": "bold"      },
  { "scope": "meta var.identifier",  "foreground": "#0000FF"                           },
  { "scope": "constant",             "foreground": "#100000", "fontStyle": "italic"    },
  { "scope": "constant.numeric",     "foreground": "#200000"                           },
  { "scope": "constant.numeric.hex",                          "fontStyle": "bold"      },
  { "scope": "constant.numeric.oct",                          "fontStyle": "underline" },
  { "scope": "constant.numeric.dec", "foreground": "#300000"                           },
];

ロードすると、テーマに表示される各ユニークな色に対してIDが生成され、カラーマップに格納されます（上記のトークンタイプの場合と同様）。

//                          1          2          3          4          5           6
colorMap = ["reserved", "#F8F8F2", "#00FF00", "#0000FF", "#100000", "#200000", "#300000"]
theme = [
  {                                  "foreground": 1                           },
  { "scope": "var",                  "foreground": 1,                          },
  { "scope": "var.identifier",       "foreground": 2, "fontStyle": "bold"      },
  { "scope": "meta var.identifier",  "foreground": 3                           },
  { "scope": "constant",             "foreground": 4, "fontStyle": "italic"    },
  { "scope": "constant.numeric",     "foreground": 5                           },
  { "scope": "constant.numeric.hex",                  "fontStyle": "bold"      },
  { "scope": "constant.numeric.oct",                  "fontStyle": "underline" },
  { "scope": "constant.numeric.dec", "foreground": 6                           },
];

次に、テーマのルールからトライ木データ構造を生成し、各ノードに解決されたテーマオプションを保持します。

観察: `constant.numeric.hex` と `constant.numeric.oct` のノードには、`constant.numeric` からこの命令を継承するため、フォアグラウンドを `5` に変更する命令が含まれています。

観察: `var.identifier` のノードは、追加の親ルール `meta var.identifier` を保持し、それに応じてクエリに応答します。

スコープがどのようにテーマされるべきかを知りたい場合、このトライ木にクエリできます。

例

トークン化の変更点

VS Codeで使用されるすべてのTextMateトークン化コードは、VS Codeから独立して使用できる別のプロジェクト、vscode-textmateに存在します。`vscode-textmate`でスコープスタックを表現する方法を変更し、完全に解決された`metadata`も格納する不変のリンクリストになりました。

新しいスコープをスコープスタックにプッシュする際、テーマトライ木で新しいスコープを検索します。スコープスタックから継承したものとテーマトライ木が返すものに基づいて、スコープリストに対して完全に解決された目的のフォアグラウンドまたはフォントスタイルを直ちに計算できます。

いくつかの例

スコープスタックからポップする場合、前のスコープリスト要素に格納されているメタデータを使用するだけで済むため、何も計算する必要はありません。

以下は、スコープリストの要素を表すTypeScriptクラスです。

export class ScopeListElement {
    public readonly parent: ScopeListElement;
    public readonly scope: string;
    public readonly metadata: number;
    ...
}

32ビットのメタデータを格納します。

/**
 * - -------------------------------------------
 *     3322 2222 2222 1111 1111 1100 0000 0000
 *     1098 7654 3210 9876 5432 1098 7654 3210
 * - -------------------------------------------
 *     xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
 *     bbbb bbbb bfff ffff ffFF FTTT LLLL LLLL
 * - -------------------------------------------
 *  - L = LanguageId (8 bits)
 *  - T = StandardTokenType (3 bits)
 *  - F = FontStyle (3 bits)
 *  - f = foreground color (9 bits)
 *  - b = background color (9 bits)
 */

最後に、トークン化エンジンからトークンをオブジェクトとして出力する代わりに

// These are generated using the Monokai theme.
tokens_before = [
  { startIndex: 0, scopes: ['source.js', 'meta.function.js', 'storage.type.function.js'] },
  { startIndex: 8, scopes: ['source.js', 'meta.function.js'] },
  {
    startIndex: 9,
    scopes: [
      'source.js',
      'meta.function.js',
      'meta.definition.function.js',
      'entity.name.function.js'
    ]
  },
  {
    startIndex: 11,
    scopes: [
      'source.js',
      'meta.function.js',
      'meta.parameters.js',
      'punctuation.definition.parameters.js'
    ]
  },
  { startIndex: 13, scopes: ['source.js', 'meta.function.js'] },
  {
    startIndex: 14,
    scopes: [
      'source.js',
      'meta.function.js',
      'meta.block.js',
      'punctuation.definition.block.js'
    ]
  }
];

// Every even index is the token start index, every odd index is the token metadata.
// We get fewer tokens because tokens with the same metadata get collapsed
tokens_now = [
  // bbbbbbbbb fffffffff FFF TTT LLLLLLLL
  0,
  16926743, // 000000010 000001001 001 000 00010111
  8,
  16793623, // 000000010 000000001 000 000 00010111
  9,
  16859159, // 000000010 000000101 000 000 00010111
  11,
  16793623 // 000000010 000000001 000 000 00010111
];

そして、それらは以下のようにレンダリングされます。

<span class="mtk9 mtki">function</span>
<span class="mtk1">&nbsp;</span>
<span class="mtk5">f1</span>
<span class="mtk1">()&nbsp;{</span>

トークンはトークナイザから直接Uint32Arrayとして返されます。私たちはバッキングのArrayBufferを保持し、上記の例ではChromeで96バイトかかります。要素自体は32バイト（8 x 32ビット数値）しかかからないはずですが、ここでもv8のメタデータオーバーヘッドを観察しているのでしょう。

いくつかの数字

以下の測定値を得るために、特性と文法が異なる3つのファイルを選択しました。

私はWindows上の比較的強力なデスクトップマシン（Electron 32ビットを使用）でテストを実行しました。

私は、同じTextMate文法が両方のVS Codeバージョンで使用されていることを確認したり、両方のバージョンでリッチ言語機能をオフにしたり、VS Code 1.8で存在し、VS Code 1.9ではもはや存在しない100スタック深度制限を解除したりするなど、りんごとりんごを比較するためにソースコードにいくつかの変更を加える必要がありました。また、bootstrap.min.cssを複数行に分割し、各行を20k文字未満にする必要がありました。

トークン化時間

トークン化はUIスレッドで譲渡的に実行されるため、以下の時間を測定するために同期的に実行するように強制するコードを追加する必要がありました（10回の実行の中央値を提示）。

トークン化でテーマのマッチングも行われるようになったとはいえ、時間短縮は各行を1パスで処理することで説明できます。以前は、トークン化パス、スコープを文字列に「近似する」二次パス、トークンをバイナリエンコードする三次パスがありましたが、現在はTextMateトークン化エンジンから直接バイナリエンコードされた形式でトークンが生成されます。ガベージコレクションが必要な生成オブジェクトの量も大幅に削減されました。

メモリ使用量

特に大きなファイルでは、折りたたみが多くのメモリを消費するため（これは別の機会の最適化です）、以下のヒープスナップショットの数値は、折りたたみをオフにして収集しました。これは、元のファイル文字列を考慮しない、モデルによって保持されているメモリを示します。

メモリ使用量が削減された理由は、トークンマップを保持しなくなったこと、同じメタデータを持つ連続するトークンの統合、そしてバッキングストアとして`ArrayBuffer`を使用したことによって説明できます。空白は目に見えないため、空白のみのトークンを常に前のトークンに統合することで、さらに改善できる可能性があります。

新しいTextMateスコープインスペクタウィジェット

テーマや文法の作成とデバッグに役立つ新しいウィジェットを追加しました。「コマンドパレット」（⇧⌘P（Windows、Linux Ctrl+Shift+P））で「開発者: エディタのトークンとスコープを検査」を実行して利用できます。

変更の検証

エディタのこのコンポーネントに変更を加えることは、私たちのアプローチ（新しいトライ木作成コード、新しいバイナリエンコーディング形式など）におけるバグが、ユーザーが目にする大きな違いにつながる可能性があるため、深刻なリスクを伴いました。

VS Codeには、私たちが作成する5つのテーマ（Light、Light+、Dark、Dark+、High Contrast）全体で、出荷するすべてのプログラミング言語の色の整合性を保証する統合スイートがあります。これらのテストは、テーマのいずれかを変更する場合と、特定の文法を更新する場合の両方に非常に役立ちます。73の統合テストのそれぞれは、フィクスチャファイル（例：test.c）と5つのテーマの期待される色（test_c.json）で構成されており、私たちのCIビルドで各コミット時に実行されます。

トークン化の変更を検証するために、古いCSSベースのアプローチを使用して、私たちが提供する14のすべてのテーマ（私たちが作成する5つのテーマだけではない）全体で、これらのテストから色付け結果を収集しました。その後、変更を加えるたびに、新しいトライ木ベースのロジックを使用して同じテストを実行し、カスタム構築されたビジュアル差分（およびパッチ）ツールを使用して、すべての色の違いを調査し、色の変更の根本原因を特定しました。この手法を使用して少なくとも2つのバグを発見し、VS Codeのバージョン間で色の変更を最小限に抑えるために、5つのテーマを変更することができました。

変更前と変更後

以下に、VS Code 1.8とVS Code 1.9で表示されたさまざまなカラーテーマを示します。

Monokai テーマ

Quiet Light テーマ

Red テーマ

まとめ

VS Code 1.9へのアップグレードで得られるCPU時間とRAMの増加を評価していただけると幸いです。今後も皆様が効率的で快適な方法でコーディングできるよう、引き続き支援してまいります。

楽しくコーディングしましょう！

Alexandru Dima、VS Codeチームメンバー @alexdima123