主题：【原创】新时代新潮流WebOS 【1】 -- 邓侃

【15】沉重的XML-DOM

前文说到，把AJAX的三驾马车，HTML/XML + CSS + JavaScript照搬到手机上去，虽然理论上行得通，但是实际运行的结果，很可能是CPU消耗高，内存占用大，工作环节多，导致整体效率不高。问题出在XML的DOM Tree，以及JavaScript上。

互联网网页的格式是HTML。当浏览器里的渲染机（Rendering Engine）得到一个网页时，在着手开始渲染之前，它先必须解析网页的内容。所谓解析，就是根据其HTML格式，生成一棵XML DOM Tree。真正的内容都在DOM Tree的叶子节点存储，而中间节点包括根节点的作用，是区分内容的段落，以及从属关系。

解析不可避免，但是解析的负担很沉重。首先，要检查整个HTML/XML文件是否符合规范，譬如每次出现一个起始tag的时候，是不是都有终止tag与之呼应。其次，有时候还需要检查XML是否符合特定的语法规则，即某一DTD或者XML-Schema的规范。这两步完成以后，才轮到构建DOM Tree的工作。数据结构越复杂，检查规范，验证语法，和构建DOM Tree，这三步的工作就越沉重。

解析完成以后，整个XML文件所描述的内容及其结构，都被存储在内存中，以DOM Tree的形式出现。DOM Tree的好处在于能够方便而且迅速地访问任何一个节点的内容，修改它的内容，删除增加或者嫁接一个子树。但是方便的代价是耗费内存。有人做过统计，平均而言，DOM Tree占用的内存，是原始文本文件尺寸的10倍以上。也就是说，如果给你一个HTML网页，假设这个网页包含1000个bytes。当你用浏览器打开这个HTML网页，单单这个HTML对应的XML DOM Tree就会占用10,000字节以上的bytes。(http://www.oracle.com/technology/oramag/oracle /03-sep/o53devxml.html)

互联网网页的格式是HTML/XML，手机页面的格式是不是也必须遵循同样的格式？1. 从功能上讲，手机页面的层次比互联网网页的要简单得多，所以似乎没有必要沿用HTML/XML/DOM Tree这样强大的数据结构。2. 互联网网页之所以用HTML格式，很大程度上是历史的延续。说得直白点，单纯从技术的角度讲，HTML未必是互联网网页的最佳格式。手机没有互联网的历史包袱，所以客观上没有义务去继承HTML/XML的代价。

Figure 1. Simple data structure to represent page layout

Courtesy http://farm4.static.flickr.com/3616/3403225403_e679c10dab_o.gif

有没有办法简化手机页面的数据格式，使之占用存储空间少，解析容易，而且编辑简便？

第一个思路是简化XML。并非所有的XML元素都必不可少，或许20/80原则对于XML也是适用的，即常用的XML元素只占20%，而其余80%的元素却很少用。所以，不妨取HTML/XML一个子集，作为专供手机页面使用的HTML。瘦身以后的XML，或许可以占用更少空间，解析也更容易。WAP中包括的WML就是这个思路。

第二个思路更极端，它质疑“树”结构的效率。换句话说，对于手机页面而言，是否需要“树”来表述它的结构？树结构最大的长处在于有利于表述从属关系。但是事实上，手机页面的结构不像互联网页面那样复杂，没有必要强调从属关系。或许一个链表就可以把手机页面的层次表达清楚。

譬如Adobe Flash规定，每个frame由若干文字或者图像组成，每段文字或者每个图像称为character，每个character都对应一个深度，depth。每个depth有且只有一个character。如果不同的characters之间有重叠部分，高层的character会遮挡低层的 character。如Figure 1中左图， 这个卡通中有文字，有人物，有玩具，有阴影。其中左边人物的左脚遮盖了右边人物的右脚。

虽然Adobe Flash能够支持XML，但是这样做的动机多半是迎合HTML/XML大行其道的现状。单纯为了表达frame的结构，其实用链表（LIST）格式就足够了。最上层到最下层不妨分别设为， 1. 文字，2. 气球，3. 左边人物，4. 右边人物，5. 脚下阴影。当然也可以设为其它顺序，只要保证重叠部分的遮盖关系正确即可，也就是只要保障左边人物在右边人物的上层就可以了。

比较一下链表结构和树结构，

1. 在DOM Tree结构中，文字和图像等等真正意义上的内容实际上只存储在树的叶子节点。树的中间节点主要是表述从属关系。链表结构摒弃了从属关系的表述，每一环都包含一个character，避免了树的中间节点的虚耗（overhead）。

当然，不是说树的中间节点完全没有用，对于结构复杂，层次众多，文字和图像各个内容实体之间关联丰富的页面来讲，或许需要树这样强大的数据结构来表述页面的结构。不过，话又说回来，如果各个内容实体之间关联错综复杂，或许树这样的数据结构也难以表述，不如用图（graph）更强大。

总之，为什么要用树结构来表述手机页面的结构，是一个值得讨论的问题。

2. 当鼠标移动等等事件发生时，XML DOM Tree负责协调事件的处理。

Figure 2. The capture and bubbling of event by the DOM tree.

Courtesy http://www.w3.org/TR/DOM-Level-3-Events/images/eventflow.png

当 Web开发人员编写HTML页面时，他会设定哪些HTML元素侦听及处理哪些事件。假设在某一个HTML里面有这么一句，<img src="bigfoot.png" onmousemove="alert('Hey, 你踩着我了!')" />。这句话的意思是，当用户访问这个页面时，页面里显示一个图片，“bigfoot.png”。当用户把鼠标移动到这个图片上时，弹出一个小窗口，窗口里写着这么一句话，“Hey, 你踩着我了!”。这个场景是如何实现的呢？

a. 当浏览器渲染HTML页面的时候，浏览器知道bigfoot.png照片在什么区域显示。

b. 当用户移动鼠标时，通过浏览器可以确定鼠标的当前位置坐标。有了这个位置坐标，就可以确定当前鼠标是不是位于bigfoot.png照片所在区域。

c. 当用户移动鼠标时，onmousemove事件就产生了。但是并不是说，一旦有新事件，就必须有响应。事实上，几乎随时都会有新事件发生。每当浏览器发现有新事件的时候，它需要确定通知谁去处理这个事件，或者决定是否忽略这个事件。

d. 确定通知谁来处理这个事件，需要借助于HTML对应的XML DOM Tree。在浏览器解析完HTML页面以后，它知道在相应的XML DOM Tree里，事件发生在哪一个叶子节点，或者发生在哪一个最靠近叶子节点的中间节点。

每当用户移动鼠标时，浏览器会从OS那里知道有onmousemove类型的事件产生。然后浏览器搜索XML DOM Tree，去确认这个事件发生在哪个节点上。在上面的例子中，绝大多数onmousemove事件没有对应的节点，所以绝大多数时间里，事件虽然发生，但是被忽略，没有任何响应。然而，即使事件被忽略，浏览器照样一遍又一遍地搜索XML DOM Tree，所造成的CPU消耗相当可观。

只有当鼠标移动到bigfoot.png照片所在区域时，浏览器才确定目标节点是<img>所在的叶子节点。

e. 确定了目标节点以后，浏览器从XML DOM Tree的根节点开始，逐步向<img>所在的叶子节点访问。从根节点到该叶子节点的路径叫capture path，从该叶子节点返溯回根节点的路径叫bubbling path。Capture path与bubbling path经过的中间节点完全相同，唯一不同之处是方向。

f. 侦听和处理事件的节点可以是叶子节点，也可以是capture path或bubbling path沿途的中间节点，或者兼而有之。在上面的例子中，只有叶子节点侦听鼠标移动事件，处理的方式是弹出一个窗口，里面写着“Hey, 你踩着我了!”。如果另外还有中间节点也侦听和处理事件，那就需要确定多个节点处理同一个事件的先后顺序，这就是capture path和bubbling path的用途。

XML DOM Tree协调事件处理的方式很沉重。主要体现在两个方面，1. 只要有风吹草动的事件发生，XML DOM Tree就要不厌其烦地一遍又一遍搜索发生事件的节点。如果XML DOM Tree结构比较大，那么搜索的成本就很高。2. 在确定谁去处理事件，什么时候处理的过程中，需要从根节点沿capture path一路访问到目标节点，再沿bubbling path一路返回根节点，事件处理的过程很长。

如果换用链表结构，执行效率会提高很多。

1. 每当有任何事件发生，也需要一遍又一遍地搜索链表，这个过程不可避免。但是每次搜索链表的计算成本相当低廉。

譬如在Figure 1中，共有5个characters。在浏览器渲染页面的时候，可以同时生成一个bitmap。页面中每个character对应bitmap中一个剪影，这样bitmap中有5个剪影。当用户移动鼠标时，鼠标所在剪影的光素的值，对应着这个character的depth。这样只需要O（1）的成本，就可以确定事件发生在哪一个character上。

当然，速度提高的代价是占用更多内存空间，也就是bitmap占用的空间。不过减少 bitmap尺寸的办法很多，譬如一个简单的办法是把原图像中相邻的四个光素合并成一个光素，这样就缩小了3/4的空间占用，如Figure 1中右图所示。这样做的后果，是当鼠标移动到characters边缘时，事件触发的精度不够高，但是对于绝大用户而言，事件触发的精度可能不需要太高。

2. 链表可以支持多个characters处理同一个事件。譬如事件发生于Figure 1中左边人物，但是作为响应，不仅左边人物有相应动作，而且脚下阴影也随之变化。实现这个关联动作的办法很简单，在左边人物处理完事件以后，主动调用阴影的相关动作，而不需要沿capture path和bubbling path访问一圈。

这样手工设定的办法，虽然没有capture path和bubbling path那样方便，但是计算成本较低。尤其是当一个事件发生时，同时响应的characters为数不多时，可以大大降低计算量。