前言

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属性(列数不同,有合并的列),表格的自动宽度会受到很大的影响,以至于错位混乱：

<tr>
    <td colspan="2">Total:</td>
    <td>$12.34</td>
</tr>

colspan对浏览器具有语义意义，因此必须进行解析。鉴于页面不是动态的，那么属性通常被视为枚举，IE创建了一个优化的属性系统，用于在格式化和布局中进行解析。

然而，今天的应用程序模式大量使用像id，class和data- *这样的属性，它们远远不如浏览器指令，而更像是通用存储：

<li id="cart" data-customerid="a8d3f916577aeec" data-market="en-us">
    <b>Total:</b>
    <span class="total">$12.34</span>
</li>

因此，这超出了存储字符串所需的最低限度。另外，由于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树的改进才刚刚开始，嘶吼会在未来进行持续的关注。