跳到主要内容

认识

2024年03月14日
柏拉文
越努力，越幸运

一、认识​

Vue.js 3.0 采用的是快速 Diff 算法。首先进行预处理, 从左往右进行比对,寻找相同的前置节点,再从右往左进行比对，寻找相同的后置节点。相同的前置节点和后置节点，它们的相对位置不变，只需要在它们之间打补丁即可。紧接着挂载新增节点和删除旧节点，最后锁定中间乱序的部分。遍历剩余新节点, 构建以 newChild.key 为 key, 以当前遍历位置 i 为 value 的剩余新节点映射表。记录剩余新节点总数(待处理总数)、当前处理数、是否发生过移动、以新节点索引为 index旧节点索引为value的新旧节点索引数组, 初始值为 0。进行中间对比的删除逻辑: 遍历剩余老节点, 如果遍历过程中, 当前处理的数量大于等于待处理总数, 说明是多余节点, 当前旧节点标记删除。否则, 根据有无设置 oldChild.key , 有设置, 基于 oldChild.key 从剩余新节点映射表中查找对应新节点索引, 没有设置, 遍历所有剩余新节点。找出对应新节点索引, 如果索引存在, 则复用旧节点,打补丁,并将当前旧节点索引存储到新旧节点索引数组中, 不存在则删除旧节点。随后进行中间对比的移动逻辑: 根据最长递增子序列, 找出新旧节点索引数组中最长稳定序列, 在新旧节点的对比中, 在递增序列里面的旧节点不需要移动, 因此, 递增序列越长, 需要移动的旧节点越少。倒序遍历待处理新节点, 根据新节点索引查找新旧节点索引数组中是否对应旧节点, 如果没有对应旧节点, 新增新节点, 如果有对应旧节点, 并且稳定序列中没有该旧节点, 移动旧节点。

二、节点结构​

2.1 旧节点​

2.2 新节点​

2.3 新旧节点​

三、单节点细节​

3.1 key 相同 type 相同​

key 相同 type 相同, 复用当前旧节点

3.2 key 相同 type 不同​

key 相同 type 不同, 不存在任何复用的可能性, 删除所有旧节点

3.3 key 不同 type 相同​

key 不同 type 相同, 当前节点不可复用, 删除当前旧节点, 继续遍历

3.4 key 不同 type 不同​

key 不同 type 不同, 不存在任何复用的可能性, 删除所有旧节点

四、多节点细节​

4.1 从左往右​

[a,b,c] => [a,b,d,e,f]: 首先从左往右进行比对，寻找相同的前置节点。如果是相同节点, 调用patch 进行更新比对; 如果不相同则停止比对，并且记录停止的下标。 此时, 从左往右相同的情况处理完毕, 剩下右边不同的节点

// 1. 从左往右遍历 [a,b,c] => [a,b,d,e]
while (i <= e1 && i <= e2) {
      const n1 = c1[i];
      const n2 = c2[i];
      if (isSameVNodeType(n1, n2)) {
        patch(n1, n2, container, null);
      } else {
        break;
      }
      i++;
}

4.2 从右往左​

[a,b,c] => [d,e,f,b,c]: 再从右往左进行比对，寻找相同的后置节点。如果是相同节点, 调用patch 进行更新比对; 如果不相同也停止比对，也进行记录停止的下标。此时, 从右往左相同的情况处理完毕, 剩下左边不同的节点

// 2. 从右往左遍历
while (i <= e1 && i <= e2) {
      const n1 = c1[e1];
      const n2 = c2[e2];
      if (isSameVNodeType(n1, n2)) {
        patch(n1, n2, container, null);
      } else {
        break;
      }
      e1--;
      e2--;
}

通过这样左右进行比对，最后就可以把真正复杂部分进行范围锁定了。

4.3 新节点多于旧节点​

[a,b] => [a,b,c]: 如果旧节点已经比对完, 还存在新节点, 此时新节点多于旧节点, 依次循环挂载新节点

// 3. 新节点多于旧节点时, 挂载新节点
if (i > e1) {
      if (i <= e2) {
        const nextPos = e2 + 1;
        const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor;
        while (i <= e2) {
          patch(null, c2[i], container, anchor);
          i++;
        }
      }
}

4.4 旧节点多于新节点​

[a,b,c] => [a,b]: 如果新节点已经比对完, 还存在旧节点, 此时旧节点多于新节点, 依次循环删除旧节点

// 4. 旧节点多语新节点时, 卸载旧节点
else if (i > e2) {
    while (i <= e1) {
        unmount(c1[i]);
        i++;
    }
}

4.5 新旧节点乱序排序​

[a,b,c,d,e,f,g] => [a,b,e,d,c,h,f,g]: 如果新节点未比对完，老节点也未比对完，则进行最后最复杂的处理

  • 1: 为剩余新节点构建key (新节点的 key):index (新节点的索引)的Map => keyToNewIndexMap, 通过循环为 keyToNewIndexMap 新增元素（此时, 如果 key 不存在, 则忽略, 因此, v-for 时, key 属性非常重要）

  • 2: 循环遍历剩下的旧节点,尝试修补匹配节点并删除不存在的节点, 记录需要匹配的节点数和已匹配的节点数, 创建一个需要匹配节点数长度的数组 newIndexToOldIndexMap, 初始化每个数组的下标的默认值为 0

    1. 如果已匹配的节点数 >= 需要匹配的节点数, 卸载当前节点, 继续遍历下一个节点

    2. 根据旧节点, 寻找当前旧节点, 在新节点中的具体位置 newIndex, 并通过 maxNewIndexSoFar 记录最大的 newIndex

      • 如果当前旧节点存在 key , 直接通过 keyToNewIndexMap[key] 即可得到在新节点中的位置

      • 如果当前旧节点不存在 key , 需要循环遍历剩余的新节点, 得到旧节点在新节点中的位置

    3. 如果 newIndex 不存在, 即当前旧节点在新节点中不存在, 那么卸载旧节点即可; 如果 newIndex 存在

      1. 则 keyToNewIndexMap[newIndex - 剩余新节点的开始位置] = 当前旧节点下标 i + 1。 备注: newIndex - 剩余新节点的开始位置 是为了不去处理已经处理好的新节点; 当前旧节点下标 i + 1 是为了说明新节点中是存在旧节点的, 且不能等于 0

      2. 如果 newIndex >= maxNewIndexSoFar 说明是递增序列, 更新 maxNewIndexSoFar

      3. 如果 newIndex < maxNewIndexSoFar 说明有节点需要移动, 将 move 变量置为 true

      4. 调用 patch 更新比对新老节点

  • 3: 剩余旧节点遍历完毕后, 移动和挂载新节点

    1. 根据 move = true 变量, 通过 newIndexToOldIndexMap 得到一个最长递增子序列的下标数据

    2. 循环遍历待处理的新节点:

      1. 判断循环的下标是否被上述的数组 newIndexToOldIndexMap 进行收集了，如果没被收集到则说明这个新节点需要进行创建

      2. 如果已经被收集了则判断该循环的下标是否在上面计算得到的最长递增子序列中，如果不在则需要对该循环节点进行移动操作。

else {
      const s1 = i;
      const s2 = i;

      // 5.1 为**剩余新节点**构建`key (新节点的 key):index (新节点的索引)`的`Map` => `keyToNewIndexMap`
      const keyToNewIndexMap: Map<string | number | symbol, number> = new Map();
      for (i = s2; i <= e2; i++) {
        const nextChild = (c2[i] = normalizeVNode(c2[i]));
        if (nextChild.key != null) {
          keyToNewIndexMap.set(nextChild.key, i);
        }
      }

      // 5.2 循环遍历剩下的旧节点,尝试修补匹配节点并删除不存在的节点, 记录需要匹配的节点数和已匹配的节点数, 创建一个需要匹配节点数长度的数组 `newIndexToOldIndexMap`, 初始化每个数组的下标的默认值为 `0`
      let j;
      let patched = 0;
      const toBePatched = e2 - s2 + 1;
      let moved = false;
      let maxNewIndexSoFar = 0;
      const newIndexToOldIndexMap = new Array(toBePatched);
      for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0;

      for (i = s1; i <= e1; i++) {
        const prevChild = c1[i];
        if (patched >= toBePatched) {
          unmount(prevChild);
          continue;
        }
        let newIndex;
        if (prevChild.key != null) {
          newIndex = keyToNewIndexMap.get(prevChild.key);
        } else {
          for (j = s2; j <= e2; j++) {
            if (
              newIndexToOldIndexMap[j - s2] === 0 &&
              isSameVNodeType(prevChild, c2[j])
            ) {
              newIndex = j;
              break;
            }
          }
        }
        if (newIndex === undefined) {
          unmount(prevChild);
        } else {
          newIndexToOldIndexMap[newIndex - s2] = i + 1;
          if (newIndex >= maxNewIndexSoFar) {
            maxNewIndexSoFar = newIndex;
          } else {
            moved = true;
          }
          patch(prevChild, c2[newIndex], container, null);
          patched++;
        }
      }

      // 5.3 剩余旧节点遍历完毕后, 移动和挂载新节点
      const increasingNewIndexSequence = moved
        ? getSequence(newIndexToOldIndexMap)
        : [];
      j = increasingNewIndexSequence.length - 1;
      for (i = toBePatched - 1; i >= 0; i--) {
        const nextIndex = s2 + i;
        const nextChild = c2[nextIndex];
        const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor;
        if (newIndexToOldIndexMap[i] === 0) {
          patch(null, nextChild, container, anchor);
        } else if (moved) {
          if (j < 0 || i !== increasingNewIndexSequence[j]) {
            move(nextChild, container, anchor);
          } else {
            j--;
          }
        }
      }
}

4.6 最长递增子序列​

假设，我们有一个这样的两组节点:

旧节点: 1,2,3,4,5,6

新节点: 1,3,2,4,6,5

我们可以根据新节点生成递增子序列, 其结果为:

1. 1,3,6  => 旧节点需要移动 2 4 5 三个节点, 就可以跟新节点保持一致

2. 1,2,4,6 => 旧节点需要移动 3 5 两个节点, 就可以跟新节点保持一致

在新旧节点的对比中, 在递增序列里面的旧节点不需要移动, 因此, 递增序列越长, 需要移动的旧节点越少。因此, 最长递增子序列 可以在 Diff 中减少旧节点移动的次数。

五、思考​

5.1 Vue Diff 中 key 的作用?​

React Diff Key 作为新旧元素的唯一标识, 当对比新旧元素时, 首先要对比的就是 key 是否相同。如果 key 不相同或者 key 不存在, 那么认为此时的旧元素不可复用, 直接将旧元素删除, 随后重新创建 Fiber 节点。

5.2 Vue Diff 为什么不能用随机数做 key？​

通过随机数设定的 key, 则会产生无序性，可能会导致所有的 key 都匹配不上，然后舍弃掉之前所有构建出来的 fiber 节点，再重新创建新的节点。

5.3 Vue Diff 最好不要使用数组的下标做为 key ?​

数组下标相对随机数来说，比较稳定一些。但数组下标对应的组件并不是一成不变的，只要在数组的前面或者中间插入元素时，该下标对应的元素就发生变化。虽然 key 没变，但对应的元素已经发生变化了。但是在 Diff 时, key 相同, type 相同会复用旧元素, 导致元素渲染错误。

因此, 数组下标作为 key 的场景是: 只有则初始时渲染一次，后续不再更新列表，只是对某个具体元素进行更新或事件的处理等, 或者没有新增、删除操作等的列表。

5.4 React Diff 为什么不采用双端对比来优化呢?​

React Fiber 目前的结构如下:

// 指向父级Fiber节点
this.return = null;
// 指向子Fiber节点
this.child = null;
// 指向右边第一个兄弟Fiber节点
this.sibling = null;

React Diff 目前的对比方式是:

  • newChildren[i] 与 oldFiber 对比

  • newChildren[i++] 与 oldFiber.sibling 对比

从已上可以得知: Fiber 链表的数据结构的特点: 就是任何一个位置的 Fiber 节点，都可以非常容易知道它的父 Fiber, 第一个子元素的 Fiber,和它的兄弟节点 Fiber。却不容易知道它前一个 Fiber 节点是谁，这就是 React 中单向链表 Fiber 节点的特点。

React 不能通过双端对比进行 Diff 算法优化是因为目前 Fiber 上没有设置反向链表，而且想知道就目前这种方案能持续多久，如果目前这种模式不理想的话，那么也可以增加双端对比算法。

5.5 为什么 Vue 不需要使用 Fiber 或者 时间分片?​

  1. 首先时间分片是为了解决 CPU 进行大量计算的问题，因为 React 本身架构的问题，在默认的情况下更新会进行过多的计算，就算使用 React 提供的性能优化 API，进行设置，也会因为开发者本身的问题，依然可能存在过多计算的问题。

  2. Vue 通过响应式依赖跟踪，在默认的情况下可以做到只进行组件树级别的更新计算，而默认下 React 是做不到的（据说 React 已经在进行这方面的优化工作了），再者 Vue 是通过 template 进行编译的，可以在编译的时候进行非常好的性能优化，比如对静态节点进行静态节点提升的优化处理，而通过 JSX 进行编译的 React 是做不到的。

  3. React 为了解决更新的时候进行过多计算的问题引入了时间分片，但同时又带来了额外的计算开销，就是任务协调的计算，虽然 React 也使用最小堆等的算法进行优化，但相对 Vue 还是多了额外的性能开销，因为 Vue 没有时间分片，所以没有这方面的性能担忧。

  4. 根据研究表明，人类的肉眼对 100 毫秒以内的时间并不敏感，所以时间分片只对于处理超过 100 毫秒以上的计算才有很好的收益，而 Vue 的更新计算是很少出现 100 毫秒以上的计算的，所以 Vue 引入时间分片的收益并不划算。

六、React vs Vue2.0 vs Vue3.0​

6.1 相同点​

  1. 在进行更新 Diff 对比的时候，都是优先处理简单的场景，再处理复杂的场景。

  2. 在处理第一轮循环剩余的节点,都需要把节点处理 key - value 的 Map 数据结构，方便在往后的比对中可以快速通过节点的 key 取到对应的节点。同样在比对两个新老节点是否相同时，key 是否相同也是非常重要的判断标准。所以不同是 React, 还是 Vue，在写动态列表的时候，都需要设置一个唯一值 key，这样在 diff 算法处理的时候性能才最大化。

6.2 不同点​

  1. key - value 的 Map 结构:

  • React.js: 构建以 oldFiber.key 为 key, oldFiber 为 value 的 Map 结构

  • Vue.js 2.0: 剩余旧节点构建以 oldVNode.key 为 key, oldVNode 索引为 value 的 Map 结构

  • Vue.js 3.0: 遍历剩余新节点, 构建以 newChild.key 为 key, 以当前遍历位置 i 为 value 的剩余新节点映射表

  1. 处理逻辑: React 中是先处理左边部分，左边部分处理不了，再进行复杂部分的处理; Vue2 则先进行首尾、首首、尾尾部分的处理，然后再进行中间复杂部分的处理；Vue3 则先处理首尾部分，然后再处理中间复杂部分，Vue2 和 Vue3 最大的区别就是在处理中间复杂部分使用了最长递增子序列算法找出稳定序列的部分。

  2. 对静态节点的处理不一样: 由于 Vue 是通过 template 模版进行编译的，所以在编译的时候可以很好对静态节点进行分析然后进行打补丁标记，然后在 Diff 的时候，Vue2 是判断如果是静态节点则跳过过循环对比，而 Vue3 则是把整个静态节点进行提升处理，Diff 的时候是不过进入循环的，所以 Vue3 比 Vue2 的 Diff 性能更高效。而 React 因为是通过 JSX 进行编译的，是无法进行静态节点分析的，所以 React 在对静态节点处理这一块是要逊色的。

  3. 对比之后的更新时机: Vue2 和 Vue3 的比对和更新是同步进行的，这个跟 React15 是相同的，就是在比对的过程中，如果发现了那些节点需要移动或者更新或删除，是立即执行的，也就是 React 中常讲的不可中断的更新，如果比对量过大的话，就会造成卡顿，所以 React16 起就更改为了比对和更新是异步进行的，所以 React16 以后的 Diff 是可以中断，Diff 和任务调度都是在内存中进行的，所以即便中断了，用户也不会知道。

  4. 对比算法: Vue2 和 Vue3 都使用了双端对比算法，而 React 的 Fiber 由于是单向链表的结构，所以在 React 不设置由右向左的链表之前，都无法实现双端对比

参考资料​

为什么 React 的 Diff 算法不采用 Vue 的双端对比算法？