Virtual DOM and Diff Algorithm

Virtual DOM

Virtual DOM is essentially a data structure that uses JavaScript objects to describe the structure of the real DOM.

• Real DOM: A large, complex object tree provided by the browser. Directly manipulating it is expensive (triggers reflows and repaints).
• Virtual DOM: Lightweight JS objects that are cheap to manipulate.

Real HTML

<div id="app" class="container">
  <h1>Hello</h1>
</div>

Corresponding Virtual DOM

const vnode = {
  tag: 'div',
  props: { id: 'app', class: 'container' },
  children: [
    { tag: 'h1', props: {}, children: ['Hello'] }
  ]
}

The Virtual DOM is the carrier of the Diff algorithm. When data changes, instead of directly manipulating the real DOM, we generate a new Virtual DOM tree, then use the Diff algorithm to compare the old and new trees, find the minimal differences, and finally update the real DOM with minimal cost.

Therefore, the statement "Virtual DOM is faster than real DOM" is not precise. The Virtual DOM itself is just a JavaScript object that facilitates diffing; the real performance gain comes from the minimal update strategy computed by the Diff algorithm. A more accurate formula is:

Efficient view update = Virtual DOM + Diff algorithm + Minimal DOM operations

Diff Algorithm

The Diff algorithm is a comparison algorithm used to find the minimal differences between old and new Virtual DOM trees. It then updates only the changed parts of the real DOM, skipping unchanged nodes, thereby improving update efficiency.

Comparison Flow

The Diff algorithm uses depth-first traversal and performs comparison only at the same level for child nodes. Starting from the root, it first compares the current node; if reusable, it recursively enters the child node arrays for comparison. After processing child nodes, it moves to the next sibling node at the same level.

When reactive data inside a component changes, it triggers the setter, which notifies all subscribers (Watchers) via Dep.notify, ultimately calling the patch method for comparison.

patch

The core of patch is to determine, via sameVnode, whether the old and new virtual nodes are of the same type:

• Yes: Call patchVnode for deep comparison and reuse.
• No: Direct replacement — remove the real DOM corresponding to the old node, create and insert the new node.

function patch(oldVnode, newVnode) {
  if (sameVnode(oldVnode, newVnode)) {
    // Same type, compare deeply
    patchVnode(oldVnode, newVnode)
  } else {
    // Different types, replace entirely
    const parent = oldVnode.el.parentNode
    const el = createElm(newVnode)  // Create real DOM from new vnode
    if (parent) {
      parent.insertBefore(el, oldVnode.el)  // Insert new node
      parent.removeChild(oldVnode.el)       // Remove old node
    }
  }
}

function sameVnode(a, b) {
  return (
    a.key === b.key && // same key
    a.tag === b.tag    // same tag name
    sameInputType(a, b) // For input tags, same type
    // other conditions ...
  )
}

patchVnode

patchVnode is used to compare the properties, text, and children of two same-type nodes. The general flow:

1. If the old and new nodes are identical (oldVnode === newVnode), return immediately.
2. If the new node is a text node (i.e., newVnode.text exists) and differs from the old text, update the real DOM text content.
3. Otherwise, the nodes may have children:
   • Both have children: Call updateChildren for head/tail pointer comparison.
   • Only new node has children: Create new child nodes and insert them into the real DOM.
   • Only old node has children: Remove old child nodes from the real DOM.
   • Neither has children: No extra processing.

function patchVnode(oldVnode, newVnode) {
  const el = (newVnode.el = oldVnode.el) // Reuse real DOM reference
  const oldCh = oldVnode.children
  const newCh = newVnode.children

  // Same object, no processing needed
  if (oldVnode === newVnode) return

  // New node is a text node
  if (newVnode.text != null) {
    if (oldVnode.text !== newVnode.text) {
      el.textContent = newVnode.text
    }
  } else {
    // New node has children
    if (oldCh && newCh) {
      // Both have children, enter core diff
      if (oldCh !== newCh) {
        updateChildren(el, oldCh, newCh)
      }
    } else if (newCh) {
      // Only new has children: create and add
      addVnodes(el, null, newCh, 0, newCh.length - 1)
    } else if (oldCh) {
      // Only old has children: remove old children
      removeVnodes(el, oldCh, 0, oldCh.length - 1)
    }
    // If neither has children, do nothing
  }
}

updateChildren

updateChildren is the core of the double-ended Diff (head/tail pointer method). It compares two arrays of child nodes at the same level. Four pointers are maintained: oldStartIdx, oldEndIdx, newStartIdx, newEndIdx. The loop executes the following logic:

1. Quick head/tail attempts (in order):

   • oldStart vs newStart: If same, patch and move both head pointers right (no DOM movement needed).
   • oldEnd vs newEnd: If same, patch and move both tail pointers left (no DOM movement needed).
   • oldStart vs newEnd: If same, patch and move the real DOM node of oldStart after oldEnd, then move oldStart right and newEnd left.
   • oldEnd vs newStart: If same, patch and move the real DOM node of oldEnd before oldStart, then move oldEnd left and newStart right.

2. Out-of-order lookup: If none of the above four comparisons match, look for the newStart node within the old node range (oldStartIdx..oldEndIdx):

   • Found: Patch, then move the real DOM of that old node before oldStart (before unprocessed nodes), mark that position in the old array as undefined (to avoid duplicate processing), and only move newStartIdx right.
   • Not found: Treat as a new node, create its real DOM and insert before oldStart, then move newStartIdx right.

3. Skipping boundaries: At the start of each loop, if oldStartIdx or oldEndIdx points to undefined, simply move that pointer inward and skip.

4. Cleanup:

   • If oldStartIdx > oldEndIdx (old nodes exhausted first), the remaining new nodes are all additions — batch create and insert.
   • If newStartIdx > newEndIdx (new nodes exhausted first), the remaining old nodes (non-undefined) are all to be removed.

Example walkthrough: Consider the following old and new nodes. The initial real DOM is a, b, c, d, e.

<!-- Old nodes -->
<ul>
  <li>a</li><li>b</li><li>c</li><li>d</li><li>e</li>
</ul>
<!-- New nodes -->
<ul>
  <li>a</li><li>d</li><li>e</li><li>f</li>
</ul>

Initial state:

DOM: a b c d e
old: [a] b c d [e]    (os=0, oe=4)
new: [a] d e [f]      (ns=0, ne=3)

Step 1: oldStart a vs newStart a — match.

No DOM movement, os++, ns++.

DOM: a b c d e
old: a [b] c d [e]   (os=1, oe=4)
new: a [d] e [f]     (ns=1, ne=3)

Step 2: None of the four comparisons match. Look for newStart d in old range [b,c,d,e], found at index 3.

Move the real DOM of d before oldStart b, mark old[3] as undefined, ns++.

DOM: a d b c e
old: a [b] c undefined [e]   (os=1, oe=4)
new: a d [e] [f]             (ns=2, ne=3)

Step 3: oldEnd e vs newStart e — match.

Move the real DOM of oldEnd e before oldStart b (i.e., after d), oe--, ns++.

DOM: a d e b c
old: a [b] c undefined e   (os=1, oe=3, oe now points to undefined at index 3)
new: a d e [f]             (ns=3, ne=3)

Note: At the start of the next loop, because oe points to undefined, it will move left again to index 2 (c), so the range becomes os=1, oe=2.

Step 4: Current valid range [b, c], newStart is f. All four comparisons fail, and f is not found.

Create the real DOM for f and insert before oldStart b, ns++ → ns=4 > ne, loop ends.

DOM: a d e f b c
old: a [b] [c] undefined e   (os=1, oe=2)
new: a d e [f] []          (ns>ne)

Cleanup: ns > ne, delete the old range from os=1 to oe=2 (i.e., b and c).

Final real DOM: a, d, e, f, matching the new Virtual DOM structure.