Vue Patch，忙啥呢？

1. Patch 是什么

举个例子，桌面上依此摆放着🍎🍐🍑🥝，需要经过某些步骤，将桌面上的水果调整为🍑🍐🥝🍉。

• 方法一：学习我们非凡桌面清理大师。

1.清空桌面
2.依次摆放好🍑🍐🥝🍉

• 方法二：基于前后差异调整，这就是 Patch 了。

1.🍎去掉
2.🍑移动到🍐的前面
3.在末尾加入🍉

Patch，[pætʃ]，补丁的意思，寻找前后两版的差异进行逐个调整的过程。实际的场景中，一组 DOM 的结构可能比例子中的列表复杂的多，因此需要一种描述蓝本的结构。一个 JS 对象表示一个元素怎么样，这就是VirtualDOM，后面简称 vnode。

如很多文章提到的一样， Patch 算法减少了 DOM 操作，避免了不必要的开销，提升性能。

真的是这样吗？

2. Patch 有用吗

回顾开头例子的两种方法，方法一的 DOM 操作步骤较少，实际的操作过程可能是这样：

wrap.innerHTML = '';
wrap.innerHTML = '
...
'; 
1
2

而方法二可以复用一部分 DOM ，但步骤可能根据数据状况变多，实际的操作过程可能是这样：

wrap.insertBefore
wrap.removeChild
wrap.setAttribute
wrap.removeAttribute
... 
1
2
3
4
5

因此，关键是探究 DOM 复用和 DOM 操作次数哪个对性能的影响更大？

设计实验

初始有较多(10000+)的 li 标签，通过通过三种方式完成 DOM 更新，比较更新时长。

...
 
1
2

• 方法一 （全量替换， DOM 操作次数多）

wrap.innerHTML = '';
for(let i = 0; i < 10000; i++) {const el = document.createElement('li');el.className = 'item1';wrap.appendChild(el);
} 
1
2
3

• 方法二 （全量替换， DOM 操作次数少）

wrap.innerHTML = '';
let str = ''
for(let i = 0; i < 10000; i++) {str += '
';
}
wrap.innerHTML = str; 
1
2
3
4
5

• 方法三 （ DOM 复用， DOM 操作次数多）

const children= [...wrap.childNodes];
const length = children.length;
for(let i = 0; i < length; i++) {if (!(i % 3)) {const el = document.createElement('li');el.className = 'item3';wrap.insertBefore(el, children[i]);wrap.removeChild(children[i]);}
} 
1
2
3
4

这里是为了模拟 patch 过程中逐个调整的过程，忽略了 patch 本身的 JS 执行成本。简单的假设一部分元素需要移除，插入新的元素；另一部分元素可以保持不动。（实际 patch 过程中很少出现这种删掉一个元素，再插入一个相同元素的『无用』操作）

CodePen Demo

结果分析

各组DOM总数与更新时长关系

方法一更新过程分析

方法二更新过程分析

方法三更新过程分析

实验总结

1.DOM 操作次数对渲染时长的影响很小
2.DOM 复用的对渲染时长有明显的正向影响
3.Patch 在浏览器『重新计算样式』阶段优势明显。

到此可以看出， Patch 的性能优势有固定的前提：

• DOM 总量足够多：如果全部重新渲染一组 DOM不超过 16.7ms，使用什么策略更新都不重要。
• 可复用的 DOM 比例够大：也就是用户与页面的一次交互只影响很『小』的区域。

理解 Patch 的意义关键在浏览器的『重新计算样式』阶段。这一阶段的工作包括：

1.更新 DOM 树，将两次渲染之间的 DOM 操作更新到树中。
2.（如果需要）编译 css 形成 styleSheets 。
3.styleSheets 与 DOM 树结合，计算每个节点的样式标准值。

显而易见， DOM 复用的比例影响了更新 DOM 和计算样式标准值的过程。

一个好的 Patch 算法会快速发现两版间相似的 DOM ，尽量多复用 DOM 。 Vue 是怎么做的呢？

3. Vue Patch 做了什么

代码细节参考 mini-vue 。该项目代码精简，保留了关键细节，是阅读 vue 源码的良好参考，值得安利😉。

前面有提到 vnode ，使用 js 对象描述 DOM 。更准确的说法是， vnode 描述了上层开发者的渲染意图（组件中的 template 或者 render 函数的返回值）。 vnode 更接近 template ，而不是最终渲染的 DOM 。举个例子， template 中对组件 CompA 的调用，体现在 vnode 上是一个 type 为 CompA 的对象。至于 CompA 里有 div 还是 span ，在 CompA 挂载后， CompA 的 vnode 会记录。

{"type": "CompA","props": {"value": "xxx"},...
} 
1
2

Patch 的工作是对比两棵 vnode 树，更新到容器中。遍历树结构很容易想到用递归实现。

function patch(oldVnode, vnode) {updateProps(oldVnode, vnode);updateChildren(oldVnode, vnode);
}
function updateChildren(oldVnode, vnode) {// 遍历两个 childrenpatch(oldVnode.children[x], vnode.children[y]);
} 
1
2
3
4

如何确定 x 和 y ，找到相似的节点进入深层的 patch，这是关键的问题。

updateChildren

0. 相似的判定

开始前先要明确『相似』的标准，即 type 和 key 都相等。

function isSameVNodeType (n1, n2) {return n1.type === n2.type && n1.key === n2.key;
}; 
1
2

• type： TagName 、 ComponentName 等，比如两个 vnode 都是 div ，或者两个 vnode 都是 CompA
• key：就是搭配 v-for 的 key 属性，不过 key 属性也可以单独使用。

1. 正向处理掉左端相似节点

// c1 是 oldVnode.children
// c2 是 vnode.children
let i = 0;
const l2 = c2.length;
let e1 = c1.length - 1;
let e2 = l2 - 1;
while (i <= e1 && i <= e2) {const prevChild = c1[i];const nextChild = c2[i];if (!isSameVNodeType(prevChild, nextChild)) {console.log("两个 child 不相似");break;}patch(prevChild, nextChild, container, parentAnchor, parentComponent);i++;
} 
1
2
3
4
5
6
7
8

从左向右遍历两个列表，处理相似的节点， i 停在第一对不相似的节点。

2. 逆向处理掉右端相似节点

while (i <= e1 && i <= e2) {const prevChild = c1[e1];const nextChild = c2[e2];if (!isSameVNodeType(prevChild, nextChild)) {\console.log("两个 child 不相似");break;}patch(prevChild, nextChild, container, parentAnchor, parentComponent);e1--;e2--;
} 
1
2

从右向左遍历两个列表，处理相似的节点， e1 和 e2 停在逆向第一对不相似的节点。

3. 老指针重合，新增新区间节点

if (i > e1 && i <= e2) {const nextPos = e2 + 1;const anchor = nextPos < l2 ? c2[nextPos].el : parentAnchor;while (i <= e2) {patch(null, c2[i], container, anchor, parentComponent);i++;}
} 
1
2

新增的过程需要判断插入的位置（ anchor 为插入位置的参照，可以参考 DOM API insertBefore ）。考虑区间内可能有 DOM 节点、组件等不同类型，所以这里使用 patch 新增，而不是 createElement 。

4. 新指针重合，删掉老区间节点

if (i > e2 && i <= e1) {while (i <= e1) {hostRemove(c1[i].el);i++;}
} 
1
2

删除过程中调用 hostRemove 内部间接调用了 DOM API removeChild 以及针对组件的 unmountComponent 。

5. 两边都有，准备双向匹配

剩余的情况代表两个列表都有未处理的节点，在进一步做双向匹配前要有一些准备工作：

let s1 = i;
let s2 = i;
const keyToNewIndexMap = new Map();
let moved = false;
let maxNewIndexSoFar = 0;

// 准备 key 映射
for (let i = s2; i <= e2; i++) {const nextChild = c2[i]; keyToNewIndexMap.set(nextChild.key, i);
}

const toBePatched = e2 - s2 + 1;
let patched = 0;
// 准备记录新老节点索引匹配的数组
const newIndexToOldIndexMap = new Array(toBePatched);
// 0 作为新节点在无匹配老节点的标识
for (let i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

维护 keyToNewIndexMap 方便后续利用 key 快速匹配。请注意 moved 和 newIndexToOldIndexMap ，表明后面的遍历有两个任务：

• 检测是否存在『换位』情况
• 记录新老节点索引匹配

6. 遍历老区间，删除无用节点，处理匹配节点

for (i = s1; i <= e1; i++) {const prevChild = c1[i];// 如果老的节点大于新节点的数量的话，那么这里在处理老节点的时候就直接删除即可if (patched >= toBePatched) {hostRemove(prevChild.el);continue;}let newIndex;if (prevChild.key != null) {// 利用 key 快速匹配newIndex = keyToNewIndexMap.get(prevChild.key);} else {// 暴力匹配for (let j = s2; j <= e2; j++) {if (newIndexToOldIndexMap[j - s2] === 0 && isSameVNodeType(prevChild, c2[j])) {newIndex = j;break;}}}if (newIndex === undefined) {// 当前节点的 key 不存在于 newChildren 中，需要把当前节点给删除掉hostRemove(prevChild.el);} else {// 新老节点都存在// 把新节点的索引和老的节点的索引建立映射关系// i + 1 是因为 i 有可能是 0 ( 0 的话会被认为新节点在老的节点中不存在)newIndexToOldIndexMap[newIndex - s2] = i + 1;// 来确定中间的节点是不是需要移动// 新的 newIndex 如果一直是升序的话，那么就说明没有移动// 所以我们可以记录最后一个节点在新的里面的索引，然后看看是不是升序// 不是升序的话，我们就可以确定节点移动过了if (newIndex >= maxNewIndexSoFar) {maxNewIndexSoFar = newIndex;} else {moved = true;}patch(prevChild, c2[newIndex], container, null, parentComponent);patched++;}
} 
1
2

遍历老的区间，利用 key 做快速匹配，对没有 key 的节点做暴力匹配。删除无用的节点。其他有匹配的节点做内部 patch ，记录到 newIndexToOldIndexMap 中。判断匹配的索引是否随遍历上升检测『换位』情况。对匹配做计数，当到达新区间个数，后面的老节点直接删除。

需要注意，这个一步只是完成了对应节点间的内部 patch ，还没有移动到新的位置。

7. 倒序遍历新区间，新增未处理的节点，用最少的移动归位

现在 newIndexToOldIndexMap 记录了每一个新节点在老区间对应的索引。以 [0, 5, 2, 1, 6, 3, 4, 7] 为例，其中的 5 表示，新区间第 2 个节点对应老区间第 5 个节点。

const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: [];
let j = increasingNewIndexSequence.length - 1; 
1
2
3
4

将 newIndexToOldIndexMap 经过最长递增子序列算法处理。 以 [0, 5, 2, 1, 6, 3, 4, 7] 为例，将得到 [3, 5, 6, 7] ，这表示 [1, 3, 4, 7] 为原数组的最长递增子序列，返回对应原数组的索引。最长递增子序列内的节点在归位过程中可以不用动✌️。

for (let i = toBePatched - 1; i >= 0; i--) {const nextIndex = s2 + i;const nextChild = c2[nextIndex];// 锚点等于当前节点索引+1// 也就是当前节点的后面一个节点(又因为是倒遍历，所以锚点是位置确定的节点)const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1].el : parentAnchor;if (newIndexToOldIndexMap[i] === 0) {// 说明新节点在老的里面不存在// 需要创建patch(null, nextChild, container, anchor, parentComponent);} else if (moved) {// 需要移动// 1. j 已经没有了 说明剩下的都需要移动了// 2. 最长递增子序列里面的值和当前的值匹配不上， 说明当前元素需要移动if (j < 0 || increasingNewIndexSequence[j] !== i) {// 移动的话使用 insert 即可hostInsert(nextChild.el, container, anchor);} else {// 这里就是命中了index 和 最长递增子序列的值// 所以可以移动指针了j--;}}
} 
1
2

倒序遍历新区间，对未处理过的节点使用 patch 新增。如果存在『换位』情况，将最长递增子序列外的节点换位到新的索引。这样用最少的移动次数就能将节点归位。

结语

关于开头 What 和 Why 的问题，看到这里自然有了答案。我们框架使用者只需要善用其中的原理（比如记得加 key 属性），使自己的组件快速更新。如果能够记得一些技巧（比如最长递增子序列）解决自己的问题，就更好了。

保持怀疑，保持好奇，文中错误欢迎指正😉