Atom1.19版本重大架構更新，新功能你都摸清楚了嗎？

作為Github上一款開源的文本編輯器，Atom一經推出就受到了廣泛的歡迎。Atom的幾個功能取決於基於開放緩衝區內容的潛在的長時間運行計算，但直到最近，才有可能從主線程上運行的JavaScript訪問緩衝區的文本。這使得很難保證Atom在所有場景下的響應能力，特別是在編輯較大的文件時。

隨著Atom 1.19版本的發布，這種情況發生了變化，這開闢了通過C ++實現的新文本存儲數據結構顯著增加並行性的途徑。這種新的設計為性能和可擴展性提供了許多好處，其中主要的工作線程能夠讀取先前緩衝區狀態的快照，而不會阻塞主線程上的寫入操作。在這篇文章中，將深入介紹Atom對文本存儲的新方法，然後探索將其成為許多優化中的第一步。

分層更改

Atom新的緩衝區表示的關鍵思想是將緩衝區的內容分為兩個主要的狀態。首先，有一個基本文本，它對應於最近讀取或寫入磁碟的文檔版本。基本的文本是不可變的，並存儲在連續分配的單個內存塊中。而疊加在基本文本上面的是未保存的更改，它們存儲在稱為Patch（補丁）的單獨的稀疏數據結構中。為了記錄編輯，而不是將緩衝區的全部內容移動到內存中，只需對這個Patch進行變更。

實際上在任何時候都可以存在多個Patch（補丁）塊。最頂層的Patch（補丁）始終是可變的，但是可以通過凍結最頂層的Patch（補丁）並將新Patch（補丁）推送到堆棧的頂部，來創建當前緩衝區內容的只讀快照。將流編輯到這個新Patch（補丁）中，直到不再需要快照，此時最頂層的補丁可以合併到前一層的Patch（補丁）中。

要讀取緩衝區狀態，需要遍歷連續的「塊」，其中每個塊對應於一個分層Patch（補丁）的更改或包含基本文本的數組的切片。

Patch（補丁）數據結構

整個系統的核心是Patch（補丁）數據結構，它描述了如何將一系列文本更改應用於某些輸入以產生新的輸出。它基本上是通過在輸入和輸出上運行差異來獲得相同的信息，但不是通過比較兩個緩衝區的內容來構建的，而是通過組合一系列的編輯來逐步構建的。

需要解決的問題

希望更好地了解Patch（補丁）解決的問題，請參考一下這個示例。先從包含xxxx的緩衝區開始，然後執行以下插入：

• insert B @ 2 -> xxBxx

• insert C @ 4 -> xxBxCx

• insert A @ 1 -> xAxBxCx

之後，需要一個對變更內容的總結，需要diff字元來表達（diff是Unix系統的一個很重要的工具，用來比較兩個文本文件的差異）。就像這樣：

[

{oldRange: [1, 1], oldText: "", newRange: [1, 2], newText: "A"},

{oldRange: [2, 2], oldText: "", newRange: [3, 4], newText: "B"},

{oldRange: [3, 3], oldText: "", newRange: [5, 6], newText: "C"}

]

這個diff中的每個entry（介面）都有一個oldRange，不考慮Patch中存在的任何其他更改。例如，描述插入C的entry具有[3，3]的oldRange，它包括了插入A和B的影響。相反，每個變化的newRange反映了Patch中所有其他編輯的空間影響。例如，插入C具有[5,6]的newRange，這說明了緩衝區中插入A和B比較早。

這種總結不需要從原始編輯流中獲得，無需額外處理。考慮在索引4插入C。這個索引已經解釋了B的先前插入，但是它並沒有考慮到A在C之前被插入，而是在C之後插入。要在上面所示的diff平台中生成oldRange和newRange，人們需要了解每個變化與其他變化的空間關係，而不管其時間順序如何。

一個簡單的解決方案

這個問題的一個簡單的解決方案是將每個更改存儲在一個列表中，每個更改都存儲其oldText，newText和distanceFromPreviousChange。人們通過瀏覽現有的更改來確定列表中每個新條目的插入位置。下面是根據上面示例中的插入如何更改列表的方法。

assert.deepEqual(patch.changes, [])

patch.splice(2, "", "B")

assert.deepEqual(patch.changes, [

{distanceFromPreviousChange: 2, oldText: "", newText: "B"}

])

patch.splice(4, "", "C")

assert.deepEqual(patch.changes, [

{oldText: "", newText: "B", distanceFromPreviousChange: 2},

{oldText: "", newText: "C", distanceFromPreviousChange: 1}

])

patch.splice(1, "", "A")

assert.deepEqual(patch.changes, [

{oldText: "", newText: "A", distanceFromPreviousChange: 1},

{oldText: "", newText: "B", distanceFromPreviousChange: 1},

{oldText: "", newText: "C", distanceFromPreviousChange: 1}

])

在這種情況下，oldText始終為空，因為人們只執行插入操作，但通過對oldText使用非空值可以輕鬆地表達刪除或替換。一旦有了這個更改列表，就可以通過遍歷列表來生成所需的摘要，根據上一次更改的這些Range的結尾，將每個變更的oldRange和newRange放在開頭。

伸展樹（Splay trees）

採用上述方法的問題是，在列表中插入更改可能需要人們檢查每一個其他更改，這會產生O（n2）的時間複雜度。

為了確保在生產中實現良好性能，人們通過使用Splay樹而不是簡單的列表來提高對O（n·log 2n）的限制。伸展樹是一種二進位搜索樹的版本，可以相當簡單的實現，並具有「自我優化」的非常良好的屬性。這意味著當它們被查詢和修改時，它們會自動調整其結構，使得訪問最近訪問節點附近的節點更便宜。對於隨機工作負載，此屬性沒有什麼幫助，但對於表現出高度局部性（如文本編輯器中出現的）的工作負載，這種自優化行為是非常有用的。

Splay樹圍繞著一個非常簡單的原則。每次訪問一個節點時，它將通過splay的特殊指針旋轉到樹的根。splay不僅將節點移動到節點樹的根，而且還減少了節點附近的樹的深度，確保下一次訪問附近的節點時，它將更接近根，因此可以更快地找到。

這個方法的值得注意的是O（n·log 2n）是一個攤銷的邊界。任何單一操作的成本可能與O（n）一樣多，從而使後續操作低本更低。實際上，這很好。任何單一的線性時間操作通常不會導致性能問題。只有當人們開始執行時間複雜度變成二次執行多個線性時間的操作，並且恰好Splay樹可以有助於避免這種情況。

如果想了解更多有關伸展樹的信息，麻省理工學院David Karger的講座做了一個很好的介紹。

為用例增加Splay樹

在文獻中，Splay樹總是作為鍵和值之間的簡單有序映射呈現。使用Patch，正在解決一個更複雜的問題：伸展樹需要在新舊的坐標空間中保持每個節點的位置，以便可以有效地更新所有後續節點的位置，插入更改。為了做到這一點，人們將每個節點與常量密鑰相關聯，而不是將每個節點與相對表達的值相關聯，這些值表示節點與舊祖先和新坐標空間之間的距離。

在上面的圖表中，每個變化都顯示為梯形，以圖形方式表示替換一行字元的空間影響。在前面所說明的列表表示中，與上一次更改的距離在兩個坐標空間中總是相同的，因為任何兩個更改之間的文本都不會被修改。在Splay樹的版本中，每個更改都要存儲與其左祖先節點的距離，其總結了整個子樹對該更改左側的空間影響。以上每個陰影較深的節點都在其左子樹中有變化，因此每個坐標空間的距離與其左祖先節點的距離不同。要將這些相對距離轉換為絕對位置，在從根降到葉的同時，在兩個坐標空間中累加一個運行總數。

要插入新的更改，將顯示正在替換的最接近範圍的現有更改。當在splay樹操作期間重新排列指針時，可以根據本地可用的信息更新到每個節點的左祖先節點的距離。一旦下限和上限節點已經旋轉到樹的根，它們之間的任何節點將被插入的更改所包含，這意味著它們可以被刪除。然後，插入新的更改，將其與樹的根目錄中的一個或兩個節點進行合併，這取決於它是否重疊。

對於patch結構，顯示不僅僅是一個保持Splay樹更平衡的機制。實際上依賴於將節點移動到根的能力，以便將新的變化連接到結構中。使用更加剛性平衡的數據結構（如紅黑樹），在不違反關鍵不變數的情況下，更難將節點旋轉到根上。

值得注意的是，在上述所有示例中，為了清楚起見，使用標量值來表示位置和距離。實際上，這些值被表示為由行和列組成的二維向量。這增加了一些複雜性，但基本思想保持不變。還值得注意的是，該結構具有超出本文中描述的緩衝區表示的實用性。人們最初創建它來聚合每個事務中發生的所有更改，以便人們可以通過diff工具通知變更監聽器，並將最緊湊的表示存儲在撤消堆棧中。還使用patch在存在面向表達式轉換（如軟包裝和代碼摺疊）的情況下對緩衝區和屏幕坐標之間的轉換進行索引。這是一個複雜的代碼段，但是人們從中得到了很多。

一些初步的優化

C++實現緩衝區本身就是一個勝利，可以獲得Atom的整體效率。JavaScript可能相當快，但從根本上說，它是一種腳本語言，具有不可避免的開銷。通過在C ++中實現緩衝區，消除了JS的開銷，並獲得了最大化效率所需的控制許可權。還通過簡化堆並在熱代碼路徑上分配更少的短期對象來減輕對V8垃圾收集器的壓力。但這些改進只是一個開始。這種新表現的真正價值在於其分層設計實現的優化。

未保存更改的進行有效備份

去年一月，當人們發現一個令人沮喪的瓶頸時，剛剛完成了另一項改進，使Atom可以處理更大的文件。編輯大文件時最大的麻煩之一是需要周期性地將大緩衝區的未保存狀態寫入磁碟。在容量足夠的情況下，甚至收集了寫緩衝非同步介紹明顯停頓的內容，雖然可以巧妙地利用requestIdleCallback和輸出流，但擔心寫入時的能量衝擊。人們一直在考慮這個新的緩衝區設計，並認為高效的後台保存是構建它的一個很好的初始動機。

出於崩潰恢復的目的，人們只關心新的緩衝區表示方式提供的未保存的更改。現在，不用寫出緩衝區的全部內容，而是將所有未完成的層組合成一個patch，並將其序列化為磁碟以及基本文本的摘要。人們正在編寫的數據量隨著更改次數的增加而不再擔心文件的大小，從而在大多數情況下效率更高。對於幾十兆位元組的未保存更改的文件，還有一些工作要做，但是這些情況是相當罕見的。

非同步保存

在Atom1.19之前的版本中，在Atom中保存緩衝區是一個同步操作。這是因為在創建Electron工具之前編寫文件的代碼路徑，以及在那些從基於瀏覽器的桌面應用程序執行非同步I/O的時候並不像現在這樣簡單。如今，這個新的緩衝區實現讓人們有機會以優雅的方式來解決這個問題。將緩衝區的內容從UTF-16轉換為用戶所需的編碼，並將其寫入磁碟，現在完全用C ++在後台線程上執行。在開始保存之前，創建一個快照，這樣用戶即使在保存速度較慢時也可以進行額外的更改，比如使用網路驅動器時。

在背景中自動完成子序列匹配

在默認情況下，Atom的自動完成系統會根據與游標前面的字元的子序列匹配來建立來自開放緩衝區的單詞。例如，bna |將會產生banana, bandaid, bandana等建議。然後，根據表示匹配質量的分數對建議進行排序。

在Atom 1.22版本之前，是通過為每個緩衝區維護唯一的單詞列表並在主線程上運行JavaScript來匹配、分數和排序建議來實現此功能。雖然這對大多數文件來說都是可行的，但隨著文件大小的增加，單詞列表開始消耗嚴重的內存，主線程上的匹配建議可能會對用戶介面（UI）造成明顯的阻礙。

由於新的緩衝區實現，在Atom 1.22之後推出了一個新的自動完成提供程序，它利用快照來執行相同的作業，沒有內存開銷，也不會對Atom的響應性產生威脅。現在，大部分任務繁重的升級都是以核心中的一個新的textbuffer.findwordswithsubsequence（文本緩衝區查找帶有子序列的單詞）方法執行的，該方法在後台線程中執行匹配，評分和排序。這意味著可以在每次按下按鍵之後可以立即開始搜索建議，而其他工作則在主線程上進行。到下一幀的時候，這些建議通常是可用的，但是當搜索它們時，不會拖延一幀。在極少的情況下，建議需要比一個計算時間更長的時間，將簡單地將它們呈現在後續的框架中。

未來的回報

這種新的緩衝區意味著為未來的許多改進奠定了基礎。在短期內，在工作線程中進行非阻塞讀取的能力將有助於人們在許多領域提高響應能力，而其中許多領域還沒有探索。

從長遠來看，將緩衝區實現轉換為C ++也為其他子系統的移植打下了基礎。如今正在逐漸建立一個名為superstring的本地庫，它實現了Atom核心的多個性能關鍵組件，如本文中描述的patch和文本存儲數據結構。人們通過V8嵌入API與JavaScript通過JavaScript進行交互操作，但它還具有在Electron之外使用的Emscripten綁定。現在，與緩衝區關聯的關鍵狀態已經成為超級管道，人們可以逐步移植任何需要訪問緩衝區內容的關鍵性代碼路徑。

需要明確的是，JavaScript的可接近性和靈活性是一個巨大的資產，所以人們會在C ++的原始性能交易之前總是慎重考慮，但是這篇博文表明，JavaScript的限制不代表所提供的表現出色的Atom也具有基本限制。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！