Understanding Vue's Diff Algorithm: A Step‑by‑Step Guide

This article introduces the Vue diff algorithm, a core part of Vue's virtual DOM rendering process, and demonstrates how to compare two arrays of VNode objects to efficiently update the real DOM.

Prerequisite Knowledge

Understand that Vue 3 uses vnode objects.

Know that a vnode is essentially a JavaScript object.

Be aware that a vnode has a children property which can be a string or an array.

With this background, you can start analyzing how Vue implements diff by comparing two arrays.

What to Do

Assume you have two arrays and need to find their differences. Consider three scenarios:

Same elements at the left side, differences later (image omitted).

Same elements at the right side, differences earlier (image omitted).

One array is longer than the other.

Left‑Side Comparison

Initialize i = 0 and increment it until a mismatching node is found, using the condition i <= c1.length - 1 && i <= c2.length - 1 and checking c1[i] === c2[i] . The index i then marks the first differing position from the left.

Right‑Side Comparison

The right‑side comparison mirrors the left‑side logic but iterates from the end of the arrays toward the start, using separate indices for each array.

Combining Left and Right

For example, comparing [A,B,C,D,E,F] with [A,B,D,C,E,F] yields a left‑side index of 2 and a right‑side index of 3.

function diff(c1: VNode[], c2: VNode[]) {
  let e1 = c1.length - 1;
  let e2 = c2.length - 1;
  let i = 0;
  // left
  while (i <= e1 && i <= e2) {
    let n1 = c1[i];
    let n2 = c2[i];
    if (isSomeVNodeType(n1, n2)) {
      // unchanged element, render directly
    } else {
      break;
    }
    i++;
  }
  // right
  while (i <= e1 && i <= e2) {
    let n1 = c1[e1];
    let n2 = c2[e2];
    if (isSomeVNodeType(n1, n2)) {
      // unchanged element, render directly
    } else {
      break;
    }
    e1--;
    e2--;
  }
}

function isSomeVNodeType(n1: VNode, n2: VNode) {
  return n1.type === n2.type && n1.key === n2.key;
}

When the New Array Is Longer

If the new array is longer, the differing region lies between i and e2 . The algorithm inserts the extra nodes:

if (i > e1 && i <= e2) {
  while (i <= e2) {
    // insert c2[i]
    i++;
  }
}

When the Old Array Is Longer

If the old array is longer, the algorithm removes the surplus nodes:

if (i <= e1 && i > e2) {
  while (i <= e1) {
    // delete c1[i]
    i++;
  }
}

Handling Equal Length with Internal Differences

When lengths match but a middle segment differs, the algorithm creates a mapping of new nodes, deletes nodes absent in the new array, and moves nodes that changed position. It uses a Map for key‑to‑index lookup and computes the longest increasing subsequence to minimize moves.

// Build key‑to‑new‑index map
const keyToNewIndexMap = new Map();
for (let i = s2; i <= e2; i++) {
  const newChild = c2[i];
  keyToNewIndexMap.set(newChild.key, i);
}

// Track old‑to‑new index mapping
const newIndexToOldIndexMap = new Array(toBePatched);
for (let i = 0; i < toBePatched; i++) {
  newIndexToOldIndexMap[i] = 0;
}

// Process each old node
for (let i = s1; i <= e1; i++) {
  const preChild = c1[i];
  // ... (logic to find newIndex, delete, or mark for move)
}

Summary

Bidirectional comparison isolates the differing region between two VNode arrays.

Key comparison determines whether two VNodes represent the same element.

Within the differing region, only three operations are needed: insert, delete, or move.

A Map is used to build a lookup table for fast key‑based matching.

The longest increasing subsequence helps identify nodes that can stay in place, reducing the number of moves.

If the article helped you, feel free to follow, like, and bookmark.