Vue3对patch(diff)的优化
before:源码地址:
这里我会直接拿 github 上的源码进行讲解:文件地址
看本文的小老弟可以打开 github 对比,也可以看我粘贴的关键部分代码。出于篇幅考虑,在这篇文章我会删减很多东西。所以推荐还是打开上面的链接看比较好。
本文重点在 section3,性子比较急的小老弟可以直接跳到那里。
section1:大体思路
- 找出不同节点部分
- 处理仅需要子节点新增与移除的情况
- 处理不可复用子节点的新增或删除
- 利用最长递增子序列优化可复用子节点的移动
section2:入口
先来看 patch 函数做了什么吧:(部分代码省略)
1 |
|
简单说说 patch 函数做了什么:
- 判断新老 vnode 的 tag 是否相同,如果不相同没有继续比较的意义,直接替换掉老的 vnode 的真实 DOM
- 根据新 vnode 的 type 来判断如何做出相应的处理
因为 vnode 的 tag 相同,可能是 DOM 元素也可能是组件,这里我们假设先不考虑组件的处理。因为需要降低文章的复杂度,让读者更专注于 patch 算法的本身而不去拘泥于细节,并且 processComponent 本身的思想也很简单:
1 |
|
如果不是第一次加载组件则 updateComponent:
1 |
|
这里使用了一个内置的 shouldUpdateComponent 控制组件是否刷新。此下不去过多展开了。
真正需要注意的仅仅有 processElement 这个方法。
processElement 这个方法很简单了,就是做个判断,然后调用真正的对元素的 patch 方法,patchElement
1 |
|
其实看过 Vue2 感觉这些和 Vue2 还是蛮像的,所以这里不做多啰嗦,继续找 patchElement:
1 |
|
这里,包含了对 props 的 patch 优化和对 children 节点的 patch 方案。
diff 的比较与复用是针对子元素的,这个 patchChildren 显然是个重点,继续往下看:
1 |
|
对于 children 的 patch 过程分别有两个方案,分别为 keyed 与 unkeyed
keyed 很好理解,就是可以存在复用的节点,比如 ul>li*n。而 unkeyed 节点显然是那些正常节点。优化的核心点显然是那些 keyed 的子节点。而下面 patchKeyedChildren 也就是真正的 Vue3 的 diff 算法的核心。
section3 核心
源码里这里的注释写的真的很棒,但是考虑读者的水平不同,我们仍然分步骤来看一下:
1 |
|
先从前向后查找第一个不可以复用的子节点,并用 i 记录这个子节点的下标:
1 |
|
然后从后向前找到不可以复用的子节点下标。这里,因为 c1 和 c2 的长度可能有所不同,所以使用 e1 和 e2 两个变量分别记录这两个数组中不可直接复用的节点下标:
接下来有两种比较容易处理的情况:
- 总顺序不变但新增了节点
- 总顺序不变但减少了节点
第一种情况很容易想到,如图:
这种情况只要把新增的节点生成挂载就好了。
看代码:
1 |
|
另一种情况就更容易了:
这种情况只要把多余的节点卸掉就好了:
1 |
|
继续,方便处理的已经结束了,下面对无序节点进行处理喽:
如下情况:
到了这步显然只需要处理 i -> e1(e2)部分的所有无须子节点的复用即可。
分三步:
构建一个 key -> index 的列表,用来确认 c1 是否在 c2 中有对应节点可供复用,并映射其位置
1
2
3
4
5
6
7
8
9
10
11const s1 = i; // prev starting index
const s2 = i; // next starting index
const keyToNewIndexMap: Map<string | number, number> = new Map();
for (i = s2; i <= e2; i++) {
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]));
if (nextChild.key != null) {
keyToNewIndexMap.set(nextChild.key, i);
}
}利用上面的映射表做一次 DOM 处理,这里主要为了下面的优化处理,将所有不可以复用的节点卸载,需要的地方我写了注释。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56let j;
let patched = 0;
const toBePatched = e2 - s2 + 1; // 待处理的c2无序部分的长度
let moved = false;
let maxNewIndexSoFar = 0;
// used for determining longest stable subsequence
// 这个列表是用来映设c2中的节点对应(c1中节点的位置 + 1)
const newIndexToOldIndexMap = new Array(toBePatched).fill(0);
for (i = s1; i <= e1; i++) {
const prevChild = c1[i];
if (patched >= toBePatched) {
// 性能优化,c1多余旧节点全部移除
unmount(prevChild, parentComponent, parentSuspense, true);
continue;
}
let newIndex;
if (prevChild.key != null) {
// 有key元素直接获取key对应的新vnode的index
newIndex = keyToNewIndexMap.get(prevChild.key);
} else {
// 无key旧vnode尝试匹配到一个可以复用的无key新vnode
for (j = s2; j <= e2; j++) {
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j] as VNode)
) {
newIndex = j;
break;
}
}
}
if (newIndex === undefined) {
// 卸载key对应的节点已经不存在或无key的且无法复用的节点
unmount(prevChild, parentComponent, parentSuspense, true);
} else {
// 记录第新节点复用的老节点的idx + 1,用来做最大递增子序列
newIndexToOldIndexMap[newIndex - s2] = i + 1;
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex;
} else {
moved = true;
}
patch(
prevChild,
c2[newIndex] as VNode,
container,
null,
parentComponent,
parentSuspense,
isSVG,
optimized
);
patched++; // 计数,用来剪枝
}
}- 下面的才是戏肉,哦不对,肉戏:
这里面用了一个概念:最长递增子序列
可以先参考leetcode300。然后再看这段代码,这里显然是用了二分查找对时间复杂度优化到了 O(nlogn),如果做完上面的题目,这里就可以理解了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40function getSequence(arr: number[]): number[] {
const p = arr.slice();
const result = [0];
let i, j, u, v, c;
const len = arr.length;
for (i = 0; i < len; i++) {
const arrI = arr[i];
if (arrI !== 0) {
j = result[result.length - 1];
if (arr[j] < arrI) {
p[i] = j;
result.push(i);
continue;
}
u = 0; // start
v = result.length - 1; // end
while (u < v) {
c = ((u + v) / 2) | 0; // mid
if (arr[result[c]] < arrI) {
u = c + 1;
} else {
v = c;
}
}
if (arrI < arr[result[u]]) {
if (u > 0) {
p[i] = result[u - 1];
}
result[u] = i;
}
}
}
u = result.length;
v = result[u - 1];
while (u-- > 0) {
result[u] = v;
v = p[v];
}
return result; // 可以复用的老节点的idx数组
}吐槽一下这个命名,简直不要太随意。我看这几个字母总是混乱,到底是哪几个单词的首字母啊,抓狂 o(≧ 口 ≦)o。
利用 getSequence 获取了一个最大递增子序列每个节点的下标数组。
下面的即是整个优化的核心,先来想想为什么这里需要拿到这个数组?
如果可以确定最大递增子序列节点位置,只需要移动不属于最大递增子序列的节点,即可完成对 DOM 的转换。代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
j = increasingNewIndexSequence.length - 1
// looping backwards so that we can use last patched node as anchor
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i
const nextChild = c2[nextIndex] as VNode
const anchor =
nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
if (newIndexToOldIndexMap[i] === 0) {
// 无复用的直接patch就好了
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
isSVG
)
} else if (moved) {
// move if:
// There is no stable subsequence (e.g. a reverse)
// OR current node is not among the stable sequence
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, MoveType.REORDER)
} else {
j--
}
}
}
}这里可能比较抽象,所以我画了一组图片。此处,假设我们已经有了最长递增子序列,同时,这些节点都是需要进行移动复用的。如下:
从 newIndexToOldIndexMap 开始,发现这里有个复用同时在 increasingNewIndexSequence 的末尾,显然,这是个不需要移动的元素。i–, j–,如下:
到这里发现,i 位置的索引不等于 j 指向的值了,所以显然是需要进行位置的变换(move 的),可以看到根据 c2,在 c1 中将 E 会被插入节点 I 的前面,然后 i–,看图:
接下来,2,1 都在递增子序列中,所以不会进行移动,依然 i–,j–,直到下图情况:
此时,j < 0,直接对老节点进行位移即可,可以看到,需要将 F 节点插入 D 节点前面即可,看图:
可以看到,已经达到了 keyedChildren 的复用,且减少了大量无意义 DOM 操作。
section 4 总结
整体感觉不算应该很难,但是我发现 Vue3 的一个有趣的地方。它将 DOM 操作底层封装成了一些特定的函数存储在 vnode 上,显然我们可以自定义一些特殊的行为然后替换原有的 DOM 操作吼。
最后的递增子序列题解我放在下面,自以为我写的是最好理解的方法了。插个腰!<(ˉ^ˉ)>
就酱,本文结束。
section Afterword 题解
leetcode300:最大上升子序列长度
1 |
|
- 本文作者:herin
- 本文链接:https://kilicmu.github.io/2020/10/07/VUE3%E5%AF%B9PATCH-DIFF-%E7%9A%84%E4%BC%98%E5%8C%96/index.html
- 版权声明:本博客所有文章均采用 BY-NC-SA 许可协议,转载请注明出处!