文本缓冲区重新实现

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 项目启动之初就没有太大变化。我们使用一个行数组，它工作得很好，因为典型的文本文档相对较小。当用户键入时，我们定位到数组中要修改的行并替换它。当插入新行时，我们将一个新的行对象拼接（splice）到行数组中，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` 内容的中间插入引起的）。

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 个字符的字符串非常快。当文件有许多行（100k+）时，行数组开始出现瓶颈。在大型文件中按顺序插入会使这种情况恶化，因为 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` 会创建一个子字符串，并在检查字符代码后立即丢弃该行子字符串。这是浪费的，我们正在努力采用更合适的方法。

为什么不用原生实现？

我一开始就承诺会回到这个问题。

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