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

永不妥协 2019-06-27

这篇是我在知乎的回答,原文在这里: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

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

300+倍的差距。

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

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

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

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

还有一种情况是当前行的输入会影响到后面(甚至是前面)的行,这时会用到结束状态:

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

在 1.9 之前的版本,vscode 如何 tokenization 呢?

比如上面的代码:

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

在 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 数据结构。

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

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

这一切都是 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 数据结构。

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

目前主要的三种编辑方式有 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 的

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

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

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

经过一系列优化,官方说道:

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:

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

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

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

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

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

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

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


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

相关推荐