文字緩衝區重新實現

2018年3月23日，作者：彭呂 (@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）可能是一個很好的起點。

使用分片表避免過多的元資料

分片表是一種用於表示文字文件（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 內容中間插入造成的）。

分片表的初始記憶體使用量接近文件大小，修改所需的記憶體與編輯次數和新增的文字成比例。因此，分片表通常能很好地利用記憶體。然而，低記憶體使用的代價是訪問邏輯行很慢。例如，如果你想獲取第 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 秒來分享他們最近在忙什麼時，重複這個冗長的名字多次是不明智的。所以我乾脆開始稱它為“分片樹”（piece tree），這反映了它的本質。

對這種資料結構有理論理解是一回事，實際效能是另一回事。您使用的語言、程式碼執行的環境、客戶端呼叫 API 的方式以及其他因素可能會顯著影響結果。基準測試可以提供全面的情況，因此我們針對小/中/大檔案對原始行陣列實現和分片樹實現進行了基準測試。

準備工作

為了得出結果，我在網上尋找了真實的示例檔案：

• checker.ts - 1.46 MB, 2.6萬行。
• sqlite.c - 4.31MB, 12.8萬行。
• Russian English Bilingual dictionary - 14MB, 55.2萬行。

並手動建立了幾個大檔案：

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

1. 記憶體使用

分片樹在載入後立即使用的記憶體非常接近原始檔案大小，並且明顯低於舊實現。第一輪，分片樹獲勝。

2. 檔案開啟時間

查詢和快取換行符比將檔案分割成字串陣列要快得多。

3. 編輯

我模擬了兩種工作流程：

• 在文件中的隨機位置進行編輯。
• 按順序打字。

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

正如預期的那樣，當檔案非常小時，行陣列獲勝。訪問小陣列中的隨機位置並修改一個大約有 100~150 個字元的字串非常快。當檔案有很多行（10萬+）時，行陣列開始出現瓶頸。在大檔案中進行順序插入會使情況變得更糟，因為 JavaScript 引擎需要做大量工作來調整大陣列的大小。分片樹表現穩定，因為每次編輯都只是一個字串追加和幾個紅黑樹操作。

4. 讀取

對於我們的文字緩衝區來說，最熱門的方法是 getLineContent。它被檢視程式碼、分詞器、連結檢測器以及幾乎所有依賴文件內容的元件呼叫。一些程式碼會遍歷整個檔案，例如連結檢測器，而其他程式碼只讀取連續的行視窗，例如檢視程式碼。因此，我著手在各種場景下對這個方法進行基準測試：

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

瞧，我們發現了分片樹的阿喀琉斯之踵。一個包含數千次編輯的大檔案將導致數千或數萬個節點。即使查詢一行是 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 會建立一個子字串，檢查字元程式碼後，行子字串立即被丟棄。這是浪費的，我們正在努力採用更合適的方法。

為什麼不用原生？

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

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