構文強調表示の最適化

2017年2月8日 - Alexandru Dima

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

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

構文強調表示

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

VS Code（およびMonaco Editor）のトークン化は、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 }
];

次に、JavaScript の数値が持つ53の仮数ビットのうち、`startIndex` (32ビット) と `type` (16ビット) を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 文法で、これは多くのエディターで採用されています。しかし、問題が1つありました。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では、サポートされているほとんどの言語で、TextMate文法と本質的に似ていますが、より表現力があり、ブラウザで実行できる記述的なトークン化エンジンであるMonarchを使用するように移行し、手動のトークナイザー用のラッパーも追加しました。全体として、これは新しいトークン化形式をサポートするために、3つのトークンプロバイダー（TextMate、Monarch、手動ラッパー）を変更する必要があることを意味し、10以上ではありません。

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

最近、Monaco Editorを消費するマイクロソフト社内の他のチームである社内パートナーから、Monaco EditorでのIE9およびIE10のサポートが不要になったというOKを得ました。

おそらく最も重要なのは、エディターで最も投票された機能がミニマップのサポートであることです。合理的な時間でミニマップをレンダリングするには、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` のノードには、フォアグラウンドを `5` に変更する指示が含まれています。これは、`constant.numeric` からこの指示を継承しているためです。

観察: `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ビットを使用）でテストを実行しました。

Apple同士を比較するために、ソースコードにいくつかの変更を加える必要がありました。例えば、両方のVS Codeバージョンでまったく同じ文法が使用されていることを確認したり、両方のバージョンでリッチ言語機能をオフにしたり、VS Code 1.8の100スタック深度制限（VS Code 1.9ではもはや存在しない）を解除したりしました。また、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つのテーマを変更することができました。

Before and After

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

Monokai テーマ

Quiet Light テーマ

Red テーマ

結論

VS Code 1.9へのアップグレードによって得られる追加のCPU時間とRAMを高く評価していただければ幸いです。そして、引き続き効率的で快適なコーディングを支援できるよう努力を続けます。

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

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