構文強調の最適化

2017年2月8日 - Alexandru Dima

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

要約: TextMate テーマは、VS Code 1.9 では、作者が意図したとおりに表示されるようになり、レンダリングが高速化され、メモリ消費量も削減されます。

構文強調

構文強調は通常、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 }
];

次に、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 のリリース時には、主に Web 言語用の手書きトークナイザーが 10 個ほどありましたが、汎用デスクトップコードエディターには間違いなく不十分でした。そこで、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は、より具体的なスコープ（それぞれA over B）に一致するため、meta.definition.functionよりも優先されます。

観察: entity.nameは、両方とも同じスコープ（A）に一致しますが、entity.nameはentityよりも具体的であるため、entityよりも優先されます。

親セレクター

事を少し複雑にするために、TextMate テーマは親セレクターもサポートしています。次に、単純なセレクターと親セレクターの両方を使用した例をいくつか示します（再びランク降順でソート）。

観察: source entityは、両方とも同じスコープ（A）に一致しますが、source entityは親スコープ（C）にも一致するため、entityよりも優先されます。

観察: entity.nameは、両方とも同じスコープ（A）に一致しますが、entity.nameはentityよりも具体的であるため、source entityよりも優先されます。

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

VS Code 1.8 における TextMate テーマ

次に、2 つの Monokai テーマルールを示します（ここでは簡潔にするために 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 を消費する Microsoft 内の他のチーム）から、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も格納するimmutable linked listに変更しました。

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

いくつかの例

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

次に、スコープリストの要素を表す 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 ビットを使用）。

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

トークン化時間

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

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

メモリ使用量

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

メモリ使用量の削減は、トークンマップを保持しなくなったこと、同じメタデータを持つ連続するトークンの縮小、およびバッキングストアとしてのArrayBufferの使用によって説明できます。空白のみのトークンを常に前のトークンに縮小することで、ここをさらに改善できます。空白がどのようにレンダリングされても問題ないためです（空白は非表示です）。

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

テーマまたはグラマーの作成とデバッグに役立つ新しいウィジェットを追加しました。コマンドパレットで開発者: エディタートークンとスコープの検査を実行できます (⇧⌘P (Windows, Linux Ctrl+Shift+P))。

変更の検証

エディターのこのコンポーネントに変更を加えることは、新しいトライ木作成コード、新しいバイナリエンコード形式などのアプローチにバグがあると、ユーザーに大きな違いが生じる可能性があるため、重大なリスクをもたらしました。

VS Code には、私たちが作成した 5 つのテーマ（Light、Light+、Dark、Dark+、High Contrast）全体で、出荷するすべてのプログラミング言語の色をアサートする統合スイートがあります。これらのテストは、テーマの 1 つに変更を加える場合と、特定のグラマーを更新する場合の両方で非常に役立ちます。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