虛拟dom及diff算法解析

什麼是DOM

文檔對象模型（DOM）是一個獨立于語言的，用于操作XML和HTML文檔的接口程式（API）。在浏覽器中，主要用來與HTML文檔打交道，同樣也用在web程式中擷取XML文檔，并使用DOM API用來通路文檔中的資料。

浏覽器HTML渲染過程

渲染引擎在獲得文檔内容之後，主要要進行以下的過程：

解析HTML以建構DOM樹 -> 建構render樹 -> 布局render樹 -> 繪制render樹

谷歌developer上的版本：

位元組 -> 字元 -> TOKEN -> 節點 -> 對象模型

重點說一下TOKEN，所謂TOKEN化，就是浏覽器将字元串轉成符合W3C HTML5标準的各種标簽，例如 < html >、< body >等标簽，每個标簽都具有特殊含義和規則。

1. 浏覽器将HTML解析成一個DOM樹，DOM樹的建構過程是一個深度周遊的過程，也就是說目前節點的所有子節點夠構件号之後才會去建構目前節點的下一個兄弟節點。
2. 将CSS解析成 CSS 對象模型，DOM 和CSSOM是獨立的資料結構。

為頁面上的任何對象計算最後一組樣式時，浏覽器都會從先從适用于該節點的最通用規則開始（如果某個節點是body的子元素，那就應用所有body的樣式），然後通過應用更具體的規則（即“向下級聯”）以遞歸的方式适用子節點的樣式優化顯示。

此外，每個浏覽器都會提供一組預設的樣式（User Agent樣式），我們自定義的樣式隻是替換這些預設樣式

1. 根據DOM樹和CSSOM來建構 Rendering Tree。

浏覽器大緻要做下列工作：

1. 從DOM樹的根節點開始周遊每個可見節點
   • 某些節點不可見（腳本标記，元标記）他們不會展現在渲染輸出中，會被忽略
   • 某些通過CSS隐藏的節點，在渲染書中也會被忽略（display:none）
2. 對于每個可見節點，為其找到适配的CSSOM規則并應用。
3. Emit可見的節點，連同其内容和計算的樣式

1. 有了Render Tree，浏覽器就知道網頁上有哪些節點，各個節點的CSS定義以及他們的從屬關系，下一步就是根據目前視窗的大小計算每個節點在螢幕中的位置，稱為layout。
2. 周遊 Render 樹，使用上一步計算出的每個節點的絕對像素繪制每個節點。

CSS和JavaScript的阻塞渲染

CSS和JavaScript檔案理論上都會阻塞頁面的渲染,也就意味着在CSS檔案和JavaScript檔案都下載下傳并處理完畢之前，浏覽器不會渲染任何内容。

為了避免CSS的阻塞，需要将它盡快的下載下傳到用戶端，以便縮短數次渲染的時間，對于隻有特定條件下才會使用的CSS樣式，可以使用CSS的“媒體類型”和“媒體查詢”來解決：

<link href="style.css" rel="stylesheet">//會阻塞
<link href="print.css" rel="stylesheet" media="print">
<link href="other.css" rel="stylesheet" media="(min-width: 40em)">
           

由于JavaScript可以修改頁面的結構和内容，是以在JavaScript處理結束之前，浏覽器并不能完全确定頁面的形态。為了提高渲染性能，可以讓JavaScript異步執行，并去除關鍵渲染路徑中不必要的JavaScript。

我們的腳本在文檔的何處插入，就在何處執行。當 HTML 解析器遇到一個 script 标記時，它會暫停建構 DOM，将控制權移交給 JavaScript 引擎；等 JavaScript 引擎運作完畢，浏覽器會從中斷的地方恢複 DOM 建構

這也就意味着腳本找不到網頁中任何在其後面的元素。

預設情況下，所有JavaScript都會組織解析器，如果引入的JavaScript是外部檔案，那浏覽器必須停下來，等待從磁盤、緩存或遠端伺服器擷取腳本，這就可能給關鍵渲染路徑增加數十值數千毫秒的延遲。

為了避免上述性能缺失，我們可以手動聲明腳本不需要在引入位置執行，也就是把腳本标記為異步：

DOM樹與渲染樹（Render Tree）

DOM樹與渲染樹存在差別

DOM 樹表示頁面結構，渲染樹表示DOM節點如何顯示

DOM樹種每一個需要顯示的節點在渲染樹中至少勳在一個對應的節點，這不包括哪些隐藏的節點，如：display：none的節點。

網絡上廣泛流傳的一張圖檔如下所示：

重繪與重排

當 DOM 的變化引起了幾何屬性（寬和高），浏覽器需要重新計算元素的集合屬性，同樣其他元素的集合屬性和位置也會是以受到影響。浏覽器會使渲染樹中的部分失效，并重新構造渲染樹。這個過程稱為重排（reflow）。完成重排後，浏覽器會重新繪制受影響的部分到螢幕中，該過程稱為重繪（repaint）。

并不是所有的 DOM 變化都會影響幾何屬性，比如背景顔色的改變就不會影響長寬，這種情況下就隻會發生一次重繪（并不需要重排），因為元素的布局沒有改變。重排和重繪的操作對性能的影響很大，這點會在 DOM 的操作的性能分析中詳細講到。

重排發生的場景如下：

• 添加或删除可見的 DOM 元素
• 元素位置改變
• 元素尺寸改變（包括：外邊距，内邊距，邊框，寬度，高度等幾何屬性）
• 内容的改變
• 頁面渲染器的初始化
• 浏覽器視窗尺寸變化也會引起重排

事件委托

頁面中的事件通常是在onload（或者DOMContentReady）時綁定到相應的元素上，這對于富互動應用的網頁來說，在onload時時間綁定會占用非常多的處理時間，并且浏覽器需要跟蹤每個事件處理器，就需要占用更多的記憶體。但是在日常使用中，并不是所有的事件都會被使用者觸發，是以這其中就有很多不必要的性能開銷。

是以就出現了事件委托。原理是：事件在被觸發之後，會逐級冒泡并能被父級元素捕捉到。這樣就隻需要在父級元素上綁定一份處理器，就可以處理所有子元素觸發的事件。典型例子就是每個LI中的事件就可以綁定在UL上，這樣避免了重複綁定。

DOM 标準裡每個事件都要經曆的三個階段：

• 捕獲
• 到達目标

• 冒泡

  IE 不支援捕獲

DOM操作性能分析

天生就慢

由于對 DOM 樹的操作天生就慢（具體底層原因我也不太清楚，可能目前浏覽器渲染 DOM 相比執行js就是慢很多），是以一般會采用以下幾種方法來優化DOM操作的性能

最小化重繪和重排

重繪和重排會涉及到大量的DOM的改變和渲染，是以代價昂貴。是以應該盡量合并對DOM的修改，也就是最後能使用盡可能少的步驟來處理想要的DOM更改。對于批量修改DOM，有以下步驟：

1. 使元素脫離文檔流

使元素脫離文檔流又有如下幾個方法：

• 隐藏元素，應用修改，重新顯示

  先display: none, 然後再display: block

• 使文檔片段在目前DOM之外建構子樹，再把它拷貝回文檔
• 将原始元素拷貝到一個脫離文檔的節點中，修改副本，完成後再替換原始元素

1. 對其應用多重改變
2. 把元素帶回文檔中

緩存布局資訊

為了更新布局資訊而去查詢布局資訊時，比如擷取偏移量等，浏覽器為了傳回最新值，會重新整理隊列并應用所有變更。而每次查詢布局資訊都會有代價，是以更好的方法是減少布局資訊的擷取次數，也就是把它指派給局部變量，然後操作局部變量。

//低效的
myElement.style.left = 1 + myElement.offsetLeft + 'px';
myElement.style.top = 1 + myElement.offsetTop + 'px';
if (myElement.offsetLeft >= 500) {
	stopAnimation();
}
//利用局部變量
current++;
myElement.style.left = current + 'px';
myElement.style.top = current + 'px';
if (myElement.offsetLeft >= 500) {
	stopAnimation();
}
           

讓元素脫離動畫流

當使用展開、折疊來顯示和隐藏部分頁面時，通常會将展開區域之外的畫面整體推動，這對浏覽器來說，就需要重排所有移動的内容，極大影響頁面渲染效率。可以使用以下步驟來避免上述情況：

• 使用絕對位置定位頁面上的需要動的元素，使其脫離文檔流。
• 當元素動起來時，會臨時覆寫部分其他的頁面，這隻導緻一小部分頁面的重繪,并不會産生大面積重排。
• 當動畫結束時恢複定位

在IE中盡量避免使用：hover

IE中大量使用

:hover

會極大地影響相應速度。

什麼是虛拟DOM

經過上面的叙述，我們了解到渲染頁面的開銷很大，更令人頭痛的是當頁面産生變化需要更新時，同樣也會産生很大的開銷。是以才有了上述基于幾種原生的減少頁面變化時重排的方法。虛拟DOM 是從另一份角度解決這個問題。

渲染方式的變化

前後端不分離

前後端不分離在前後端還不分離的時代，前端其實不需要關心頁面狀态的改變。某個按鈕的點選或者form的送出都會使整個頁面重新整理，後端去處理使用者的操作，并重新生成一套新的前端來交給浏覽器渲染。

There is no change. The universe is immutable.

開始前後端分離

初代的前端架構提供了可以把DOM樹和MODEL分離的基礎，并可以記錄MODEL的變化，但是将MODEL的變化應用到UI顯示上還是需要開發者自己來。

I have no idea what I should re-render. You figure it out.

資料綁定

将data model 和 DOM 進行綁定，能夠監聽data model 的改變，并且知道該如何更新到DOM。

I know exactly what changed and what should be re-rendered because I control your models and views.

AngularJS：Dirty Checking

AngularJs 在渲染資料的過程中為每個資料添加了一個監聽，這樣Angular 會去檢查所有監聽器去判斷資料是否改變，如果改變就對其進行重新渲染。這也是資料綁定的其中一種形式。

I have no idea what changed, so I’ll just check everything that may need updating.

React: Virtual DOM

當頁面渲染之後，React會保留一份虛拟DOM在記憶體裡。

當data model 發生改變之後，React會重新渲染一份新的虛拟DOM與之前保留的虛拟DOM進行比較，并針對改變的部分進行重新渲染。

虛拟DOM的優點是你不用關心變化，因為整個DOM都會重新虛拟渲染一遍，并利用DOM diff算法來最小化地進行高成本的DOM操作。當然，虛拟DOM和資料綁定并不沖突,Vue2.0之後就引入了虛拟DOM，同時它還使用了資料綁定。

I have no idea what changed so I’ll just re-render everything and see what’s different now.

前端開發中對于變化的監聽一直是主要問題，目前的這些前端架構也就是為了去解決這些問題。

虛拟DOM Diff算法

傳統Diff算法的算法複雜度達到了O(n^3)，其中n是樹中節點的總數，這個算法複雜度是一個對性能很不友好的複雜度。如果采用傳統Diff算法，即使JavaScript的執行速度相比DOM操作很快，那對性能的改善肯定也有限。React所采用的是優化後的Diff算法，把算法複雜度降到了O(n)，這樣就能滿足一般情況下的性能要求。之是以能把複雜度如此多的複雜度，是因為React制定了大膽的Diff政策。

• WEB UI中的DOM節點跨層級的移動操作特别少，是以在比較差異的時候可以隻比較統計的節點。
• 擁有相同類的兩個元件将會生成相似的樹形結構，擁有不同類的兩個元件将會生成不同的樹形結構。

• 針對同一層級的一組節點，可以通過唯一id進行區分。

  React利用上述的三點政策分别對Tree Diff、Component Diff以及Element Diff進行了優化。

Diff算法首先需要對新舊兩棵樹進行深度優先周遊，對每個節點進行唯一的标記。在深度優先周遊的時候，每周遊到一個節點就把該節點和新的樹進行對比，如果有差異的話就記錄在一個對象裡面。新舊樹之間的差異包括：

• 替換掉原來的節點；
• 移動、删除、新增子節點；
• 修改節點屬性或綁定的事件；
• 對文本節點内容的修改等。

基于政策一，React的Tree Diff将隻會對相同顔色方框内的DOM節點進行比較，即同一父節點下的所有子節點。當發現節點已經不存在時，則該節點及其子節點會被完全删除掉，不會用于進一步的比較。這樣隻需要對樹進行一次周遊，便能完成整個 DOM 樹的比較。這也就意味着如果出現了DOM節點的跨層級移動，React的Diff算法會重新進行渲染跨層級的節點，這對性能具有一定的影響。

React是基于元件建構應用的，基于政策二React會直接判斷新元件和舊元件是否為同一類，如果屬于同一類元件則進行Tree Diff；如果判斷不是同一類元件，則判定該元件為Dirty 元件，進而替換整個元件的所有子節點。如圖6所示，當元件D群組件G被判定為不同類元件之後。會直接删除元件D，重新建立元件G及其子節點。

政策三主要應對節點的移動隻是在同級中重新排序，如果也對其進行重新渲染的話，就會有一些不必要的性能損失。這就需要使用上文提到的同一層節點所具有的唯一id，對新的同一層的所有節點與舊的節點應用清單對比算法來比較差異。這個問題可以抽象成字元串的最小編輯距離問題，其時間複雜度為O(m*n)，但是通常在應用中不需要真的達到最小操作，一般會使用優化後時間複雜度為O(max(m, n))的算法。

經過上述步驟，我們會記錄下所有需要更改的節點，這些節點會變成一個DOM更新檔。我們就可以根據不同類型的差異将這些更新檔更行到相應的對節點上。

小結

随着前端的開發越來越向富互動方面發展，肯定會不斷地推動前端開發中對性能的優化。本文所介紹的虛拟DOM算法在浏覽器渲染上的應用使得DOM的渲染效率相比之前有了極大地提升，并且能夠讓開發人員能夠專著與業務需求，而不用考慮該如何去處理DOM的變化。

在看到虛拟DOM的優勢的同時，我們也要關注其存在的問題。由于其自身特性，需要時刻儲存一份虛拟的DOM樹在記憶體中，對某些大型頁面應用來說這将會對性能造成極大的影響。又由于其針對每次的DOM更新都需要重新渲染一遍DOM，雖然相比傳統方式已經有了很大的性能提升，但是其還是不足以應對高重新整理率的頁面應用。