文本缓冲区重新实现

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

行数组表示法的另一个问题是打开文件的速度。为了构建行数组，我们必须按换行符分割内容，这样每行都会得到一个字符串对象。分割本身会影响性能，您将在后面的基准测试中看到。

寻找新的文本缓冲区实现

旧的行数组表示法创建耗时且消耗大量内存，但它提供了快速的行查找。在理想世界中，我们只存储文件的文本，而不存储任何额外的元数据。因此，我们开始寻找需要较少元数据的数据结构。在审查了各种数据结构后，我发现片段表可能是一个很好的起点。

通过使用片段表避免过多的元数据

片段表是用于表示文本文档（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` 会创建一个子字符串，检查字符代码后，该行子字符串立即被丢弃。这是浪费的，我们正在努力采用更适合的方法。

为什么不用原生？

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

总结：我们尝试了。但对我们来说行不通。

我们用 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