专栏首页ACM算法日常VS Code、ATOM这些开源文本编辑器的代码实现中有哪些奇技淫巧?

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

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

小编前言:

最近看了一下文本编辑方面的算法,发现坑还挺多,富文本更是被称之为天坑,一个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:

如果一直关注 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-crdtgithub.com


这篇回答仅仅是一个提纲,里面的每个知识点都可以展开了讲三天三夜。每个知识点我都加了链接,感兴趣的可以跟随链接去深入了解。

温馨提示

如果你喜欢本文,请分享到朋友圈,想要获得更多信息,请关注ACM算法日常

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:justjavac

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 字符串反转-HDU 1062

    Ignatius likes to write words in reverse way. Given a single line of text which ...

    ACM算法日常
  • 如果说2019年哪一门“外语”特别火,我想那一定是Python。

    小学生要学Python,高考要加入Python,你常玩的手机游戏是Python写的,人工智能首选语言是Python,现在连微软官方Excel都要把Python作...

    ACM算法日常
  • leetcode 9 | 回文数 (两种不同的解决方式)

    判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

    ACM算法日常
  • VMware更新 | 修复Apache Flex BlazeDS中的漏洞

    VMware发布了数个产品的版本更新,目的是修复Apache Flex BlazeDS中的一个漏洞。 据VMware介绍,Flex BlazeDS组件应用在数个...

    FB客服
  • 蓝桥杯 基础练习 阶乘计算

    n!可能很大,而计算机能表示的整数范围有限,需要使用高精度计算的方法。使用一个数组A来表示一个大整数a,A[0]表示a的个位,A[1]表示a的十位,依次类推。...

    Debug客栈
  • k3s原理分析丨如何搞定k3s node注册失败问题

    面向边缘的轻量级K8S发行版k3s于去年2月底发布后,备受关注,在发布后的10个月时间里,Github Star达11,000颗。于去年11月中旬已经GA。但正...

    k3s中文社区
  • 通过几个事例,就可以说明 for...of 循环在 JS 是不可或缺

    JavaScript 中的for...of语句就是这种情况,可从ES2015开始使用。

    前端小智@大迁世界
  • Attack Monitor:一款功能强大的终端检测&恶意软件分析软件

    Attack Monitor是一款Python应用程序,可以帮助安全研究人员增强Windows 7/2008(及所有更高版本)工作站或服务器的安全监控功能,并且...

    FB客服
  • 用手机运行Python代码

    在手机上运行Python需要用一个软件,叫QPython3L,当然还有别的软件也是可以运行Python的,不过我认为QPython3L是其中相对较好的一个。

    诸葛青云
  • Java List用法代码分析——非常详细

    Java中可变数组的原理就是不断的创建新的数组,将原数组加到新的数组中,下文对Java List用法做了详解。

    Java团长

扫码关注云+社区

领取腾讯云代金券