文本缓冲区重实现

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

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

寻找新的文本缓冲区实现

旧的行数组表示法创建需要大量时间，消耗大量内存，但它提供了快速的行查找。在一个完美的世界里，我们只会存储文件的文本，不存储额外的元数据。因此，我们开始寻找需要较少元数据的数据结构。在回顾了各种数据结构后，我发现 piece table 可能是一个很好的起点。

使用 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
}

文件初次加载后，piece table 会将整个文件内容存储在 original 字段中。added 字段为空。只有一个类型为 NodeType.Original 的节点。当用户在文件末尾输入时，我们会将新内容附加到 added 字段，并在节点列表末尾插入一个新的类型为 NodeType.Added 的节点。类似地，当用户在节点中间进行编辑时，我们会根据需要分割该节点并插入新的节点。

下面的动画展示了如何在 piece table 结构中逐行访问文档。它有两个缓冲区（original 和 added）和三个节点（这是由于在 original 内容中间插入引起的）。

piece table 的初始内存使用量接近文档大小，而修改所需的内存与编辑次数和添加的文本量成正比。因此，piece table 通常能很好地利用内存。然而，低内存使用的代价是访问逻辑行速度较慢。例如，如果您想获取第 1000 行的内容，唯一的方法是从文档开头开始遍历每个字符，找到前 999 个换行符，然后读取每个字符直到下一个换行符。

使用缓存加快行查找速度

传统的 piece table 节点只包含偏移量，但我们可以添加换行符信息以加快行内容查找。存储换行符位置的直观方法是存储节点文本中遇到的每个换行符的偏移量。

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]，它们将给出行的开始和结束的相对偏移量。由于我们知道一个节点有多少个换行符，访问文档中的任意一行就很简单：从第一个节点开始逐个读取节点，直到找到目标换行符。

该算法仍然很简单，并且比以前效果更好，因为我们现在可以跳过整个文本块，而不是逐个字符地迭代。稍后我们将看到，我们可以做得更好。

避免字符串连接陷阱

piece table 包含两个缓冲区，一个用于从磁盘加载的原始内容，另一个用于用户编辑。在 VS Code 中，我们使用 Node.js 的 fs.readFile 加载文本文件，它以 64KB 的块交付内容。因此，当文件很大时，例如 64MB，我们将收到 1000 个块。接收到所有块后，我们可以将它们连接成一个大字符串并存储在 piece table 的 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 的文件，piece table 将有 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 个元素的数组。由于我们不是直接在连续内存空间上操作，将一个数组分割成两个比仅仅移动指针代价更高。

好消息是，piece table 中的缓冲区要么是只读的（原始缓冲区），要么是只追加的（更改缓冲区），因此缓冲区内的换行符不会移动。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

我很想将这个文本缓冲区称为“基于红黑树优化了行模型的多缓冲区 piece table”。但在我们的每日站会中，每个人只有 90 秒分享自己的工作进展，重复这个冗长的名称多次是不明智的。所以我只是开始称之为“piece tree”，这反映了它的本质。

对这种数据结构有理论上的理解是一回事，实际性能是另一回事。您使用的语言、代码运行的环境、客户端调用您 API 的方式以及其他因素都可能显著影响结果。基准测试可以提供全面的图景，因此我们对小型/中型/大型文件进行了基准测试，比较了原始行数组实现和 piece tree 实现。

准备工作

为了得出有说服力的结果，我在网上寻找了真实的文件

• 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. 内存使用量

piece tree 在加载后的内存使用量非常接近原始文件大小，并且显著低于旧实现。第一轮，piece tree 获胜。

2. 文件打开时间

查找和缓存换行符比将文件分割成字符串数组要快得多

3. 编辑

我模拟了两种工作流程

• 在文档的随机位置进行编辑。
• 按顺序输入。

我试图模拟这两种场景：对文档应用 1000 次随机编辑或 1000 次顺序插入，然后看看每个文本缓冲区需要多少时间。

如预期，当文件非常小时，行数组表现最佳。访问小数组中的随机位置并修改一个约 100~150 个字符的字符串非常快。当文件行数很多时（10 万+），行数组开始出现瓶颈。在大文件中进行顺序插入会使情况更糟，因为 JavaScript 引擎需要做大量工作来调整大数组的大小。Piece tree 表现稳定，因为每次编辑只是字符串追加和几次红黑树操作。

4. 读取

对于我们的文本缓冲区，最“热”的方法是 getLineContent。它被视图代码、分词器、链接检测器以及几乎所有依赖于文档内容的组件调用。有些代码会遍历整个文件，例如链接检测器，而其他代码只读取连续行的窗口，例如视图代码。因此，我着手在各种场景下对这个方法进行基准测试。

• 在进行 1000 次随机编辑后，对所有行调用 getLineContent。
• 在进行 1000 次顺序插入后，对所有行调用 getLineContent。
• 在进行 1000 次随机编辑后，读取 10 个不同的行窗口。
• 在进行 1000 次顺序插入后，读取 10 个不同的行窗口。

瞧，我们找到了 piece tree 的阿喀琉斯之踵。一个大文件经过数千次编辑后，将导致数千甚至数万个节点。即使查找一行的时间复杂度是 O(log N)，其中 N 是节点数，这也显著高于行数组所拥有的 O(1)。

拥有数千次编辑的情况相对罕见。您可能在大文件中替换常用字符序列后达到这个状态。此外，每次调用 getLineContent 的时间是以微秒计，所以目前我们并不担心这个问题。大多数 getLineContent 调用来自视图渲染和分词，而对行内容的后续处理要耗时得多。DOM 构建和渲染或视口的分词通常需要数十毫秒，其中 getLineContent 仅占不到 1%。尽管如此，我们仍在考虑最终实现一个规范化步骤，在满足例如节点数量过多等特定条件时重新创建缓冲区和节点。

结论和注意事项

除了基于行的查找之外，piece tree 在大多数场景下都优于行数组，这也在预期之中。

吸取的教训

• 这次重新实现教会我最重要的一课是始终进行实际性能分析。每一次我发现自己关于哪些方法会成为瓶颈的假设都与现实不符。例如，当我开始实现 piece tree 时，我专注于优化三个原子操作：insert、delete 和 search。但当我将其集成到 VS Code 中时，这些优化都不重要了。最“热”的方法是 getLineContent。
• 处理 CRLF 或混合换行符序列是程序员的噩梦。对于每一次修改，我们需要检查它是否分割了一个回车/换行（CRLF）序列，或者是否创建了一个新的 CRLF 序列。在树的上下文中处理所有可能的情况，我尝试了几次才找到一个既正确又快速的解决方案。
• GC 很容易占用您的 CPU 时间。我们的文本模型过去假设缓冲区存储在一个数组中，即使有时不需要，我们也经常使用 getLineContent。例如，如果我们只想知道一行第一个字符的字符码，我们先使用 getLineContent，然后再调用 charCodeAt。使用 piece tree，getLineContent 会创建一个子字符串，检查字符码后，该行子字符串会立即被丢弃。这是浪费的，我们正在努力采用更适合的方法。

为什么不用原生实现？

我在开头承诺过会回到这个问题。

TL;DR：我们尝试了。对我们来说行不通。

我们用 C++ 构建了一个文本缓冲区实现，并使用原生 node 模块绑定将其集成到 VS Code 中。文本缓冲区是 VS Code 中一个常用的组件，因此有许多调用会指向它。当调用方和实现都用 JavaScript 编写时，V8 能够内联许多此类调用。而使用原生文本缓冲区时，存在 JavaScript <=> C++ 的往返开销，鉴于往返次数之多，它们拖慢了所有操作。

例如，VS Code 的切换行注释命令的实现方式是遍历所有选中的行，并逐行分析。这个逻辑是用 JavaScript 编写的，并将对每一行调用 TextBuffer.getLineContent。每次调用，我们都会跨越 C++/JavaScript 边界，并且为了遵守我们所有代码都基于的 API，我们必须返回一个 JavaScript string。

我们的选择很简单。在 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