語法突顯最佳化

2017 年 2 月 8 日 - Alexandru Dima

Visual Studio Code 1.9 版包含一項我們一直在努力的酷炫效能改進，我想告訴大家這個故事。

重點摘要 TextMate 主題在 VS Code 1.9 中看起來會更像作者的本意，同時渲染速度更快，記憶體消耗更少。

語法突顯

語法突顯通常包含兩個階段。Token 會指派給原始碼，然後主題會以這些 Token 為目標，指派色彩，瞧！您的原始碼就會以色彩渲染。這項功能將文字編輯器轉變為程式碼編輯器。

VS Code (和 Monaco Editor) 中的 Token 化是逐行、從上到下、單次傳遞執行的。Token 化工具可以在 Token 化行的末尾儲存一些狀態，在 Token 化下一行時會傳回該狀態。這是許多 Token 化引擎使用的技術，包括 TextMate 文法，可讓編輯器在使用者進行編輯時僅重新 Token 化一小部分的行。

大多數時候，在一行上輸入會導致僅重新 Token 化該行，因為 Token 化工具傳回相同的結束狀態，且編輯器可以假設後續行不會取得新的 Token

更罕見的情況是，在一行上輸入會導致重新 Token 化/重新繪製目前行和下方的一些行 (直到遇到相同的結束狀態)

過去我們如何表示 Token

VS Code 中編輯器的程式碼在 VS Code 存在之前就已撰寫完成。它以 Monaco Editor 的形式在各種 Microsoft 專案 (包括 Internet Explorer 的 F12 工具) 中發行。我們當時的一項要求是減少記憶體使用量。

過去，我們是手動撰寫 Token 化工具 (即使在今天，在瀏覽器中解譯 TextMate 文法仍然不可行，但那是另一個故事)。對於以下這行，我們會從我們手動撰寫的 Token 化工具取得以下 Token

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' }
];

保留該 Token 陣列在 Chrome 中佔用 648 個位元組，因此就記憶體而言，儲存這類物件的成本非常高昂 (每個物件執行個體都必須保留空間來指向其原型、其屬性清單等等)。我們目前的機器確實有大量 RAM，但為 15 個字元的行儲存 648 個位元組是無法接受的。

因此，當時，我們想出了一種二進位格式來儲存 Token，這種格式一直使用到 VS Code 1.8 (包括)。鑑於會有重複的 Token 類型，我們將它們收集在一個個別的對應中 (每個檔案)，做法如下

//     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 位元。我們的 Token 陣列最終會像這樣，而對應陣列會針對整個檔案重複使用

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

保留這個 Token 陣列在 Chrome 中佔用 104 個位元組。元素本身應該只佔用 56 個位元組 (7 個 64 位元數字)，而其餘部分可能是因為 v8 儲存其他與陣列相關的中繼資料，或者可能是以 2 的次方配置後端儲存體所造成的。不過，記憶體節省量很明顯，而且每行 Token 越多，效果越好。我們對這種方法感到滿意，而且從那時起就一直使用這種表示法。

注意：可能有更精簡的方式來儲存 Token，但以二進位可搜尋的線性格式儲存 Token，可在記憶體使用量和存取效能方面提供最佳的權衡。

Token <-> 主題比對

我們認為遵循瀏覽器最佳做法會是個好主意，例如將樣式設定留給 CSS，因此在渲染上述行時，我們會使用 map 解碼二進位 Token，然後使用如下的 Token 類型來渲染它

  <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 個手動撰寫的 Token 化工具，主要用於網路語言，這絕對不足以應付一般用途的桌面程式碼編輯器。請看 TextMate 文法，這是一種描述性形式的 Token 化規則指定方式，已被許多編輯器採用。不過，有一個問題，TextMate 文法的運作方式與我們手動撰寫的 Token 化工具不太一樣。

TextMate 文法透過使用 begin/end 狀態或 while 狀態，可以推送跨越多個 Token 的範圍。以下是 JavaScript TextMate 文法下的相同範例 (為簡潔起見，忽略空白字元)

VS Code 1.8 中的 TextMate 文法

如果我們要剖析範圍堆疊，每個 Token 基本上都會取得範圍名稱陣列，而我們會從 Token 化工具取得如下的內容

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'
    ]
  }
];

所有 Token 類型都是字串，而我們的程式碼尚未準備好處理字串陣列，更不用說對 Token 的二進位編碼造成什麼影響了。因此，我們繼續使用以下策略將範圍陣列「近似」* 為單一字串

• 忽略最不特定的範圍 (即 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' }
];

*: 我們當時的做法完全錯誤，「近似」是一個非常好的詞 :)。

這些 Token 接著會「放入」，並遵循與手動撰寫的 Token 化工具相同的程式碼路徑 (取得二進位編碼)，然後也會以相同的方式渲染

<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 主題與 範圍選取器 搭配運作，範圍選取器會選取具有特定範圍的 Token，並將主題資訊 (例如色彩、粗體等) 套用至這些 Token。

假設有一個具有以下範圍的 Token

//            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 主題看起來還可以，但永遠不像作者的本意。有時，差異很小，但有時這些差異會完全改變主題的感覺。

一些美好的巧合

隨著時間的推移，我們已逐步淘汰手動撰寫的 Token 化工具 (最後一個是 HTML，僅在幾個月前)。因此，在今天的 VS Code 中，所有檔案都使用 TextMate 文法進行 Token 化。對於 Monaco Editor，我們已遷移到使用 Monarch (一種描述性 Token 化引擎，在核心上與 TextMate 文法相似，但更具表現力，而且可以在瀏覽器中執行)，適用於大多數支援的語言，而且我們已為手動 Token 化工具新增了包裝函式。總而言之，這表示支援新的 Token 化格式將需要變更 3 個 Token 提供者 (TextMate、Monarch 和手動包裝函式)，而且不會超過 10 個。

幾個月前，我們檢閱了 VS Code 核心中讀取 Token 類型的所有程式碼，我們注意到這些消費者只關心字串、規則運算式或註解。例如，括號比對邏輯會忽略包含範圍 "string"、"comment" 或 "regex" 的 Token。

最近，我們已從我們的內部合作夥伴 (Microsoft 內部使用 Monaco Editor 的其他團隊) 獲得許可，他們不再需要在 Monaco Editor 中支援 IE9 和 IE10。

可能最重要的是，編輯器最受歡迎的功能是 迷你地圖支援。為了在合理的時間內渲染迷你地圖，我們無法使用 DOM 節點和 CSS 比對。我們可能會使用畫布，而且我們需要知道 JavaScript 中每個 Token 的色彩，這樣我們才能用正確的色彩繪製那些小字母。

我們最大的突破可能是，我們不需要儲存 Token，也不需要儲存其範圍，因為 Token 只會在主題比對或括號比對跳過字串方面產生效果。

最後，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"                           },
];

載入時，我們會為主題中顯示的每個唯一色彩產生一個識別碼，並將其儲存在色彩對應中 (與我們對上述 Token 類型所做的類似)

//                          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。

例如

Token 化的變更

VS Code 中使用的所有 TextMate Token 化程式碼都位於個別專案 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)
 */

最後，Token 不是以物件的形式從 Token 化引擎發出

// 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>

Token 會以 Uint32Array 的形式直接從 Token 化工具傳回。我們保留後端 ArrayBuffer，對於上述範例，這在 Chrome 中佔用 96 個位元組。元素本身應該只佔用 32 個位元組 (8 個 32 位元數字)，但我們可能再次觀察到一些 v8 中繼資料額外負荷。

一些數字

為了取得以下測量結果，我挑選了三個具有不同特性和不同文法的檔案

我已在 Windows 上功能相當強大的桌面電腦上執行測試 (該電腦使用 Electron 32 位元)。

我必須對原始碼進行一些變更，才能將蘋果與蘋果進行比較，例如確保在 VS Code 版本中使用完全相同的文法、在兩個版本中都關閉豐富的語言功能，或解除 VS Code 1.8 中存在的 100 個堆疊深度限制，VS Code 1.9 中不再存在此限制等等。我也必須將 bootstrap.min.css 分割成多行，才能讓每行少於 2 萬個字元。

Token 化時間

Token 化以產生方式在 UI 執行緒上執行，因此我必須新增一些程式碼來強制它同步執行，才能測量以下時間 (呈現 10 次執行的中位數)

雖然 Token 化現在也執行主題比對，但時間節省量可以用對每一行執行單次傳遞來解釋。而在此之前，會有一個 Token 化傳遞、一個將範圍「近似」為字串的次要傳遞，以及一個將 Token 進行二進位編碼的第三次傳遞，現在 Token 是直接從 TextMate Token 化引擎以二進位編碼方式產生的。需要進行記憶體回收的產生物件數量也大幅減少。

記憶體使用量

摺疊會消耗大量記憶體，尤其對於大型檔案而言 (這是另一個時間點的最佳化)，因此我已在關閉摺疊的情況下收集以下堆積快照數字。這顯示模型保留的記憶體，不包括原始檔案字串

記憶體使用量減少可以用不再保留 Token 對應、具有相同中繼資料的連續 Token 摺疊，以及使用 ArrayBuffer 作為後端儲存體來解釋。我們可以透過始終將僅限空白字元的 Token 摺疊到先前的 Token 中來進一步改進此處，因為空白字元呈現什麼色彩並不重要 (空白字元是不可見的)。

新的 TextMate 範圍檢查器 Widget

我們新增了一個新的 Widget，以協助撰寫和偵錯主題或文法：您可以使用開發人員：檢查編輯器 Token 和範圍在命令面板中執行它 (⇧⌘P (Windows、Linux Ctrl+Shift+P))。

驗證變更

對編輯器的這個元件進行變更會帶來一些嚴重的風險，因為我們方法中的任何錯誤 (在新的 Trie 建立程式碼、新的二進位編碼格式等等中) 都可能導致使用者可見的巨大差異。

在 VS Code 中，我們有一個整合套件，會針對我們在我們撰寫的五個主題 (淺色、淺色 +、深色、深色 +、高對比) 中發行的所有程式設計語言判斷色彩。當對我們的主題之一進行變更以及更新特定文法時，這些測試都非常有幫助。73 個整合測試中的每一個都包含一個固定裝置檔案 (例如 test.c) 和五個主題的預期色彩 (test_c.json)，而且它們會在我們的 CI 建置 上針對每個認可執行。

為了驗證 Token 化變更，我們已從這些測試中收集色彩化結果，跨越我們隨附的所有 14 個主題 (不只是我們撰寫的五個主題)，使用舊的 CSS 型方法。然後，在每次變更之後，我們使用新的 Trie 型邏輯執行相同的測試，並使用自訂建置的可視化差異 (和修補程式) 工具，我們會深入研究每個色彩差異，並找出色彩變更的根本原因。我們使用此技術至少發現了 2 個錯誤，而且我們能夠變更我們的五個主題，以在 VS Code 版本之間獲得最小的色彩變更

變更前後

以下是各種色彩主題在 VS Code 1.8 和現在在 VS Code 1.9 中的外觀

Monokai 主題

Quiet Light 主題

Red Theme

結論

我希望您會感謝從升級到 VS Code 1.9 獲得的額外 CPU 時間和 RAM，並且我們可以繼續讓您以有效率且愉快的方式編碼。

祝您編碼愉快！

Alexandru Dima，VS Code 團隊成員 @alexdima123