Reconciliation Algorithm

The Diffing Problem

Here's a number that should surprise you: comparing two arbitrary trees is O(n³) in the general case. For a tree with 1,000 nodes, that is one billion operations. React needs to diff trees 60 times per second. The general algorithm is completely unusable.

So React cheats — brilliantly. It solves this with two heuristics that reduce the problem to O(n):

1. Elements of different types produce different trees — if a <div> becomes a <span>, React does not attempt to patch it. It unmounts the entire old subtree and mounts a new one.
2. The key prop hints which children are stable across renders — React uses keys to match children in the old tree to children in the new tree without scanning the entire list.

These heuristics are not guaranteed to produce the minimum number of DOM mutations. They are designed to produce correct results fast in the 99.9% case.

Same Type: Update

This is the happy path. When the old and new elements have the same type, React keeps the DOM node and updates only the changed attributes.

// Old
<div className="before" title="stuff" />

// New
<div className="after" title="stuff" />

// React's action: keep the DOM node, update className from "before" to "after"
// title is unchanged — no DOM operation needed

For components, same type means React keeps the instance (class) or the fiber (function). It calls the component again with new props, and the reconciliation continues recursively into the component's children.

// Old
<UserCard name="Alice" role="engineer" />

// New
<UserCard name="Alice" role="senior engineer" />

// React's action: keep the UserCard fiber, call it with new props
// The component re-renders with role="senior engineer"
// React then reconciles UserCard's returned JSX against the previous output

Different Type: Unmount and Mount

And here's where React gets ruthless. When the element type changes, React tears down the entire old subtree — unmounting all components, destroying state, removing DOM nodes — and builds the new subtree from scratch.

// Old
<div>
  <Counter />    {/* Has internal state: count = 5 */}
  <p>Hello</p>
</div>

// New
<section>
  <Counter />    {/* Fresh mount: count = 0 */}
  <p>Hello</p>
</section>

// React's action:
// 1. Unmount entire <div> subtree (Counter loses state, <p> removed from DOM)
// 2. Mount entire <section> subtree (new Counter with count=0, new <p>)

This is aggressive but correct. React assumes that structurally different containers produce structurally different content. In practice, this heuristic is right almost always.

// BUG: toggling isSpecial unmounts and remounts the entire form
function Page({ isSpecial }) {
  if (isSpecial) {
    return <div className="special"><Form /></div>;
  }
  return <section className="normal"><Form /></section>;
}
// Fix: use the same container type, change only the className
function Page({ isSpecial }) {
  return (
    <div className={isSpecial ? 'special' : 'normal'}>
      <Form />
    </div>
  );
}

List Reconciliation: Why Keys Matter

This is the part that burns people in production more than almost anything else. When reconciling a list of children, React needs to figure out which items are new, which were removed, and which just moved. Without keys, React can only compare children by position.

Without Keys (Index-Based)

// Old
<ul>
  <li>Alice</li>    {/* index 0 */}
  <li>Bob</li>      {/* index 1 */}
</ul>

// New (Charlie prepended)
<ul>
  <li>Charlie</li>  {/* index 0 — React thinks this is "Alice updated to Charlie" */}
  <li>Alice</li>    {/* index 1 — React thinks this is "Bob updated to Alice" */}
  <li>Bob</li>      {/* index 2 — React creates a new node */}
</ul>

// React's action without keys:
// 1. Update text of li[0] from "Alice" to "Charlie"
// 2. Update text of li[1] from "Bob" to "Alice"
// 3. Insert new li[2] with "Bob"
// Three DOM mutations. All components at index 0 and 1 re-render with wrong props.

Every child "shifts" — React updates every single item. And here's the really nasty part: if these list items have state (checkboxes, form inputs, animations), that state gets attached to the wrong items.

With Keys

// Old
<ul>
  <li key="alice">Alice</li>
  <li key="bob">Bob</li>
</ul>

// New
<ul>
  <li key="charlie">Charlie</li>
  <li key="alice">Alice</li>
  <li key="bob">Bob</li>
</ul>

// React's action with keys:
// 1. "charlie" is new — insert new li
// 2. "alice" — same key, same type, same props — no update needed
// 3. "bob" — same key, same type, same props — no update needed
// One DOM insertion. Existing components keep their state.

The Key Reconciliation Algorithm

React's key-based reconciliation uses a two-pass approach for lists:

Pass 1: Linear scan from the start. Compare old children and new children position by position. As long as keys match, update in place. Stop at the first mismatch.

Pass 2: Map-based matching. Build a map of key → old fiber for remaining old children. Walk through remaining new children, looking up each key in the map. If found: reuse the fiber (move). If not found: create new.

// Simplified from ReactChildFiber.js — reconcileChildrenArray
function reconcileChildrenArray(returnFiber, currentFirstChild, newChildren) {
  let oldFiber = currentFirstChild;
  let newIdx = 0;

  // PASS 1: Match from the beginning
  for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
    if (oldFiber.key !== newChildren[newIdx].key) {
      break; // Keys diverge — switch to map-based
    }
    // Same key: update this fiber with new props
    updateSlot(returnFiber, oldFiber, newChildren[newIdx]);
    oldFiber = oldFiber.sibling;
  }

  // PASS 2: Build map, match remaining
  const existingChildren = mapRemainingChildren(oldFiber);
  for (; newIdx < newChildren.length; newIdx++) {
    const matchedFiber = existingChildren.get(newChildren[newIdx].key);
    if (matchedFiber) {
      // Reuse existing fiber (move operation)
      existingChildren.delete(newChildren[newIdx].key);
    } else {
      // Create new fiber (insertion)
    }
  }

  // Delete remaining old fibers not matched by any new child
  existingChildren.forEach(child => deleteChild(returnFiber, child));
}

Render Phase vs Commit Phase

Now let's talk about the two-phase architecture — and understanding the boundary between them is critical for everything from debugging to performance optimization.

Render Phase (Pure, Interruptible)

The render phase walks the fiber tree, calling components, diffing output, and building a list of changes needed. It produces side effects but does not execute them.

• Calls component functions / class render() methods
• Runs hooks (useState, useMemo, etc.)
• Diffs old vs new fiber children
• Tags fibers with effect flags: Placement, Update, Deletion
• No DOM mutations, no lifecycle side effects
• Can be interrupted, restarted, or abandoned (in concurrent mode)

Commit Phase (Effectful, Synchronous)

The commit phase takes the completed fiber tree and applies all effects to the DOM in one synchronous batch.

1. Before mutation: Read DOM measurements (getSnapshotBeforeUpdate)
2. Mutation: Apply all DOM changes (insertions, updates, deletions)
3. Layout: Run useLayoutEffect callbacks, componentDidMount/componentDidUpdate
4. After the browser paints: Run useEffect callbacks

Render Phase                          Commit Phase
─────────────                         ────────────
beginWork(App)                        ┌─ Before Mutation
beginWork(Header)                     │   getSnapshotBeforeUpdate
completeWork(Header)                  │
beginWork(Main)          ──commit──→  ├─ Mutation
beginWork(Content)                    │   DOM insertions/updates/deletions
completeWork(Content)                 │
completeWork(Main)                    ├─ Layout
completeWork(App)                     │   useLayoutEffect callbacks
                                      │
[Interruptible]                       └─ [Synchronous, uninterruptible]
                                      
                                      Browser paints
                                      ↓
                                      useEffect callbacks (async)

Effect Flags and the Subtree Flags Optimization

Here's a clever optimization you'll appreciate. React tags each fiber with flags indicating what effects it needs:

const Placement    = 0b0000000000000010;  // New node — needs DOM insertion
const Update       = 0b0000000000000100;  // Changed — needs DOM attribute update
const Deletion     = 0b0000000000001000;  // Removed — needs DOM removal
const ChildDeletion = 0b0000000000010000; // A child was deleted

In older React, the commit phase walked the entire fiber tree looking for fibers with flags. With the subtreeFlags optimization (React 18+), each fiber aggregates its children's flags upward during completeWork:

// During completeWork, bubble child flags up
fiber.subtreeFlags |= child.flags | child.subtreeFlags;

Now during the commit phase, React can skip entire subtrees that have no effects:

if (fiber.subtreeFlags === NoFlags && fiber.flags === NoFlags) {
  // Skip this entire subtree — nothing changed
  return;
}

For a tree of 10,000 fibers where only 5 changed, the commit phase visits ~20 fibers instead of 10,000.

Reconciliation Rules Summary