文本缓冲区重新实现

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 字节，因此行数组使用大约 600 MB 的内存来存储文档。这大约是初始文件大小的 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 加载文本文件，该文件以 64 KB 块的形式提供内容。因此，当文件很大时，例如 64 MB，我们将收到 1000 个块。收到所有块后，我们可以将它们连接成一个大型字符串，并将其存储在片段表的 original 字段中。

这听起来很合理，直到 V8 踩了你的脚趾。我尝试打开一个 500 MB 的文件，并收到一个异常，因为在我使用的 V8 版本中，最大字符串长度为 256 MB。此限制将在未来版本的 V8 中提升到 1 GB，但这并不能真正解决问题。

我们可以不保存 original 和 added 缓冲区，而是保存一个缓冲区列表。我们可以尝试使该列表保持简短，或者我们可以从 fs.readFile 返回的内容中获得启发，并避免任何字符串连接。每次我们从磁盘接收一个 64 KB 的块时，我们将其直接推送到 buffers 数组，并创建一个指向该缓冲区的节点。

class PieceTable {
  buffers: string[];
  nodes: Node[];
}

class Node {
  bufferIndex: number;
  start: number; // start offset in buffers[bufferIndex]
  length: number;
  lineStarts: number[];
}

使用平衡二叉树来提高查找行速度

字符串连接不再是问题，我们现在可以打开大型文件，但这会导致另一个潜在的性能问题。假设我们加载一个 64 MB 的文件，片段表将有 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

我们发现了片段树的阿喀琉斯之踵。一个大型文件，经过 1000 次编辑，会导致数千甚至数万个节点。即使查找一行是 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++ 中构建了一个文本缓冲区实现，并使用原生节点模块绑定将其集成到 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