文本缓冲区重新实现

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

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

寻找新的文本缓冲区实现

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

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

片段表是一种用于表示文本文档（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 的块传输内容。因此，当文件很大时，例如 64MB，我们将收到 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 的默认设置。

编码愉快！

吕鹏（Peng Lyu），VS Code 团队成员 @njukidreborn