【vue设计与实现】简单Diff算法 1-减少DOM操作的性能开销

关于Diff算法，简单来说，当新旧vnode的子节点都是一组节点的时候后，为了以最小的性能开销完成更新操作，需要比较两组子节点，用于比较的算法就叫Diff算法。

核心Diff只关心新旧虚拟节点都存在一组子节点的情况。之前针对两组子节点的更新，采用了一种简单直接的手段，即卸载全部旧子节点，再挂在全部新子节点。但是没有复用任何DOM元素，带了极大的性能开销。看下面的例子：

// 旧vnode
const oldVnode = {
	type: 'div',
	children: [
		{type: 'p',children: '1'},
		{type: 'p',children: '2'},
		{type: 'p',children: '3'},
	]
}

// 新vnode
const newVnode = {
	type: 'div',
	children: [
		{type: 'p',children: '4'},
		{type: 'p',children: '5'},
		{type: 'p',children: '6'},
	]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

如果按之前简单的做法，需要执行6次DOM操作

但是观察上面新旧vnode的子节点，可以发现：

• 更新前后的所有子节点都是p标签，即标签元素不变
• 只有p标签的子节点（文本节点）会发生变化

所以最理想的更新方式是，直接更新这个p标签的文本节点的内容。这样一共加起来总共要3次DOM操作。
按照这个思路，可以重新实现两组子节点的更新逻辑，如下面patchChildren函数的代码：

function patchChildren(n1,n2,container){
	if(typeof n2.children === 'string'){
		// 省略部分代码
	}else if(Array.isArray(n2.children)){
		const oldChildren = n1.children
		const newChildren = n2.children
		//遍历旧的children
		for(let i=0;i<oldChilren.length;i++){
			// 调用patch函数逐个更新子节点
			patch(oldChildren[i],newChildren[i])
		}
	}else{
		/.../
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这种做法问题也很明显，这里假定的是新的一组子节点的数量和旧的相同，但是新旧两组子节点的数量未必相同。当新的节点数量少于旧的，就意味着有些节点在更新后应该被卸载。类似地，新的一组子节点的数量也可以比旧的多，这时候应该挂在新增节点。

因此，在更新时，不应该是遍历旧的一组子节点，而是遍历其中长度较短的那一组。最终实现如下：

function patchChildren(n1,n2,container){
	if(typeof n2.children === 'string'){
		// 省略部分代码
	}else if(Array.isArray(n2.children)){
		const oldChildren = n1.children
		const newChildren = n2.children
		// 旧的一组子节点的长度
		const oldLen = oldChildren.length
		// 旧的一组子节点的长度
		const newLen = newChildren.length
		// 两组子节点的公共长度，即两者中较短的那一组子节点的长度
		const commonLength = Math.min(oldLen,newLen)
		// 遍历commonLength次
		for(let i=0;i<commonLength;i++){
			patch(oldChildren[i],newChildre[i])
		}
		// 如果newLen>oldLen，说明有新子节点需要挂载
		if(newLen > oldLen){
			for(let i=commonLength; i< newLen; i++){
				patch(null, newChildren[i],container)
			}
		}else if(oldLen > newLen){
			// 如果newLen>oldLen，说明有旧子节点需要卸载
			for(let i = commonLength; i< oldLen; i++){
				unmount(oldChildren[i])
			}
		}
		
	}else{
		/.../
	}
}
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

这样，无论新旧两组子节点的数量关系如何，渲染器都能够正确地挂载或卸载他们。