文字緩衝區重新實現

2018年3月23日，呂鵬，@njukidreborn

Visual Studio Code 1.21版本包含了一個全新的文字緩衝區實現，它在速度和記憶體使用方面都大大提升了效能。在這篇部落格文章中，我將講述我們如何選擇和設計資料結構與演算法，從而實現這些改進的故事。

關於JavaScript程式的效能討論通常會涉及到應該用原生程式碼實現多少的問題。對於VS Code的文字緩衝區，這些討論開始於一年多以前。在深入探索中，我們發現C++實現的文字緩衝區可以顯著節省記憶體，但我們並未看到期望的效能提升。在自定義的原生表示和V8的字串之間轉換字串成本很高，在我們的案例中，這抵消了在C++中實現文字緩衝區操作所獲得的任何效能。我們將在本文末尾更詳細地討論這一點。

由於不採用原生實現，我們不得不尋找改進JavaScript/TypeScript程式碼的方法。像這篇來自Vyacheslav Egorov的啟發性部落格文章展示瞭如何將JavaScript引擎推向極限，並儘可能地榨取效能。即使沒有低階引擎技巧，透過使用更合適的資料結構和更快的演算法，仍然有可能將速度提高一個或多個數量級。

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

編輯器的心智模型是基於行的。開發人員逐行閱讀和編寫原始碼，編譯器提供基於行/列的診斷，堆疊跟蹤包含行號，分詞引擎逐行執行，等等。雖然簡單，但自我們啟動Monaco專案第一天以來，為VS Code提供支援的文字緩衝區實現並沒有太大變化。我們使用一個行陣列，並且它工作得很好，因為典型的文字文件相對較小。當用戶輸入時，我們在陣列中找到要修改的行並替換它。當插入新行時，我們將一個新的行物件插入到行陣列中，JavaScript引擎會為我們完成繁重的工作。

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

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

尋找新的文字緩衝區實現

舊的行陣列表示可能需要很長時間來建立並消耗大量記憶體，但它提供了快速的行查詢。在一個理想的世界中，我們只會儲存檔案的文字，而不會儲存額外的元資料。因此，我們開始尋找需要較少元資料的資料結構。在審查了各種資料結構之後，我發現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
}

檔案最初載入後，分塊表在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 行。
sqlite.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序列。在樹的上下文中處理所有可能的情況，我嘗試了幾次才得到一個正確且快速的解決方案。
**垃圾回收很容易佔用你的CPU時間**。我們的文字模型曾經假設緩衝區儲存在一個數組中，我們經常使用getLineContent，即使有時沒有必要。例如，如果我們只想知道一行第一個字元的字元程式碼，我們首先使用getLineContent，然後執行charCodeAt。使用分塊樹，getLineContent會建立一個子字串，並在檢查字元程式碼後立即將該行子字串丟棄。這是浪費的，我們正在努力採用更合適的方法。

為什麼不用原生實現？

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

TL;DR：我們嘗試了。對我們來說沒成功。

我們用C++構建了一個文字緩衝區實現，並使用原生node模組繫結將其整合到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中的預設設定。

編碼愉快！

呂鵬，VS Code團隊成員 @njukidreborn