新时代新潮流 WebOS【15】沉重的 XML-DOM

公司

2009-04-03 00:35

前文说到,把 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,000bytes 以上的空间

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

Simple data structure to represent page layout

Figure 1. Simple data structure to represent page layout

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

第一个思路是简化 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)。
    当然,不是说树的中间节点完全没有用。树所表达的从属包含关系,有利于浏览器在进行页面渲染时,支持内容元素的相对定位式的布局。假设丧失了这种从属包含关系,那么仅能绝对定位式布局。这两种方式的工作量相差很大。不妨做一个简单的试验作为体验,首先用 HTML + CSS 设计一个稍微有点复杂的页面。然后尝试把所有元素的 style 的 position 属性设为 absolute 后,重复一下设计,或许这时你会发现页面 的布局有点奇怪,请你耐心做做修改。几番尝试以后,绝对定位式布局造成的工作量的增加,就不言而喻了。
    另外,对于结构复杂,层次众多,文字和图像各个内容实体之间关联丰富的页面来讲,或许需要树这样强大的数据结构来表述页面的结构。不过,话又说回来,如果各个内容实体之间关联错综复杂,或许树这样的数据结构也难以表述,不如用图(graph)更合适。
    但是,手机页面的尺寸较小,结构简单。在这种情境下,是否有必要沿用树结构来表述手机页面的结构,是一个值得讨论的问题。
  2. 当鼠标移动等等事件发生时,XML DOM Tree 负责协调事件的处理。

The capture and bubbling of event by the DOM tree

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

当 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 为数不多时,可以大大降低计算量。
后评论

评论在审核通过后将对所有人可见

正在加载中

移动互联网的围观者、起哄者、以及肇事者。

本篇来自栏目

解锁订阅模式,获得更多专属优质内容