深入Vue2.x的虚拟DOM diff原理

2019 年 8 月 21 日

深入Vue2.x的虚拟DOM diff原理

Vue的核心是双向绑定和虚拟DOM(下文我们简称为vdom),关于双向绑定可以参阅木琴的文章《剖析Vue原理&实现双向绑定MVVM》,vdom是树状结构,其节点为vnode,vnode和浏览器DOM中的Node一一对应,通过vnode的elm属性可以访问到对应的Node。

vdom因为是纯粹的JS对象,所以操作它会很高效,但是vdom的变更最终会转换成DOM操作,为了实现高效的DOM操作,一套高效的虚拟DOM diff算法显得很有必要。

Vue的diff算法是基于snabbdom改造过来的,感兴趣的朋友可以选择查阅。



这是一张很经典的图,出自《React’s diff algorithm》,Vue 的 diff 算法也同样,即仅在同级的 vnode 间做 diff,递归地进行同级 vnode 的 diff,最终实现整个 DOM 树的更新。那同级 vnode diff 的细节又是怎样的呢?正是本文所要讲的。


一、例子


我们在下文中将使用这个简化的例子来讲述 diff 的过程



如上图的例子,更新前是 1 到 10 排列的 Node 列表,更新后是乱序排列的 Node 列表。罗列一下图中有以下几种类型的节点变化情况:


(1)头部相同、尾部相同的节点:如 1、10


(2)头尾相同的节点:如 2、9(处理完头部相同、尾部相同节点之后)


(3)新增的节点:11


(4)删除的节点:8


(5)其他节点:3、4、5、6、7


二、简单的 diff


简单的 diff 算法可以这样设计:


逐个遍历 newVdom 的节点,找到它在 oldVdom 中的位置,如果找到了就移动对应的 DOM 元素,如果没找到说明是新增节点,则新建一个节点插入。遍历完成之后如果 oldVdom 中还有没处理过的节点,则说明这些节点在 newVdom 中被删除了,删除它们即可。


仔细思考一下,几乎每一步都要做移动 DOM 的操作,这在 DOM 整体结构变化不大时的开销是很大的,实际上 DOM 变化不大的情况现实中经常发生,很多时候我们只需要变更某个节点的文本而已。


接下来我们看一下 Vue 的 diff 实现


三、Vue 的 diff 实现


上图例子中我画上了 oldStart+oldEnd,newStart+newEnd 这样 2 对指针,分别对应 oldVdom 和 newVdom 的起点和终点。起止点之前的节点是待处理的节点,Vue 不断对 vnode 进行处理同时移动指针直到其中任意一对起点和终点相遇。处理过的节点 Vue 会在 oldVdom 和 newVdom 中同时将它标记为已处理(标记方法后文中有介绍)。Vue 通过以下措施来提升 diff 的性能。


(一)优先处理特殊场景


(1)头部的同类型节点、尾部的同类型节点


这类节点更新前后位置没有发生变化,所以不用移动它们对应的 DOM


(2)头尾/尾头的同类型节点


这类节点位置很明确,不需要再花心思查找,直接移动 DOM 就好


处理了这些场景之后,一方面一些不需要做移动的 DOM 得到快速处理,另一方面待处理节点变少,缩小了后续操作的处理范围,性能也得到提升


(二)“原地复用”


“原地复用”是指 Vue 会尽可能复用 DOM,尽可能不发生 DOM 的移动。Vue 在判断更新前后指针是否指向同一个节点,其实不要求它们真实引用同一个 DOM 节点,实际上它仅判断指向的是否是同类节点(比如 2 个不同的 div,在 DOM 上它们是不一样的,但是它们属于同类节点),如果是同类节点,那么 Vue 会直接复用 DOM,这样的好处是不需要移动 DOM。再看上面的实例,假如 10 个节点都是 div,那么整个 diff 过程中就没有移动 DOM 的操作了。


“原地复用”在 Vue 的官方文档中有提到,虽然带来了好处,但是也会产生一些问题,朋友们可以复习一下


https://cn.vuejs.org/v2/guide/list.html#key


https://cn.vuejs.org/v2/guide/conditional.html#用-key-管理可复用的元素


四、按步解剖实例


(一)整体视图



先看一张整体视图,整个 diff 分两部分:


(1)第一部分是一个循环,循环内部是一个分支逻辑,每次循环只会进入其中的一个分支,每次循环会处理一个节点,处理之后将节点标记为已处理(oldVdom 和 newVdom 都要进行标记,如果节点只出现在其中某一个 vdom 中,则另一个 vdom 中不需要进行标记),标记的方法有 2 种,当节点正好在 vdom 的指针处,移动指针将它排除到未处理列表之外即可,否则就要采用其他方法,Vue 的做法是将节点设置为 undefined。


(2)循环结束之后,可能 newVdom 或者 oldVdom 中还有未处理的节点,如果是 newVdom 中有未处理节点,则这些节点是新增节点,做新增处理。如果是 oldVdom 中有这类节点,则这些是需要删除的节点,相应在 DOM 树中删除之


整个过程是逐步找到更新前后 vdom 的差异,然后将差异反应到 DOM 树上(也就是 patch),特别要提一下 Vue 的 patch 是即时的,并不是打包所有修改最后一起操作 DOM(React 则是将更新放入队列后集中处理),朋友们会问这样做性能很差吧?实际上现代浏览器对这样的 DOM 操作做了优化,并无差别。


(二)逐步解析


(1)处理头部的同类型节点,即 oldStart 和 newStart 指向同类节点的情况,如下图中的节点 1


这种情况下,将节点 1 的变更更新到 DOM,然后对其进行标记,标记方法是 oldStart 和 newStart 后移 1 位即可,过程中不需要移动 DOM(更新 DOM 或许是要的,比如属性变更了,文本内容变更了等等)



(2)处理尾部的同类型节点,即 oldEnd 和 newEnd 指向同类节点的情况,如下图中的节点 10


与情况(1)类似,这种情况下,将节点 10 的变更更新到 DOM,然后 oldEnd 和 newEnd 前移 1 位进行标记,同样也不需要移动 DOM



(3)处理头尾/尾头的同类型节点,即 oldStart 和 newEnd,以及 oldEnd 和 newStart 指向同类节点的情况,如下图中的节点 2 和节点 9


先看节点 2,其实是往后移了,移到哪里?移到 oldEnd 指向的节点(即节点 9)后面,移动之后标记该节点,将 oldStart 后移 1 位,newEnd 前移一位



操作结束之后情况如下图



同样地,节点 9 也是类似的处理,处理完之后成了下面这样



(4)处理新增的节点


newStart 来到了节点 11 的位置,在 oldVdom 中找不到节点 11,说明它是新增的


那么就创建一个新的节点,插入 DOM 树,插到什么位置?插到 oldStart 指向的节点(即节点 3)前面,然后将 newStart 后移 1 位标记为已处理(注意 oldVdom 中没有节点 11,所以标记过程中它的指针不需要移动),处理之后如下图



(5)处理更新的节点


经过第(4)步之后,newStart 来到了节点 7 的位置,在 oldVdom 中能找到它而且不在指针位置(查找 oldVdom 中 oldStart 到 oldEnd 区间内的节点),说明它的位置移动了


那么需要在 DOM 树中移动它,移到哪里?移到 oldStart 指向的节点(即节点 3)前面,与此同时将节点标记为已处理,跟前面几种情况有点不同,newVdom 中该节点在指针下,可以移动 newStart 进行标记,而在 oldVdom 中该节点不在指针处,所以采用设置为 undefined 的方式来标记(一定要标记吗?后面会提到)



处理之后就成了下面这样



(6)处理 3、4、5、6 节点


经过第(5)步处理之后,我们看到了令人欣慰的一幕,newStart 和 oldStart 又指向了同一个节点(即都指向节点 3),很简单,按照(1)中的做法只需移动指针即可,非常高效,3、4、5、6 都如此处理,处理完之后如下图



(7)处理需删除的节点


经过前 6 步处理之后(实际上前 6 步是循环进行的),朋友们看 newStart 跨过了 newEnd,它们相遇啦!而这个时候,oldStart 和 oldEnd 还没有相遇,说明这 2 个指针之间的节点(包括它们指向的节点,即上图中的节点 7、节点 8)是此次更新中被删掉的节点。


OK,那我们在 DOM 树中将它们删除,再回到前面我们对节点 7 做了标记,为什么标记是必需的?标记的目的是告诉 Vue 它已经处理过了,是需要出现在新 DOM 中的节点,不要删除它,所以在这里只需删除节点 8。


在应用中也可能会遇到 oldVdom 的起止点相遇了,但是 newVdom 的起止点没有相遇的情况,这个时候需要对 newVdom 中的未处理节点进行处理,这类节点属于更新中被加入的节点,需要将他们插入到 DOM 树中。



至此,整个 diff 过程结束了


Vue 的 diff 算法与动态规划算法中的经典案例“计算 a 到 b 的最小编辑距离”看上去有些相似,实际完全不同,Vue 的 diff 相对来说轻量很多,感兴趣的朋友可以查阅相关资料进行了解。


好啦,感谢你的阅读,希望能帮助你理解 Vue 的 diff 算法,在阅读过程中遇到的问题也欢迎一起交流!


作者介绍:


汪玉林,高级工程师,增值产品部前端 Leader,目前团队负责手 Q 游戏中心、手 Q 游戏运营、手 Q 阅读等项目,有丰富的 Web 前端架构经验。


本文转载自公众号小时光茶舍(ID:gh_7322a0f167b5)。


原文链接:


https://mp.weixin.qq.com/s/pd0Mshl-f0aJ8C-1Vc95Zw


2019 年 8 月 21 日 10:561119

评论

发布
暂无评论
发现更多内容
深入Vue2.x的虚拟DOM diff原理-InfoQ