Understanding Vue2 and Vue3 Diff Algorithms: Core Principles and Process

The diff algorithm is an efficient method that compares nodes on the same tree level, avoiding full tree traversal and achieving O(n) time complexity. It is widely used, for example, in Vue’s virtual DOM to compare old and new VNode trees during rendering.

Two notable characteristics of the algorithm are:

Comparisons are performed only within the same level, never across levels.

During the diff process, pointers move from both ends toward the middle.

Vue 2 Diff Algorithm Core

Basic Principle

First compare the heads and tails of the old and new node lists to find unchanged nodes.

Then perform cross‑comparison (head vs. tail) to locate reusable moved nodes.

Create a keyToIndex hash map for the old nodes and use it to find reusable nodes in the new list.

Finally, remove excess old nodes or add missing new nodes.

Diff Process

Step 1: Initialization

let oldStartIdx = 0 // 老vnode遍历的开始下标

let newStartIdx = 0 // 新vnode遍历的开始下标

let oldEndIdx = oldCh.length - 1 // 老vnode 列表长度

let oldStartVnode = oldCh[0] // 老vnode列表第一个子元素

let oldEndVnode = oldCh[oldEndIdx] // 老vnode列表最后一个子元素

let newEndIdx = newCh.length - 1 // 新vnode列表长度

let newStartVnode = newCh[0] // 新vnode列表第一个子元素

let newEndVnode = newCh[newEndIdx] // 新vnode列表最后一个子元素

Step 2: Loop through nodes

Four cases are handled during each iteration:

Case 1 – if (sameVnode(oldStartVnode, newStartVnode)) { patchVnode(...); oldStartVnode = oldCh[++oldStartIdx]; newStartVnode = newCh[++newStartIdx]; }

Case 2 – else if (sameVnode(oldEndVnode, newEndVnode)) { patchVnode(...); oldEndVnode = oldCh[--oldEndIdx]; newEndVnode = newCh[--newEndIdx]; }

Case 3 – else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right patchVnode(...); canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm)); oldStartVnode = oldCh[++oldStartIdx]; newEndVnode = newCh[--newEndIdx]; }

Case 4 – else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left patchVnode(...); canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm); oldEndVnode = oldCh[--oldEndIdx]; newStartVnode = newCh[++newStartIdx]; }

If none of the above matches, a hash map keyToOldIdx is created (or reused) to locate a reusable old node by key. If a matching node is found, it is patched and moved; otherwise a new element is created with createElm .

Step 3: Add or Remove Nodes

// oldStartIdx > oldEndIdx 说明老的 vnode 已遍历完

if (oldStartIdx > oldEndIdx) { // add remaining new nodes }

// newStartIdx > newEndIdx 说明新的 vnode 已遍历完

else if (newStartIdx > newEndIdx) { // remove remaining old nodes }

In the example, after the loop the new list is longer, so the remaining node F is created and inserted after B .

Vue 3 Diff Algorithm Core

Basic Principle

Head‑to‑head and tail‑to‑tail comparisons are performed first.

A map keyToNewIndexMap is built for the remaining new nodes.

The longest increasing subsequence (LIS) of the mapped indices is computed; nodes that belong to the LIS stay in place.

Other nodes are moved, added, or removed based on the LIS result.

Diff Process

Step 1: Initialization

let i = 0; // new/old vnode start index

const l2 = c2.length; // new vnode length

let e1 = c1.length - 1; // old vnode end index

let e2 = l2 - 1; // new vnode end index

Step 2: Head Comparison

while (i <= e1 && i <= e2) { const prevChild = c1[i]; const nextChild = c2[i]; if (!isSameVNodeType(prevChild, nextChild)) { break; } patch(prevChild, nextChild, container, parentAnchor, parentComponent); i++; }

Step 3: Tail Comparison

while (i <= e1 && i <= e2) { const prevChild = c1[e1]; const nextChild = c2[e2]; if (!isSameVNodeType(prevChild, nextChild)) { break; } patch(prevChild, nextChild, container, parentAnchor, parentComponent); e1--; e2--; }

Step 4: Process Remaining Nodes

If old nodes are exhausted, create the remaining new nodes.

If new nodes are exhausted, remove the remaining old nodes.

Otherwise, build keyToNewIndexMap , create newIndexToOldIndexMap , compute the LIS with getSequence , and then iterate backwards to insert or move nodes as needed.

// Build keyToNewIndexMap

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

// Initialize newIndexToOldIndexMap

const toBePatched = e2 - s2 + 1;

const newIndexToOldIndexMap = new Array(toBePatched); for (let i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0;

// Traverse old nodes and fill the map

for (let i = s1; i <= e1; i++) { const prevChild = c1[i]; let newIndex; if (prevChild.key != null) { newIndex = keyToNewIndexMap.get(prevChild.key); } else { // fallback linear search ... }

if (newIndex === undefined) { hostRemove(prevChild.el); } else { newIndexToOldIndexMap[newIndex - s2] = i + 1; // track for LIS }

}

// Compute LIS

const increasingNewIndexSequence = moved ? getSequence(newIndexToOldIndexMap) : [];

Finally, a backward loop creates missing nodes and moves nodes that are not part of the LIS:

for (let 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) { patch(null, nextChild, container, anchor, parentComponent); } else if (moved) { if (j < 0 || increasingNewIndexSequence[j] !== i) { hostInsert(nextChild.el, container, anchor); } else { j--; } } }

Diff Summary

Vue 2 builds a {key → oldVnode} map and moves nodes directly when a matching key is found.

Vue 3 builds an index‑mapping array, computes the longest increasing subsequence, keeps those nodes stationary, and moves the rest, resulting in fewer DOM operations.