Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
What is the Diff algorithm? In a nutshell, the DIff algorithm is a comparison algorithm, that is, the process of comparing old and new VNodes (to see where changes are needed, and then where changes are made). During the comparison process, the implementation completes the generation of new VNodes without changing the old VNodes.
So how does the Diff algorithm work? In fact, in the last article we covered three scenarios, with high and low performance. So what scheme does Vue use to implement diff algorithm?
In fact, Vue determines which solution the diff algorithm takes based on whether or not you pass in a key:
- There are
key, the scheme is adopted3, the implementation ofpatchKeyedChildren()Methods; - There is no
key, the scheme is adopted2, the implementation ofpatchUnkeyedChildren()Methods;
The source code is as follows:
Let’s look at the case where there is no key, using the previous code as an example:
<ul>
<li v-for="item in letters">{{ item }}</li>
</ul>
Copy the codeVue calls the patchUnkeyedChildren() method:
The diagram is as follows:
We can find that the above diff algorithm is not efficient:
C和DNothing really needs to be changed;- But as a result of
C被FThis causes all the following content to be changed once, and finally addedD.
In the case of a key, add the key binding to the previous code (there is no ID, so we assume item is unique) :
<ul>
<li v-for="item in letters" :key="item">{{ item }}</li>
</ul>
Copy the codeVue calls patchKeyedChildren() : patchKeyedChildren()
// This method is in the baseCreateRenderer function in packages/ Run-time core/ SRC /renderer.ts
const patchKeyedChildren = (
c1: VNode[], // Old VNodes, ['A', 'B', 'C', 'D']
c2: VNodeArrayChildren, // New VNodes, ['A', 'B', 'F', 'C', 'D']
container: RendererElement,
parentAnchor: RendererNode | null,
parentComponent: ComponentInternalInstance | null,
parentSuspense: SuspenseBoundary | null,
isSVG: boolean,
slotScopeIds: string[] | null,
optimized: boolean
) = > {
let i = 0
const l2 = c2.length
// The position of the last VNode in old VNodes (index)
let e1 = c1.length - 1 // prev ending index
// Last VNode position in the new VNodes (index)
let e2 = l2 - 1 // next ending index
// 1. sync from start
// Synchronously traverse the old and new VNodes from the header
// (a b) c
// (a b) d e
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)) { // If the old and new vNodes are the same (same type and same key)
// Start patch
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else { / / otherwise
// break out of the loop
break
}
i++
}
// 2. sync from end
// Synchronously traverse the old and new VNodes from the tail
// 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)) { // If the old and new vNodes are the same (same type and same key)
// Start patch
patch(
n1,
n2,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} else { / / otherwise
// break out of the loop
break
}
e1--
e2--
}
// 3. common sequence + mount
// If the old VNodes are traversed and the new VNodes have remaining nodes, add (mount) the remaining new nodes
// (a b)
// (a b) c
// i = 2, e1 = 1, e2 = 2
// (a b)
// c (a b)
// i = 0, e1 = -1, e2 = 0
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1
const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchor
while (i <= e2) {
// If null is passed to the first parameter of patch, subsequent mounting operations will be performed
patch(
null,
(c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i])),
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
i++
}
}
}
// 4. common sequence + unmount
// If the new VNodes are traversed and the old VNodes are left, remove (unmount) the remaining old nodes
// (a b) c
// (a b)
// i = 2, e1 = 2, e2 = 1
// a (b c)
// (b c)
// i = 0, e1 = 0, e2 = -1
else if (i > e2) {
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
}
// 5. unknown sequence
// If it is an unknown node sequence (i.e. there is an unknown sequence of positions in the middle),
// Create index map with key.
// Match the VNodes in the new VNodes from the old VNodes as much as possible (i.e., make maximum use of the old nodes), then remove the remaining VNodes in the old VNodes,
// Then move the node and mount the new node
// [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 = 5
else {
const s1 = i // prev starting index
const s2 = i // next starting index
// 5.1 build key:index map for newChildren
// Create an index map based on the key
const keyToNewIndexMap: Map<string | number.number> = new Map(a)for (i = s2; i <= e2; i++) {
const nextChild = (c2[i] = optimized
? cloneIfMounted(c2[i] as VNode)
: normalizeVNode(c2[i]))
if(nextChild.key ! =null) {
if (__DEV__ && 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 present
// Walk through the old node, compare to modify the old node, remove the old node is no longer used
let j
let patched = 0
const toBePatched = e2 - s2 + 1
let moved = false
// used to track whether any node has moved
let maxNewIndexSoFar = 0
// works as Map<newIndex, oldIndex>
// Note that oldIndex is offset by +1
// and oldIndex = 0 is a special value indicating the new node has
// no corresponding old node.
// used for determining longest stable subsequence
const 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 removal
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
let newIndex
if(prevChild.key ! =null) {
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
// key-less node, try to locate a key-less node of the same type
for (j = s2; j <= e2; j++) {
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j] as VNode)
) {
newIndex = j
break}}}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] as VNode,
container,
null,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
patched++
}
}
// move and mount
// generate longest stable subsequence only when nodes have moved
// Get the longest increment subsequence to move and mount
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) {
// mount new
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
isSVG,
slotScopeIds,
optimized
)
} 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--
}
}
}
}
}
Copy the codeThe core steps are as follows:
The diagram is as follows:
- The comparison is traversed from the head:
- The old and new nodes are the same (
typeAnd the samekeyAlso), continue to compare; C和F的keyDifferent, jump out of the cycle;
- The old and new nodes are the same (
- Traverse the comparison from the tail:
- The old and new nodes are the same (
typeAnd the samekeyAlso), continue to compare; B和F的keyDifferent, jump out of the cycle;
- The old and new nodes are the same (
- If the old nodes have been traversed and there are additional new nodes, add these new nodes:
- If the new nodes have been traversed and there are redundant old nodes, remove these old nodes:
- The final case is the unknown node sequence, which is the node with out-of-order in the middle:
Therefore, we can find that when Vue performs diff algorithm, as long as there is a key, it will try its best to optimize the operation by using key:
- In the absence of
keyThe time,diffThe efficiency of algorithm is low; - Keep the same when inserting or reordering
keyYou can makediffThe algorithm is more efficient;
Now, if you look back at the official explanation of what the key attribute does, is it clearer?
In general, in practical development, when v-for is used, we usually add the key attribute and bind the key attribute to a unique value (such as ID), so that the performance of the diff algorithm is higher.