Vue3diff算法原理和优化

野性酷女 2022-11-04 14:22 168阅读 0赞

#     #

关注前端公众号 【前端每日一博】

![c46f65a31c1e140b3cb6b0332979c093.gif][]

## 前言 ##

面试官：

你知道 Vue3.0 Object.difineProperty和vue3.0的proxy的区别吗？

你知道 Vue3.0 diff算法原理和它有什么优化吗？

你知道 Vue3.0 proxy是如何通知相关组件进行重新渲染吗？

...

你：。。。

`随着vue3.0beta版本的发布，vue3.0正式版本相信不久就会与我们相遇。尤雨溪在直播中也说了vue3.0的新特性typescript强烈支持，proxy响应式原理，重新虚拟dom，优化diff算法性能提升等等。可想而知，Vue3.0时代有一大波我们需要了解的东西。`

**「废话不多说，今天的主题是和大家分享一下Vue 虚拟Dom、Diff算法原理以及源码解析、以及Vue3.0的diff算法是如何进行优化的。」**

其他系列在此：

**「Vue3.0时代你必须了解的：响应式原理」**

**「Vue3.0时代你必须了解的：compositon api 用法和注意事项」**

**「基于项目实战阐述vue3.0新型状态管理和逻辑复用方式」**

## 目录 ##

1.  virtual dom
2.  diff算法原理
3.  Vue3.0 diff算法优化

## virtual dom ##

如果咱们不了解virtual dom 的话，要理解DIff算法是比较困难的。

### 概念： ###

1.  template
2.  渲染函数
3.  vnode(virtual dom)
4.  patch(diff算法)
5.  view

![7e0892bf6c28093d2ed209aa2a2fcfe4.png][]

*  Vue.js通过编译将template 模板转换成渲染函数(render ) ，执行渲染函数就可以得到一个虚拟节点树
 *  VNode 虚拟节点：它可以代表一个真实的 dom 节点。通过 createElement 方法能将 VNode 渲染成 dom 节点。简单地说，vnode可以理解成节点描述对象，它描述了应该怎样去创建真实的DOM节点。
 *  patch(也叫做patching算法)：虚拟DOM最核心的部分，它可以将vnode渲染成真实的DOM，这个过程是对比新旧虚拟节点之间有哪些不同，然后根据对比结果找出需要更新的的节点进行更新。这点我们从单词含义就可以看出， patch本身就有补丁、修补的意思，其实际作用是在现有DOM上进行修改来实现更新视图的目的。Vue的Virtual DOM Patching算法是基于Snabbdom的实现，并在些基础上作了很多的调整和改进。

### 什么是virtual dom ###

通俗易懂的来说就是用一个简单的对象去代替复杂的dom对象。

如果你去打印一下一个真实的DOM节点，就会发现DOM节点上有很多属性，如果Vue每次都生成一个新的真实DOM节点，对性能是巨大的浪费。

Virtual DOM 实际上就是以JavaScript对象（VNode ）为基础形成一棵树，对真实DOM的一层抽象。Vue最终的工作就是通过这棵树批量生成真实的DOM节，可以说两者存在一层映射关系。

简单来说，可以把Virtual DOM 理解为一个简单的JS对象，并且最少包含标签名( tag)、属性(attrs)和子元素对象( children)三个属性。不同的框架对这三个属性的命名会有点差别。

对于虚拟DOM，咱们来看一个简单的实例，就是下图所示的这个，详细的阐述了模板 → 渲染函数 → 虚拟DOM树 → 真实DOM的一个过程

![e8e26c9f8ef21ba38f15839fb7d77c12.png][]

其实虚拟DOM在Vue.js主要做了两件事：

*  提供与真实DOM节点所对应的虚拟节点vnode
 *  将虚拟节点vnode和旧虚拟节点oldVnode进行对比（diff算法），然后更新视图

总结：**「vdom是为了减轻性能压力。dom是昂贵的，昂贵的一方面在dom本身的重量，dom节点在js里的描述是个非常复杂属性很多原型很长的超级对象，另一方面是浏览器渲染进程和js进程是独立分离的，操作dom时的通信和浏览器本身需要重绘的时耗都是很高的。所以大家机智的搞了个轻量的vdom去模拟dom，vdom每个节点都只挂载js操作的必要属性，每次组件update时都先操作vdom，通过vdom的比对，得到一个真实dom的需要操作的集合。整个机制是在JavaScript层面计算，在完成之前并不会操作DOM，等数据稳定之后再实现精准的修改。」**

## 分析diff算法 ##

由上我们知道了，新的虚拟DOM和旧的虚拟DOm是通过diff算法进行比较之后更新的。

### Vue2.x diff算法 ###

### Vue2.x diff算法原理 ###

传统diff算法通过循环递归对节点进行依次对比效率低下，算法复杂度达到O(N^3)，主要原因在于其追求完全比对和最小修改，而React、Vue则是放弃了完全比对及最小修改，才实现从O(N^3) => O(N)。

优化措施有：

*  **「分层diff」**：不考虑跨层级移动节点，让新旧两个VDOM树的比对无需循环递归（复杂度大幅优化，直接下降一个数量级的首要条件）。这个前提也是Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计。

在同层节点中，采用了**「双端比较的算法」**过程可以概括为：oldCh和newCh各有两个头尾的变量StartIdx和EndIdx，它们的2个变量相互比较，一共有4种比较方式。如果4种比较都没匹配，如果设置了key，就会用key进行比较，在比较的过程中，变量会往中间靠，一旦StartIdx>EndIdx表明oldCh和newCh至少有一个已经遍历完了，就会结束比较；

![31db6bd2585dc1406df07fcee3b528be.png][]

当发生以下情况则跳过比对，变为插入或删除操作：

*  **「组件的Type(Tagname)不一致」**，原因是绝大多数情况拥有相同type的两个组件将会生成相似的树形结构，拥有不同type的两个组件将会生成不同的树形结构，所以type不一致可以放弃继续比对。
 *  **「列表组件的Key不一致」**，旧树中无新Key或反之。毕竟key是元素的身份id，能直接对应上是否是同一个节点。
 *  对触发了getter/setter 的组件进行diff，精准减少diff范围

### Vue3.0 diff ###

#### diff痛点 ####

vue2.x中的虚拟dom是进行**「全量的对比」**，在运行时会对所有节点生成一个虚拟节点树，当页面数据发生变更好，会遍历判断virtual dom所有节点（包括一些不会变化的节点）有没有发生变化；虽然说diff算法确实减少了多DOM节点的直接操作，但是这个**「减少是有成本的」**，如果是复杂的大型项目，必然存在很复杂的父子关系的VNode,**「而Vue2.x的diff算法，会不断地递归调用 patchVNode，不断堆叠而成的几毫秒，最终就会造成 VNode 更新缓慢」**。

那么Vue3.0是如何解决这些问题的呢

##### 动静结合 PatchFlag #####

来个????：

在Vue3.0中，在这个模版编译时，编译器会在动态标签末尾加上 /\* Text\*/ PatchFlag。**「也就是在生成VNode的时候，同时打上标记，在这个基础上再进行核心的diff算法」**并且 PatchFlag 会标识动态的属性类型有哪些，比如这里 的TEXT 表示只有节点中的文字是动态的。而patchFlag的类型也很多。这里直接引用一张图片。

![4633c65c33a1a4811c3377862f9d43a0.png][]

其中大致可以分为两类：

*  当 patchFlag 的值「大于」 0 时，代表所对应的元素在 patchVNode 时或 render 时是可以被优化生成或更新的。
 *  当 patchFlag 的值「小于」 0 时，代表所对应的元素在 patchVNode 时，是需要被 full diff，即进行递归遍历 VNode tree 的比较更新过程。

看源码：

export function render(_ctx, _cache, $props, $setup, $data, $options) {
     return (_openBlock(), _createBlock("div", null, [
      _createVNode("p", null, "'HelloWorld'"),
      _createVNode("p", null, _toDisplayString(_ctx.msg), 1 /* TEXT */)
     
     ]))
    }
    ****

这里的`_createVNode("p", null, _toDisplayString(_ctx.msg), 1 /* TEXT */)`就是对变量节点进行标记。

总结：**「Vue3.0对于不参与更新的元素，做静态标记并提示，只会被创建一次，在渲染时直接复用。」**

其中还有cacheHandlers（事件侦听器缓存），这里就不讲了。

##### diff算法源码解析 #####

以数组为栗子：

newNode:[a,b,c,d,e,f,g] 
    
    oldNode:[a,b,c,h,i,j,f,g]

步骤1:**「从首部比较new vnode 和old vnode」**,如果碰到不同的节点，跳出循环，否则继续，直到一方遍历完成；

`由此我们得到newNode和oldNode首部相同的片段为 a,b,c，`

源码：

const patchKeyedChildren = (
        c1,
        c2,
        container,
        parentAnchor,
        parentComponent,
        parentSuspense,
        isSVG,
        optimized
    ) => {
        let i = 0;  
        const l2 = c2.length
        let e1 = c1.length - 1
        let e2 = c2.length - 1
    
        
        while (i <= e1 && i <= e2) {
          const n1 = c1[i]
          const n2 = c2[i]
          if (isSameVNodeType(n1, n2)) {
            patch(
              n1,
              n2,
              container,
              parentAnchor,
              parentComponent,
              parentSuspense,
              isSVG,
              optimized
            )
          } else {
            break
          }
          i++
        }
        
        //这里的isSameVNodeType
          export function isSameVNodeType(n1: VNode, n2: VNode): boolean {
          // 比较类型和key是否一致（）
          return n1.type === n2.type && n1.key === n2.key
          }

**「Tip」**:这里的isSameVNodeType从**「type和key」**，因此key作为唯一值是非常重要的，这也就解释了 v-for循环遍历不能用index作为key的原因。

步骤2:**「从尾部比较new vnode 和old vnode」**,如果碰到不同的节点，跳出循环，否则继续，直到一方遍历完成；

`由此我们得到newNode和oldNode尾部相同的片段为 f,g`

while (i <= e1 && i <= e2) {
          const n1 = c1[e1]
          const n2 = c2[e2]
          if (isSameVNodeType(n1, n2)) {
            patch(
              n1,
              n2,
              container,
              parentAnchor,
              parentComponent,
              parentSuspense,
              isSVG,
              optimized
            )
          } else {
            break
          }
          e1--
          e2--
        }
    }

在遍历过程中满足`i > e1 && i < e2`，说明 **「仅有节点新增」**

if (i > e1) {
        if (i <= e2) {
            const nextPos = e2 + 1;
            const anchor = nextPos < l2 ? c2[nextPos] : parentAnchor
            while (i <= e2) {
                patch(
                    null,
                    c2[i],
                    container,
                    anchor,
                    parentComponent,
                    parentSuspense,
                    isSVG
                )
                i++
            }
        }
    } else if {
        ...
    } else {
       ...
    }

在遍历过程中满足`i > e1 && i > e2`，说明 **「仅有节点移除」**

if (i > e1) {
      //
    } else if (i > e2) {
        while (i <= e1) {
            unmount(c1[i], parentComponent, parentSuspense, true)
            i++
        }
    } else {
        //
    }

步骤3: **「节点移动、新增或删除」**

经过以上步骤，剩下的就是不确定的元素，那么diff算法将遍历 所有的new node，将key和索引存在keyToNewIndexMap中，为map解构，

if (i > e1) {
      //
    } else if (i > e2) {
      //
    } else {
        const s1 = i
        const s2 = i
    
        const keyToNewIndexMap = new Map()
        for (i = s2; i <= e2; i++) {
            const nextChild = c2[i]
            if (nextChild.key !== null) {
                keyToNewIndexMap.set(nextChild.key, i)
            }
        }
    }

接下来

for (i = s1; i <= e1; i++) { /* 开始遍历老节点 */
            const prevChild = c1[i]
            if (patched >= toBePatched) { /* 已经patch数量大于等于， */
              /* ① 如果 toBePatched新的节点数量为0 ，那么统一卸载老的节点 */
              unmount(prevChild, parentComponent, parentSuspense, true)
              continue
            }
            let newIndex
             /* ② 如果,老节点的key存在 ，通过key找到对应的index */
            if (prevChild.key != null) {
              newIndex = keyToNewIndexMap.get(prevChild.key)
            } else { /*  ③ 如果,老节点的key不存在 */
              for (j = s2; j <= e2; j++) { /* 遍历剩下的所有新节点 */
                if (
                  newIndexToOldIndexMap[j - s2] === 0 && /* newIndexToOldIndexMap[j - s2] === 0 新节点没有被patch */
                  isSameVNodeType(prevChild, c2[j] as VNode)
                ) { /* 如果找到与当前老节点对应的新节点那么 ，将新节点的索引，赋值给newIndex  */
                  newIndex = j
                  break
                }
              }
            }
            if (newIndex === undefined) { /* ①没有找到与老节点对应的新节点，删除当前节点，卸载所有的节点 */
              unmount(prevChild, parentComponent, parentSuspense, true)
            } else {
              /* ②把老节点的索引，记录在存放新节点的数组中， */
              newIndexToOldIndexMap[newIndex - s2] = i + 1
              if (newIndex >= maxNewIndexSoFar) {
                maxNewIndexSoFar = newIndex
              } else {
                /* 证明有节点已经移动了   */
                moved = true
              }
              /* 找到新的节点进行patch节点 */
              patch(
                prevChild,
                c2[newIndex] as VNode,
                container,
                null,
                parentComponent,
                parentSuspense,
                isSVG,
                optimized
              )
              patched++
            }
     }

之后通过 计算出**「最长递增子序列」** 减少Dom元素的移动，达到最少的 dom 操作。至于什么是最长递增子序列，有兴趣的小伙伴可以自信查阅。

## 最后 ##

Vue3.0 的diff原理和优化也讲完了，如有错误，欢迎指出。

![ead4507e15b52a14d501dbab8e15335f.gif][]

[c46f65a31c1e140b3cb6b0332979c093.gif]: /images/20221023/d39aedfdcc284da8bb0e5095b4e12e2e.png
[7e0892bf6c28093d2ed209aa2a2fcfe4.png]: /images/20221023/4875eff7f9254901aca88f6cdbb2afa3.png
[e8e26c9f8ef21ba38f15839fb7d77c12.png]: /images/20221023/270102eb878649a19e4c956323ab8c4f.png
[31db6bd2585dc1406df07fcee3b528be.png]: /images/20221023/28cd6bc522e94dd380cc019ca383b7bc.png
[4633c65c33a1a4811c3377862f9d43a0.png]: /images/20221023/eaf466695b174c73917028e01a03ce2a.png
[ead4507e15b52a14d501dbab8e15335f.gif]: /images/20221023/04078db2f9314f39b3d8092110bea674.png