五千年(敝帚自珍)

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

共:💬594 🌺1902
全看分页树展 · 主题 跟帖
家园 【原创】【15】沉重的XML-DOM

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

关键词(Tags): #硅谷评论
全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河