文本缓冲区重新实现

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 的块传递内容。因此，当文件很大时，例如 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，300 万行。
checker.ts X 128 - 184MB，300 万行。

1. 内存使用

分段树加载后立即使用的内存非常接近原始文件大小，并且明显低于旧的实现。第一轮，分段树获胜

Memory usage

2. 文件打开时间

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

File opening

3. 编辑

我模拟了两种工作流程

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

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

Random edits

正如预期的那样，当文件非常小时，行数组胜出。访问小型数组中的随机位置并调整一个大约有 100~150 个字符的字符串确实很快。当文件有很多行（10 万+）时，行数组开始变得迟钝。在大型文件中进行顺序插入会使情况更糟，因为 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