語法高亮中的最佳化

2017年2月8日 - Alexandru Dima

Visual Studio Code 1.9 版本包含了一個我們一直在努力的酷炫效能改進，我想講述它的故事。

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

語法高亮

語法高亮通常由兩個階段組成。首先將標記分配給原始碼，然後主題會針對這些標記，分配顏色，然後，您的原始碼就以顏色呈現出來。它是將文字編輯器變成程式碼編輯器的重要功能。

VS Code（以及 Monaco 編輯器）中的標記化逐行，從上到下，單次透過執行。標記器可以在標記化行的末尾儲存一些狀態，該狀態將在標記化下一行時傳回。這是許多標記化引擎（包括 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 個手寫標記器，主要用於網路語言，這對於通用桌面程式碼編輯器來說絕對不夠。於是引入了 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。

可能最重要的是，編輯器最受關注的功能是 迷你地圖支援。為了在合理的時間內渲染迷你地圖，我們不能使用 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