Vue3 diff 算法解析
点击关注上方蓝字，阅读更多干货~
Vue作为业界优秀的开源框架，同时也是业内广泛采用的技术方案，其源码设计非常优秀。学习vue3源码有助于提高伙伴能力、拓展技术视野，也能在实际的业务中帮助伙伴排查问题。
Diff算法是vue渲染器的一个重要组成部分，解决了操作dom成本过高的问题。通过diff算法可以高效地实现渲染的局部更新，避免dom全量更新带来的性能负担。在长列表、重渲染、重交互的场景，伙伴可以借鉴diff算法的思想来提升渲染性能，达到提升用户体验的目的。
本文目标是讲一下diff算法的实现方式，吸收内部优秀的代码设计，并将设计模式运用到实际业务中。本文主要讲述以下内容：
概述虚拟dom的概念
概述vue3的patch的概念 解析patchKeyedChildren的实现方式 解析patchUnkeyedChildren的实现方式 与vue2 diff的对比
2 背景
原生dom中有很多我们不需要的节点、属性，因此在浏览器环境中进行dom的操作开销是很大的。 如果此时修改了部分数据，直接渲染真实dom又会引起整个dom树的重绘和重排，造成性能负担。
图1 diff流程
3 源码解析
3.1 虚拟dom
在传统的页面开发中，频繁变动dom会造成浏览器的回流或者重绘，这种方式消耗计算资源较大。为了解决这个问题，我们需要虚拟dom这一层抽象，用对象的方式来描述真实的dom，就能将性能消耗从真实dom操作的级别降低至JavaScript层面，尽可能地一次性将差异更新到dom中，这样我们就有更多的优化空间，相对而言性能更加优秀。
不仅如此，虚拟dom也能让Vue和React之类的框架支持除浏览器之外的其他平台（react native、uni-app、taro等跨平台框架）。
<div><p id="vnode1">1</p><p id="vnode2">2</p><p id="vnode3">3</p><p id="vnode4">4</p></div>
const vnode = {type: 'div',children: [{type: 'p',props: {id: 'vnode1'},key: '1',children: '1'},{type: 'p',props: {id: 'vnode2'},key: '2',children: '2'},{type: 'p',props: {id: 'vnode3'},key: '3',children: '3'}, {type: 'p',props: {id: 'vnode4'},key: '4',children: '4'}]}
如果需要把HTML的结构改变为如下结构：
<div><p id="vnode4">4</p><p id="vnode1">1</p><p id="vnode2">2</p><p id="vnode3">3</p></div>
传统的方式会导致整个dom树的重绘和重排，但分析结构可以得出结论：把节点4移动到头部就是最小损耗的操作，这就是diff算法需要做的事。
图2 最小损耗操作
3.2 Diff过程
3.2.1 节点判断
在采取diff算法比较新旧节点的时候，比较只会在同层级进行，因为复杂度过高，不会跨层级比较。
<div><p>123</p></div><div><span>456</span></div>
上面的代码会分别比较同一层的两个div以及第二层的p和span ，但是不会拿div和span作比较。
图3 比较过程
function isSameVNodeType(n1: VNode, n2: VNode): boolean {return n1.type === n2.type && // 比较类型n1.key === n2.key // 比较标记}
3.2.2 patch过程
首先要从patch函数开始看起。Vue在通过VNode节点渲染dom时，并不是通过当前的VNode节点去暴力的更新dom节点，而是对新旧两个VNode节点通过patch进行比较，然后通过对比结果找出差异的属性或节点进行按需更新。
创建需要新增的节点 移除已经废弃的节点 移动或修改需要更新的节点
const patch = (n1, n2, container, anchor = null, parentComponent = null, parentSuspense = null, isSVG = false, slotScopeIds = null, optimized = isHmrUpdating ? false : !!n2.dynamicChildren) => {/**Vnode有不同的类型，可以分为：简单类型：文本、注释、Static。复杂类型：组件、Fragment、Component、Teleport、Suspense。patch思路，可以看作一个深度优先遍历。简单类型就相当于JS中的原始数据类型：字符串、数字、布尔。复杂类型就相当于JS中的引用类型：对象、数组、Map、Set。不同的节点类型，需要采取不同的patch方式。而patch函数的主要职责就是去判断Vnode的节点类型（打上patchFlag标志），然后调用对应类型的Vnode处理方式，进行更细致的patch（最后进行render渲染）。*/if (n1 === n2) {return;}// patching & not same type, unmount old treeif (n1 && !isSameVNodeType(n1, n2)) {anchor = getNextHostNode(n1);unmount(n1, parentComponent, parentSuspense, true);n1 = null;}if (n2.patchFlag === -2 /* BAIL */) {optimized = false;n2.dynamicChildren = 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);x}else {patchStaticNode(n1, n2, container, isSVG);}break;case Fragment:// Fragment 类型处理processFragment(n1, n2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);break;default:if (shapeFlag & 1 /* ELEMENT */) {// ELEMENT 类型处理processElement(n1, n2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);}else if (shapeFlag & 6 /* COMPONENT */) {// 组件 类型处理processComponent(n1, n2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);}else if (shapeFlag & 64 /* TELEPORT */) {// 节点移动 类型处理type.process(n1, n2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized, internals);}else if (shapeFlag & 128 /* SUSPENSE */) {// 节点移动 类型处理type.process(n1, n2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized, internals);}else {warn('Invalid VNode type:', type, `(${typeof type})`);}}// set refif (ref != null && parentComponent) {setRef(ref, n1 && n1.ref, parentSuspense, n2 || n1, !n2);}};
patch函数的核心处理逻辑如下图所示：
图4 patch函数结构
patch函数的主要职责就是判断Vnode的节点类型（打上patchFlag标志），然后调用对应类型的Vnode处理方式，进行更细致的patch（最后进行render渲染）。
其中patchFlag用于标识编译优化信息，可以理解为对虚拟节点VNode的属性进行描述的标志。根据patchFlag判断出需要更新的内容，实现靶向更新。
export const enum PatchFlags {// 表示vnode具有动态textContent的元素TEXT = 1,// 表示vnode具有动态的classCLASS = 1 << 1,// 表示具有动态的styleSTYLE = 1 << 2,// 表示具有动态的非class和style的propsPROPS = 1 << 3,// 表示props具有动态的key，与CLASS、STYLE、PROPS冲突FULL_PROPS = 1 << 4,// 表示有监听事件(在同构期间需要添加)HYDRATE_EVENTS = 1 << 5,// 表示vnode是个children顺序不会改变的fragmentSTABLE_FRAGMENT = 1 << 6,// 表示children带有key的fragmentKEYED_FRAGMENT = 1 << 7,// 表示children没有key的fragmentUNKEYED_FRAGMENT = 1 << 8,// 表示vnode只需要非props的patch。例如只有标签中只有ref或指令NEED_PATCH = 1 << 9,// 表示vnode存在动态的插槽。例如动态的插槽名DYNAMIC_SLOTS = 1 << 10,// 表示用户在模板的根级别存在注释而创建的片段，这是一个仅用于开发的标志，因为注释在生产中被剥离DEV_ROOT_FRAGMENT = 1 << 11,// 以下都是一些特殊的flag，它们不能使用位运算进行匹配// 表示vnode经过静态提升HOISTED = -1,// diff算法应该退出优化模式BAIL = -2}
Vue3中通过patch函数生成出一个数字枚举来对虚拟节点进行标记，采用按位与（&）运算来确定节点的属性，比如文本节点、数组节点、组件节点等等，CPU中有直接对应位操作的指令，提升判断效率。
有key的处理， 进入patchKeyedChildren流程
无key的处理， 进入patchUnkeyedChildren流程
const patchChildren = (n1, n2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized = false) => {const c1 = n1 && n1.children;const prevShapeFlag = n1 ? n1.shapeFlag : 0;const c2 = n2.children;const { patchFlag, shapeFlag } = n2;// fast path// 这个 patchFlag，就是一个判断渲染的节点上是包含 key 的一个标识符if (patchFlag > 0) {if (patchFlag & 128 /* KEYED_FRAGMENT */) {// 当节点上面存在 key，执行的是 patchKeyedChildren 方法// this could be either fully-keyed or mixed (some keyed some not)// presence of patchFlag means children are guaranteed to be arrayspatchKeyedChildren(c1, c2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);return;}else if (patchFlag & 256 /* UNKEYED_FRAGMENT */) {// 当前节点上不存在 key，执行的是 patchUnkeyedChildren 方法// unkeyedpatchUnkeyedChildren(c1, c2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);return;}}}
有key的处理
首遍历
/* 从头对比找到有相同的节点 patch ，发现不同，立即跳出*/while (i <= e1 && i <= e2) {const n1 = c1[i];const n2 = (c2[i] = optimized? cloneIfMounted(c2[i]): normalizeVNode(c2[i]));// isSameVNodeType 根据type与key的维度判断同一节点if (isSameVNodeType(n1, n2)) {// 相同就打补丁patch(n1, n2, container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);}else {// 不相同就跳出break;}// 记录下标i++;}
尾遍历
/* 从尾部对比找到有相同的节点 patch ，发现不同，立即跳出*/while (i <= e1 && i <= e2) {const n1 = c1[e1];const n2 = (c2[e2] = optimized? cloneIfMounted(c2[e2]): normalizeVNode(c2[e2]));// isSameVNodeType 根据type与key的维度判断同一节点if (isSameVNodeType(n1, n2)) {// 相同就打补丁patch(n1, n2, container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);}else {// 不相同就跳出break;}// 记录下标e1--;e2--;}
旧节点挂载完毕
/* 如果新的节点大于老的节点数 ，对于剩下的节点全部以新的vnode处理（ 这种情况说明已经patch完相同的vnode ） */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] = optimized? cloneIfMounted(c2[i]): normalizeVNode(c2[i])), container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);i++;}}}
新节点挂载完毕
// 只有旧的节点剩余else if (i > e2) {while (i <= e1) {// 执行旧节点卸载unmount(c1[i], parentComponent, parentSuspense, true);i++;}}
新节点挂载完毕代表只有旧的节点剩余，执行旧节点卸载。
皆有剩余
// 5. unknown sequence// [i ... e1 + 1]: a b [c d e] f g// [i ... e2 + 1]: a b [e d c h] f g// i = 2, e1 = 4, e2 = 5else {const s1 = i; // prev starting indexconst s2 = i; // next starting index// 5.1 build key:index map for newChildren// 生成一个 Map 把新的元素的 key(如果存在) 和它对应的下标保存起来。const keyToNewIndexMap = new Map();for (i = s2; i <= e2; i++) {const nextChild = (c2[i] = optimized? cloneIfMounted(c2[i]): normalizeVNode(c2[i]));if (nextChild.key != null) {if (keyToNewIndexMap.has(nextChild.key)) {warn(`Duplicate keys found during update:`, JSON.stringify(nextChild.key), `Make sure keys are unique.`);}keyToNewIndexMap.set(nextChild.key, i);}}// 5.2 loop through old children left to be patched and try to patch// matching nodes & remove nodes that are no longer presentlet j;let patched = 0; // 已经patch完的数量const toBePatched = e2 - s2 + 1; // 需要patch的数量,即c2剩下的元素数量let moved = false; // 是否需要进行移动操作// used to track whether any node has movedlet maxNewIndexSoFar = 0; // 用来辅助判定moved// 生成c2中剩下的元素,在c1中的原来的位置的对应数组，初始化都为0// 数组长度为 toBePatched，即剩下的 c2 中的元素数量// 比如 oldchildren = [a, b, (c, d, e, f,) g, h],// newchildren = [a, b, (d, e, f, c,) g, h]// d 在 new 中 index 为 2，在 old 中为 3const 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) {// all new children have been patched so this can only be a removalunmount(prevChild, parentComponent, parentSuspense, true);continue;}let newIndex;// 寻找 key 是否存在if (prevChild.key != null) {newIndex = keyToNewIndexMap.get(prevChild.key);}else {// 如果没有 key 就在 c2 剩下的元素中 寻找同样没有 key 且，还没有配对的元素for (j = s2; j <= e2; j++) {if (newIndexToOldIndexMap[j - s2] === 0 &&isSameVNodeType(prevChild, c2[j])) {newIndex = j;break;}}}// 如果 newindex 不存在，说明 child 在 c2 中不存在，卸载就行了if (newIndex === undefined) {unmount(prevChild, parentComponent, parentSuspense, true);}else {// 如果存在，找到对应的位置newIndexToOldIndexMap[newIndex - s2] = i + 1;if (newIndex >= maxNewIndexSoFar) {maxNewIndexSoFar = newIndex;}else {moved = true;}patch(prevChild, c2[newIndex], container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);// 比较新老元素patched++;}}// 5.3 move and mount 最长递增子序列const increasingNewIndexSequence = moved? getSequence(newIndexToOldIndexMap): shared.EMPTY_ARR;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) {// 新元素没有在 c1 中匹配到index 新建就行了patch(null, nextChild, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);}else if (moved) {// move if:// 最大子序列下标中 对应的元素不需要移动，其他的元素要进行move// 如果 i 对应的不是最长子序列中的下标 进行move移动元素if (j < 0 || i !== increasingNewIndexSequence[j]) {move(nextChild, container, anchor, 2 /* REORDER */);}else {j--;}}}}
图7 新旧节点列表
oldVNodes: [0,1,2,3,4,5]；newVNodes: [0,3,1,2,4,5]
图8 最小损耗操作
function getSequence(arr) {const p = arr.slice();const result = [0]; // 保存最长递增子序列的索引 以默认第0个位基准let i, j, u, v, c;const len = arr.length;for (i = 0; i < len; i++) {// 【1】 找到索引先放进去const arrI = arr[i];if (arrI !== 0) {j = result[result.length - 1]; // 找到序列中的最后一项if (arr[j] < arrI) { // 取出序列中的最后一项对应的值 与当前项的值相比较p[i] = j; // 当前一项result.push(i); // 记录索引continue;}// 【2】 二分查找 在结果集中找到比当前值大的 用当前值的索引将其替换掉// result是递增序列 采用二分查找是最快的u = 0;v = result.length - 1; // 二分查找 前后索引while (u < v) { // 最终 start = end 就停止了c = (u + v) >> 1;// 拿result中间值 和 当前项 比较if (arr[result[c]] < arrI) { // 找比arrI大的值 或者等于arrIu = c + 1;}else {v = c;}}if (arrI < arr[result[u]]) { // 当前项小于中间值就替换掉大的那一项if (u > 0) { // end > 0 才需要替换 p[i]就是当前一项p[i] = result[u - 1]; // 【3.3】替换并记录前驱节点，核心点：记录 “要替换的值的 前一个的索引”}result[u] = i;}}}u = result.length;v = result[u - 1];// 倒序追溯 根据前驱节点一个个向前查找while (u-- > 0) {result[u] = v; // 最后一项肯定是正确的v = p[v]; // 重新赋值}return result;}
通过贪心+二分查找拿到数组索引列表
旧的VNode数大于新的VNode数，卸载多余节点。 先创建一个空数组result保存索引 遍历nums，将当前项current和result的最后一项对应的值进行比较 如果当前项大于最后一项，直接往result中新增一项 否则，针对result数组进行二分查找，找到并替换比当前项大的那项
通过前驱节点重建列表
const result = [1, 3, 4, 6, 7, 9]const preIndexArr = [undefined, 0, undefined, 1, 3, 4, 4, 6, 1]
图10 重建列表
这样我们就得到了最长递增子序列，此时只需要以此序列为基准，移动在序列外的元素，达到节省性能的目的。因此，递增序列越长时，vue3的性能优势越显著，这样就完成了PatchKeyedChildren比较的过程。
无key的处理
源码实现：
const patchUnkeyedChildren = (c1, c2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized) => {c1 = c1 || shared.EMPTY_ARR;c2 = c2 || shared.EMPTY_ARR;const oldLength = c1.length;const newLength = c2.length;const commonLength = Math.min(oldLength, newLength);let i;// 每次比对新旧节点会调用patch方法// 该方法的执行流程是：// 1. 如果两个节点一样不做处理// 如果节点不同就更新for (i = 0; i < commonLength; i++) {const nextChild = (c2[i] = optimized? cloneIfMounted(c2[i]): normalizeVNode(c2[i]));patch(c1[i], nextChild, container, null, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized);}if (oldLength > newLength) {// 卸载多余节点// remove oldunmountChildren(c1, parentComponent, parentSuspense, true, false, commonLength);}else {// 创建多余节点// mount newmountChildren(c2, container, anchor, parentComponent, parentSuspense, isSVG, slotScopeIds, optimized, commonLength);}};
图11 diff流程
含有key属性主要用patchKeyedChildren策略进行新旧节点对比。如果不使用key，vue会使用一种最大限度减少动态元素并且尽可能的尝试就地修改/复用相同类型元素的策略。
Diff流程：
获取旧的和新的VNode数组（列表）的长度
Math.min（c1.length,c2.length）获取新旧数组中长度最短的值，然后遍历短的VNode列表
相同的就不更新，不同的就更新
直到遍历完成：
旧的VNode数大于新的VNode数，卸载多余节点
新的VNode数小于新的VNode数，创建多余节点
3.2.2 与vue2 diff的对比
vue2核心diff算法采用的是双端比较算法
双端指针头尾比较 剩余节点旧列表删除或新列表添加
vue3核心diff算法采用的是去头尾的最长递增子序列算法
双端指针头尾比较 最长递增序列
Vue2、vue3的diff算法实现差异主要体现在：处理完首尾节点后，对剩余节点的处理方式。
Vue3则是建立一个存储新节点数组中的剩余节点在旧节点数组上的索引的映射关系数组，建立完成这个数组后也即找到了可复用的节点，然后通过这个数组计算得到最长递增子序列，这个序列中的节点保持不动，将新节点数组中的剩余节点移动到正确的位置。
4 业务思考
4.1 不推荐使用index作为key的原因
图12 报错警告
若对数据进行逆序添加、逆序删除等破坏顺序的操作，会出现数组下标变化的场景，index的变化会导致vue认为是同一节点，导致更新异常
若不存在对数据逆序添加、逆序删除等破坏顺序的操作，则没有问题
根据上述问题，我们自然也找到了解决方法：唯一的ID作为key。
4.2 patchflag优化判断性能
Vue3采用了位运算优化判断性能，因CPU中有直接对应位操作的指令，可以提升判断效率更，在遇到大量判断的场景，我们可以借鉴patchflag的解决方案。
let skills = 0;const SKILLS = {CSS: 1 ,JS: 1 << 1,HTML: 1 << 2,WEB_GL: 1 << 3}skills = skills | SKILLS.JS;if (skills & SKILLS.JS) {CODE}
如何理解这段代码？
图13 1<<2字节位置
图14 skills | skill 时的字节位置
接下来，我们比较传统的判断测试：
图15 与传统判断方式的对比
4.3 最长递增序列的应用场景
这个例子是肉眼可见的能找到最优解，但是当数据量大，排序后比较混乱的时候，就不那么容易找到最优解了。这个时候如果你曾经接触过算法，你很容易联想到这个问题跟最长公共子序列算法要解决的场景非常契合。
5 总结
Diff算法是vue用于解决数据更新时操作dom成本过高的解决方案，当数据更新时，用于确定最优的更新视图的策略。Diff在有key时使用了双指针+最长递增子序列实现，复杂度为O(nlogn)；diff在没有key时会找到短列表比较，再执行新增或删除，复杂度为O(n)。
相比于vue2的双端比较算法，两者的实现差异主要体现在：处理完首尾节点后，对剩余节点的处理方式，vue3 diff相比vue2性能更好，在递增序列越长时越显著。
What：diff算法是一种对新旧虚拟DOM树进行比较，得出两者差异，确定最优的更新视图的策略算法
Why：减少渲染真实dom的开销，提高性能
When：页面更新，重新渲染时用到
Where：Vue中，当数据发生改变时，set方法会调用Dep.notify通知所有订阅者Watcher，订阅者就会调用patch给真实的dom打补丁 Who：Vue（patch、patchKeyedChildren、patchUnkeyedChildren） How：深度优先、同层比较；tag不同，生成树形结构不同；使用key来标识稳定节点
戴夫，来自缦图互联网中心前端团队。
--------END--------
也许你还想看