认识
一、认识
Vue.js 3.0 采用的是 双端对比 + 快速 Diff 算法。
一、单节点 Diff: newVNode 为对象, 说明为单节点, 进行单节点 Diff。通过 key 和 type 来决定是否复用、更新或销毁单个节点。
二、多节点 Diff: newVNode 为数组, 说明为多节点, 进行多节点 Diff。
-
双端快速比对, 先从左和右两端比对, 快速处理没有变化的部分。首先进行预处理, 从左往右进行比对,寻找相同的前置节点,再从右往左进行比对，寻找相同的后置节点。相同的前置节点和后置节点，它们的相对位置不变，只需要在它们之间打补丁即可。这种双端扫描能够快速跳过那些在前后都没有发生变化的部分，从而减少需要进一步比对的节点数。在双端对比之后, 剩下的部分（中间未匹配的节点）需要更精细的对比。
-
中间部分比对, 紧接着挂载新增节点和删除旧节点，最后锁定中间乱序的部分, 遍历剩余新节点。处理过程如下: 1. 为剩余的新节点构建
key-to-newIndex映射，方便快速定位。2. 遍历旧节点, 尝试找到在新节点中的位置, 如果旧节点在新节点中找不到，则卸载它, 如果能找到，则记录其在新数组中的位置到一个数组中, 利用 最长递增子序列 算法从记录的索引数组中找出最长递增序列, 那些节点在新节点中的位置如果是递增的，则不需要移动, 其余需要移动。3. 如果新节点剩余数量大于旧节点，则说明有新增的节点，直接依次调用patch(null, newVNode)创建并插入DOM, 如果旧节点剩余数量大于新节点，则依次卸载多余的旧节点。
二、节点结构
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-
如果已匹配的节点数
>=需要匹配的节点数, 卸载当前节点, 继续遍历下一个节点 -
根据旧节点, 寻找当前旧节点, 在新节点中的具体位置
newIndex, 并通过maxNewIndexSoFar记录最大的newIndex-
如果当前旧节点存在
key, 直接通过keyToNewIndexMap[key]即可得到在新节点中的位置 -
如果当前旧节点不存在
key, 需要循环遍历剩余的新节点, 得到旧节点在新节点中的位置
-
-
如果
newIndex不存在, 即当前旧节点在新节点中不存在, 那么卸载旧节点即可; 如果newIndex存在-
则
keyToNewIndexMap[newIndex - 剩余新节点的开始位置] = 当前旧节点下标 i + 1。 备注:newIndex - 剩余新节点的开始位置是为了不去处理已经处理好的新节点;当前旧节点下标 i + 1是为了说明新节点中是存在旧节点的, 且不能等于0 -
如果
newIndex >= maxNewIndexSoFar说明是递增序列, 更新maxNewIndexSoFar -
如果
newIndex < maxNewIndexSoFar说明有节点需要移动, 将move变量置为true -
调用
patch更新比对新老节点
-
-
-
3: 剩余旧节点遍历完毕后, 移动和挂载新节点
-
根据
move = true变量, 通过newIndexToOldIndexMap得到一个最长递增子序列的下标数据 -
循环遍历待处理的新节点:
-
判断循环的下标是否被上述的数组
newIndexToOldIndexMap进行收集了，如果没被收集到则说明这个新节点需要进行创建 -
如果已经被收集了则判断该循环的下标是否在上面计算得到的最长递增子序列中，如果不在则需要对该循环节点进行移动操作。
-
-
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.5 为什么 Vue 不需要使用 Fiber 或者 时间分片?
-
首先时间分片是为了解决
CPU进行大量计算的问题，因为React本身架构的问题，在默认的情况下更新会进行过多的计算，就算使用React提供的性能优化API，进行设置，也会因为开发者本身的问题，依然可能存在过多计算的问题。 -
Vue通过响应式依赖跟踪，在默认的情况下可以做到只进行组件树级别的更新计算，而默认下React是做不到的（据说React已经在进行这方面的优化工作了），再者Vue是通过template进行编译的，可以在编译的时候进行非常好的性能优化，比如对静态节点进行静态节点提升的优化处理，而通过JSX进行编译的React是做不到的。 -
React为了解决更新的时候进行过多计算的问题引入了时间分片，但同时又带来了额外的计算开销，就是任务协调的计算，虽然React也使用最小堆等的算法进行优化，但相对Vue还是多了额外的性能开销，因为Vue没有时间分片，所以没有这方面的性能担忧。 -
根据研究表明，人类的肉眼对
100毫秒以内的时间并不敏感，所以时间分片只对于处理超过100毫秒以上的计算才有很好的收益，而Vue的更新计算是很少出现100毫秒以上的计算的，所以Vue引入时间分片的收益并不划算。
5.6 React Diff Vs Vue2.0 Diff Vs Vue3.0 Diff
React: 在进行 Diff 对比时, 通过对比 ReactElement 数组 与 Fiber 单链表, Fiber 结构方便快速访问父、子和兄弟节点, 但因为没有直接引用前一个节点, 只能从左到右依次比对, 无法实现双端对比。 从头到尾逐一对比新旧节点, 处理第一轮循环剩余的节点, React 需要把 Old Fiber 处理 old Fiber Key - to - Old Fiber 的 Map 数据结构。判断移动的逻辑为: 通过新节点的 key 在 Map 中查找是否存在对应的旧 Fiber。如果找到, 就说明这个节点理论上可以复用。每个旧节点都有一个原始位置索引（oldIndex）, React 会将这个 oldIndex 与之前记录的 lastPlacedIndex 进行比较, 如果 oldIndex >= lastPlacedIndex, 说明这个节点在旧列表中的顺序保持相对正确, 不需要移动。然后更新 lastPlacedIndex 为当前 oldIndex。如果 oldIndex < lastPlacedIndex, 则说明该节点在旧列表中的位置比前面复用的节点要早, 意味着新节点在当前的位置上与旧节点的顺序已经发生逆转, 即需要进行移动操作。React 因为是通过 JSX 进行编译的，是无法进行静态节点分析的，所以 React 在对静态节点处理这一块是要逊色的。
Vue2.0: 在进行 Diff 对比时, 通过对比新旧 VNode 数组。进行双端对比, 先进行首尾、首首、尾尾部分的处理，然后再进行中间复杂部分的处理。处理第一轮循环剩余的节点, 剩余旧节点构建 oldVNode.key - to - oldVNode.index 的 Map 映射结构。Vue 是通过 template 模版进行编译的，所以在编译的时候可以很好对静态节点进行分析然后进行打补丁标记，然后在 Diff 的时候，Vue2 是判断如果是静态节点则跳过过循环对比
Vue3.0: 在进行 Diff 对比时, 通过对比新旧 VNode 数组。进行双端对比, 先处理首尾部分，然后再处理中间复杂部分。处理第一轮循环剩余的节点, 构建 newVNode.key - to - newVNode.index 的剩余节点映射 Map。判断移动的逻辑为: 遍历旧节点, 尝试找到在新节点中的位置, 如果旧节点在新节点中找不到，则卸载它, 如果能找到，则记录其在新数组中的位置到一个数组中, 利用 最长递增子序列 算法从记录的索引数组中找出最长递增序列, 那些节点在新节点中的位置如果是递增的，则不需要移动, 其余需要移动。由于 Vue 是通过 template 模版进行编译的，所以在编译的时候可以很好对静态节点进行分析然后进行打补丁标记，然后在 Diff 的时候, Vue3 则是把整个静态节点进行提升处理，Diff 的时候是不过进入循环的，所以 Vue3 比 Vue2 的 Diff 性能更高效。
React、Vue2.0、Vue3.0 都采用了 Map 来优化移动检测, 计算查找和比较, 来高效判断哪些节点需要移动。