作為Github上一款開(kāi)源的文本編輯器，Atom一經(jīng)推出就受到了廣泛的歡迎。Atom的幾個(gè)功能取決于基于開(kāi)放緩沖區(qū)內(nèi)容的潛在的長(zhǎng)時(shí)間運(yùn)行計(jì)算，但直到最近，才有可能從主線程上運(yùn)行的JavaScript訪問(wèn)緩沖區(qū)的文本。這使得很難保證Atom在所有場(chǎng)景下的響應(yīng)能力，特別是在編輯較大的文件時(shí)。
隨著Atom 1.19版本的發(fā)布，這種情況發(fā)生了變化，這開(kāi)辟了通過(guò)C ++實(shí)現(xiàn)的新文本存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)顯著增加并行性的途徑。這種新的設(shè)計(jì)為性能和可擴(kuò)展性提供了許多好處，其中主要的工作線程能夠讀取先前緩沖區(qū)狀態(tài)的快照，而不會(huì)阻塞主線程上的寫(xiě)入操作。在這篇文章中，將深入介紹Atom對(duì)文本存儲(chǔ)的新方法，然后探索將其成為許多優(yōu)化中的第一步。
分層更改
Atom新的緩沖區(qū)表示的關(guān)鍵思想是將緩沖區(qū)的內(nèi)容分為兩個(gè)主要的狀態(tài)。首先，有一個(gè)基本文本，它對(duì)應(yīng)于最近讀取或?qū)懭氪疟P(pán)的文檔版本?；镜奈谋臼遣豢勺兊?，并存儲(chǔ)在連續(xù)分配的單個(gè)內(nèi)存塊中。而疊加在基本文本上面的是未保存的更改，它們存儲(chǔ)在稱為Patch(補(bǔ)丁)的單獨(dú)的稀疏數(shù)據(jù)結(jié)構(gòu)中。為了記錄編輯，而不是將緩沖區(qū)的全部?jī)?nèi)容移動(dòng)到內(nèi)存中，只需對(duì)這個(gè)Patch進(jìn)行變更。
實(shí)際上在任何時(shí)候都可以存在多個(gè)Patch(補(bǔ)丁)塊。最頂層的Patch(補(bǔ)丁)始終是可變的，但是可以通過(guò)凍結(jié)最頂層的Patch(補(bǔ)丁)并將新Patch(補(bǔ)丁)推送到堆棧的頂部，來(lái)創(chuàng)建當(dāng)前緩沖區(qū)內(nèi)容的只讀快照。將流編輯到這個(gè)新Patch(補(bǔ)丁)中，直到不再需要快照，此時(shí)最頂層的補(bǔ)丁可以合并到前一層的Patch(補(bǔ)丁)中。
要讀取緩沖區(qū)狀態(tài)，需要遍歷連續(xù)的“塊”，其中每個(gè)塊對(duì)應(yīng)于一個(gè)分層Patch(補(bǔ)丁)的更改或包含基本文本的數(shù)組的切片。
Patch(補(bǔ)丁)數(shù)據(jù)結(jié)構(gòu)
整個(gè)系統(tǒng)的核心是Patch(補(bǔ)丁)數(shù)據(jù)結(jié)構(gòu)，它描述了如何將一系列文本更改應(yīng)用于某些輸入以產(chǎn)生新的輸出。它基本上是通過(guò)在輸入和輸出上運(yùn)行差異來(lái)獲得相同的信息，但不是通過(guò)比較兩個(gè)緩沖區(qū)的內(nèi)容來(lái)構(gòu)建的，而是通過(guò)組合一系列的編輯來(lái)逐步構(gòu)建的。
需要解決的問(wèn)題
希望更好地了解Patch(補(bǔ)丁)解決的問(wèn)題，請(qǐng)參考一下這個(gè)示例。先從包含xxxx的緩沖區(qū)開(kāi)始，然后執(zhí)行以下插入：
insert B @ 2 -> xxBxx
insert C @ 4 -> xxBxCx
insert A @ 1 -> xAxBxCx
之后，需要一個(gè)對(duì)變更內(nèi)容的總結(jié)，需要diff字符來(lái)表達(dá)(diff是Unix系統(tǒng)的一個(gè)很重要的工具，用來(lái)比較兩個(gè)文本文件的差異)。就像這樣：
[
{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'}
]
這個(gè)diff中的每個(gè)entry(接口)都有一個(gè)oldRange，不考慮Patch中存在的任何其他更改。例如，描述插入C的entry具有[3，3]的oldRange，它包括了插入A和B的影響。相反，每個(gè)變化的newRange反映了Patch中所有其他編輯的空間影響。例如，插入C具有[5,6]的newRange，這說(shuō)明了緩沖區(qū)中插入A和B比較早。
這種總結(jié)不需要從原始編輯流中獲得，無(wú)需額外處理?？紤]在索引4插入C。這個(gè)索引已經(jīng)解釋了B的先前插入，但是它并沒(méi)有考慮到A在C之前被插入，而是在C之后插入。要在上面所示的diff平臺(tái)中生成oldRange和newRange，人們需要了解每個(gè)變化與其他變化的空間關(guān)系，而不管其時(shí)間順序如何。
一個(gè)簡(jiǎn)單的解決方案
這個(gè)問(wèn)題的一個(gè)簡(jiǎn)單的解決方案是將每個(gè)更改存儲(chǔ)在一個(gè)列表中，每個(gè)更改都存儲(chǔ)其oldText，newText和distanceFromPreviousChange。人們通過(guò)瀏覽現(xiàn)有的更改來(lái)確定列表中每個(gè)新條目的插入位置。下面是根據(jù)上面示例中的插入如何更改列表的方法。
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始終為空，因?yàn)槿藗冎粓?zhí)行插入操作，但通過(guò)對(duì)oldText使用非空值可以輕松地表達(dá)刪除或替換。一旦有了這個(gè)更改列表，就可以通過(guò)遍歷列表來(lái)生成所需的摘要，根據(jù)上一次更改的這些Range的結(jié)尾，將每個(gè)變更的oldRange和newRange放在開(kāi)頭。
伸展樹(shù)(Splay trees)
采用上述方法的問(wèn)題是，在列表中插入更改可能需要人們檢查每一個(gè)其他更改，這會(huì)產(chǎn)生O(n2)的時(shí)間復(fù)雜度。
為了確保在生產(chǎn)中實(shí)現(xiàn)良好性能，人們通過(guò)使用Splay樹(shù)而不是簡(jiǎn)單的列表來(lái)提高對(duì)O(n·log 2n)的限制。伸展樹(shù)是一種二進(jìn)制搜索樹(shù)的版本，可以相當(dāng)簡(jiǎn)單的實(shí)現(xiàn)，并具有“自我優(yōu)化”的非常良好的屬性。這意味著當(dāng)它們被查詢和修改時(shí)，它們會(huì)自動(dòng)調(diào)整其結(jié)構(gòu)，使得訪問(wèn)最近訪問(wèn)節(jié)點(diǎn)附近的節(jié)點(diǎn)更便宜。對(duì)于隨機(jī)工作負(fù)載，此屬性沒(méi)有什么幫助，但對(duì)于表現(xiàn)出高度局部性(如文本編輯器中出現(xiàn)的)的工作負(fù)載，這種自優(yōu)化行為是非常有用的。
Splay樹(shù)圍繞著一個(gè)非常簡(jiǎn)單的原則。每次訪問(wèn)一個(gè)節(jié)點(diǎn)時(shí)，它將通過(guò)splay的特殊指針旋轉(zhuǎn)到樹(shù)的根。splay不僅將節(jié)點(diǎn)移動(dòng)到節(jié)點(diǎn)樹(shù)的根，而且還減少了節(jié)點(diǎn)附近的樹(shù)的深度，確保下一次訪問(wèn)附近的節(jié)點(diǎn)時(shí)，它將更接近根，因此可以更快地找到。
這個(gè)方法的值得注意的是O(n·log 2n)是一個(gè)攤銷的邊界。任何單一操作的成本可能與O(n)一樣多，從而使后續(xù)操作低本更低。實(shí)際上，這很好。任何單一的線性時(shí)間操作通常不會(huì)導(dǎo)致性能問(wèn)題。只有當(dāng)人們開(kāi)始執(zhí)行時(shí)間復(fù)雜度變成二次執(zhí)行多個(gè)線性時(shí)間的操作，并且恰好Splay樹(shù)可以有助于避免這種情況。
如果想了解更多有關(guān)伸展樹(shù)的信息，麻省理工學(xué)院David Karger的講座做了一個(gè)很好的介紹。
為用例增加Splay樹(shù)
在文獻(xiàn)中，Splay樹(shù)總是作為鍵和值之間的簡(jiǎn)單有序映射呈現(xiàn)。使用Patch，正在解決一個(gè)更復(fù)雜的問(wèn)題：伸展樹(shù)需要在新舊的坐標(biāo)空間中保持每個(gè)節(jié)點(diǎn)的位置，以便可以有效地更新所有后續(xù)節(jié)點(diǎn)的位置，插入更改。為了做到這一點(diǎn)，人們將每個(gè)節(jié)點(diǎn)與常量密鑰相關(guān)聯(lián)，而不是將每個(gè)節(jié)點(diǎn)與相對(duì)表達(dá)的值相關(guān)聯(lián)，這些值表示節(jié)點(diǎn)與舊祖先和新坐標(biāo)空間之間的距離。
在上面的圖表中，每個(gè)變化都顯示為梯形，以圖形方式表示替換一行字符的空間影響。在前面所說(shuō)明的列表表示中，與上一次更改的距離在兩個(gè)坐標(biāo)空間中總是相同的，因?yàn)槿魏蝺蓚€(gè)更改之間的文本都不會(huì)被修改。在Splay樹(shù)的版本中，每個(gè)更改都要存儲(chǔ)與其左祖先節(jié)點(diǎn)的距離，其總結(jié)了整個(gè)子樹(shù)對(duì)該更改左側(cè)的空間影響。以上每個(gè)陰影較深的節(jié)點(diǎn)都在其左子樹(shù)中有變化，因此每個(gè)坐標(biāo)空間的距離與其左祖先節(jié)點(diǎn)的距離不同。要將這些相對(duì)距離轉(zhuǎn)換為絕對(duì)位置，在從根降到葉的同時(shí)，在兩個(gè)坐標(biāo)空間中累加一個(gè)運(yùn)行總數(shù)。
要插入新的更改，將顯示正在替換的最接近范圍的現(xiàn)有更改。當(dāng)在splay樹(shù)操作期間重新排列指針時(shí)，可以根據(jù)本地可用的信息更新到每個(gè)節(jié)點(diǎn)的左祖先節(jié)點(diǎn)的距離。一旦下限和上限節(jié)點(diǎn)已經(jīng)旋轉(zhuǎn)到樹(shù)的根，它們之間的任何節(jié)點(diǎn)將被插入的更改所包含，這意味著它們可以被刪除。然后，插入新的更改，將其與樹(shù)的根目錄中的一個(gè)或兩個(gè)節(jié)點(diǎn)進(jìn)行合并，這取決于它是否重疊。
對(duì)于patch結(jié)構(gòu)，顯示不僅僅是一個(gè)保持Splay樹(shù)更平衡的機(jī)制。實(shí)際上依賴于將節(jié)點(diǎn)移動(dòng)到根的能力，以便將新的變化連接到結(jié)構(gòu)中。使用更加剛性平衡的數(shù)據(jù)結(jié)構(gòu)(如紅黑樹(shù))，在不違反關(guān)鍵不變量的情況下，更難將節(jié)點(diǎn)旋轉(zhuǎn)到根上。
值得注意的是，在上述所有示例中，為了清楚起見(jiàn)，使用標(biāo)量值來(lái)表示位置和距離。實(shí)際上，這些值被表示為由行和列組成的二維向量。這增加了一些復(fù)雜性，但基本思想保持不變。還值得注意的是，該結(jié)構(gòu)具有超出本文中描述的緩沖區(qū)表示的實(shí)用性。人們最初創(chuàng)建它來(lái)聚合每個(gè)事務(wù)中發(fā)生的所有更改，以便人們可以通過(guò)diff工具通知變更監(jiān)聽(tīng)器，并將最緊湊的表示存儲(chǔ)在撤消堆棧中。還使用patch在存在面向表達(dá)式轉(zhuǎn)換(如軟包裝和代碼折疊)的情況下對(duì)緩沖區(qū)和屏幕坐標(biāo)之間的轉(zhuǎn)換進(jìn)行索引。這是一個(gè)復(fù)雜的代碼段，但是人們從中得到了很多。
一些初步的優(yōu)化
C++實(shí)現(xiàn)緩沖區(qū)本身就是一個(gè)勝利，可以獲得Atom的整體效率。JavaScript可能相當(dāng)快，但從根本上說(shuō)，它是一種腳本語(yǔ)言，具有不可避免的開(kāi)銷。通過(guò)在C ++中實(shí)現(xiàn)緩沖區(qū)，消除了JS的開(kāi)銷，并獲得了最大化效率所需的控制權(quán)限。還通過(guò)簡(jiǎn)化堆并在熱代碼路徑上分配更少的短期對(duì)象來(lái)減輕對(duì)V8垃圾收集器的壓力。但這些改進(jìn)只是一個(gè)開(kāi)始。這種新表現(xiàn)的真正價(jià)值在于其分層設(shè)計(jì)實(shí)現(xiàn)的優(yōu)化。
未保存更改的進(jìn)行有效備份
去年一月，當(dāng)人們發(fā)現(xiàn)一個(gè)令人沮喪的瓶頸時(shí)，剛剛完成了另一項(xiàng)改進(jìn)，使Atom可以處理更大的文件。編輯大文件時(shí)最大的麻煩之一是需要周期性地將大緩沖區(qū)的未保存狀態(tài)寫(xiě)入磁盤(pán)。在容量足夠的情況下，甚至收集了寫(xiě)緩沖異步介紹明顯停頓的內(nèi)容，雖然可以巧妙地利用requestIdleCallback和輸出流，但擔(dān)心寫(xiě)入時(shí)的能量沖擊。人們一直在考慮這個(gè)新的緩沖區(qū)設(shè)計(jì)，并認(rèn)為高效的后臺(tái)保存是構(gòu)建它的一個(gè)很好的初始動(dòng)機(jī)。
出于崩潰恢復(fù)的目的，人們只關(guān)心新的緩沖區(qū)表示方式提供的未保存的更改?，F(xiàn)在，不用寫(xiě)出緩沖區(qū)的全部?jī)?nèi)容，而是將所有未完成的層組合成一個(gè)patch，并將其序列化為磁盤(pán)以及基本文本的摘要。人們正在編寫(xiě)的數(shù)據(jù)量隨著更改次數(shù)的增加而不再擔(dān)心文件的大小，從而在大多數(shù)情況下效率更高。對(duì)于幾十兆字節(jié)的未保存更改的文件，還有一些工作要做，但是這些情況是相當(dāng)罕見(jiàn)的。
異步保存
在Atom1.19之前的版本中，在Atom中保存緩沖區(qū)是一個(gè)同步操作。這是因?yàn)樵趧?chuàng)建Electron工具之前編寫(xiě)文件的代碼路徑，以及在那些從基于瀏覽器的桌面應(yīng)用程序執(zhí)行異步I/O的時(shí)候并不像現(xiàn)在這樣簡(jiǎn)單。如今，這個(gè)新的緩沖區(qū)實(shí)現(xiàn)讓人們有機(jī)會(huì)以優(yōu)雅的方式來(lái)解決這個(gè)問(wèn)題。將緩沖區(qū)的內(nèi)容從UTF-16轉(zhuǎn)換為用戶所需的編碼，并將其寫(xiě)入磁盤(pán)，現(xiàn)在完全用C ++在后臺(tái)線程上執(zhí)行。在開(kāi)始保存之前，創(chuàng)建一個(gè)快照，這樣用戶即使在保存速度較慢時(shí)也可以進(jìn)行額外的更改，比如使用網(wǎng)絡(luò)驅(qū)動(dòng)器時(shí)。
在背景中自動(dòng)完成子序列匹配
在默認(rèn)情況下，Atom的自動(dòng)完成系統(tǒng)會(huì)根據(jù)與光標(biāo)前面的字符的子序列匹配來(lái)建立來(lái)自開(kāi)放緩沖區(qū)的單詞。例如，bna |將會(huì)產(chǎn)生banana, bandaid, bandana等建議。然后，根據(jù)表示匹配質(zhì)量的分?jǐn)?shù)對(duì)建議進(jìn)行排序。
在Atom 1.22版本之前，是通過(guò)為每個(gè)緩沖區(qū)維護(hù)唯一的單詞列表并在主線程上運(yùn)行JavaScript來(lái)匹配、分?jǐn)?shù)和排序建議來(lái)實(shí)現(xiàn)此功能。雖然這對(duì)大多數(shù)文件來(lái)說(shuō)都是可行的，但隨著文件大小的增加，單詞列表開(kāi)始消耗嚴(yán)重的內(nèi)存，主線程上的匹配建議可能會(huì)對(duì)用戶接口(UI)造成明顯的阻礙。
由于新的緩沖區(qū)實(shí)現(xiàn)，在Atom 1.22之后推出了一個(gè)新的自動(dòng)完成提供程序，它利用快照來(lái)執(zhí)行相同的作業(yè)，沒(méi)有內(nèi)存開(kāi)銷，也不會(huì)對(duì)Atom的響應(yīng)性產(chǎn)生威脅?，F(xiàn)在，大部分任務(wù)繁重的升級(jí)都是以核心中的一個(gè)新的textbuffer.findwordswithsubsequence(文本緩沖區(qū)查找?guī)в凶有蛄械膯卧~)方法執(zhí)行的，該方法在后臺(tái)線程中執(zhí)行匹配，評(píng)分和排序。這意味著可以在每次按下按鍵之后可以立即開(kāi)始搜索建議，而其他工作則在主線程上進(jìn)行。到下一幀的時(shí)候，這些建議通常是可用的，但是當(dāng)搜索它們時(shí)，不會(huì)拖延一幀。在極少的情況下，建議需要比一個(gè)計(jì)算時(shí)間更長(zhǎng)的時(shí)間，將簡(jiǎn)單地將它們呈現(xiàn)在后續(xù)的框架中。
未來(lái)的回報(bào)
這種新的緩沖區(qū)意味著為未來(lái)的許多改進(jìn)奠定了基礎(chǔ)。在短期內(nèi)，在工作線程中進(jìn)行非阻塞讀取的能力將有助于人們?cè)谠S多領(lǐng)域提高響應(yīng)能力，而其中許多領(lǐng)域還沒(méi)有探索。
從長(zhǎng)遠(yuǎn)來(lái)看，將緩沖區(qū)實(shí)現(xiàn)轉(zhuǎn)換為C ++也為其他子系統(tǒng)的移植打下了基礎(chǔ)。如今正在逐漸建立一個(gè)名為superstring的本地庫(kù)，它實(shí)現(xiàn)了Atom核心的多個(gè)性能關(guān)鍵組件，如本文中描述的patch和文本存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)。人們通過(guò)V8嵌入API與JavaScript通過(guò)JavaScript進(jìn)行交互操作，但它還具有在Electron之外使用的Emscripten綁定?，F(xiàn)在，與緩沖區(qū)關(guān)聯(lián)的關(guān)鍵狀態(tài)已經(jīng)成為超級(jí)管道，人們可以逐步移植任何需要訪問(wèn)緩沖區(qū)內(nèi)容的關(guān)鍵性代碼路徑。
需要明確的是，JavaScript的可接近性和靈活性是一個(gè)巨大的資產(chǎn)，所以人們會(huì)在C ++的原始性能交易之前總是慎重考慮，但是這篇博文表明，JavaScript的限制不代表所提供的表現(xiàn)出色的Atom也具有基本限制。
京公網(wǎng)安備 11010502049343號(hào)