🚀 取得 ！

文字緩衝區重新實作

2018 年 3 月 23 日，Peng Lyu，@njukidreborn

Visual Studio Code 1.21 版本包含全新的文字緩衝區實作方式，在速度和記憶體使用量方面都更有效能。在這篇部落格文章中，我想分享我們如何選擇和設計資料結構與演算法，以達成這些改進的故事。

關於 JavaScript 程式的效能討論通常會涉及應在原生程式碼中實作多少內容的討論。對於 VS Code 文字緩衝區而言，這些討論在一年前就已開始。在深入探索期間，我們發現以 C++ 實作文字緩衝區可以顯著節省記憶體，但我們沒有看到我們期望的效能提升。在自訂原生表示法和 V8 字串之間轉換字串成本高昂，在我們的案例中，這會損害從以 C++ 實作文字緩衝區操作所獲得的任何效能。我們將在本篇文章的結尾更詳細地討論這一點。

由於不採用原生方式，我們必須找到改進 JavaScript/TypeScript 程式碼的方法。Vyacheslav Egorov 的這篇啟發人心的部落格文章等文章，展示了將 JavaScript 引擎推向極限並盡可能榨取效能的方法。即使沒有低階引擎技巧，仍然有可能透過使用更適合的資料結構和更快的演算法，將速度提高一個或多個數量級。

先前的文字緩衝區資料結構

編輯器的心理模型是以行為基礎。開發人員逐行讀取和寫入原始碼，編譯器提供以行/列為基礎的診斷，堆疊追蹤包含行號，語彙分析引擎逐行執行等等。雖然簡單，但驅動 VS Code 的文字緩衝區實作方式自我們啟動 Monaco 專案的第一天起就沒有太大改變。我們使用行陣列，它運作良好，因為典型的文字文件相對較小。當使用者輸入時，我們會找到陣列中要修改的行並替換它。當插入新行時，我們會將新的行物件拼接到行陣列中，而 JavaScript 引擎會為我們完成繁重的工作。

然而，我們不斷收到報告指出，開啟某些檔案會在 VS Code 中導致記憶體不足崩潰。例如，一位使用者無法開啟一個 35 MB 的檔案。根本原因是該檔案的行數太多，達到 1370 萬行。我們會為每一行建立一個 ModelLine 物件，而每個物件約使用 40-60 位元組，因此行陣列約使用 600MB 記憶體來儲存文件。這大約是初始檔案大小的 20 倍！

行陣列表示法的另一個問題是開啟檔案的速度。為了建構行陣列，我們必須依行分隔符號分割內容，以便為每一行取得一個字串物件。分割本身會損害效能，您將在稍後的基準測試中看到。

尋找新的文字緩衝區實作方式

舊的行陣列表示法可能需要很長時間才能建立，並且消耗大量記憶體，但它可以快速查找行。在理想情況下，我們只會儲存檔案的文字，而不會儲存額外的中繼資料。因此，我們開始尋找需要較少中繼資料的資料結構。在檢閱各種資料結構後，我發現片段表 (piece table) 可能是一個好的起點。

透過使用片段表 (piece table) 避免過多的中繼資料

片段表 (Piece table) 是一種資料結構，用於表示文字文件（TypeScript 原始碼）上的一系列編輯。

class PieceTable {
  original: string; // original contents
  added: string; // user added contents
  nodes: Node[];
}

class Node {
  type: NodeType;
  start: number;
  length: number;
}

enum NodeType {
  Original,
  Added
}

檔案初始載入後，片段表 (piece table) 會在 original 欄位中包含整個檔案內容。added 欄位是空的。有一個 NodeType.Original 類型的單一節點。當使用者在檔案末尾輸入時，我們會將新內容附加到 added 欄位，並且我們將在節點列表的末尾插入一個 NodeType.Added 類型的新節點。同樣地，當使用者在節點中間進行編輯時，我們會分割該節點並根據需要插入一個新節點。

下面的動畫顯示如何在片段表 (piece table) 結構中逐行存取文件。它有兩個緩衝區 (original 和 added) 和三個節點（這是由在 original 內容中間插入內容所造成的）。

Traditional piece table

片段表 (piece table) 的初始記憶體使用量接近文件的大小，而修改所需的記憶體與編輯次數和新增的文字成正比。因此，片段表 (piece table) 通常能有效利用記憶體。然而，低記憶體使用量的代價是存取邏輯行速度較慢。例如，如果您想要取得第 1000 行的內容，唯一的方法是從文件開頭開始逐個字元迭代，找到前 999 個換行符號，然後讀取每個字元直到下一個換行符號。

使用快取來加快行查找速度

傳統的片段表 (piece table) 節點僅包含偏移量，但我們可以新增換行符號資訊以加快行內容查找速度。儲存換行符號位置的直覺方式是儲存節點文字中遇到的每個換行符號的偏移量。

class PieceTable {
  original: string;
  added: string;
  nodes: Node[];
}

class Node {
  type: NodeType;
  start: number;
  length: number;
  lineStarts: number[];
}

enum NodeType {
  Original,
  Added
}

例如，如果您想要存取給定 Node 實例中的第二行，您可以讀取 node.lineStarts[0] 和 node.lineStarts[1]，這將提供行開始和結束的相對偏移量。由於我們知道一個節點有多少個換行符號，因此存取文件中的隨機行非常簡單：從第一個節點開始讀取每個節點，直到找到目標換行符號。

演算法仍然很簡單，而且比以前更好，因為我們現在可以跳過整個文字區塊，而不是逐字元迭代。我們稍後會看到我們可以做得更好。

避免字串串聯陷阱

片段表 (piece table) 保留兩個緩衝區，一個用於從磁碟載入的原始內容，另一個用於使用者編輯。在 VS Code 中，我們使用 Node.js fs.readFile 載入文字檔，它以 64KB 的區塊傳遞內容。因此，當檔案很大時，例如 64 MB，我們將收到 1000 個區塊。在收到所有區塊後，我們可以將它們串聯成一個大型字串，並將其儲存在片段表 (piece table) 的 original 欄位中。

這聽起來很合理，直到 V8 妨礙您。我嘗試開啟一個 500MB 的檔案，並收到例外狀況，因為在我使用的 V8 版本中，字串的最大長度為 256MB。此限制將在未來版本的 V8 中提升至 1GB，但這並不能真正解決問題。

我們可以保留緩衝區列表，而不是保留 original 和 added 緩衝區。我們可以嘗試縮短該列表，或者我們可以從 fs.readFile 返回的內容中獲得啟發，並避免任何字串串聯。每次我們從磁碟收到 64KB 區塊時，我們都會將其直接推送到 buffers 陣列，並建立一個指向此緩衝區的節點。

class PieceTable {
  buffers: string[];
  nodes: Node[];
}

class Node {
  bufferIndex: number;
  start: number; // start offset in buffers[bufferIndex]
  length: number;
  lineStarts: number[];
}

透過使用平衡二元樹提升行查找速度

解決字串串聯問題後，我們現在可以開啟大型檔案，但這將我們引導到另一個潛在的效能問題。假設我們載入一個 64MB 的檔案，片段表 (piece table) 將有 1000 個節點。即使我們在每個節點中快取換行符號位置，我們也不知道哪個絕對行號在哪個節點中。為了取得行的內容，我們必須遍歷所有節點，直到找到包含該行的節點。在我們的範例中，我們必須遍歷最多 1000 個節點，具體取決於我們尋找的行號。因此，最壞情況下的時間複雜度為 O(N)（N 是節點的計數）。

在每個節點中快取絕對行號，並在節點列表上使用二元搜尋可以提高查找速度，但是每當我們修改節點時，我們都必須造訪所有後續節點以套用行號增量。這是不可行的，但是二元搜尋的想法很好。為了達到相同的效果，我們可以利用平衡二元樹。

我們現在必須決定應該使用什麼中繼資料作為比較樹狀節點的鍵。如前所述，使用節點在文件中的偏移量或絕對行號會將編輯操作的時間複雜度提高到 O(N)。如果我們想要 O(log n) 的時間複雜度，我們需要一些僅與樹狀節點的子樹相關的東西。因此，當使用者編輯文字時，我們會重新計算已修改節點的中繼資料，然後沿著父節點一路將中繼資料變更冒泡到根節點。

如果 Node 只有四個屬性 (bufferIndex、start、length、lineStarts)，則需要幾秒鐘才能找到結果。為了加快速度，我們還可以儲存節點左子樹的文字長度和換行符號計數。這樣，從樹的根節點按偏移量或行號搜尋可以很有效率。儲存右子樹的中繼資料是相同的，但我們不需要快取兩者。

類別現在看起來像這樣

class PieceTable {
  buffers: string[];
  rootNode: Node;
}

class Node {
  bufferIndex: number;
  start: number;
  length: number;
  lineStarts: number[];

  left_subtree_length: number;
  left_subtree_lfcnt: number;
  left: Node;
  right: Node;
  parent: Node;
}

在所有不同類型的平衡二元樹中，我們選擇了紅黑樹，因為它更「編輯友善」。

減少物件配置

假設我們在每個節點中儲存換行符號偏移量。每當我們變更節點時，我們可能必須更新換行符號偏移量。例如，假設我們有一個包含 999 個換行符號的節點，lineStarts 陣列有 1000 個元素。如果我們平均分割節點，那麼我們將建立兩個節點，每個節點都有一個包含約 500 個元素的陣列。由於我們不是直接在線性記憶體空間上操作，因此將陣列分割成兩個比僅移動指標更耗費成本。

好消息是片段表 (piece table) 中的緩衝區是唯讀的（原始緩衝區）或僅附加的（已變更的緩衝區），因此緩衝區內的換行符號不會移動。Node 可以簡單地保留對其對應緩衝區上換行符號偏移量的兩個參考。我們做得越少，效能就越好。我們的基準測試顯示，應用此變更使我們實作中的文字緩衝區操作速度提高了三倍。但稍後會詳細介紹實際的實作方式。

class Buffer {
    value: string;
    lineStarts: number[];
}

class BufferPosition {
    index: number; // index in Buffer.lineStarts
    remainder: number;
}

class PieceTable {
    buffers: Buffer[];
    rootNode: Node;
}

class Node {
    bufferIndex: number;
    start: BufferPosition;
    end: BufferPosition;
    ...
}

piece tree

片段樹 (Piece tree)

我很想將這個文字緩衝區稱為「針對行模型最佳化的多緩衝區紅黑樹片段表 (piece table)」。但是在我們的每日立會中，當每個人都僅限 90 秒分享他們一直在做的事情時，多次重複這個長名稱並不明智。因此，我只是開始將其稱為「片段樹 (piece tree)」，這反映了它的本質。

對於這種資料結構有理論上的理解是一回事，真實世界的效能又是另一回事。您使用的語言、程式碼執行的環境、用戶端調用您 API 的方式以及其他因素都可能顯著影響結果。基準測試可以提供全面的概況，因此我們針對小型/中型/大型檔案，對原始行陣列實作方式和片段樹 (piece tree) 實作方式執行了基準測試。

準備工作

為了呈現結果，我在網路上尋找了真實的檔案。

  • checker.ts - 1.46 MB，2.6 萬行。
  • sqlite.c - 4.31MB，12.8 萬行。
  • 俄英雙語詞典 - 14MB，55.2 萬行。

並手動建立了一些大型檔案。

  • 新開啟的 VS Code Insider 的 Chromium 堆積快照 - 54MB，300 萬行。
  • checker.ts X 128 - 184MB，300 萬行。

1. 記憶體使用量

片段樹 (piece tree) 在載入後立即的記憶體使用量非常接近原始檔案大小，並且明顯低於舊的實作方式。第一輪，片段樹 (piece tree) 勝出。

Memory usage

2. 檔案開啟時間

尋找和快取換行符號比將檔案分割成字串陣列快得多。

File opening

3. 編輯

我模擬了兩種工作流程。

  • 在文件中隨機位置進行編輯。
  • 依序輸入。

我嘗試模擬這兩種情境：對文件套用 1000 次隨機編輯或 1000 次循序插入，然後查看每個文字緩衝區需要多少時間。

Random edits

如預期，當檔案非常小時，行陣列勝出。存取小陣列中的隨機位置並調整約 100~150 個字元的字串非常快。當檔案有很多行（10 萬行以上）時，行陣列開始窒息。大型檔案中的循序插入使情況更糟，因為 JavaScript 引擎需要做大量工作才能調整大型陣列的大小。片段樹 (piece tree) 的行為穩定，因為每次編輯都只是一個字串附加和幾個紅黑樹操作。

4. 讀取

對於我們的文字緩衝區，最熱門的方法是 getLineContent。它由檢視程式碼、語彙分析器、連結偵測器以及幾乎每個依賴文件內容的元件調用。某些程式碼會遍歷整個檔案，例如連結偵測器，而其他程式碼僅讀取循序行的視窗，例如檢視程式碼。因此，我開始在各種情境下對此方法進行基準測試。

  • 在進行 1000 次隨機編輯後，對所有行調用 getLineContent。
  • 在進行 1000 次循序插入後，對所有行調用 getLineContent。
  • 在進行 1000 次隨機編輯後，讀取 10 個不同的行視窗。
  • 在進行 1000 次循序插入後，讀取 10 個不同的行視窗。

Read all lines after random edits

噠啦，我們找到了片段樹 (piece tree) 的致命弱點。一個大型檔案，經過數千次編輯，將導致數千個或數萬個節點。即使查找行的時間複雜度為 O(log N)，其中 N 是節點數，這也遠高於行陣列享有的 O(1)。

擁有數千次編輯相對罕見。在大型檔案中替換常見字元序列後，您可能會達到這個數量。此外，我們談論的是每次 getLineContent 調用數微秒，因此目前我們並不擔心。大多數 getLineContent 調用都來自檢視渲染和語彙分析，而行內容的後處理更耗時。DOM 建構和渲染或檢視區的語彙分析通常需要數十毫秒，其中 getLineContent 僅佔不到 1%。儘管如此，我們正在考慮最終實作正規化步驟，如果滿足某些條件（例如節點數量過多），我們將在其中重新建立緩衝區和節點。

結論與注意事項

片段樹 (piece tree) 在大多數情境下都優於行陣列，但基於行的查找除外，這是預期的。

經驗教訓

  • 這次重新實作教會我最重要的一課是始終進行真實世界的效能分析。每次我都發現我對哪些方法會成為熱點的假設與現實不符。例如，當我開始片段樹 (piece tree) 實作時，我專注於調整三個原子操作：insert、delete 和 search。但是當我將其整合到 VS Code 中時，這些最佳化都無關緊要。最熱門的方法是 getLineContent。
  • 處理 CRLF 或混合換行符號序列是程式設計師的夢魘。對於每次修改，我們都需要檢查它是否分割了換行字元/換行符號 (CRLF) 序列，或者是否建立了新的 CRLF 序列。在樹狀結構的上下文中處理所有可能的情況，我嘗試了多次，直到找到一個正確且快速的解決方案。
  • 垃圾收集 (GC) 很容易耗盡您的 CPU 時間。我們的文字模型過去假設緩衝區儲存在陣列中，並且我們經常使用 getLineContent，即使有時沒有必要。例如，如果我們只想知道一行的第一個字元的字元碼，我們會先使用 getLineContent，然後再執行 charCodeAt。使用片段樹 (piece tree)，getLineContent 會建立一個子字串，並且在檢查字元碼後，立即丟棄行子字串。這很浪費，我們正在努力採用更適合的方法。

為什麼不採用原生方式？

我在文章開頭承諾會回到這個問題。

簡而言之：我們嘗試過了。但對我們來說行不通。

我們以 C++ 建構了文字緩衝區實作方式，並使用原生節點模組繫結將其整合到 VS Code 中。文字緩衝區是 VS Code 中常用的元件，因此對文字緩衝區進行了許多調用。當調用者和實作方式都以 JavaScript 撰寫時，V8 能夠內聯許多這些調用。使用原生文字緩衝區，存在 JavaScript <=> C++ 往返，並且考慮到往返次數，它們會減慢所有速度。

例如，VS Code 的「切換行註解」命令是透過循環遍歷所有選取的行並逐行分析它們來實作的。此邏輯以 JavaScript 撰寫，並將為每一行調用 TextBuffer.getLineContent。對於每次調用，我們最終都會跨越 C++/JavaScript 邊界，並且我們必須傳回 JavaScript 字串，以便遵守我們所有程式碼都建立在其之上的 API。

我們的選項很簡單。在 C++ 中，我們要麼在每次調用 getLineContent 時分配一個新的 JavaScript 字串，這意味著複製實際的字串位元組，要麼我們利用 V8 的 SlicedString 或 ConstString 類型。但是，只有當我們的底層儲存也使用 V8 的字串時，我們才能使用 V8 的字串類型。不幸的是，V8 的字串不是多執行緒安全的。

我們本可以嘗試透過變更 TextBuffer API 或將越來越多的程式碼移至 C++ 來避免 JavaScript/C++ 邊界成本來克服這個問題。但是，我們意識到我們同時在做兩件事：我們正在使用與行陣列不同的資料結構撰寫文字緩衝區，並且我們正在以 C++ 而不是 JavaScript 撰寫它。因此，與其花費半年時間在我們不知道是否會得到回報的事情上，我們決定將文字緩衝區的執行階段保留在 JavaScript 中，而僅變更資料結構和相關演算法。我們認為，這是正確的決定。

未來工作

我們仍然有一些需要最佳化的案例。例如，「尋找」命令目前逐行執行，但不應該這樣做。當僅需要行子字串時，我們也可以避免不必要地調用 getLineContent。我們將逐步發布這些最佳化。即使沒有這些進一步的最佳化，新的文字緩衝區實作方式也比我們以前的方式提供了更好的使用者體驗，並且現在是最新穩定 VS Code 版本中的預設值。

祝您編碼愉快！

Peng Lyu，VS Code 團隊成員 @njukidreborn