語法高亮最佳化

2017年2月8日 - Alexandru Dima

Visual Studio Code 1.9 版本包含了一個我們一直在努力實現的很棒的效能改進，我想分享一下它的故事。

TL;DR TextMate 主題在 VS Code 1.9 中的顯示將更接近其作者的意圖，同時渲染速度更快，記憶體消耗更少。

語法高亮

語法高亮通常包括兩個階段。首先，將標記（tokens）分配給原始碼；然後，主題以這些標記為目標，分配顏色，這樣，您的原始碼就以彩色的形式呈現了。這是將文字編輯器變成程式碼編輯器的核心功能。

VS Code（以及 Monaco 編輯器）中的標記化（tokenization）是逐行、自上而下、一次性完成的。標記器可以在標記完一行後儲存一些狀態，該狀態將在標記下一行時傳回。這是包括 TextMate 語法在內的許多標記化引擎使用的一種技術，它允許編輯器在使用者進行編輯時只重新標記一小部分行。

大多數情況下，在一行上輸入只會導致該行重新標記，因為標記器返回相同的結束狀態，編輯器可以假設後續行不會獲取新的標記

在更罕見的情況下，在一行上輸入會導致當前行及其下面的一些行重新標記/重新繪製（直到遇到相同的結束狀態）

我們過去如何表示標記

VS Code 中的編輯器程式碼是在 VS Code 存在之前很久編寫的。它以 Monaco 編輯器 的形式隨各種 Microsoft 專案釋出，包括 Internet Explorer 的 F12 工具。我們當時的一個要求是減少記憶體使用。

過去，我們手動編寫標記器（即使在今天，在瀏覽器中解釋 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 的冪次方分配後備儲存。然而，記憶體節省是顯而易見的，並且隨著每行標記的增加而變得更好。我們對這種方法很滿意，並且從那時起一直使用這種表示方式。

注意：可能還有更緊湊的儲存標記的方式，但將它們儲存為可進行二分搜尋的線性格式在記憶體使用和訪問效能方面提供了最佳權衡。

標記 <-> 主題匹配

我們認為遵循瀏覽器最佳實踐是個好主意，例如將樣式留給 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 更具體。

注意：還有第三種選擇器，涉及排除作用域，我們在此不討論。我們沒有新增對這種型別的支援，並且我們注意到它在實際中很少使用。

VS Code 1.8 中的 TextMate 主題

這裡有兩個 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 編輯器，我們已遷移到為大多數受支援的語言使用 Monarch（一個描述性的標記化引擎，核心上與 TextMate 語法相似，但更具表現力，可以在瀏覽器中執行），並且我們為手動標記器添加了一個包裝器。總而言之，這意味著支援一種新的標記化格式需要更改 3 個標記提供者（TextMate、Monarch 和手動包裝器），而不是超過 10 個。

幾個月前，我們審查了 VS Code 核心中讀取標記型別的所有程式碼，我們注意到這些消費者只關心字串、正則表示式或註釋。例如，括號匹配邏輯會忽略包含作用域 "string"、"comment" 或 "regex" 的標記。

最近，我們得到了內部合作伙伴（Microsoft 內部使用 Monaco 編輯器的其他團隊）的同意，他們不再需要在 Monaco 編輯器中支援 IE9 和 IE10。

可能最重要的是，編輯器最受好評的功能是 minimap 支援。為了在合理的時間內渲染 minimap，我們不能使用 DOM 節點和 CSS 匹配。我們可能會使用 canvas，我們需要在 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                           },
];

然後我們將從主題規則生成一個 Trie 資料結構，其中每個節點都保留已解析的主題選項

觀察：constant.numeric.hex 和 constant.numeric.oct 的節點包含將前景色更改為 5 的指令，因為它們從 constant.numeric 繼承了此指令。

觀察：var.identifier 的節點保留了額外的父規則 meta var.identifier，並將相應地回答查詢。

當我們想知道一個作用域應該如何設定主題時，我們可以查詢這個 trie。

例如

標記化更改

VS Code 中使用的所有 TextMate 標記化程式碼都位於一個單獨的專案 vscode-textmate 中，該專案可以獨立於 VS Code 使用。我們更改了在 vscode-textmate 中表示作用域堆疊的方式，使其成為 一個不可變的連結串列，該連結串列還儲存完全解析的 metadata。

當將一個新作用域推送到作用域堆疊時，我們將在主題 trie 中查詢新作用域。然後，我們可以根據從作用域堆疊繼承的內容以及主題 trie 返回的內容，立即計算出作用域列表所需的完全解析的前景色或字型樣式。

一些示例

當從作用域堆疊中彈出時，無需計算任何內容，因為我們可以直接使用儲存在先前作用域列表元素中的元資料。

這是表示作用域列表中元素的 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 元資料開銷。

一些數字

為了獲得以下測量結果，我選擇了三個具有不同特徵和不同語法的文​​件

我在一臺效能相當強大的 Windows 桌面機器上運行了測試（使用 Electron 32 位）。

我不得不對原始碼進行一些更改才能進行公平比較，例如確保在兩個 VS Code 版本中使用了完全相同的語法，關閉兩個版本中的富語言功能，或者取消 VS Code 1.8 中不再存在的 100 堆疊深度限制等。我還必須將 bootstrap.min.css 分成多行，以使每行少於 20k 字元。

標記化時間

標記化在 UI 執行緒上以讓步方式執行，因此我不得不新增一些程式碼來強制它同步執行以測量以下時間（顯示 10 次執行的中位數）

儘管現在標記化還包括主題匹配，但時間節省可以透過對每行進行一次遍歷來解釋。而在以前，會有一個標記化過程，第二個過程將作用域“近似”為字串，第三個過程將標記進行二進位制編碼，現在標記直接從 TextMate 標記化引擎以二進位制編碼方式生成。需要垃圾回收的生成物件數量也大幅減少。

記憶體使用

摺疊功能消耗大量記憶體，特別是對於大檔案（這是另一個時間的最佳化），因此我在關閉摺疊的情況下收集了以下堆快照資料。這顯示了模型持有的記憶體，不包括原始檔案字串

記憶體使用減少可以透過不再保留標記對映、具有相同元資料的連續標記的摺疊以及使用 ArrayBuffer 作為後備儲存來解釋。我們可以透過始終將僅包含空白的標記摺疊到前一個標記中來進一步改進，因為空白的渲染顏色無關緊要（空白是不可見的）。

新的 TextMate 作用域檢查器小部件

我們添加了一個新的小部件來幫助編寫和除錯主題或語法：您可以在命令面板中執行開發人員：檢查編輯器標記和作用域（⇧⌘P (Windows, Linux Ctrl+Shift+P)）。

驗證更改

對編輯器的這個元件進行更改存在一些嚴重的風險，因為我們方法中的任何錯誤（在新 trie 建立程式碼中，在新二進位制編碼格式中等）都可能導致巨大的使用者可見差異。

在 VS Code 中，我們有一個整合套件，它斷言我們釋出的五種主題（Light、Light+、Dark、Dark+、High Contrast）中所有程式語言的顏色。這些測試在更改我們的某個主題以及更新特定語法時都非常有幫助。73 個整合測試中的每一個都包含一個固定檔案（例如 test.c）以及五個主題的預期顏色（test_c.json），並且它們在我們的 CI 構建上的每次提交時都會執行。

為了驗證標記化更改，我們使用舊的基於 CSS 的方法收集了所有 14 個隨附主題（不只是我們編寫的五個主題）的顏色化結果。然後，在每次更改後，我們使用新的基於 trie 的邏輯執行相同的測試，並使用定製的視覺化差異（和補丁）工具，我們檢視每一個顏色差異並找出顏色更改的根本原因。我們使用這種技術捕獲了至少 2 個錯誤，並且我們能夠更改我們的五個主題以在 VS Code 版本之間實現最小的顏色更改

之前和之後

下面是各種顏色主題在 VS Code 1.8 和現在 VS Code 1.9 中的顯示效果

Monokai 主題

Quiet Light 主題

Red 主題

總結

我希望您會喜歡升級到 VS Code 1.9 後獲得的額外 CPU 時間和 RAM，並且我們可以繼續讓您以高效愉快的方式進行編碼。

程式設計愉快！

Alexandru Dima, VS Code 團隊成員 @alexdima123