淺析React Diff 與 Fiber

前言

React 已從15升級為了16，其中Diff算法的優化和改進是最大的特性。 文章將從React 15的Diff算法說起，延展到React Fiber。

React Diff

傳統 diff 算法 通過循環遞歸對節點進行依次對比。

缺點顯而易見：效率低下，算法複雜度達到 O(n^3)。 React Diff算法將 O(n^3) 複雜度的問題轉換成 O(n) 複雜度的問題。

Diff 策略

1. Web UI 中 DOM 節點跨層級的移動操作特別少，可以忽略不計。
2. 擁有相同類的兩個組件將會生成相似的樹形結構，擁有不同類的兩個組件將會生成不同的樹形結構。
3. 對於同一層級的一組子節點，它們可以通過唯一 id 進行區分。

基於以上三個前提策略，React 分別對 tree diff、component diff 以及 element diff 進行算法優化。

Tree Diff

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

由於 DOM 節點跨層級的移動操作少到可以忽略不計，針對這一現象，React 通過 updateDepth 對 Virtual DOM 樹進行層級控制，只會對相同顏色方框內的 DOM 節點進行比較，即同一個父節點下的所有子節點。當發現節點已經不存在，則該節點及其子節點會被完全刪除掉，不會用於進一步的比較。這樣只需要對樹進行一次遍歷，便能完成整個 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，這種情況下 preChild=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 提出優化策略：

允許開發者對同一層級的同組子節點，添加唯一 key 進行區分

雖然只是小小的改動，性能上卻發生了翻天覆地的變化。

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

執行邏輯：

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

React Fiber

原由

眾所周知，JavaScript在瀏覽器的主線程上運行，通常樣式計算、佈局以及頁面繪製會一起運行。如果JavaScript運行時間過長，就會阻塞這些其他工作，可能導致掉幀。

React運行時存在3種實例

<code>DOM 真實DOM節點
-------
Instances React維護的Virtual DOM Tree node
-------
Elements 描述UI長什麼樣子（type, props）/<code>

Instances是根據Elements創建的，對組件及DOM節點的抽象表示，Virtual DOM Tree維護了組件狀態以及組件與DOM樹的關係

在首次渲染過程中構建出Virtual DOM Tree，後續需要更新時（setState()），diff Virtual DOM Tree得到DOM change，並把DOM change應用（patch）到DOM樹。

自頂向下的遞歸mount/update，無法中斷（持續佔用主線程），這樣主線程上的佈局、動畫等週期性任務以及交互響應就無法立即得到處理，影響體驗。

同時也造成了React在一些響應體驗要求較高的場景不適用，比如動畫，佈局和手勢等。

由此誕生了Fiber。

優化

Fiber解決這個問題的思路是增量更新。

把渲染/更新過程（遞歸diff）拆分成一系列小任務，每次檢查樹上的一小部分，做完看是否還有時間繼續下一個任務，有的話繼續，沒有的話把自己掛起，主線程不忙的時候再繼續。

Fiber Tree

增量更新需要更多的上下文信息，之前的Virtual DOM Tree顯然難以滿足，所以擴展出了fiber tree（即Fiber上下文的Virtual DOM Tree），更新過程就是根據輸入數據以及現有的fiber tree構造出新的fiber tree（workInProgress tree）。因此，Instance層新增了這些實例：

<code>DOM
    真實DOM節點
-------
effect
    每個workInProgress tree節點上都有一個effect list
    用來存放diff結果
    當前節點更新完畢會向上merge effect list（queue收集diff結果）
- - - -
workInProgress
    workInProgress tree是reconcile過程中從fiber tree建立的當前進度快照，用於斷點恢復
- - - -
fiber
    fiber tree與Virtual DOM Tree類似，用來描述增量更新所需的上下文信息 

-------
Elements
    描述UI長什麼樣子（type, props）/<code>

fiber tree實際上是個單鏈表（Singly Linked List）樹結構,結構如下：

<code>{
stateNode, // 狀態節點
child,  // 子節點
return,  // 表示當前節點處理完畢後，應該向誰提交自己的成果（effect list）
sibling,    // 兄弟節點
...
}/<code>

拆分

把渲染/更新過程分為2個階段：

<code>1. diff ~ render/reconciliation
2. patch ~ commit/<code>

• diff階段(可中斷)的實際工作是對比prevInstance和nextInstance的狀態，找出差異及其對應的DOM change。
  diff本質上是一些計算（遍歷、比較），是可拆分的（算一半待會兒接著算）
• patch階段（不可中斷）把本次更新中的所有DOM change應用到DOM樹，是一連串的DOM操作。
  該階段由於兩方面的原因並不會進行拆分 1. 可能造成DOM實際狀態與維護的內部狀態不一致，另外還會影響體驗。 2. DOM更新的耗時比起diff及生命週期函數耗時可忽略不計

render/reconciliation

以fiber tree為基礎，把每個fiber作為一個工作單元，自頂向下逐節點構造workInProgress tree（構建中的新fiber tree）

具體過程如下：

1. 如果當前節點不需要更新，直接把子節點clone過來，跳到步驟5；需要更新則打上tag
2. 更新當前節點狀態（props, state, context等）
3. 調用shouldComponentUpdate()，false的話，跳到步驟5
4. 調用render()獲得新的子節點，併為子節點創建fiber（創建過程會盡量複用現有fiber，子節點增刪也發生在這裡）
5. 如果沒有產生child fiber，該工作單元結束，把effect list歸併到return，並把當前節點的sibling作為下一個工作單元；否則把child作為下一個工作單元
6. 如果沒有剩餘可用時間了，等到下一次主線程空閒時才開始下一個工作單元；否則，立即開始做
7. 如果沒有下一個工作單元了（回到了workInProgress tree的根節點），render/reconciliation階段結束，進入pendingCommit狀態

實際上是1-6的工作循環，7是出口，工作循環每次只做一件事，做完看要不要喘口氣。

通過每個節點更新結束時向上歸併effect list來收集任務結果，reconciliation結束後，根節點的effect list裡記錄了包括DOM change在內的所有side effect

所以，構建workInProgress tree的過程就是diff的過程，通過requestIdleCallback來調度執行一組任務，每完成一個任務後回來看看有沒有插隊的（更緊急的），每完成一組任務，把時間控制權交還給主線程，直到下一次requestIdleCallback回調再繼續構建workInProgress tree

commit

該階段是一口氣直接做完（同步執行），不被控制和中止，這個階段的實際工作量是比較大的，所以儘量不要在後3個生命週期函數里乾重活兒

• 處理effect list（包括3種處理：更新DOM樹、調用組件生命週期函數以及更新ref等內部狀態）
• 該階段結束時，所有更新都commit到DOM樹上了。

調度任務

requestIdleCallback：調度方法，作用類似於通知主線程在不忙的時候告知我，我有幾個不太著急的事情要做。

但只是希望通過調度做到流暢體驗，並不能絕對保證流暢（具體還需看需渲染內容的耗時）

調度任務具體分為：

• 工作循環：每個工作單元結束檢查是否還有時間做下一個，沒時間了就先“掛起”
• 優先級機制：用來處理突發事件與優化次序，用來動態調整任務調度，是工作循環的輔助機制，最先做最重要的事情

調度最重要的兩種狀態： - 中斷：檢查當前正在處理的工作單元，保存當前成果（firstEffect,lastEffect），修改tag標記一下，迅速收尾並再開一個requestIdleCallback，下次有機會再做。 - 斷點恢復：下次再處理到該工作單元時，看tag是被打斷的任務，接著做未完成的部分或者重做。

無論是時間用盡“自然”中斷，還是被高優任務粗暴打斷，對中斷機制來說都一樣。

生命週期

生命週期函數被分為2個階段

<code>// render/reconciliation階段
componentWillMount
componentWillReceiveProps
shouldComponentUpdate
componentWillUpdate

// commit階段
componentDidMount 

componentDidUpdate
componentWillUnmount/<code>

render/reconciliation階段的生命週期函數可能會被多次調用，默認以低優先級執行，被高優先級任務打斷的話，稍後重新執行。

小結

關鍵特性

• 增量渲染（把渲染任務拆分成塊，勻到多幀）
• 更新時能夠暫停，終止，複用渲染任務
• 給不同類型的更新賦予優先級
• 併發方面新的基礎能力

增量渲染用來解決掉幀的問題，渲染任務拆分之後，每次只做一小段，做完一段就把時間控制權交還給主線程，而不像之前長時間佔用。這種策略叫做cooperative scheduling（合作式調度），是操作系統的3種任務調度策略之一。

源碼變化

• React 16 在源碼結構上產生了很大變化 - mountComponent/updateComponent()被拆分重組成了beginWork(),completeWork(),commitWork()
• 在Fiber體系下DOM節點抽象用ReactDOMFiberComponent表示,ReactDOMComponent被取消；組件用ReactFiberClassComponent表示，ReactCompositeComponent被替代。
• Fiber體系的核心機制是負責任務調度的ReactFiberScheduler，相當於之前的ReactReconciler - Virtual DOM Tree變成了Fiber Tree，由自上而下的簡單樹結構變成了基於單鏈表的樹結構，維護的節點關係更多一些。

Virtual DOM Tree 與 Fiber Tree對比圖

演進

從React 15 到 React 16 ，對於DOM節點的渲染實現了3個方面的優化：

• React通過virtual DOM減少了實際改動真實DOM的開銷
• 通過Diff算法減少了實際渲染的頻次與變動範圍
• 通過Fiber重構來改變這種不可控的現狀，進一步提升交互體驗，在用戶態單線程條件下實現類似多進程的系統級別調度。

如果文章能幫助你理解一些前端知識點，請收藏、分享和關注本專欄，謝謝。

閱讀更多 路演前端 的文章

關鍵字: 算法 淺析 如上圖