VS Code、ATOM这些开源文本编辑器的代码实现中有哪些奇技淫巧？

ACM算法日常

发布于 2020-02-25 12:20:30

1.6K0

发布于 2020-02-25 12:20:30

转载声明：本文来源于知乎，经原作者同意进行转载，原文见原文链接。

小编前言：

最近看了一下文本编辑方面的算法，发现坑还挺多，富文本更是被称之为天坑，一个office word可以复杂到和操作系统、浏览器一样的程度，这其中现代化的文本编辑器非vscode莫属，本文和大家一起开开眼界，以后有意在文本编辑器方面进坑的可以研究一下。

顺带提一下我的markdown编辑器，目前全新改版成了支持复杂dom结构的编辑器，支持树形嵌套样式、表格、代码、latex公式等，采用QT纯C++实现，希望能尽快做完~估计还要等几个月~~

正文：

研究 V8 比较多，也关注了一下 vscode 和 atom 的性能，每次 vscode、atom 的 change log 我都会看一遍。印象最深的是 vscode 1.14 的一次更新日志，doApplyEdits Lines inserted using splice · Issue #351 · Microsoft/monaco-editor：不要在循环中使用 splice。

下图是我一年前跑的测试结果：Inserting an array within an array

300+倍的差距。

再之前，vscode 还有一次很大的性能提升，版本 1.9 改进了语法高亮的算法。

语法高亮的过程通常分为 2 个阶段(tokenization 和 render)：先将源码分割为 token，然后使用不同的主题对分割后的 token 进行着色。

tokenization 的过程是：从上到下逐行运行。tokenizer 在行的末尾存储一些状态，在 tokenize 下一行时会用到这些状态。这样，在用户进行编辑时仅需要重新 tokenize 行的一小部分，而不需要扫描整个文件内容。

比如：

还有一种情况是当前行的输入会影响到后面（甚至是前面）的行，这时会用到结束状态：

在 1.9 之前的版本，vscode 如何 tokenization 呢？

比如上面的代码：

在 vscode 种这样存储：

tokens = [
    { startIndex:  0, type: 'keyword.js' },
    { startIndex:  8, type: '' },
    { startIndex:  9, type: 'identifier.js' },
    { startIndex: 11, type: 'delimiter.paren.js' },
    { startIndex: 12, type: 'delimiter.paren.js' },
    { startIndex: 13, type: '' },
    { startIndex: 14, type: 'delimiter.curly.js' },
]

{ startIndex: 0, type: 'keyword.js' } 表示从 0 开始的 token 是一个 keyword。

VSCode 团队在博客种指出：这在 Chrome 中占据 648 个字节，因此存储这样的对象在内存方面的代价非常高（每个对象实例必须保留指向其原型的空间，以及其属性列表等）。为了存储这 15 个字符而需要使用 648 字节是不可接受的。

所以，vscode 使用二进制来存储 token：

和上面的表示法相比，只是把 type 由字符串变成了数字，本质上并没有节约太多的内存。但是别着急，vscode 还有黑科技。

我们都知道 JavaScript 使用 IEEE-754 标准存储双精度浮点数，尾数为 53bit。能够在不丢失精度的情况下处理的最大整数为 2^53-1。因此 vscode 使用其中的 48bit 进行编码：使用 32bit 来存储 startIndex，16bit 来存储type。于是上面的对象在 vscode 种被存储为：

每个数字是 64bit(8字节)，一共是 7 个数字，存储这些元素一共需要 7*8 = 56 字节，再加上数组的额外开销共需要 104 个字节，只有之前的 648 字节的 1/6。

而主题的渲染则用到了 Trie 数据结构。

这个学过《数据结构》的都懂，算不上奇技淫巧，就不展开了。

这一切都是 2017 年 3 月发布的 vscode 1.9。

而今年 3 月，vscode 又重写了 Text Buffer。我们都知道，当开发者使用编辑器时，大部分时间就是，写新代码，改旧代码，写新代码，改旧代码，…… 说到底还是对 text 进行编辑。

对于高性能的文本操作，vscode 最初尝试使用 C++ 进行编写，毕竟 C++ 的性能要比 JavaScript 高出不少，但是事实却不够理想，使用 C++ 确实节约了内存，但是在使用 C++ 模块时，需要在 JavaScript 和 C++ 之间往返数次，这大大减慢了 vscode 的性能。

vscode 团队从 Vyacheslav Egorov 的一篇文章 Maybe you don't need Rust and WASM to speed up your JS 收到了启发，如何充分压榨 V8 引擎的性能。mrale.ph 的博客我几乎每篇都看，非常经典，也非常难懂。

大多编辑器都是基于行的：程序员逐行编写代码，编译器提供基于行的反馈信息，堆栈跟踪包含行号，tokenization 引擎逐行运行…… 在 vscode 的早期版本中也是直接把每行代码作为字符串存储在数组中。

但是这种方式存在一些问题：

无法打开大文件，因为把所有内容读入数组中可能导致内存不足。
即使文件不大，但是行数太多也无法打开。例如，一个用户无法打开一个 35 MB 的文件。根本原因是该文件的行数太多，1370 万行。引擎将为ModelLine每行和每个对象使用大约 40-60 个字节，因此整个数组使用大约 600MB 内存来存储文档。也就是说打开这个 35M 的文件需要 600M 的内容，20 倍啊！！！
另一个问题就是速度。为了构建这个数组，必须通过换行符分割内容，以便每行获得一个字符串对象。

于是 vscode 开始寻找新的数据结构，最终选择了 Piece table。不知道为什么这么晚才选择 piece table，要知道在微软的 office word 中早就已经使用了 piece table。我也是在一次 Java 读取 word 的 jar 包源码中第一次知道的 piece table 数据结构。

推荐几篇延伸阅读的文章：

Emacs 编辑器的 buffer 论文：Flexichain: An editable sequence and its gap-buffer implementation 2004-04-05
piece table 的：Data Structures for Text Sequences 1998-06-10
Ropes: An Alternative to Strings 1995-12

目前主要的三种编辑方式有 gap buffer, rope, piece table。

最近用 Atom 少了。

上一次让我兴奋的地方是：The State of Atom's Performance。在2017年6月 Atom 使用了 piece table 数据结构，使用 C++ 重新实现了 text buffer：Atom's new concurrency-friendly buffer implementation。比 vscode 还要早半年，但是为什么还是这么慢呢？？？

Atom 使用 V8 的自定义快照（snapshot）提升启动性能，最终删除了影响性能的 jQuery 和自定义 element。就连 V8 的

Atom 还更新了 DOM 渲染的方式：A new approach to text rendering，而这个新算法包括一个类似 React 的 vdom，从 issue 来看这是一个大工程啊，包含了近 100 个 task

经过一系列优化，官方说道：

we made loading Atom almost 50% faster and snapshots were a crucial tool that enabled some otherwise impossible optimizations.

我们使 Atom 快了 50%，snapshot 功不可没。（PS：我一定是使用了假的 Atom）

不过 snapshot 确实是 V8 的神器，Nodejs 也看到了 Atom 的成果，于 2017-11-16 开了 issue ：speeding up Node.js startup using V8 snapshot · Issue #17058 · nodejs/node。这在我之前的专栏里面有介绍：Node.js 新计划：使用 V8 snapshot 将启动速度提升 8 倍。

最近一次关注 Atom 是 atom/xray。知乎上也有相关的讨论，atom 开发的下一代编辑器（莫非已经定义 atom 为上一代编辑器了吗）。大概就是一种“大号废了，开小号重练”的感觉。

值得学习的地方是 text 处理使用 copy-on-write CRDT：