Vue3对patch(diff)的优化

before:源码地址:

这里我会直接拿 github 上的源码进行讲解:文件地址

看本文的小老弟可以打开 github 对比,也可以看我粘贴的关键部分代码。出于篇幅考虑,在这篇文章我会删减很多东西。所以推荐还是打开上面的链接看比较好。

本文重点在 section3,性子比较急的小老弟可以直接跳到那里。

section1:大体思路

  1. 找出不同节点部分
  2. 处理仅需要子节点新增与移除的情况
  3. 处理不可复用子节点的新增或删除
  4. 利用最长递增子序列优化可复用子节点的移动

section2:入口

先来看 patch 函数做了什么吧:(部分代码省略)

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
56
const patch: PatchFn = (
n1,
n2,
container
//...
) => {
// patching & not same type, unmount old tree
if (n1 && !isSameVNodeType(n1, n2)) {
anchor = getNextHostNode(n1);
unmount(n1, parentComponent, parentSuspense, true);
n1 = null;
}

const { type, ref, shapeFlag } = n2;
switch (type) {
case Text:
processText(n1, n2, container, anchor);
break;
case Comment:
processCommentNode(n1, n2, container, anchor);
break;
case Static:
if (n1 == null) {
mountStaticNode(n2, container, anchor, isSVG);
} else if (__DEV__) {
patchStaticNode(n1, n2, container, isSVG);
}
break;
case Fragment:
processFragment(
n1,
n2,
container
// ....
);
break;
default:
if (shapeFlag & ShapeFlags.ELEMENT) {
processElement(
n1,
n2,
container
//...
);
} else if (shapeFlag & ShapeFlags.COMPONENT) {
processComponent(
n1,
n2,
container
// ...
);
}
// ...
}
// ....
};

简单说说 patch 函数做了什么:

  1. 判断新老 vnode 的 tag 是否相同,如果不相同没有继续比较的意义,直接替换掉老的 vnode 的真实 DOM
  2. 根据新 vnode 的 type 来判断如何做出相应的处理

因为 vnode 的 tag 相同,可能是 DOM 元素也可能是组件,这里我们假设先不考虑组件的处理。因为需要降低文章的复杂度,让读者更专注于 patch 算法的本身而不去拘泥于细节,并且 processComponent 本身的思想也很简单:

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
const processComponent = (
n1: VNode | null,
n2: VNode,
container: RendererElement,
anchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
optimized: boolean
) => {
if (n1 == null) {
if (n2.shapeFlag & ShapeFlags.COMPONENT_KEPT_ALIVE) {
(parentComponent!.ctx as KeepAliveContext).activate(
n2,
container,
anchor,
isSVG,
optimized
);
} else {
mountComponent(
n2,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
optimized
);
}
} else {
updateComponent(n1, n2, optimized);
}
};

如果不是第一次加载组件则 updateComponent:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const updateComponent = (n1: VNode, n2: VNode, optimized: boolean) => {
const instance = (n2.component = n1.component)!;
if (shouldUpdateComponent(n1, n2, optimized)) {
if (__FEATURE_SUSPENSE__ && instance.asyncDep && !instance.asyncResolved) {
if (__DEV__) {
pushWarningContext(n2);
}
updateComponentPreRender(instance, n2, optimized);
if (__DEV__) {
popWarningContext();
}
return;
} else {
instance.next = n2;
invalidateJob(instance.update);
instance.update();
}
} else {
n2.component = n1.component;
n2.el = n1.el;
instance.vnode = n2;
}
};

这里使用了一个内置的 shouldUpdateComponent 控制组件是否刷新。此下不去过多展开了。

真正需要注意的仅仅有 processElement 这个方法。

processElement 这个方法很简单了,就是做个判断,然后调用真正的对元素的 patch 方法,patchElement

1
2
3
4
5
6
7
8
9
const processElement = (n1: VNode | null, n2: VNode, container: RendererElement,
// ...
) => {
if (n1 == null) {
mountElement(// ...)
} else {
patchElement(n1, n2, parentComponent, parentSuspense, isSVG, optimized)
}
}

其实看过 Vue2 感觉这些和 Vue2 还是蛮像的,所以这里不做多啰嗦,继续找 patchElement:

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
const patchElement = (
n1: VNode,
n2: VNode,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
optimized: boolean
) => {
const el = (n2.el = n1.el!);
let { patchFlag, dynamicChildren, dirs } = n2;
// #1426 take the old vnode's patch flag into account since user may clone a
// compiler-generated vnode, which de-opts to FULL_PROPS
patchFlag |= n1.patchFlag & PatchFlags.FULL_PROPS;
const oldProps = n1.props || EMPTY_OBJ;
const newProps = n2.props || EMPTY_OBJ;
let vnodeHook: VNodeHook | undefined | null;

if ((vnodeHook = newProps.onVnodeBeforeUpdate)) {
invokeVNodeHook(vnodeHook, parentComponent, n2, n1);
}
if (dirs) {
invokeDirectiveHook(n2, n1, parentComponent, "beforeUpdate");
}

if (patchFlag > 0) {
// ...
} else if (!optimized && dynamicChildren == null) {
// unoptimized, full diff
patchProps();
//...
}

if (dynamicChildren) {
patchBlockChildren();
//...
} else if (!optimized) {
// full diff
patchChildren(
n1,
n2,
el,
null,
parentComponent,
parentSuspense,
areChildrenSVG
);
}

if ((vnodeHook = newProps.onVnodeUpdated) || dirs) {
queuePostRenderEffect(() => {
vnodeHook && invokeVNodeHook(vnodeHook, parentComponent, n2, n1);
dirs && invokeDirectiveHook(n2, n1, parentComponent, "updated");
}, parentSuspense);
}
};

这里,包含了对 props 的 patch 优化和对 children 节点的 patch 方案。

diff 的比较与复用是针对子元素的,这个 patchChildren 显然是个重点,继续往下看:

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
const patchChildren: PatchChildrenFn = (
// ...
) => {
const c1 = n1 && n1.children
const prevShapeFlag = n1 ? n1.shapeFlag : 0
const c2 = n2.children

const { patchFlag, shapeFlag } = n2
// fast path
if (patchFlag > 0) {
if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
patchKeyedChildren(
c1 as VNode[],
c2 as VNodeArrayChildren,
container,
anchor,
// ...
)
return
} else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
// unkeyed
patchUnkeyedChildren(
c1 as VNode[],
c2 as VNodeArrayChildren,
//...
)
return
}
}

对于 children 的 patch 过程分别有两个方案,分别为 keyed 与 unkeyed

keyed 很好理解,就是可以存在复用的节点,比如 ul>li*n。而 unkeyed 节点显然是那些正常节点。优化的核心点显然是那些 keyed 的子节点。而下面 patchKeyedChildren 也就是真正的 Vue3 的 diff 算法的核心。

section3 核心

源码里这里的注释写的真的很棒,但是考虑读者的水平不同,我们仍然分步骤来看一下:

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
const patchKeyedChildren = (
c1: VNode[],
c2: VNodeArrayChildren,
container: RendererElement,
parentAnchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
optimized: boolean
) => {
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1; // prev ending index
let e2 = l2 - 1; // next ending index

while (i <= e1 && i <= e2) {
const n1 = c1[i];
const n2 = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]));
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
optimized
);
} else {
break;
}
i++;
}
//...
};

先从前向后查找第一个不可以复用的子节点,并用 i 记录这个子节点的下标:

vnodes_i

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
// 2. sync from end
// a (b c)
// d e (b c)
while (i <= e1 && i <= e2) {
const n1 = c1[e1];
const n2 = (c2[e2] = optimized
? cloneIfMounted(c2[e2] as VNode)
: normalizeVNode(c2[e2]));
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
optimized
);
} else {
break;
}
e1--;
e2--;
}

然后从后向前找到不可以复用的子节点下标。这里,因为 c1 和 c2 的长度可能有所不同,所以使用 e1 和 e2 两个变量分别记录这两个数组中不可直接复用的节点下标:

vnodes_i2

接下来有两种比较容易处理的情况:

  1. 总顺序不变但新增了节点
  2. 总顺序不变但减少了节点

第一种情况很容易想到,如图:

patch1

这种情况只要把新增的节点生成挂载就好了。

看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1;
const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor;
while (i <= e2) {
patch(
null,
(c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i])),
container,
anchor,
parentComponent,
parentSuspense,
isSVG
);
i++;
}
}
}

另一种情况就更容易了:

patch2

这种情况只要把多余的节点卸掉就好了:

1
2
3
4
5
6
else if (i > e2) {
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
}

继续,方便处理的已经结束了,下面对无序节点进行处理喽:

如下情况:

unsequence_list

到了这步显然只需要处理 i -> e1(e2)部分的所有无须子节点的复用即可。

分三步:

  1. 构建一个 key -> index 的列表,用来确认 c1 是否在 c2 中有对应节点可供复用,并映射其位置

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    const 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);
    }
    }
  2. 利用上面的映射表做一次 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
    56
    let 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++; // 计数,用来剪枝
    }
    }
    1. 下面的才是戏肉,哦不对,肉戏:

    这里面用了一个概念:最长递增子序列

    可以先参考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
    40
    function 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
    33
    const 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–,如下:

    子序列2

    到这里发现,i 位置的索引不等于 j 指向的值了,所以显然是需要进行位置的变换(move 的),可以看到根据 c2,在 c1 中将 E 会被插入节点 I 的前面,然后 i–,看图:

    子序列3

    接下来,2,1 都在递增子序列中,所以不会进行移动,依然 i–,j–,直到下图情况:

    子序列4

    此时,j < 0,直接对老节点进行位移即可,可以看到,需要将 F 节点插入 D 节点前面即可,看图:

    子序列5

    可以看到,已经达到了 keyedChildren 的复用,且减少了大量无意义 DOM 操作。

section 4 总结

整体感觉不算应该很难,但是我发现 Vue3 的一个有趣的地方。它将 DOM 操作底层封装成了一些特定的函数存储在 vnode 上,显然我们可以自定义一些特殊的行为然后替换原有的 DOM 操作吼。

最后的递增子序列题解我放在下面,自以为我写的是最好理解的方法了。插个腰!<(ˉ^ˉ)>

就酱,本文结束。

section Afterword 题解

leetcode300:最大上升子序列长度

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
var lengthOfLIS = function (nums) {
const ret = [];
for (let i = 0; i < nums.length; ++i) {
const max = ret[ret.length - 1] ? ret[ret.length - 1] : 0;
if (nums[i] > max) {
ret.push(nums[i]);
} else {
let idx = binarySearch(ret, nums[i]);
idx = idx >= 0 ? idx : -idx - 1;
ret[idx] = nums[i];
}
}

return ret.length;

function binarySearch(ret, searchVal) {
let start = 0,
end = ret.length - 1;
let mid = 0;
while (start < end) {
mid = Math.floor((start + end) / 2);
if (ret[mid] === searchVal) return mid;
if (ret[mid] < searchVal) {
start = mid + 1;
} else {
end = mid;
}
}
return -(start + 1);
}
};

solution

查看评论