vueDiff 算法解读

简介: 前言在面试中谈到 vue 源码,一般都会扯扯 diff 算法,而这个 diff 又在网上传的神乎其神的,说是提升了页面更新性能,我们一起看看到底咋回事吧

前言


在面试中谈到 vue 源码,一般都会扯扯 diff 算法,而这个 diff 又在网上传的神乎其神的,说是提升了页面更新性能,我们一起看看到底咋回事吧


传统diff算法


在 Jquery 时代,“前辈们”就告诉过我,频繁的操作 DOM 是很消耗性能的,我们可以在拼接完 HTML 片段后,通过 innerHTML 来替换整个 DOM,效率提升杠杠的。


所以之前我一直有个疑问,diff 算法为什么通过比较节点,复用节点可以达到性能提升,直接替换整个 innerHTML 不更高效么?


带着疑问在网上查阅了一些文章,感觉似乎是明白了


首先,创建一个完整的节点对象的成本是非常大的,因为 DOM 节点是个非常复杂的对象

const elm = document.createElement('div')
for(let propName in elm) {
    console.log(propName)
}
复制代码

所以即使我们在浏览器中通过 innerHTML 来替换整个 DOM,浏览器也会通过比较不同的节点来达到复用。


比较算法涉及每个新旧节点的两两比较,其复杂度为 O(n^2),比较之后还得计算最小转化方式,所以综合复杂度就是 O(n^3),我们称此为 传统diff算法



具体可以参看 react的diff 从O(n^3)到 O(n) ,请问 O(n^3) 和O(n) 是怎么算出来?


框架层diff算法的原理


相较于 传统的diff算法,框架层的 diff 有个大前提假设

Web UI 中 DOM 节点跨层级的移动操作特别少,可以忽略不计


所以 diff 的核心就在于,它只对同层节点进行比较,忽略跨层节点的复用

99.png


就如上图所示,只会比较父元素相同的同层节点的复用性。


值得注意的是,同层节点的比较也不会两两进行,而是按照一定的顺序比较,或通过 key 属性判断,所以只需要遍历一次新节点,因此算法的复杂度就降低到了O(n)


通过vue源码来看diff


其实 diff 算法的原理就是这么简单,无非是递归加上遍历节点来比较节点复用性。但在 vue 源码中,具体是如何实现的呢?一起看看


虚拟节点(Virtual Dom)


首先要明白,在 vue 中会维护一个和 DOM 节点对应的 vnode 对象

例如


<div key="1">123</div>
复制代码


在 vue 中就会有个 vnode 对象与之对应,我们列举了其中几个关键属性

{
  elm: el, // 对应真实的DOM节点
  tag: 'div',
  key: 1,
  text: '123',
  children: []
}
复制代码

vnodechildren 数组中对应子节点的 vnode 对象,所以在 vue 中通过 vnode 和真实的 DOM 树进行映射,我们也称之为虚拟树


正是有了虚拟树,当数据更新时。我们可以对比新数据构建的 vnode 和老数据构建的 oldVnode 的差异,来实现外科手术式的精准更新。


而我们对比差异的算法就是采用的 diff。通过 diff 对比虚拟树的差异,将差异通过打补丁(patch)的方式更新到对应的真实 DOM 节点上。


patch函数


patch函数是 diff 流程的入口函数

100.png



其接收两个入参,分别是虚拟节点 vnodeoldVnode,对虚拟节点进行 diff 分析

function patch (oldVnode, vnode) {
  // some code
  if (sameVnode(oldVnode, vnode)) {
    // patch existing root node
    patchVnode(oldVnode, vnode)
  } else {
    // replacing existing element
    const oldElm = oldVnode.elm
    const parentElm = nodeOps.parentNode(oldElm)
    // create new node
    createElm(
      vnode,
      null,
      parentElm,
      nodeOps.nextSibling(oldElm)
    )
    // destroy old node
    if (isDef(parentElm)) {
      removeVnodes([oldVnode], 0, 0)
    }
  }
  return vnode.elm
}
复制代码

patch函数的逻辑比较简单

  1. 判断节点是否可以复用,可以复用则对节点打补丁
  2. 节点不可复用,创建新的节点插入到旧节点之前,同时删除旧节点

可以看出来,如果节点不可复用,直接创建新节点替换,旧的子节点也将不再考虑复用。这就是对应了 diff 的假设,Web UI 中 DOM 节点跨层级的移动操作特别少,可以忽略不计

我们再来看看 sameVnode 函数是如何判断可复用性的

function sameVnode (a, b) {
  return (
    a.key === b.key && (
      (
        a.tag === b.tag &&
        a.isComment === b.isComment &&
        isDef(a.data) === isDef(b.data) &&
        sameInputType(a, b)
      ) || (
        isTrue(a.isAsyncPlaceholder) &&
        a.asyncFactory === b.asyncFactory &&
        isUndef(b.asyncFactory.error)
      )
    )
  )
}
复制代码

这段 vue 的完整源码涉及的变量比较多,我们只需要了解大致是通过 tagkeyinputType 来判断的就行。也就是说,当 tagkeyinputType 完全相同时,我们认定节点可复用。

patchVnode函数

接下来,再看看是如何对可复用节点进行打补丁的

function patchVnode(oldVnode, vnode) {
  // some code
  if (oldVnode === vnode) {
    return;
  }
  const elm = (vnode.elm = oldVnode.elm);
  const oldCh = oldVnode.children;
  const ch = vnode.children;
  // 非文本节点
  if (isUndef(vnode.text)) {
    // 新旧节点都有子节点
    if (isDef(oldCh) && isDef(ch)) {
      // 子节点的同层比较
      if (oldCh !== ch)
        updateChildren(elm, oldCh, ch);
    } else if (isDef(ch)) {
      // 仅新元素有子节点
      if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, "");
      addVnodes(elm, null, ch, 0, ch.length - 1, null);
      // 仅旧元素有子节点
    } else if (isDef(oldCh)) {
      removeVnodes(oldCh, 0, oldCh.length - 1);
    } else if (isDef(oldVnode.text)) {
      // 清空文本
      nodeOps.setTextContent(elm, "");
    }
  // 文本节点,更新文本即可
  } else if (oldVnode.text !== vnode.text) {
    nodeOps.setTextContent(elm, vnode.text);
  }
}
复制代码

patchVnode函数的逻辑也不复杂,一起来分析分析


  1. 找到对应的 dom 节点 elm,并且赋值给 vnode.elm

  2. 判断新节点类型(vnode.text),如果是文本节点,更新 elm 文本即可

  3. 非文本节点下,判断新老节点的子节点

  4. 如果新老节点都有子节点,走子节点的同层比较流程 updateChildren

  5. 如果只有新节点有子节点,直接使用 addVnodes 为 elm 添加子节点(先删除文本)

  6. 如果只有旧节点有子节点,使用 removeVnodes 移除即可

  7. 如果都没有子节点,判断旧数据是否有文本节点,有则清空


这是一个很简单的通过数据(vnode oldVnode)来为真实节点 elm 打补丁更新节点的过程,addVnodes 和 removeVnodes 啥的就是直接操作 elm 节点更新了。


值得注意的是,这边涉及了子节点的同层比较 updateChildren,我们来看看它是如何工作的,也就是说如何从父节点进一步流转到子节点对比的。


updateChildren


子节点的对比流程就稍微复杂一点了,因为涉及如何判断是否存在同层可复用节点,是根据 key 属性来判定呢?还是通过其它顺序呢?


function updateChildren(parentElm, oldCh, newCh) {
  let oldStartIdx = 0;
  let newStartIdx = 0;
  let oldEndIdx = oldCh.length - 1;
  let oldStartVnode = oldCh[0];
  let oldEndVnode = oldCh[oldEndIdx];
  let newEndIdx = newCh.length - 1;
  let newStartVnode = newCh[0];
  let newEndVnode = newCh[newEndIdx];
  let oldKeyToIdx, idxInOld, vnodeToMove, refElm;
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (isUndef(oldStartVnode)) {
      oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
    } else if (isUndef(oldEndVnode)) {
      oldEndVnode = oldCh[--oldEndIdx];
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(oldStartVnode, newStartVnode);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldStartVnode, newEndVnode)) {
      // Vnode moved right
      patchVnode(oldStartVnode, newEndVnode);
      nodeOps.insertBefore(
        parentElm,
        oldStartVnode.elm,
        nodeOps.nextSibling(oldEndVnode.elm)
      );
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    } else if (sameVnode(oldEndVnode, newStartVnode)) {
      // Vnode moved left
      patchVnode(oldEndVnode, newStartVnode);
      nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      if (isUndef(oldKeyToIdx))
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      idxInOld = isDef(newStartVnode.key)
        ? oldKeyToIdx[newStartVnode.key]
        : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
      if (isUndef(idxInOld)) {
        // New element
        createElm(
          newStartVnode,
          null,
          parentElm,
          oldStartVnode.elm
        );
      } else {
        vnodeToMove = oldCh[idxInOld];
        if (sameVnode(vnodeToMove, newStartVnode)) {
          patchVnode(vnodeToMove, newStartVnode);
          oldCh[idxInOld] = undefined;
          nodeOps.insertBefore(
            parentElm,
            vnodeToMove.elm,
            oldStartVnode.elm
          );
        } else {
          // same key but different element. treat as new element
          createElm(newStartVnode, insertedVnodeQueue, parentElm);
        }
      }
      newStartVnode = newCh[++newStartIdx];
    }
  }
  if (oldStartIdx > oldEndIdx) {
    refElm = isUndef(newCh[newEndIdx + 1])
      ? null
      : newCh[newEndIdx + 1].elm;
    addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx);
  } else if (newStartIdx > newEndIdx) {
    removeVnodes(oldCh, oldStartIdx, oldEndIdx);
  }
}
复制代码

咋一看,代码还挺长的嘞,但其实就是有多个 IF-ELSEIF 的分类流程而已,相信我,代码看似冗长却依然简单


建议分析前像我一样先画个图,因为代码前部分的变量真的有点多

101.png



首先我们把 startIdx endIdx 称为左指针,右指针,相应的 startVnode,endVnode 我们称其为左节点,右节点,变量一下子就清晰了好多有木有

好了,开始分析逻辑了


  1. 当左指针小于等于右指针循环遍历(说明上下区间都有节点)

  2. 判断老节点边界为null的情况,向内移动指针

  3. 判断左节点是否可以复用,可以则为节点打补丁(递归调用 patchVnode,下同),向右移动指针

  4. 否则,判断右节点是否可以复用,可以则为节点打补丁,向左移动指针

  5. 否则,判断新右节点和旧左节点是否可以复用,可以则为节点打补丁,同时将旧左节点移动旧右节点前面,再向内移动指针(移动的过程会淘汰旧的右节点)

  6. 同理,判断新左节点和旧右节点,进行类似操作

  7. 当上面的几种情况都无法复用的话,接下来使用 key 来判断是否可以复用(判断新左节点)


首先,通过 createKeyToOldIdx 函数来得到旧节点索引和 key 属性的映射,数据结构为

{
  keyIdx: oldChIdx
}
复制代码


再赋值 idxInOld 变量为新左节点的 key 对应的旧节点索引

idxInOld = isDef(newStartVnode.key)
  ? oldKeyToIdx[newStartVnode.key]
  : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx);
复制代码


一起看看当新节点没有 key 的时候,findIdxInOld 函数的逻辑,返回第一个可以复用的旧节点

function findIdxInOld (node, oldCh, start, end) {
  for (let i = start; i < end; i++) {
    const c = oldCh[i]
    // 返回第一个可以复用的旧节点(旧节点的key也一定会是null)
    if (isDef(c) && sameVnode(node, c)) return i
  }
}
复制代码


如果未找到 key 可复用的节点索引,则创建新的节点,移动到旧左节点(oldStartVnode.elm)之前

if (isUndef(idxInOld)) {
  // New element
  createElm(
    newStartVnode,
    null,
    parentElm,
    oldStartVnode.elm
  );
}
复制代码


如果找到 key 对应的旧节点,还要通过 sameVnode 再判断是否真正可复用,不可复用则还是创建新节点。确认 key 对应的旧节点可复用,为旧节点打补丁,旧节点数组元素设置为  null(这也是第一步要判断是否为 null 的原因),同时将旧节点移动到旧左节点(oldStartVnode.elm)之前


vnodeToMove = oldCh[idxInOld];
if (sameVnode(vnodeToMove, newStartVnode)) {
  patchVnode(vnodeToMove, newStartVnode);
  oldCh[idxInOld] = undefined;
  nodeOps.insertBefore(
    parentElm,
    vnodeToMove.elm,
    oldStartVnode.elm
  );
} else {
  // same key but different element. treat as new element
  createElm(newStartVnode, insertedVnodeQueue, parentElm);
}
复制代码


最后完成本步逻辑,向内移动指针

newStartVnode = newCh[++newStartIdx];
复制代码

  1. 执行完上边遍历程序之后,跳出循环

  2. 如果旧节点已经遍历完,则批量向后添加剩余新节点
if (oldStartIdx > oldEndIdx) {
  refElm = isUndef(newCh[newEndIdx + 1])
    ? null
    : newCh[newEndIdx + 1].elm;
  addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx);
}
复制代码

  1. 如果新节点已经遍历完,则批量删除剩余旧节点
if (newStartIdx > newEndIdx) {
  removeVnodes(oldCh, oldStartIdx, oldEndIdx);
}
复制代码


至此,updateChildren 的逻辑也就讲完了,其中的难点在于分类判断的情况比较多,而其精髓在于指针(索引)的移动。


温馨提示:insertBefore 方法是可以移动节点的,它会删除原节点,大家可以看看MDN的说明

举个例子

下面我们举个栗子看看

我们假定所有节点都有对应的 key 属性(值和字母对应)

102.png


  1. 对比左节点 A === A 可复用,向右移动指针


103.png

  1. 对比节点 B === B 可复用,将 B 移动 D 之前,向内移动指针


103.png

  1. C 找不到复用节点,在 D 之前创建新节点,同时移动指针

104.png


  1. 不满足循环条件,跳出循环
  2. 根据 oldStartIdx oldEndIdx 删除旧节点 D F G

105.png


总结

Diff 的原理其实比较简单,就是同层比较复用性。但是如何比较同层节点复用性的逻辑上还是比较繁多的,需要我们化繁为简,自然就能看懂。上面的分析可能会有错误的地方,欢迎大家指出。大家新年快乐!


参考



相关文章
|
2月前
|
算法
算法题(8)
算法题(8)
12 4
|
11月前
|
算法
算法有穷性
算法有穷性
208 2
|
算法 数据安全/隐私保护
《算法》世界 二
一.算法要素 1.数据对象的运算和操作:计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合,成为该计算机系统的指令系统。一个计算机的基本运算和操作有如下四类: 1.算术运算:加减乘除等运算 2.逻辑运算:或、且、非等运算 3.关系运算:大于、小于、等于、不等于等运算 4.数据传输:输入、输出、赋值等运算 2.算法的控制结构:一个算法的功能结构不仅取决于所选用的操作,而且还与各操作之间的执行顺序有关。
170 1
《算法》世界 二
|
机器学习/深度学习 算法 TensorFlow
秒懂算法 | RIB算法
结合微观行为序列的推荐(recommendation with sequences of micro behaviors, RIB)在物品序列的基础上,加入了对异构行为和停留时间的建模。对异构行为的建模使得模型能够捕捉更加细粒度的用户兴趣,而用户在某个页面上的停留时间则反映了用户对这个页面的感兴趣程度,并且停留时间越长,购买商品的转化率通常也会越高。
261 0
秒懂算法 | RIB算法
|
算法
A*算法
A*算法
233 0
A*算法
|
算法 索引
紫书之子集生成三种算法
紫书之子集生成三种算法
紫书之子集生成三种算法
|
算法
【算法之初步认识】
【算法之初步认识】
143 0
【算法之初步认识】
|
人工智能 算法
什么是算法?
当人们提到“算法”一词,往往就会把它们当成专属于“人工智能”的范畴,很多专业的计算机人士也是,提起算法就头疼,不知道如何学习算法,慢慢的对算法就会失去兴趣,算法不仅仅是计算机行业特有的,在我们的生活中也处处存在着算法,算法是专注于解决问题的过程和方法。
180 1
什么是算法?
算法硬算能提升多少
解决一个问题,想到一个方法,设计个对应的模型,开始训练吧。。。。 是这个思路没错吧(别较真,较真你就输了。) 然后就是慢长的等待,2天,3天。。。 transformer的WMT训练了3.5天,几天的训练是家常便饭了现在。
808 0
|
算法 C++ 编译器