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

摘要：知乎上也有相关的讨论，开发的下一代编辑器莫非已经定义为上一代编辑器了吗。

这篇是我在知乎的回答，原文在这里：justjavac: VS Code、ATOM这些开源文本编辑器的代码实现中有哪些奇技淫巧？

研究 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：

//     0        1               2                  3                      4
map = ["", "keyword.js", "identifier.js", "delimiter.paren.js", "delimiter.curly.js"];
tokens = [
    { startIndex:  0, type: 1 },
    { startIndex:  8, type: 0 },
    { startIndex:  9, type: 2 },
    { startIndex: 11, type: 3 },
    { startIndex: 12, type: 3 },
    { startIndex: 13, type: 0 },
    { startIndex: 14, type: 4 },
]

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

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

tokens = [
                 //       type                 startIndex
     4294967296, // 0000000000000001 00000000000000000000000000000000
              8, // 0000000000000000 00000000000000000000000000001000
     8589934601, // 0000000000000010 00000000000000000000000000001001
    12884901899, // 0000000000000011 00000000000000000000000000001011
    12884901900, // 0000000000000011 00000000000000000000000000001100
             13, // 0000000000000000 00000000000000000000000000001101
    17179869198, // 0000000000000100 00000000000000000000000000001110
]

每个数字是 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：

如果一直关注 Atom，对于 CRDT 应该不会陌生。Atom 的多人实时共同编辑插件 https://teletype.atom.io/ 就是使用的 CRDT。

CRDT 全称：Conflict-Free Replicated Data Types，强行翻译过来就是“无冲突可复制数据类型”。

CRDT 论文： A comprehensive study of Convergent and Commutative Replicated Data Types 2011-01-13

CAP定理：在分布式系统中，最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项中的两项。

很多分布式系统都舍弃了C（一致性）：允许可以在某些时刻不一致，转而求其次要求系统满足最终一致性。这也是目前很多 nosql 数据库追求的方式（另一种是传统的符合 ACID 特性的数据库系统，放弃了A(可用性)，这种系统称为强一致性）。

而在最终一致性分布式系统中，一个最基本的问题就是，应该采用什么样的数据结构来保证最终一致性？ 答案就是 CRDT。

atom/teletype-crdt

这篇文章只是一个提纲，里面的每个知识点都可以展开了讲上三天三夜。