摘要：知乎上也有相關(guān)的討論，開發(fā)的下一代編輯器莫非已經(jīng)定義為上一代編輯器了嗎。

這篇是我在知乎的回答，原文在這里：justjavac: VS Code、ATOM這些開源文本編輯器的代碼實(shí)現(xiàn)中有哪些奇技淫巧？

研究 V8 比較多，也關(guān)注了一下 vscode 和 atom 的性能，每次 vscode、atom 的 change log 我都會看一遍。印象最深的是 vscode 1.14 的一次更新日志，doApplyEdits Lines inserted using splice · Issue #351 · Microsoft/monaco-editor：不要在循環(huán)中使用 splice。

下圖是我一年前跑的測試結(jié)果：Inserting an array within an array

300+倍的差距。

在之前 vscode 還有一次很大的性能提升，在版本 1.9 的時候，改進(jìn)了語法高亮的算法。

語法高亮的過程通常分為 2 個階段(tokenization 和 render)：先將源碼分割為 token，然后使用不同的主題對分割后的 token 進(jìn)行著色。

tokenization 的過程是：從上到下逐行運(yùn)行。tokenizer 在行的末尾存儲一些狀態(tài)，在 tokenize 下一行時會用到這些狀態(tài)。這樣，在用戶進(jìn)行編輯時僅需要重新 tokenize 行的一小部分，而不需要掃描整個文件內(nèi)容。

還有一種情況是當(dāng)前行的輸入會影響到后面（甚至是前面）的行，這時會用到結(jié)束狀態(tài)：

在 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 團(tuán)隊(duì)在博客種指出這在 Chrome 中占據(jù) 648 個字節(jié)，因此存儲這樣的對象在內(nèi)存方面的代價非常高（每個對象實(shí)例必須保留指向其原型的空間，以及其屬性列表等）。為 15 個字符存儲 648 字節(jié)是不可接受的。

所以，vscode 使用二進(jìn)制來存儲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 由字符串變成了數(shù)字，本質(zhì)上并沒有節(jié)約太多的內(nèi)存。但是別著急，vscode 還有黑科技。

我們都知道 JavaScript 使用 IEEE-754 標(biāo)準(zhǔn)存儲雙精度浮點(diǎn)數(shù)，尾數(shù)為 53bit。能夠在不丟失精度的情況下處理的最大整數(shù)為 2^53-1。因此 vscode 使用其中的 48big 進(jìn)行編碼：使用 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
]

每個數(shù)字是 64bit(8字節(jié))，一共是 7 個數(shù)字，存儲這些元素一共需要 7*8 = 56 字節(jié)，再加上數(shù)組的額外開銷共需要 104 個字節(jié)，只有之前的 648 字節(jié)的 1/6。

而主題的渲染則用到了 Trie 數(shù)據(jù)結(jié)構(gòu)。

這個學(xué)過《數(shù)據(jù)結(jié)構(gòu)》的都懂，算不上奇技淫巧，就不展開了。

這一切都是 2017 年 3 月發(fā)布的 vscode 1.9。

而今年 3 月，vscode 又重寫了 Text Buffer。用戶使用編輯器，大部分時間就是寫新代碼，改舊代碼，說到底還是對 text 進(jìn)行編輯。

對于高性能的文本操作，vscode 最初嘗試使用 C++ 進(jìn)行編寫，畢竟 C++ 的性能要比 JavaScript 高出不少，但是事實(shí)卻不夠理想，使用 C++ 確實(shí)節(jié)約了內(nèi)存，但是在使用 C++ 模塊時，需要在 JavaScript 和 C++ 之間往返數(shù)次，這大大減慢了 vscode 的性能。

vscode 團(tuán)隊(duì)從 Vyacheslav Egorov 的一篇文章 Maybe you don"t need Rust and WASM to speed up your JS 收到了啟發(fā)，如何充分壓榨 V8 引擎的性能。mrale.ph 的博客我?guī)缀趺科伎矗浅＝?jīng)典，也非常難懂 。

大多編輯器都是基于行的。程序員逐行編寫代碼，編譯器提供基于行的反饋信息，堆棧跟蹤包含行號，tokenization 引擎逐行運(yùn)行…… 在 vscode 的早期版本中也是直接把每行代碼作為字符串存儲在數(shù)組中。

但是這種方式存在一些問題：

無法打開大文件，因?yàn)榘阉袃?nèi)容讀入數(shù)組中可能導(dǎo)致內(nèi)存不足。

即使文件不大，但是行數(shù)太多也無法打開。例如，一個用戶無法打開一個 35 MB 的文件。根本原因是該文件的行數(shù)太多，1370 萬行。引擎將為ModelLine每行和每個對象使用大約 40-60 個字節(jié)，因此整個數(shù)組使用大約 600MB 內(nèi)存來存儲文檔。也就是說打開這個 35M 的文件需要 600M 的內(nèi)容，20 倍啊！！！

另一個問題就是速度。為了構(gòu)建這個數(shù)組，必須通過換行符分割內(nèi)容，以便每行獲得一個字符串對象。

于是 vscode 開始尋找新的數(shù)據(jù)結(jié)果，最終選擇了 Piece table。不知道為什么這么晚才選擇 piece table，要知道在微軟的 office word 中早就已經(jīng)使用了 piece table。我也是在一次 Java 讀取 word 的 jar 包源碼中第一次知道的 piece table 數(shù)據(jù)結(jié)構(gòu)。

推薦幾篇延伸閱讀的文章：

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 數(shù)據(jù)結(jié)構(gòu)，使用 C++ 重新實(shí)現(xiàn)了 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

經(jīng)過一系列優(yōu)化，官方說道：

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 確實(shí)是 V8 的神器，Nodejs 也看到了 Atom 的成果，于 2017-11-16 開了 issue ：speeding up Node.js startup using V8 snapshot · Issue #17058 · nodejs/node。這在我之前的專欄里面有介紹：Node.js 新計劃：使用 V8 snapshot 將啟動速度提升 8 倍。

最近一次關(guān)注 Atom 是 atom/xray。知乎上也有相關(guān)的討論，atom 開發(fā)的下一代編輯器（莫非已經(jīng)定義 atom 為上一代編輯器了嗎）。大概就是一種“大號廢了，開小號重練”的感覺。

值得學(xué)習(xí)的地方是 text 處理使用 copy-on-write CRDT：

如果一直關(guān)注 Atom，對于 CRDT 應(yīng)該不會陌生。Atom 的多人實(shí)時共同編輯插件 https://teletype.atom.io/ 就是使用的 CRDT。

CRDT 全稱：Conflict-Free Replicated Data Types，強(qiáng)行翻譯過來就是“無沖突可復(fù)制數(shù)據(jù)類型”。

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

CAP定理：在分布式系統(tǒng)中，最多只能同時滿足一致性（Consistency）、可用性（Availability）和分區(qū)容錯性（Partition tolerance）這三項(xiàng)中的兩項(xiàng)。

很多分布式系統(tǒng)都舍棄了C（一致性）：允許可以在某些時刻不一致，轉(zhuǎn)而求其次要求系統(tǒng)滿足最終一致性。這也是目前很多 nosql 數(shù)據(jù)庫追求的方式（另一種是傳統(tǒng)的符合 ACID 特性的數(shù)據(jù)庫系統(tǒng)，放棄了A(可用性)，這種系統(tǒng)稱為強(qiáng)一致性）。

而在最終一致性分布式系統(tǒng)中，一個最基本的問題就是，應(yīng)該采用什么樣的數(shù)據(jù)結(jié)構(gòu)來保證最終一致性？ 答案就是 CRDT。

atom/teletype-crdt

這篇文章只是一個提綱，里面的每個知識點(diǎn)都可以展開了講上三天三夜。