文字緩衝區重新實作

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 倍！

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

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

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

透過使用片段表來避免過多的元資料

片段表是一種用於表示文字文件（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
}

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

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

Traditional piece table

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

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

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

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]，這將提供行開始和結束的相對偏移量。由於我們知道節點有多少個換行符號，因此在文件中存取隨機行非常簡單：從第一個節點開始讀取每個節點，直到找到目標換行符號。

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

避免字串串連陷阱

片段表保存兩個緩衝區，一個用於從磁碟載入的原始內容，另一個用於使用者編輯。在 VS Code 中，我們使用 Node.js fs.readFile 載入文字檔案，它以 64KB 的區塊傳遞內容。因此，當檔案很大時，例如 64 MB，我們將收到 1000 個區塊。在收到所有區塊後，我們可以將它們串連成一個大的字串並將其儲存在片段表的 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 的檔案，片段表將有 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 個元素的陣列。由於我們不是直接在線性記憶體空間上操作，因此將陣列分割成兩個比僅移動指標更耗費成本。

好消息是片段表中的緩衝區是唯讀的（原始緩衝區）或僅附加的（已變更的緩衝區），因此緩衝區內的換行符號不會移動。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

片段樹

我很想將此文字緩衝區稱為「多緩衝區片段表，搭配紅黑樹，針對行模型最佳化」。但在我們的每日站立會議中，當每個人都僅限 90 秒分享他們的最新進度時，多次重複這個長名稱是不明智的。所以我只是開始將其稱為「片段樹」，這反映了它的本質。

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

準備工作

為了說明結果，我在網路上尋找了真實的檔案

checker.ts - 1.46 MB，26k 行。
sqlite3.c - 4.31MB，128k 行。
俄語-英語雙語字典 - 14MB，552k 行。

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

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

1. 記憶體使用量

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

Memory usage

2. 檔案開啟時間

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

File opening

3. 編輯

我模擬了兩種工作流程

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

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

Random edits

正如預期的那樣，當檔案非常小時，行陣列勝出。存取小型陣列中的隨機位置並調整大約有 100~150 個字元的字串真的很快。當檔案有很多行（10 萬行以上）時，行陣列開始變得吃力。大型檔案中的循序插入使情況變得更糟，因為 JavaScript 引擎為了調整大型陣列而做了很多工作。片段樹的行為穩定，因為每次編輯都只是字串附加和幾個紅黑樹操作。

4. 讀取

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

在完成 1000 次隨機編輯後，呼叫所有行的 getLineContent。
在完成 1000 次循序插入後，呼叫所有行的 getLineContent。
在完成 1000 次隨機編輯後，讀取 10 個不同的行視窗。
在完成 1000 次循序插入後，讀取 10 個不同的行視窗。

Read all lines after random edits

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

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

結論與注意事項

片段樹在大多數情境中都優於行陣列，除了基於行的查找，這是預料之中的。

經驗教訓

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

為什麼不使用原生？

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

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

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

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

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

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

未來工作

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

祝您編碼愉快！

Peng Lyu，VS Code 團隊成員 @njukidreborn