Today, I would like to share some knowledge related to the Diff algorithm that is often heard in Vue.
Some friends may not fully understand what the Diff algorithm is and what it is used for. We will first briefly introduce the role of the Diff algorithm in Vue 3 and related knowledge, making it easier for those without a background to understand this article.
If you already have a general understanding of the relevant background knowledge, feel free to skip this part and go directly to the next section to see the journey of patch minimal quantization (i.e., the Diff algorithm).
This article aims to minimize code and provide more animated demonstrations. We will explore the wisdom of our predecessors through a series of conceptual diagrams.
Introduction#
In Vue, the virtual VNode is used for comparison and then for mounting/updating/unmounting operations, with the most important being the update operation. The efficiency of the update operation affects the rendering page's update volume. The closer it is to the update volume brought by the framework at compile time, the higher the performance will be. To minimize the update volume brought by Vue, which is a compile-time + runtime framework, the Diff algorithm was introduced to detect the smallest differences between the old and new node trees, resulting in the least amount of updates and improved page performance.
Currently, in "Vue.js Design and Implementation," the Diff algorithm is limited to cases where both the old and new nodes have keys, and it does not mention how to reduce the minimal quantization of patches when there are no keys. The key can serve as a unique identifier for elements to compare old and new nodes.
Next, we will explore the performance improvements in update operations step by step, from simple and crude to complex and elegant.
Direct#
The simplest and most straightforward approach is to completely ignore whether there are differences between the old and new nodes, directly uninstall all old nodes and remount the new nodes into the container. This completes the update operation. This method does not even need to be called Diff because it does not care about differences; it simply involves brainlessly uninstalling and remounting. As shown in the figure below, this direct operation of fully uninstalling and then fully remounting is straightforward but simple. However, the performance is far from that of imperative code. There are node handling methods that do not require uninstallation and only need to move node positions to achieve the goal, which leads us to contemplate such algorithms in pursuit of higher performance.
Figure 0-1 Full Uninstall & Full Mount
Simple#
Origin#
Compared to the full uninstall & full mount approach, we can clearly see one issue: the measurement of reusable nodes. We can observe the old and new sets of nodes in Figure 1-1.
Figure 1-1 Comparison of Old and New Trees
We can clearly see that some nodes only need to be moved very simply, some nodes only need to update the text content differences, and some only need to uninstall the extra old nodes or mount the extra new nodes.
Reuse and Key#
So how do we compare whether the nodes in the old and new trees are the same? In our contemplation, Vue provides us with the answer: add a key attribute to nodes as a unique value, akin to an ID card for nodes.
Figure 1-2 Comparison of Nodes with and without Keys
This way, we have a basis for comparing nodes, avoiding brainless full uninstallation and full mounting operations, and truly beginning the exploration of the Diff algorithm.
Now that we have established that each node in this list has a unique key, we can proceed to handle the reuse of DOM nodes.
Next, let's re-examine Figure 1-1 of the old and new node trees to see what we need to do to minimize DOM operations.
We find the following situations in this pair of old and new node trees:
- Nodes p-1, p-2, p-3, and p-4 can be reused with the old nodes.
- Node p-5 needs to be unmounted.
- Node p-6 needs to be mounted.
- Nodes may need to be moved.
What we need to do next is quite simple, roughly corresponding to the above situations:
- Check the old tree for nodes with the same key based on the new tree. If found, perform a patch operation.
- If a node in the new tree cannot find a reusable node in the old tree, it indicates that this is a new node that needs to be mounted.
- If a node in the old tree cannot find a corresponding node in the new tree (i.e., it has not been reused), it indicates that this is an old node that needs to be unmounted.
- Move the nodes that need to be moved.
/**
* Simple Diff Algorithm
* @param oldVNode Old node list
* @param vNode New node list
* @param container Node list mounting container
*/
function simpleDiff(oldVNode: VNode[], vNode: VNode[], container: ContainerElement) {
for (let i = 0; i < vNode.length; i++) {
let findLock = false; // Indicates whether this new node has found a reusable old node
for (let j = 0; j < oldVNode.length; j++) {
if ((typeof vNode[i].key !== "undefined") && vNode[i].key === oldVNode[j].key) { // Find reusable elements based on unique key
findLock = true; // Found a reusable node
// This step synchronizes the old node's element to the new node's element property
patch(oldVNode[j], vNode[i], container);
// ??? Does the node need to be moved, and where should it be moved to?
break;
};
}
if (!findLock) {
// If we reach here, it means no reusable node was found, a new node needs to be created and inserted
// patch(null, vNode[i], container, ???); Insert the element at the anchor position
}
};
// Traverse the old tree to find nodes that need to be unmounted
oldVNode.forEach(oldElement => {
if (!vNode.find(newElement => newElement.key === oldElement.key)) {
unMountElement(oldElement);
};
});
};
The difficulty in processing these steps lies in moving nodes: how to move them and where to move them? This is also a very important step in the Diff process.
Moving#
Next, let's combine Figure 1-2 to observe how we should move/mount elements. As shown in Figure 1-3.
Figure 1-3 New and Old Virtual Nodes and Real Nodes
Does it feel a bit chaotic? What is the anchor position for moving elements here? Let's think in reverse: under what circumstances do nodes not need to be moved? The answer is when the order of the old and new node lists remains unchanged. If unchanged, it means that each time the new node list goes to find reusable nodes in the old node list, the index of the old nodes shows an increasing trend.
For example, in Figure 1-2, the found old node index trend is [0, 1, 2, 3, 4].
When we look at Figure 1-3, the found old node index trend is [3, 2, -1, 0, 1] (here we temporarily denote the index value of the old node found for newly mounted nodes as -1, but in the actual moving process, newly mounted nodes will not enter the trend calculation). Now, looking back at the found old node index trend, we can see that p-4 has an index of 3 in the old nodes, and p-3 has an index of 2 in the old nodes. This indicates that the p-3 node in the new nodes needs to be moved, as the real element position of p-3 is after the real element position of p-4. In this example, all new nodes are behind p-4, and we are comparing based on the old index of p-4. However, in larger examples, we need to continuously update the baseline (the cutoff index of the increasing trend) to determine whether this node needs to be moved.
To make it easier, more direct, comprehensive, and quick for everyone to feel this moving process, we can look at this code execution animation demonstration in Figure 1-4.
Figure 1-4 Full Process Animation Demonstration of Node Movement
/**
* Simple Diff Algorithm
* @param oldVNode Old node list
* @param vNode New node list
* @param container Node list mounting container
*/
function simpleDiff(oldVNode: VNode[], vNode: VNode[], container: ContainerElement) {
let lastMaxIndex = 0; // Current maximum old index value
for (let i = 0; i < vNode.length; i++) {
let findLock = false;
for (let j = 0; j < oldVNode.length; j++) {
if ((typeof vNode[i].key !== "undefined") && vNode[i].key === oldVNode[j].key) {
// ***Omitting patch code***
if (j < lastMaxIndex) { // Needs to move
const prevElement = vNode[i - 1];
if (prevElement) {
insertElement(container, oldVNode[j]._element, prevElement._element?.nextSibling ?? null);
};
} else {
lastMaxIndex = j;
}
break;
};
}
if (!findLock) {
// If we reach here, it means no reusable node was found, a new node needs to be created and inserted, the anchor position follows the same logic as above
const prevElement = vNode[i - 1];
patch(null, vNode[i], container, prevElement?._element?.nextSibling ?? null);
}
};
// ***Omitting node unmounting code***
};
Double-Ended#
Origin#
In the simple diff algorithm, we sometimes discover more efficient steps in certain examples, as shown in the figure below.
Figure 2-1 Special Example
We find that if we follow the execution flow of the simple diff algorithm, we need to first move p-1 behind p-3, and then move p-2 behind p-1. However, when we observe this pair of old and new node lists, we see that I only need to move p-3 in front of node p-1, as shown in Figure 2-2. A situation that could be solved in one step requires two moves in the diff algorithm.
Figure 2-2 Handling with Fewer DOM Moves in Some Cases
Thought#
Now that we have identified the optimization point, we need to think about how to optimize it. In the double-ended diff algorithm, we establish corresponding head and tail indices for both the old and new node lists, and compare the VNodes at the four index positions while continuously moving the corresponding indices, as shown in Figure 2-3.
Figure 2-3 Double-Ended Index and Comparison Diagram
We will find that in some cases, we can indeed find nodes that need to be processed with the same key at the head and tail through these four comparisons and then move the corresponding indices. For example, in Figure 2-3, let's not think about the case where (p-3<=>p-1, p-2<=>p-3, p-3<=>p-3, p-2<=>p-1) does not find the same key. We will first consider how to move nodes when we encounter such situations.
Moving#
-
newVNode[newStartIndex].key === oldVNode[oldStartIndex].keyWhen equal, it means the node does not need to be moved; just perform a patch operation and then move both
newStartIndexandoldStartIndexforward. -
newVNode[newEndIndex].key === oldVNode[oldEndIndex].keyWhen equal, it means the node does not need to be moved; just perform a patch operation and then move both
newEndIndexandoldEndIndexbackward. -
newVNode[newEndIndex].key === oldVNode[oldStartIndex].keyOriginally at the head index position of the old node list, it now needs to move to the tail index position of the new node list, indicating that the node needs to be moved to the next position of
oldVNode[oldEndIndex], and then correctly update the indices involved in this round, movingnewEndIndexbackward andoldStartIndexforward. -
newVNode[newStartIndex].key === oldVNode[oldEndIndex].keyOriginally at the tail index position of the old node list, it now needs to move to the head index position of the new node list, indicating that the node needs to be moved to the previous position of
oldVNode[oldStartIndex], i.e., the head, and then correctly update the indices involved, movingnewStartIndexforward andoldEndIndexbackward.
In the example of Figure 2-3, these four conditions are sufficient. However, we can see in Figure 2-4 that there may be cases where none of these four conditions are met. How should we handle that?
Figure 2-4 Special Example
Clearly, we only need to take newVNode[newStartIndex] as the base and try to find the node with the same key in oldVNode. If found, perform a patch and then move the newStartIndex index forward. The node with the same key in oldVNode becomes undefined. Here, we forcibly search again in oldVNode and mark the found node as undefined to avoid unexpected situations caused by repeated processing when indexing this node later. However, we also need to add conditions to avoid oldVNode[oldStartIndex] or oldVNode[oldEndIndex] being undefined and timely update the indices of oldStartIndex or oldEndIndex as needed. Of course, since there are cases where we find the same key, there are also cases where we do not find it, indicating that newVNode[newStartIndex] is a new node that needs to be mounted.
Now that we have completed the situation judgment and handled special cases, in some more special examples, when the number of nodes on one side is different, it may happen that one side has oldStartIndex > oldEndIndex, terminating the loop, or one side has newStartIndex > newEndIndex, terminating the loop, causing nodes on the side with more nodes to remain unmounted/unmounted. We find that this situation is always unilateral, so we can summarize a certain rule to provide a fallback for the termination of the while loop.
Like the simple diff algorithm, I will also provide a code execution animation demonstration here to help us visualize and understand double-ended Diff, as seen in Figure 2-5.
Figure 2-5 Double-Ended Diff Execution Flow Diagram
/**
* Double-Ended Diff Algorithm
* @param oldVNode
* @param vNode
* @param container
*/
function doubleEndedDiff(oldVNode: (VNode | undefined)[], vNode: VNode[], container: ContainerElement) {
let oldStartIndex = 0;
let newStartIndex = 0;
let oldEndIndex = oldVNode.length - 1;
let newEndIndex = vNode.length - 1;
while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
const oldStartVNode = oldVNode[oldStartIndex];
const oldEndVNode = oldVNode[oldEndIndex];
const newStartVNode = vNode[newStartIndex];
const newEndVNode = vNode[newEndIndex];
// Prevent old nodes from being operated as undefined
if (!oldStartVNode) {
oldStartIndex++;
continue;
}
if (!oldEndVNode) {
oldEndIndex--;
continue;
}
// Four types of comparisons for moving nodes
if (oldStartVNode.key === newStartVNode.key) {
patch(oldStartVNode, newStartVNode, container)
oldStartIndex++;
newStartIndex++;
} else if (oldEndVNode.key === newEndVNode.key) {
patch(oldEndVNode, newEndVNode, container);
oldEndIndex--;
newEndIndex--;
} else if (oldStartVNode.key === newEndVNode.key) {
patch(oldStartVNode, newEndVNode, container);
insertElement(container, oldStartVNode._element, oldEndVNode._element?.nextSibling);
oldStartIndex++;
newEndIndex--;
} else if (oldEndVNode.key === newStartVNode.key) {
// Patch
patch(oldEndVNode, newStartVNode, container);
insertElement(container, oldEndVNode._element, oldStartVNode._element);
// Move index
oldEndIndex--;
newStartIndex++;
} else {
// Find the old node with the same key as the new node
const findOldIndex = oldVNode.findIndex(node => node && node.key === newStartVNode.key);
if (findOldIndex > 0) {
// Patch
patch(oldVNode[findOldIndex]!, newStartVNode, container);
insertElement(container, oldVNode[findOldIndex]!._element, oldStartVNode._element);
oldVNode[findOldIndex] = undefined;
newStartIndex ++;
} else { // Indicates that this newStartVNode is a new node
patch(null, newStartVNode, container, oldStartVNode._element);
newStartIndex++;
}
}
}
// The old nodes have been looped through, but there are remaining new nodes that need to be mounted
if (oldEndIndex < oldStartIndex && newStartIndex <= newEndIndex) {
for (let i = newStartIndex; i <= newEndIndex; i++) {
patch(null, vNode[i], container, vNode[i - 1]?._element?.nextSibling);
}
} else if(newEndIndex < newStartIndex && oldStartIndex <= oldEndIndex) {
for (let i = oldStartIndex; i <= oldEndIndex; i++) {
oldVNode[i] && unMountElement(oldVNode[i]!);
}
}
}
Fast#
Origin#
During the performance testing of Vue using the double-ended diff algorithm in the js-framework-benchmark, it was noted that the fast diff performance used by ivi and inferno is slightly better than that of Vue using the double-ended diff. It is necessary to understand and learn from their ideas and experiences to improve performance.
Figure 3-1 Performance Comparison of ivi, Inferno, Vue, and React
Some gossip: I have heard some people complain that React's performance is slow because React's internal virtual node data structure is a self-designed singly linked list structure, which prevents React from using double-ended diff algorithms and can only search for diffs in one direction. Some developers have borrowed React's ideas, discarded its self-designed data structure, and adopted double-ended diff, resulting in significant performance improvements, such as in Unis.
Thought#
There is a scenario where the preceding and succeeding nodes are the same, and only the middle part of the elements is different. In this case, there is a very similar algorithm called "pure text diff" that mainly applies to pure text, as shown in Figure 3-1.
Figure 3-1 Example of Pure Text Diff Concept
We find that in these two segments of old and new text, only the middle div has changed, while the surrounding text remains input. So can this idea help us process the new and old node lists? Let's observe the following example in Figure 3-2.
Figure 3-2 Example Applying Pure Text Diff Concept
We find that it seems like a good choice to first process the same preceding nodes (i.e., newVNode[startIndex] === oldVNode[startIndex]) and the same succeeding nodes (newVNode[endIndex] === oldVNode[endIndex]), and then separately handle the disordered nodes in the middle. This can avoid considering whether the current new node needs to be moved when encountering nodes that only require update operations.
However, upon further reflection, it seems a bit unbelievable that such an optimization point could improve performance so much. Of course, the fast diff algorithm also introduces the concept of the longest increasing subsequence. The purpose of introducing this concept is to handle the remaining nodes other than the same preceding and succeeding nodes more efficiently, helping with operations like moving, as seen in Figure 3-3.
Figure 3-3 Fast Diff Algorithm Node Movement Execution Diagram
Moving#
After looking at the above diagram, we notice a key point: how do we derive source? source is used to record the corresponding indices of new nodes in old nodes. We typically achieve this by using a double for loop, but this has the drawback of high time complexity, reaching O(n^2), meaning that as the data volume increases, the time consumption doubles.
const newVNodePatchCount = newEndIndex - startIndex + 1;
const source = new Array(newVNodePatchCount).fill(-1); // Mapping of new and old node positions
let moved = false;
let pos = 0;
// Double loop has high time complexity, O(n^2)
for (let i = startIndex; i <= newEndIndex; i++) {
for (let j = startIndex; j <= oldEndIndex; j++) {
if (vNode[i].key === oldVNode[j].key) { // Find the mapping point of new and old nodes
patch(oldVNode[j], vNode[i], container);
source[i - startIndex] = j;
if (j < pos) { // Locate the maximum index in the new node tree, which can be used to determine whether to move nodes
moved = true;
} else {
pos = j;
}
break;
}
}
}
// Traverse the old node list to unmount nodes that were not reused
oldVNode.forEach(oldElement => {
if (!vNode.find(newElement => newElement.key === oldElement.key)) {
unMountElement(oldElement);
};
});
Time complexity is a fundamental concept that must be mastered in algorithms, used to roughly represent the time consumption of a piece of code. It is often accompanied by space complexity, which is used to represent the memory size required/consumed by a piece of code. In today's era of ample memory capacity, it is common to use space to exchange time to reduce time complexity, meaning using more memory to lower time complexity.
Looking back at the above code, does it feel familiar? Yes, it is the simple Diff algorithm. Except for the lack of node movement and new node functionality, everything else is basically the same. Next, let's observe the following optimized code.
const newVNodePatchCount = newEndIndex - startIndex + 1;
const source = new Array(newVNodePatchCount).fill(-1); // Mapping of new and old node positions
let moved = false;
let pos = 0;
const keySourceMap: Record<number | string | symbol, number> = {};
for (let i = startIndex; i <= newEndIndex; i++) {
keySourceMap[vNode[i].key!] = i; // Use unique key + array retention to associate the differences between the new and old trees
}
for (let i = startIndex; i <= oldEndIndex; i++) {
const sourceKey = keySourceMap[oldVNode[i].key!];
if (sourceKey !== undefined) { // Indicates that there are reusable nodes
patch(oldVNode[i], vNode[sourceKey], container); // Patch operation
source[sourceKey - startIndex] = i; // Mapping point of new and old nodes with the same key
if (sourceKey < pos) { // Locate the maximum index in the new node tree, which can be used to determine whether to move nodes
moved = true;
} else {
pos = sourceKey;
}
} else { // If not found, it indicates that this old node needs to be unmounted
unMountElement(oldVNode[i]);
};
}
We find that the original O(n^2) time complexity of the double for loop has been successfully split, reducing the time complexity to O(n). However, we notice an additional variable called keySourceMap. This is the optimization method we used, space to exchange time.
Now, the next step is to calculate the longest increasing subsequence based on source. We need to consider why the longest increasing subsequence is necessary. The longest increasing subsequence is a list of increasing items, indicating that the order of nodes in this longest increasing subsequence is correct and does not require node movement, thus minimizing the number of node movements. This is the greatest role of the longest increasing subsequence here.
Next, as before, I will provide a code execution animation demonstration of the fast diff, please refer to Figure 3-4.
Figure 3-4 Fast Diff Algorithm Execution Flow Diagram
/**
* Fast Diff Algorithm
* @param oldVNode
* @param vNode
* @param container
*/
function fastDiff(oldVNode: VNode[], vNode: VNode[], container: ContainerElement) {
let startIndex = 0;
while(oldVNode[startIndex] && vNode[startIndex] && oldVNode[startIndex]?.key === vNode[startIndex]?.key) { // Preceding node check
patch(oldVNode[startIndex], vNode[startIndex], container);
startIndex ++;
};
let oldEndIndex = oldVNode.length - 1;
let newEndIndex = vNode.length - 1;
// If the preceding nodes have already checked one of the new or old nodes, there is no need to check the succeeding nodes. If this layer of detection is not done, it may lead to unexpected rendering situations.
if ((startIndex !== oldVNode.length) || (startIndex !== vNode.length)) {
while(oldVNode[oldEndIndex] && vNode[newEndIndex] && oldVNode[oldEndIndex].key === vNode[newEndIndex].key) { // Succeeding node check
patch(oldVNode[oldEndIndex], vNode[newEndIndex], container);
oldEndIndex--;
newEndIndex--;
};
}
if (newEndIndex >= startIndex && oldEndIndex < startIndex) { // Indicates that the old nodes have been checked, but there are still unexamined nodes in the new nodes
for (let i = startIndex; i <= newEndIndex; i++) {
patch(null, vNode[i], container, vNode[newEndIndex + 1]?._element); // Mount
}
} else if (newEndIndex < startIndex && oldEndIndex >= startIndex) { // Indicates that the new nodes have been checked, but there are still unexamined nodes in the old nodes
for (let i = startIndex; i <= oldEndIndex; i++) {
unMountElement(oldVNode[i]); // Unmount
}
} else { // Indicates that there are still unmounted/unmounted nodes in both new and old nodes
// doubleEndedDiff(oldVNode.slice(startIndex, oldEndIndex + 1), vNode.slice(startIndex, newEndIndex + 1), container);
const newVNodePatchCount = newEndIndex - startIndex + 1;
const source = new Array(newVNodePatchCount).fill(-1); // Mapping of new and old node positions
let moved = false;
let pos = 0;
// Double loop has high time complexity, O(n^2)
// for (let i = startIndex; i <= newEndIndex; i++) {
// for (let j = startIndex; j <= oldEndIndex; j++) {
// if (vNode[i].key === oldVNode[j].key) { // Find the mapping point of new and old nodes
// patch(oldVNode[j], vNode[i], container);
// source[i - startIndex] = j;
// if (j < pos) { // Locate the maximum index in the new node tree, which can be used to determine whether to move nodes
// moved = true;
// } else {
// pos = j;
// }
// break;
// }
// }
// }
// // Traverse the old node list to unmount nodes that were not reused
// oldVNode.forEach(oldElement => {
// if (!vNode.find(newElement => newElement.key === oldElement.key)) {
// unMountElement(oldElement);
// };
// });
// Space to exchange time, reducing time complexity, O(n)
const keySourceMap: Record<number | string | symbol, number> = {};
for (let i = startIndex; i <= newEndIndex; i++) {
keySourceMap[vNode[i].key!] = i; // Use unique key + array retention to associate the differences between the new and old trees
}
for (let i = startIndex; i <= oldEndIndex; i++) {
const sourceKey = keySourceMap[oldVNode[i].key!];
if (sourceKey !== undefined) { // Indicates that there are reusable nodes
patch(oldVNode[i], vNode[sourceKey], container); // Patch operation
source[sourceKey - startIndex] = i; // Mapping point of new and old nodes with the same key
if (sourceKey < pos) { // Locate the maximum index in the new node tree, which can be used to determine whether to move nodes
moved = true;
} else {
pos = sourceKey;
}
} else { // If not found, it indicates that this old node needs to be unmounted
unMountElement(oldVNode[i]);
};
}
if (moved) {
// Calculate the longest increasing subsequence
const result = getSequence(source);
let longestLastIndex = result.length - 1; // Last index of the longest increasing subsequence
let newLastIndex = newEndIndex - startIndex; // Last index value of the new node list starting from the startIndex
for (let i = newLastIndex; i >= 0; i--) { // Reverse loop
if (source[i] === -1) { // Indicates that this node is a new node
const currentVNode = vNode[i + startIndex];
patch(null, currentVNode, container, vNode[i + startIndex + 1]?._element); // Insert using the next node of the current new node as the anchor
} else if (i !== result[longestLastIndex]) { // Not the longest increasing subsequence, the node needs to be moved
// The nodes have been patched (the element properties have also been synchronized), only node movement needs to be considered, and the anchor position is still handled as above for new nodes
const currentVNode = vNode[i + startIndex];
insertElement(container, currentVNode._element, vNode[i + startIndex + 1]?._element);
} else { // Indicates that we have encountered the longest increasing subsequence, this node does not need to be moved, move the longestLastIndex index forward
longestLastIndex--;
}
}
};
}
};
References#
"Vue.js Design and Implementation," Chapters 7, 8, 9, 10, and 11.