文本缓冲区重新实现

2018年3月23日，吕鹏，@njukidreborn

Visual Studio Code 1.21版本包含了一个全新的文本缓冲区实现，它在速度和内存使用方面都大大提升了性能。在这篇博客文章中，我将讲述我们如何选择和设计数据结构与算法，从而实现这些改进的故事。

关于JavaScript程序的性能讨论通常会涉及到应该用原生代码实现多少的问题。对于VS Code的文本缓冲区，这些讨论开始于一年多以前。在深入探索中，我们发现C++实现的文本缓冲区可以显著节省内存，但我们并未看到期望的性能提升。在自定义的原生表示和V8的字符串之间转换字符串成本很高，在我们的案例中，这抵消了在C++中实现文本缓冲区操作所获得的任何性能。我们将在本文末尾更详细地讨论这一点。

由于不采用原生实现，我们不得不寻找改进JavaScript/TypeScript代码的方法。像这篇来自Vyacheslav Egorov的启发性博客文章展示了如何将JavaScript引擎推向极限，并尽可能地榨取性能。即使没有低级引擎技巧，通过使用更合适的数据结构和更快的算法，仍然有可能将速度提高一个或多个数量级。

之前的文本缓冲区数据结构

编辑器的心智模型是基于行的。开发人员逐行阅读和编写源代码，编译器提供基于行/列的诊断，堆栈跟踪包含行号，分词引擎逐行运行，等等。虽然简单，但自我们启动Monaco项目第一天以来，为VS Code提供支持的文本缓冲区实现并没有太大变化。我们使用一个行数组，并且它工作得很好，因为典型的文本文档相对较小。当用户输入时，我们在数组中找到要修改的行并替换它。当插入新行时，我们将一个新的行对象插入到行数组中，JavaScript引擎会为我们完成繁重的工作。

然而，我们不断收到报告称打开某些文件会导致VS Code出现内存不足崩溃。例如，一位用户无法打开一个35 MB的文件。根本原因是该文件行数太多，达到1370万行。我们将为每行创建一个ModelLine对象，每个对象大约使用40-60字节，因此行数组需要大约600MB内存来存储文档。这大约是初始文件大小的20倍！

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

寻找新的文本缓冲区实现

旧的行数组表示可能需要很长时间来创建并消耗大量内存，但它提供了快速的行查找。在一个理想的世界中，我们只会存储文件的文本，而不会存储额外的元数据。因此，我们开始寻找需要较少元数据的数据结构。在审查了各种数据结构之后，我发现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
}

文件最初加载后，分块表在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个字符的字符串速度非常快。当文件有很多行（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序列。在树的上下文中处理所有可能的情况，我尝试了几次才得到一个正确且快速的解决方案。
**垃圾回收很容易占用你的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