標籤:

React 源碼剖析系列 - 不可思議的 react diff

目前,前端領域中 React 勢頭正盛,使用者眾多卻少有能夠深入剖析內部實現機制和原理。本系列文章希望通過剖析 React 源碼,理解其內部的實現原理,知其然更要知其所以然。

React diff 作為 Virtual DOM 的加速器,其演算法上的改進優化是 React 整個界面渲染的基礎,以及性能提高的保障,同時也是 React 源碼中最神秘、最不可思議的部分,本文從源碼入手,深入剖析 React diff 的不可思議之處。

  • 閱讀本文需要對 React 有一定的了解,如果你不知何為 React,請詳讀 React 官方文檔。

  • 如果你對 React diff 存在些許疑惑,或者你對演算法優化感興趣,那麼本文值得閱讀和討論。

前言

React 中最值得稱道的部分莫過於 Virtual DOM 與 diff 的完美結合,特別是其高效的 diff 演算法,讓用戶可以無需顧忌性能問題而」任性自由」的刷新頁面,讓開發者也可以無需關心 Virtual DOM 背後的運作原理,因為 React diff 會幫助我們計算出 Virtual DOM 中真正變化的部分,並只針對該部分進行實際 DOM 操作,而非重新渲染整個頁面,從而保證了每次操作更新後頁面的高效渲染,因此 Virtual DOM 與 diff 是保證 React 性能口碑的幕後推手。

行文至此,可能會有讀者質疑:React 無非就是引入 diff 這一概念,且 diff 演算法也並非其首創,何必吹噓的如此天花亂墜呢?

其實,正是因為 diff 演算法的普識度高,就更應該認可 React 針對 diff 演算法優化所做的努力與貢獻,更能體現 React 開發者們的魅力與智慧!

傳統 diff 演算法

計算一棵樹形結構轉換成另一棵樹形結構的最少操作,是一個複雜且值得研究的問題。傳統 diff 演算法通過循環遞歸對節點進行依次對比,效率低下,演算法複雜度達到 O(n^3),其中 n 是樹中節點的總數。O(n^3) 到底有多可怕,這意味著如果要展示1000個節點,就要依次執行上十億次的比較。這種指數型的性能消耗對於前端渲染場景來說代價太高了!現今的 CPU 每秒鐘能執行大約30億條指令,即便是最高效的實現,也不可能在一秒內計算出差異情況。

如果 React 只是單純的引入 diff 演算法而沒有任何的優化改進,那麼其效率是遠遠無法滿足前端渲染所要求的性能。

因此,想要將 diff 思想引入 Virtual DOM,就需要設計一種穩定高效的 diff 演算法,而 React 做到了!

那麼,React diff 到底是如何實現的呢?

詳解 React diff

傳統 diff 演算法的複雜度為 O(n^3),顯然這是無法滿足性能要求的。React 通過制定大膽的策略,將 O(n^3) 複雜度的問題轉換成 O(n) 複雜度的問題

diff 策略

  1. Web UI 中 DOM 節點跨層級的移動操作特別少,可以忽略不計。

  2. 擁有相同類的兩個組件將會生成相似的樹形結構,擁有不同類的兩個組件將會生成不同的樹形結構。

  3. 對於同一層級的一組子節點,它們可以通過唯一 id 進行區分。

基於以上三個前提策略,React 分別對 tree diff、component diff 以及 element diff 進行演算法優化,事實也證明這三個前提策略是合理且準確的,它保證了整體界面構建的性能。

  • tree diff

  • component diff

  • element diff

本文中源碼 ReactMultiChild.js

tree diff

基於策略一,React 對樹的演算法進行了簡潔明了的優化,即對樹進行分層比較,兩棵樹只會對同一層次的節點進行比較。

既然 DOM 節點跨層級的移動操作少到可以忽略不計,針對這一現象,React 通過 updateDepth 對 Virtual DOM 樹進行層級控制,只會對相同顏色方框內的 DOM 節點進行比較,即同一個父節點下的所有子節點。當發現節點已經不存在,則該節點及其子節點會被完全刪除掉,不會用於進一步的比較。這樣只需要對樹進行一次遍歷,便能完成整個 DOM 樹的比較。

updateChildren: function(nextNestedChildrenElements, transaction, context) { updateDepth++; var errorThrown = true; try { this._updateChildren(nextNestedChildrenElements, transaction, context); errorThrown = false; } finally { updateDepth--; if (!updateDepth) { if (errorThrown) { clearQueue(); } else { processQueue(); } } }}

分析至此,大部分人可能都存在這樣的疑問:如果出現了 DOM 節點跨層級的移動操作,React diff 會有怎樣的表現呢?是的,對此我也好奇不已,不如試驗一番。

如下圖,A 節點(包括其子節點)整個被移動到 D 節點下,由於 React 只會簡單的考慮同層級節點的位置變換,而對於不同層級的節點,只有創建和刪除操作。當根節點發現子節點中 A 消失了,就會直接銷毀 A;當 D 發現多了一個子節點 A,則會創建新的 A(包括子節點)作為其子節點。此時,React diff 的執行情況:create A -> create B -> create C -> delete A

由此可發現,當出現節點跨層級移動時,並不會出現想像中的移動操作,而是以 A 為根節點的樹被整個重新創建,這是一種影響 React 性能的操作,因此 React 官方建議不要進行 DOM 節點跨層級的操作

注意:在開發組件時,保持穩定的 DOM 結構會有助於性能的提升。例如,可以通過 CSS 隱藏或顯示節點,而不是真的移除或添加 DOM 節點。

component diff

React 是基於組件構建應用的,對於組件間的比較所採取的策略也是簡潔高效。

  • 如果是同一類型的組件,按照原策略繼續比較 virtual DOM tree。

  • 如果不是,則將該組件判斷為 dirty component,從而替換整個組件下的所有子節點。

  • 對於同一類型的組件,有可能其 Virtual DOM 沒有任何變化,如果能夠確切的知道這點那可以節省大量的 diff 運算時間,因此 React 允許用戶通過 shouldComponentUpdate() 來判斷該組件是否需要進行 diff。

如下圖,當 component D 改變為 component G 時,即使這兩個 component 結構相似,一旦 React 判斷 D 和 G 是不同類型的組件,就不會比較二者的結構,而是直接刪除 component D,重新創建 component G 以及其子節點。雖然當兩個 component 是不同類型但結構相似時,React diff 會影響性能,但正如 React 官方博客所言:不同類型的 component 是很少存在相似 DOM tree 的機會,因此這種極端因素很難在實現開發過程中造成重大影響的。

element diff

當節點處於同一層級時,React diff 提供了三種節點操作,分別為:INSERT_MARKUP(插入)、MOVE_EXISTING(移動)和 REMOVE_NODE(刪除)。

  • INSERT_MARKUP,新的 component 類型不在老集合里, 即是全新的節點,需要對新節點執行插入操作。

  • MOVE_EXISTING,在老集合有新 component 類型,且 element 是可更新的類型,generateComponentChildren 已調用 receiveComponent,這種情況下 prevChild=nextChild,就需要做移動操作,可以復用以前的 DOM 節點。

  • REMOVE_NODE,老 component 類型,在新集合里也有,但對應的 element 不同則不能直接復用和更新,需要執行刪除操作,或者老 component 不在新集合里的,也需要執行刪除操作。

function enqueueInsertMarkup(parentInst, markup, toIndex) { updateQueue.push({ parentInst: parentInst, parentNode: null, type: ReactMultiChildUpdateTypes.INSERT_MARKUP, markupIndex: markupQueue.push(markup) - 1, content: null, fromIndex: null, toIndex: toIndex, });}function enqueueMove(parentInst, fromIndex, toIndex) { updateQueue.push({ parentInst: parentInst, parentNode: null, type: ReactMultiChildUpdateTypes.MOVE_EXISTING, markupIndex: null, content: null, fromIndex: fromIndex, toIndex: toIndex, });}function enqueueRemove(parentInst, fromIndex) { updateQueue.push({ parentInst: parentInst, parentNode: null, type: ReactMultiChildUpdateTypes.REMOVE_NODE, markupIndex: null, content: null, fromIndex: fromIndex, toIndex: null, });}

如下圖,老集合中包含節點:A、B、C、D,更新後的新集合中包含節點:B、A、D、C,此時新老集合進行 diff 差異化對比,發現 B != A,則創建並插入 B 至新集合,刪除老集合 A;以此類推,創建並插入 A、D 和 C,刪除 B、C 和 D。

React 發現這類操作繁瑣冗餘,因為這些都是相同的節點,但由於位置發生變化,導致需要進行繁雜低效的刪除、創建操作,其實只要對這些節點進行位置移動即可。

針對這一現象,React 提出優化策略:允許開發者對同一層級的同組子節點,添加唯一 key 進行區分,雖然只是小小的改動,性能上卻發生了翻天覆地的變化!

新老集合所包含的節點,如下圖所示,新老集合進行 diff 差異化對比,通過 key 發現新老集合中的節點都是相同的節點,因此無需進行節點刪除和創建,只需要將老集合中節點的位置進行移動,更新為新集合中節點的位置,此時 React 給出的 diff 結果為:B、D 不做任何操作,A、C 進行移動操作,即可。

那麼,如此高效的 diff 到底是如何運作的呢?讓我們通過源碼進行詳細分析。

首先對新集合的節點進行循環遍歷,for (name in nextChildren),通過唯一 key 可以判斷新老集合中是否存在相同的節點,if (prevChild === nextChild),如果存在相同節點,則進行移動操作,但在移動前需要將當前節點在老集合中的位置與 lastIndex 進行比較,if (child._mountIndex < lastIndex),則進行節點移動操作,否則不執行該操作。這是一種順序優化手段,lastIndex 一直在更新,表示訪問過的節點在老集合中最右的位置(即最大的位置),如果新集合中當前訪問的節點比 lastIndex 大,說明當前訪問節點在老集合中就比上一個節點位置靠後,則該節點不會影響其他節點的位置,因此不用添加到差異隊列中,即不執行移動操作,只有當訪問的節點比 lastIndex 小時,才需要進行移動操作。

以上圖為例,可以更為清晰直觀的描述 diff 的差異對比過程:

  • 從新集合中取得 B,判斷老集合中存在相同節點 B,通過對比節點位置判斷是否進行移動操作,B 在老集合中的位置 B._mountIndex = 1,此時 lastIndex = 0,不滿足 child._mountIndex < lastIndex 的條件,因此不對 B 進行移動操作;更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),其中 prevChild._mountIndex 表示 B 在老集合中的位置,則 lastIndex = 1,並將 B 的位置更新為新集合中的位置prevChild._mountIndex = nextIndex,此時新集合中 B._mountIndex = 0,nextIndex++ 進入下一個節點的判斷。

  • 從新集合中取得 A,判斷老集合中存在相同節點 A,通過對比節點位置判斷是否進行移動操作,A 在老集合中的位置 A._mountIndex = 0,此時 lastIndex = 1,滿足 child._mountIndex < lastIndex的條件,因此對 A 進行移動操作enqueueMove(this, child._mountIndex, toIndex),其中 toIndex 其實就是 nextIndex,表示 A 需要移動到的位置;更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),則 lastIndex = 1,並將 A 的位置更新為新集合中的位置 prevChild._mountIndex = nextIndex,此時新集合中A._mountIndex = 1,nextIndex++ 進入下一個節點的判斷。

  • 從新集合中取得 D,判斷老集合中存在相同節點 D,通過對比節點位置判斷是否進行移動操作,D 在老集合中的位置 D._mountIndex = 3,此時 lastIndex = 1,不滿足 child._mountIndex < lastIndex的條件,因此不對 D 進行移動操作;更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),則 lastIndex = 3,並將 D 的位置更新為新集合中的位置 prevChild._mountIndex = nextIndex,此時新集合中D._mountIndex = 2,nextIndex++ 進入下一個節點的判斷。

  • 從新集合中取得 C,判斷老集合中存在相同節點 C,通過對比節點位置判斷是否進行移動操作,C 在老集合中的位置 C._mountIndex = 2,此時 lastIndex = 3,滿足 child._mountIndex < lastIndex 的條件,因此對 C 進行移動操作 enqueueMove(this, child._mountIndex, toIndex);更新 lastIndex = Math.max(prevChild._mountIndex, lastIndex),則 lastIndex = 3,並將 C 的位置更新為新集合中的位置 prevChild._mountIndex = nextIndex,此時新集合中 C._mountIndex = 3,nextIndex++ 進入下一個節點的判斷,由於 C 已經是最後一個節點,因此 diff 到此完成。

以上主要分析新老集合中存在相同節點但位置不同時,對節點進行位置移動的情況,如果新集合中有新加入的節點且老集合存在需要刪除的節點,那麼 React diff 又是如何對比運作的呢?

以下圖為例:

  • 從新集合中取得 B,判斷老集合中存在相同節點 B,由於 B 在老集合中的位置 B._mountIndex = 1,此時lastIndex = 0,因此不對 B 進行移動操作;更新 lastIndex = 1,並將 B 的位置更新為新集合中的位置B._mountIndex = 0,nextIndex++進入下一個節點的判斷。

  • 從新集合中取得 E,判斷老集合中不存在相同節點 E,則創建新節點 E;更新 lastIndex = 1,並將 E 的位置更新為新集合中的位置,nextIndex++進入下一個節點的判斷。

  • 從新集合中取得 C,判斷老集合中存在相同節點 C,由於 C 在老集合中的位置C._mountIndex = 2,lastIndex = 1,此時 C._mountIndex > lastIndex,因此不對 C 進行移動操作;更新 lastIndex = 2,並將 C 的位置更新為新集合中的位置,nextIndex++ 進入下一個節點的判斷。

  • 從新集合中取得 A,判斷老集合中存在相同節點 A,由於 A 在老集合中的位置A._mountIndex = 0,lastIndex = 2,此時 A._mountIndex < lastIndex,因此對 A 進行移動操作;更新 lastIndex = 2,並將 A 的位置更新為新集合中的位置,nextIndex++ 進入下一個節點的判斷。

  • 當完成新集合中所有節點 diff 時,最後還需要對老集合進行循環遍歷,判斷是否存在新集合中沒有但老集合中仍存在的節點,發現存在這樣的節點 D,因此刪除節點 D,到此 diff 全部完成。

_updateChildren: function(nextNestedChildrenElements, transaction, context) { var prevChildren = this._renderedChildren; var nextChildren = this._reconcilerUpdateChildren( prevChildren, nextNestedChildrenElements, transaction, context ); if (!nextChildren && !prevChildren) { return; } var name; var lastIndex = 0; var nextIndex = 0; for (name in nextChildren) { if (!nextChildren.hasOwnProperty(name)) { continue; } var prevChild = prevChildren && prevChildren[name]; var nextChild = nextChildren[name]; if (prevChild === nextChild) { // 移動節點 this.moveChild(prevChild, nextIndex, lastIndex); lastIndex = Math.max(prevChild._mountIndex, lastIndex); prevChild._mountIndex = nextIndex; } else { if (prevChild) { lastIndex = Math.max(prevChild._mountIndex, lastIndex); // 刪除節點 this._unmountChild(prevChild); } // 初始化並創建節點 this._mountChildAtIndex( nextChild, nextIndex, transaction, context ); } nextIndex++; } for (name in prevChildren) { if (prevChildren.hasOwnProperty(name) && !(nextChildren && nextChildren.hasOwnProperty(name))) { this._unmountChild(prevChildren[name]); } } this._renderedChildren = nextChildren;},// 移動節點moveChild: function(child, toIndex, lastIndex) { if (child._mountIndex < lastIndex) { this.prepareToManageChildren(); enqueueMove(this, child._mountIndex, toIndex); }},// 創建節點createChild: function(child, mountImage) { this.prepareToManageChildren(); enqueueInsertMarkup(this, mountImage, child._mountIndex);},// 刪除節點removeChild: function(child) { this.prepareToManageChildren(); enqueueRemove(this, child._mountIndex);},_unmountChild: function(child) { this.removeChild(child); child._mountIndex = null;},_mountChildAtIndex: function( child, index, transaction, context) { var mountImage = ReactReconciler.mountComponent( child, transaction, this, this._nativeContainerInfo, context ); child._mountIndex = index; this.createChild(child, mountImage);},

當然,React diff 還是存在些許不足與待優化的地方,如下圖所示,若新集合的節點更新為:D、A、B、C,與老集合對比只有 D 節點移動,而 A、B、C 仍然保持原有的順序,理論上 diff 應該只需對 D 執行移動操作,然而由於 D 在老集合的位置是最大的,導致其他節點的 _mountIndex < lastIndex,造成 D 沒有執行移動操作,而是 A、B、C 全部移動到 D 節點後面的現象。

在此,讀者們可以討論思考:如何優化上述問題?

建議:在開發過程中,盡量減少類似將最後一個節點移動到列表首部的操作,當節點數量過大或更新操作過於頻繁時,在一定程度上會影響 React 的渲染性能。

總結

  • React 通過制定大膽的 diff 策略,將 O(n3) 複雜度的問題轉換成 O(n) 複雜度的問題;

  • React 通過分層求異的策略,對 tree diff 進行演算法優化;

  • React 通過相同類生成相似樹形結構,不同類生成不同樹形結構的策略,對 component diff 進行演算法優化;

  • React 通過設置唯一 key的策略,對 element diff 進行演算法優化;

  • 建議,在開發組件時,保持穩定的 DOM 結構會有助於性能的提升;

  • 建議,在開發過程中,盡量減少類似將最後一個節點移動到列表首部的操作,當節點數量過大或更新操作過於頻繁時,在一定程度上會影響 React 的渲染性能。

參考資料

  • A Survey on Tree Edit Distance and Related Problems

  • Reconciliation

如果本文能夠為你解決些許關於 React diff 演算法的疑惑,請點個贊吧!

推薦閱讀:

Vue2技術棧歸納與精粹
2.2 webpack
React把PropTypes放到一個獨立包
Rx 的編程方式(一)

TAG:JavaScript | React |