在Microsoft Edge中實現DOM樹

前言

DOM是Web平台編程模型的基礎，其設計和性能直接影響著瀏覽器管道(Pipeline)的模型，然而，DOM的歷史演化卻遠不是一個簡單的事情。

在過去三年中，微軟的安全專家們早已經開始在Microsoft Edge上對DOM進行了重構，這次重構的主要目標就是要搭建一個更加先進的架構，提供更好的實際操作性能和更加簡潔的操作。在這篇文章中，微軟的安全專家們將引導我們來了解Internet Explorer和Microsoft Edge中DOM的歷史演變過程，以及他們在這幾年對DOM樹先進化演變的影響。現在我們已經能看到新的DOM架構對Windows 10 Creators Update性能大幅提升的幫助：

安全專家們認為真正的DOM架構應該是幾個子系統的相互協調與合作，比如在Microsoft Edge中，就包括JS中的事件綁定，事件捕獲，事件編輯，拼寫檢查，HTML屬性，CSSOM，文本設置和其他所有相關的功能。在這些子系統中，DOM樹正位於中心。

由上圖可以看出，DOM真的是構成Web編程模型的幾個子系統的協調。但這只是DOM非常表面的東西，真正的一些內部細節，還要從DOM的歷史開始說起。

Internet Explorer DOM樹的歷史

如今的網路開發人員一提起DOM，就通常會想到一棵看起來像這樣結構的樹：

然而，現實操作卻並不是像我們想的這麼簡單，比如，Internet Explorer的DOM實現就相當的複雜。

簡單來說，Internet Explorer的DOM就是為了滿足90年代的網頁設計的，當時設計原始數據結構時，Web主要是一個文檔查看器，頂多包含幾個動畫GIF和幾幅圖像。因此，DOM的演算法和數據結構更接近於Microsoft Word這樣的文檔查看器。回想早期的網路，因為JavaScript不允許腳本化網頁，所以我們所了解的DOM樹根本就不存在。當是，由於文本是主要的實現手段，所以DOM的內部設計都是圍繞快速，高效的文本來進行存儲和操作的。WYSIWYG富文本編輯器就是當是的產物，專門用於字元插入和有限的格式化。

以文本為中心的設計

作為以文本為中心的設計結果，DOM的原理結構就是為文本存儲做準備的，這是一個複雜的文本數組系統，可以通過最少或在沒有內存分配的情況下進行高效拆分和連接。存儲功能可以將文本和標籤表示為線性進程，可由全局索引或字元位置（CP）定址。在給定的CP中插入文本是非常高效的，並且通過高效的「拼接」操作集中複製或粘貼一系列文本。下圖就清楚的表明如何將包含「hello world」的簡單標記載入到文本存儲中，以及如何為每個字元和標籤分配CP。

為了存儲非文本數據，例如，格式化和分組信息，另一組對象的存儲就必須單獨維護，比如，樹位置（TreePos對象）的雙向鏈接列表。 TreePos對象是HTML源標記中的標籤語義，每個邏輯元素由開始和結束TreePos表示。這種線性結構使得在深度優先時，可以很快的遍歷整個DOM樹，幾乎每個DOM都需要搜索API，CSS以及布局演算法。之後，安全專家們將TreePos對象擴展到另外兩種「位置」：TreeDataPos（用於指示文本的佔位符）和PointerPos（用於指示插入符號，範圍邊界點，如生成的內容節點）。

每個TreePos對象還包括一個CP對象，它作為標籤的全局序數索引（對於像legacy document.all API這樣的東西有用）。從TreePos進入文本存儲時要用到CP，通過比較節點順序，甚至減去CP索引來查找文本的長度。

為了將這些節點整合在一起，TreeNode將會把它們綁定在一起，並建立了JavaScript DOM所期望的「樹」的層次，如下所示。

增加複雜層次

原有的這些CP基礎造成了DOM極其複雜，為了使整個系統能高效的運行，CP必須是最新的。因此，在每次DOM操作之後，例如輸入文本，複製或粘貼，DOM API操作，甚至點擊頁面在DOM中設置插入點都可以更新CP。最初，DOM操作主要由HTML解析器或用戶操作驅動，所以CP始終保持最新的模型是完全合理的。但是隨著JavaScript和DHTML的興起，這些操作變得越來越普遍和頻繁。

為了保持原來的更新速度，DOM添加了新的結構並且伸展樹(SplayTree)也隨之產生，伸展樹是在TreePos對象上添加了一系列重疊的樹連接。首先這些複雜結構的增加提高了DOM的性能，可以用O（log n）速度實現全局CP更新。然而，伸展樹實際上僅針對重複的本地搜索進行優化。

另一個在設計中出現的現象就是前面提到的複製或粘貼的「拼接」操作被擴展到處理所有的樹突變中。核心的拼接功能分三步進行，如下圖所示。

在步驟1中，拼接將通過從操作開始到操作結束遍歷樹形位置來記錄拼接信息。然後創建一個拼接記錄，其中包含此操作的命令指令。

在步驟2中，與該操作相關聯的所有節點，即，TreeNode和TreePos對象會從樹中刪除。要注意的是，在IE DOM樹中，TreeNode / TreePos對象與腳本引用的Element對象不同，以便於重疊標籤，因此刪除它們不是從功能方面考慮的。

在步驟3中，使用拼接記錄來重新創建目標位置中的新對象。例如，為了完成一個appendChild DOM操作，splice創建了一個圍繞節點的範圍（從TreeNode開始到TreePos結尾），將原來位置的編輯範圍經過拼接，創建了新的節點來表示節點及其子節點的新位置。大家可以想像一下，這樣一來雖然創造了很多內存分配，但演算法的速度也降低了很多。

原來的DOM沒有經過封裝

以上只是Internet Explorer DOM複雜性的幾個例子，還有就是原來的DOM沒有經過封裝，所以從Parser一直到Display系統的代碼都有CP / TreePos依賴關係，這就需要很多dev-years來處理。

由於複雜性很容易引起運行錯誤，而DOM代碼庫又對代碼的可靠性非常。所以，據不完全統計，從IE7到IE11，大約有28％的IE可靠性錯誤來源於核心DOM組件的代碼。而且這種複雜性也直接削弱了IE的靈活性，所以HTML5的每個新功能的改變都要付出很大的成本。

在Microsoft Edge中對DOM樹進行改造

2015年Spartan項目的推出，讓微軟有了改造DOM的機會。Spartan項目開始的第一步就是刪除舊代碼和舊技術。從vestige開始，如docmodes和條件注釋，專家們開始了大量的重構工作，其中最關鍵的目標就是DOM的核心樹。

我們知道原有的以文本為中心的模式不再適用於新的思路，我們需要的是一個真正的內部的DOM樹，以滿足現代DOM API的需求。為此，我們需要解除複雜的層次，來處理以前幾乎不可能的性能調整和相關係統協調。所以在對DOM樹進行重新封裝時，我們就要避免在核心數據結構上創建跨組件依賴，最終所有這些努力都將形成一個新的DOM樹。

為了儘可能平穩地過渡到最新的DOM並避免在改造結束時新的DOM樹所造成的使用混亂，專家們分三個階段將現有的代碼轉換到原來的狀態。

改造的第一階段定義了樹的組件邊界與對應的API協議，微軟的專家們選擇將API設計為在節點上運行的一組「讀取器」和「寫入器」功能，而不是像以下的API：

parent.appendChild(child);

element.nextSibling;

新的的API看起來如下：

TreeWriter::AppendChild(parent, child);

TreeReader::GetNextSibling(element);

在這個新的API設計中，樹的對象只是API中的身份，允許更強大的協議和表達細節，在第3階段這些將被證明是非常有用的。

第二階段是將所有依賴於原來樹內部的代碼遷移到新建立的組件邊界API中，在遷移期間，樹API的實現將繼續由傳統結構提供支持。第二階段的工作花費的時間是最多的，總共花了幾年的時間來老樹結構的封裝樹。

在第三階段，為了讓所有外部代碼也使用新的樹組件邊界API，專家們要開始重構和替換核心數據結構。為此，專家們整合了對象，例如，單獨的TreePos，TreeNode和Element對象，同時刪除了伸展樹、拼接功能、PointerPos對象的概念以及文本存儲功能。只有這樣，我們才能徹底擺脫原來CP的代碼。

新的樹結構簡單直觀，它使用了四個指針而不是通常的五個，專家們可以隱藏最後一個指針的優化TreeReader API，而不改變單個調用。重新布置過的樹是相當高效的，大家甚至可以在公共DOM API上看到CPU性能的一些改進：

使用新的DOM樹，可靠性也得到顯著改善，IE可靠性錯誤也從28％下降到10％左右，同時還讓減少調試時間減少了很多。

對DOM樹其他子系統的進一步優化

新的DOM樹API是由一個簡潔高效的樹提供支持，現在我們將注意力轉移到構成DOM的其他子系統上，其目的就是為了提高子系統內的高效運行以及它們之間高效通信：

例如，最慢的DOM API（即使在DOM樹工作之後）原來也是querySelectorAll。這是一個通用的搜索API，並使用選擇器引擎來搜索DOM中的特定元素。由於許多搜索都把特定元素的屬性作為搜索標準，例如，元素的ID或其類別標識符。一旦搜索代碼進入屬性子系統，與新的DOM樹處理完全的子系統，處理搜索的效率非常的慢。

對於屬性子系統，專家們簡化了元素內容屬性的存儲機制。在Web的早期階段，DOM屬性的一個很好的例子就是colspan屬性，在用IE瀏覽器製作預覽網頁的時候,如果表格使用了colspan屬性(列數不同,有合併的列),表格的自動寬度會受到很大的影響,以至於錯位混亂：

Total:

$12.34

colspan對瀏覽器具有語義意義，因此必須進行解析。鑒於頁面不是動態的，那麼屬性通常被視為枚舉，IE創建了一個優化的屬性系統，用於在格式化和布局中進行解析。

然而，今天的應用程序模式大量使用像id，class和data- *這樣的屬性，它們遠遠不如瀏覽器指令，而更像是通用存儲：

Total:

$12.34

因此，這超出了存儲字元串所需的最低限度。另外，由於UI框架經常會進行跨元素重複CSS類，所以專家們打算將字元串霧化以減少內存使用，並提高像QuerySelector這樣的API的性能。

雖然可靠地測量和改進性能經歷了很多困難，但測試時候的缺陷也被進行了很好的記錄。為了獲得對瀏覽器性能的最全面的了解，Microsoft Edge團隊對用戶的實際測量進行了現場監測，並結合基準測試的組合來指導最終的優化：

以下是專家們在構建的第一個Child API的監控樣本，這些數據並不能直接操作，因為它不提供性能優化所需的API調用的所有細節即DOM樹的形狀和大小，但它是用戶體驗的唯一直接測量標準，可以提供反饋意見。

通過在諸如Bing Maps和Office 365這樣的複雜網站和應用程序中捕獲和重複真實用戶的場景，我們不太可能對不適用於用戶的優化進行過度資源的頭圖。下圖就是在Bing Maps上模擬用戶的報告樣本，其中每個數據點都是瀏覽器構建過的，並且提供有關統計分布測量的詳細信息以及更多調查地更改信息鏈接。

在基準類別中，最令專家們興奮的改進是在Speedometer。Speedometer使用TodoMVC應用程序模擬了幾種流行的Web框架，包括Ember，Backbone，jQuery，Angular和React。隨著新的DOM樹的使用和其他瀏覽器子系統的相應改進，如Chakra JavaScript引擎，運行Speedometer的時間相比以前減少了30％，在Creators Update中，運行速度提升了35％。

當然，最重要的性能指標還是用戶的反應，以下就是我們總結的幾個用戶的想法。

總結

快速的DOM對於當今的網路應用和體驗至關重要。Windows 10 Creators Update是首次專註於重新構建的DOM樹的性能。同時，微軟的安全專家們也將繼續改進測試的方法，如CSS使用和API目錄。

目前對DOM樹的改進才剛剛開始，嘶吼會在未來進行持續的關注。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！