文本缓冲区重新实现

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

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

寻找新的文本缓冲区实现

旧的行数组表示法可能需要大量时间来创建并消耗大量内存,但它提供了快速的行查找。在理想情况下,我们只会存储文件的文本而不需要额外的元数据。因此,我们开始寻找需要较少元数据的数据结构。在审查了各种数据结构后,我发现片段表可能是一个不错的起点。

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

片段表是一种用于表示对文本文档(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的新节点。同样,当用户在节点中间进行编辑时,我们将根据需要拆分该节点并插入一个新节点。

下面的动画展示了如何在一个片段表结构中逐行访问文档。它有两个缓冲区(originaladded)和三个节点(这是由于在 original 内容的中间插入导致的)。


传统的片段表


初始内存使用量接近文档的大小,修改所需的内存与编辑次数和添加的文本量成正比。因此,通常来说,片段表能很好地利用内存。然而,低内存使用的代价是访问逻辑行的速度较慢。例如,如果你想获取第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,但这并没有真正解决问题。

我们可以不持有originaladded缓冲区,而是持有一个缓冲区列表。我们可以尝试保持这个列表简短,或者我们可以从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只有四个属性(bufferIndexstartlengthlineStarts),找到结果需要几秒钟。为了更快,我们还可以存储节点左子树的文本长度和换行计数。这样从树的根节点按偏移量或行号搜索可以更高效。存储右子树的元数据是相同的,但我们不需要同时缓存两者。

现在的类看起来像这样:

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;
    ...
}

片段树


片段树

我很想称这个文本缓冲区为"使用红黑树的多缓冲区片段表,针对行模型优化"。但在我们的每日站会上,当每个人只有90秒的时间来分享他们的进展时,多次重复这个长名字并不明智。所以我简单地开始称它为"片段树",这反映了它的本质。

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

准备工作

为了展示结果,我在网上寻找了真实的文件:

并手动创建了几个大文件:

  • 新打开的VS Code Insider的Chromium堆快照 - 54MB,3M行。
  • checker.ts X 128 - 184MB, 3M 行。

1. 内存使用

加载后,片段树的内存使用量非常接近原始文件大小,并且明显低于旧实现。第一轮,片段树胜出:

内存使用情况

2. 文件打开时间

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

文件打开

3. 编辑

我已经模拟了两个工作流程:

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

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

随机编辑

正如预期的那样,当文件非常小时,行数组表现优异。在小数组中访问随机位置并调整一个大约有100~150个字符的字符串确实非常快。当文件有很多行(10万行以上)时,行数组开始表现不佳。在大文件中进行顺序插入会使情况变得更糟,因为JavaScript引擎为了调整大数组的大小做了很多工作。片段树表现稳定,因为每次编辑只是一个字符串追加和几次红黑树操作。

4. 阅读

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

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

随机编辑后读取所有行

TA DA,我们发现了片段树的致命弱点。一个大文件,经过数千次编辑,将会产生成千上万的节点。尽管查找一行的时间复杂度是O(log N),其中N是节点的数量,但这明显比行数组所享有的O(1)要高得多。

拥有数千次编辑是相对罕见的。你可能在替换大文件中常见的字符序列后达到这个数量。此外,我们讨论的是每次getLineContent调用的微秒级时间,所以这不是我们目前关心的问题。大多数getLineContent调用来自视图渲染和标记化,而行内容的后续处理要耗时得多。DOM构建和渲染或视口的标记化通常需要几十毫秒,其中getLineContent只占不到1%。尽管如此,我们正在考虑最终实现一个规范化步骤,如果满足某些条件(如节点数量过多),我们将重新创建缓冲区和节点。

结论与注意事项

在大多数情况下,片段树的表现优于行数组,除了基于行的查找,这是预料之中的。

经验教训

  • 这次重新实现教会我的最重要的一课是始终进行实际性能分析。每次我发现我对哪些方法会成为热点的假设与实际情况不符。例如,当我开始实现片段树时,我专注于调整三个原子操作:insertdeletesearch。但当我将其集成到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的SlicedStringConstString类型。然而,只有在我们底层存储也使用V8的字符串时,我们才能使用V8的字符串类型。不幸的是,V8的字符串不是多线程安全的。

我们本可以通过改变TextBuffer API,或者将越来越多的代码转移到C++来避免JavaScript/C++边界成本来克服这个问题。然而,我们意识到我们同时在处理两件事:我们正在使用不同于行数组的数据结构编写一个文本缓冲区,并且我们正在用C++而不是JavaScript编写它。因此,与其花费半年时间在我们不知道是否会成功的事情上,我们决定将文本缓冲区的运行时保留在JavaScript中,只改变数据结构和相关算法。在我们看来,这是正确的决定。

未来工作

我们仍然有一些需要优化的情况。例如,查找命令目前是逐行运行的,但不应如此。当只需要行的子字符串时,我们也可以避免不必要的getLineContent调用。我们将逐步发布这些优化。即使没有这些进一步的优化,新的文本缓冲区实现也提供了比我们之前更好的用户体验,并且现在是最新稳定版VS Code中的默认设置。

编程快乐!

彭律,VS Code 团队成员 @njukidreborn