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

01-25

目前，前端領域中 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 策略

Web UI 中 DOM 節點跨層級的移動操作特別少，可以忽略不計。
擁有相同類的兩個組件將會生成相似的樹形結構，擁有不同類的兩個組件將會生成不同的樹形結構。
對於同一層級的一組子節點，它們可以通過唯一 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 不在新集合里的，也需要執行刪除操作。

如下圖，老集合中包含節點：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 演算法的疑惑，請點個贊吧！

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

前言