Vuejs设计与实现 —— 渲染器核心 Diff 算法(上)

简介: Vuejs设计与实现 —— 渲染器核心 Diff 算法

image.png

前言

当组件发生更新时会重新执行 render 方法生成新的 vnode 节点,而当 新旧vnode 都是 一组节点 时,为了以最小的性能开销完成 更新操作,需要比较两组子节点,其中用于比较的算法就叫 Diff 算法。Vue 中的 Diff 算法实际上也是一个逐步演进的过程,那么下面就来看看它是如何演进、优化成如今的 Diff 算法的。

简单 diff 算法

在进行 新旧 两组子节点的更新时,去遍历 新旧 一组子节点中 长度较短 的一组,目的是为了尽可能多的调用 pacth 函数进行更新。

理想状态

理想状态 指新旧一组节点中 新旧节点前后位置没有发生变化.

在这个前提下新的一组节点可以比旧的一组子节点多、少或相等:

  • 新旧 一组节点的中 较短 的一组长度,作为公共长度 commonLength
  • 通过以 commonLength 作为循环结束的条件,通过 patch 函数对当前遍历到的 新旧 进行 pacth 更新操作
  • 新旧 一组节点的长度一致,那么意味着其全部是 更新操作
  • commonLength 长度后的,就代表是属于其他多余的节点,这个多余的节点会根据 新旧 的具体情况进行不同的处理:
  • 新的 一组子节点有剩余,则代表有新的节点需要 挂载,通过 patch 函数进行挂载操作
  • 旧的 一组子节点有剩余,则代表有旧的节点需要 卸载,通过 unmount 进行卸载操作

image.png

非理想状态

非理想状态 指的是 新旧 一组子节点中相 同位置节点不相同.

此时简单 diff 算法仍然会以 commonLength 进行遍历,并通过 patch(n1, n2) 的方式去更新,但在 pacth 函数中由于 n1n2 节点不是相同节点,此时会直接将 旧节点 进行 卸载,然后将 新节点 进行 挂载 操作,哪怕是当前 新旧 一组节点中在不同位置有相同的节点可复用,但简单 diff 算法完全不知道是否有可复用的节点,它完全是依赖于 pacth 来判断当前新旧节点是否是相同的节点。

image.png

小结

显然,简单 diff 算法下课通过减少 DOM 操作的次数,提升了一定的更新性能,但在非理想状态下,其更新方式和简单直接的更新方式一致:即卸载旧节点、挂载新节点,这意味着它仍然有被优化的空间。

基于 key 的简单 diff 算法

上述算法的缺陷在于 非理想状态diff 的过程仍然比较固定,即只能比较同位置的节点是否一致,那么优化的方式也是显而易见,只需要引入 key 用来标识 新旧一组子节点中 是否存在相同 key 的节点,若存在则复用 真实 DOM 节点,即更新和移动 DOM 节点即可。

image.png

核心

  • 通过遍历 新的一组 子节点中的节点,去 旧的一组 子节点中基于 key 寻找可复用的节点,找到可复用节点进行 patch更新
  • 根据 lastIndex 决定是否要进行 移动
  • find 变量为 false 时认为当前节点是需要进行 挂载
  • 最后在通过 从旧节点中依次查找新节点中去查找,通过 has 变量判断是否需要进行 卸载

以下是简单的伪代码实现:

function patchChildren(n1, n2, container) {
  if (typeof n2 === "string") {
    // 省略代码
  } else if (Array.isArray(n2.children)) {
    const oldChildren = n1.children; // 旧的一组子节点
    const newChildren = n2.children; // 新的一组子节点
    let lastIndex = 0; // 用于判断当前节点移动的位置
    // 遍历新的一组子节点:更新、移动、挂载
    for (let i = 0; i < newChildren.length; i++) {
      const newVnode = newChildren[i];
      let find = false; // 标识是否能在旧的一组子节点中找到可复用的节点
      let j = 0;
      // 遍历旧的一组子节点
      for (j; j < oldChildren.length; j++) {
        const oldVnode = oldChildren[j];
        // 根据 key 判断是否是相同节点,及是否可复用
        if (newVnode.key === oldVnode.key) {
          find = true;
          // 通过 patch 进行【更新】
          patch(oldVnode, newVnode, container);
          // 若 j < lastIndex 的值,表示需要【移动】
          if (j < lastIndex) {
            // 获取当前节点对应的上一个 preVnode 节点
            const preVnode = newChildren[i - 1];
            // 若上一个 preVnode 节点不存在,则表示当前 vnode 是头节点
            if (preVnode) {
              // 获取上一个节点对应的 preVnode 对应的真实 DOM 的下一个兄弟元素作为锚点元素
              const anchor = preVnode.el.nextSibling;
              // 移动操作
              insert(newVnode.el, container, anchor);
            }
          } else {
            lastIndex = j;
          }
          break;
        }
      }
      // 若 find 仍然为 false,则意味着没有可复用节点
      // 即当前的 newVnode 节点需要被【挂载】
      if (!find) {
        // 挂载也需要挂载到正确的位置,因此需要锚点元素
        const preVnode = newChildren[i - 1];
        let anchor = null;
        if (preVnode) {
          // 若存在前一个 newVnode 节点,则将其真实 DOM 对应的下一个兄弟元素,作为锚点元素
          anchor = preVnode.el.nextSibling;
        } else {
          // 若不存在前一个 newVnode 节点,则将容器节点中的第一个子元素,作为锚点元素
          anchor = container.firstChild;
        }
        // 基于锚点元素挂载新节点
        patch(null, newVnode, container, anchor);
      }
    }
    // 遍历旧的一组子节点:卸载多余旧节点
    for (let i = 0; i < oldChildren.length; i++) {
        // 当前旧节点
        const oldVnode = oldChildren[i];
        // 拿旧的子节点 oldVnode 去新的一组子节点中寻找具有相同 key 值的节点
        const has = newChildren.find(vnode => vnode.key === oldVnode.key);
        // 若没有找到相同 key 的节点,则说明需要删除或卸载当前旧节点
        if(!has){
            unmount(oldVnode);
        }
    }
  } else {
    // 省略代码
  }
}
复制代码

小结

实际上 diff 操作的目的是 更新、移动、挂载、卸载 的过程,基于 key 可以在 新旧一组子节点 中尽可能找到可复用节点,即尽可能的通过 DOM 移动操作来完成更新,避免过多地对 DOM 元素进行销毁和重建。

虽然实现了尽可能复用 DOM 节点,但是上述算法对 DOM移动操作 仍然不是最优的,其中 lastIndex 记录的是 旧的一组子节点中上次被更新的索引位置

  • 理论上只需要移动依次 DOM 即可完成更新,即只需要将旧 p3 节点移动到末尾节点即可
  • 而事实上基于以上算法,使得其移动方式并不是最优的,导致了旧 p1p2 节点对应的真实 DOM 节点被移动

image.png

双端 Diff 算法

双端 Diff 算法是一种同时对新旧两组子节点的两个端点进行比较的算法.

这是在实践中总结出来的,通常在一组子节点中对基于两端的操作是比较常见的,因此可以基于这样的假设去尽量减少每个新节点都要通过遍历一次旧的一组子节点的操作。

核心

只要 命中 以下 四种假设,则可以直接通过 patch() 进行 更新

  • 旧的头结点 等于 新的头结点,不需移动
  • 旧的尾节点 等于 新的尾节点,不需移动
  • 旧的头结点 等于 新的尾结点,需要移动
  • 旧的尾节点 等于 新的头节点,需要移动不能命中 这四种假设,那么仍然需要基于 key 通过遍历找到 当前新节点老的一组子节点 中的位置索引:
  • 若在老的一组子节点中 找到 当前新节点
  • 同一节点,则通过 pacth() 进行 更新
  • 不是 同一节点(key 相同,但节点类型不同),则视为新元素,并进行 挂载 操作
  • 若在老的一组子节点中 没有找到 当前新节点,则意味着当前新节点需要进行 挂载 操作 当 老节点 或者 新节点 被遍历完了,就需要对剩余的节点进行操作:
  • oldStartIdx > oldEndIdx 表示 老节点遍历完成,若 新节点有剩余,则说明剩余的节点是新增的节点,需要进行挂载 操作
  • newStartIdx > newEndIdx 表示 新节点遍历完成,若 老节点有剩余,则说明剩余部分节点需要被删除,需要进行 卸载 操作

优势

与基于 key 的简单 diff 算法相比,在相同情况下,原来简单 diff 算法需要两次移动 DOM 操作才能完成的更新,双端 diff 算法只需要一次 DOM 移动即可完成更新:

  • 第一次比较 命中假设 4,即 oldChildren[oldEndIdx] === newChildren[newStartIdx],需要通过 pacth 进行 更新,并将当前旧尾节点对应的 DOM 元素 移动 到旧头结点之前
  • 此时 oldEndIdx 需要 -1,而 newStartIdx 需要 +1
  • 第二次比较 命中假设 1,即 oldChildren[oldStartIdx] === newChildren[newStartIdx],由于此时属于新旧头结点相同,只需要通过 pacth 进行 更新 即可
  • 此时 oldStartIdxnewStartIdx 都需要 +1
  • 第二次比较 命中假设 1,即 oldChildren[oldStartIdx] === newChildren[newStartIdx],由于此时属于新旧头结点相同,只需要通过 pacth 进行 更新 即可
  • 此时 oldStartIdxnewStartIdx 都需要 +1
  • 最后,由于不满足循环条件 oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx 跳出循环,双端 diff 结束
  • image.png

Vue2 中对应源码

/*
   diff 过程:
     diff 优化:
               1. 四种假设:
                          newStart === oldStart
                          newEnd === oldEnd
                          newStart === oldEnd
                          newEnd === oldStart
               2. 假设新老节点开头结尾有相同节点的情况: 
                - 一旦命中假设,就避免了一次循环,以提高执行效率
                - 如果没有命中假设,则执行遍历,从老节点中找到新开始节点
                  找到相同节点,则执行 patchVnode,然后将老节点移动到正确的位置
     如果老节点先于新节点遍历结束,则剩余的新节点执行新增节点操作
     如果新节点先于老节点遍历结束,则剩余的老节点执行删除操作,移除这些老节点
  */
  function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
    // 老节点的开始索引
    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
    // removeOnly 是一个特殊的标志,仅由 <transition-group> 使用,
    // 以确保被移除的元素在离开转换期间保持在正确的相对位置
    const canMove = !removeOnly
    if (process.env.NODE_ENV !== 'production') {
      // 检查新节点的 key 是否重复
      checkDuplicateKeys(newCh)
    }
    // 遍历新老两组节点,只要有一组遍历完(开始索引超过结束索引)则跳出循环
    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)) {
        // 老开始节点和新开始节点是同一个节点,执行 patch
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        // patch 结束后老开始和新开始的索引分别加 1,开始下一个节点
        oldStartVnode = oldCh[++oldStartIdx]
        newStartVnode = newCh[++newStartIdx]
      } else if (sameVnode(oldEndVnode, newEndVnode)) {
        // 老结束和新结束是同一个节点,执行 patch
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        // patch 结束后老结束和新结束的索引分别减 1,开始下一个节点
        oldEndVnode = oldCh[--oldEndIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
        // 老开始和新结束是同一个节点,执行 patch
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
        // 处理被 transtion-group 包裹的组件时使用
        canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
        // patch 结束后老开始索引加 1,新结束索引减 1,开始下一个节点
        oldStartVnode = oldCh[++oldStartIdx]
        newEndVnode = newCh[--newEndIdx]
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
        // 老结束和新开始是同一个节点,执行 patch
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
        canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
        // patch 结束后,老结束的索引减 1,新开始的索引加 1,开始下一个节点
        oldEndVnode = oldCh[--oldEndIdx]
        newStartVnode = newCh[++newStartIdx]
      } else {
        // 如果上面的四种假设都不成立,则通过遍历找到新开始节点在老节点中的位置索引
        // 找到老节点中每个节点 key 和 索引之间的关系映射:
        // 如 oldKeyToIdx = { key1: idx1, ... }
        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, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
        } else {
          // 在老节点中找到新开始节点了
          vnodeToMove = oldCh[idxInOld]
          if (sameVnode(vnodeToMove, newStartVnode)) {
            // 如果这两个节点是同一个,则执行 patch
            patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
            // patch 结束后将该老节点置为 undefined
            oldCh[idxInOld] = undefined
            canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
          } else {
            // same key but different element. treat as new element
            // 最后这种情况是,找到节点了,但是发现两个节点不是同一个节点,
            // 则视为新元素,执行创建
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
          }
        }
        // 老节点向后移动一个
        newStartVnode = newCh[++newStartIdx]
      }
    }
    // 走到这里,说明老节点或者新节点被遍历完了
    if (oldStartIdx > oldEndIdx) {
      // 老节点被遍历完了,新节点有剩余,则说明这部分剩余的节点是新增的节点,然后添加这些节点
      refElm = isUndef(newCh[newEndIdx + 1]) ? null : newCh[newEndIdx + 1].elm
      addVnodes(parentElm, refElm, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else if (newStartIdx > newEndIdx) {
      // 新节点被遍历完了,老节点有剩余,说明这部分的节点被删掉了,则移除这些节点
      removeVnodes(oldCh, oldStartIdx, oldEndIdx)
    }
  }


目录
打赏
0
0
0
0
2
分享
相关文章
Figma-Low-Code:快速将Figma设计转换为Vue.js应用,支持低代码渲染、数据绑定
Figma-Low-Code 是一个开源项目,能够直接将 Figma 设计转换为 Vue.js 应用程序,减少设计师与开发者之间的交接时间,支持低代码渲染和数据绑定。
355 3
Figma-Low-Code:快速将Figma设计转换为Vue.js应用,支持低代码渲染、数据绑定
|
9月前
|
Vue 中的 Diff 算法
【10月更文挑战第18天】需要注意的是,Diff 算法虽然能够提高性能,但在某些复杂的场景下,可能仍然会存在一些性能瓶颈。因此,在实际开发中,我们需要根据具体情况合理地使用 Diff 算法,并结合其他优化手段来提高应用的性能。
131 56
Vue 异步渲染
【10月更文挑战第23天】Vue 异步渲染是提高应用性能和用户体验的重要手段。通过理解异步渲染的原理和优化策略,我们可以更好地利用 Vue 的优势,开发出高效、流畅的前端应用。同时,在实际开发中,要注意数据一致性、性能监控和调试等问题,确保应用的稳定性和可靠性。
Diff 算法的实现原理
【10月更文挑战第18天】Diff 算法是 Vue.js 中实现高效 DOM 更新的核心机制,通过合理的比较和优化策略,能够在保证界面正确性的同时,最大程度地减少 DOM 操作,提高应用的性能和用户体验。
200 2
vue 中diff算法
【10月更文挑战第10天】
120 1
机器人路径规划和避障算法matlab仿真,分别对比贪婪搜索,最安全距离,RPM以及RRT四种算法
本程序基于MATLAB 2022A实现机器人路径规划与避障仿真,对比贪婪搜索、最安全距离、RPM和RRT四种算法。通过地图模拟环境,输出各算法的路径规划结果,展示其在避障性能与路径优化方面的差异。代码包含核心路径搜索逻辑,并附有测试运行图示,适用于机器人路径规划研究与教学演示。
111 64
基于精英个体保留策略遗传优化的生产调度算法matlab仿真
本程序基于精英个体保留策略的遗传算法,实现生产调度优化。通过MATLAB仿真,输出收敛曲线与甘特图,直观展示调度结果与迭代过程。适用于复杂多约束生产环境,提升资源利用率与调度效率。
基于FPGA的图像退化算法verilog实现,分别实现横向和纵向运动模糊,包括tb和MATLAB辅助验证
本项目基于FPGA实现图像运动模糊算法,包含横向与纵向模糊处理流程。使用Vivado 2019.2与MATLAB 2022A,通过一维卷积模拟点扩散函数,完成图像退化处理,并可在MATLAB中预览效果。
|
24天前
|
基于BigBangBigCrunch优化(BBBC)的目标函数求解算法matlab仿真
本程序基于BigBang-BigCrunch优化算法(BBBC)实现目标函数求解的MATLAB仿真,具备良好的全局搜索与局部收敛能力。程序输出适应度收敛曲线及多变量变化曲线,展示算法迭代过程中的优化趋势。使用MATLAB 2022A运行,通过图形界面直观呈现“大爆炸”与“大坍缩”阶段在解空间中的演化过程,适用于启发式优化问题研究与教学演示。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问