Part 7 · 6 chapters · ~40 min

Reconciliation

React does not compute the optimal tree diff; it makes two assumptions that turn O(n³) into one pass, stores the tree so the pass can pause, reconciles siblings with the keyed algorithm, and skips subtrees whose inputs are unchanged by reference. This part is each of those as an algorithm, then the alternatives that diff less or not at all, and how to measure which part is the cost.

Why O(n) and not O(n³)

the question

"React diffs the whole tree on every render. How is that not quadratic, or worse?"

Because it does not compute the optimal diff. The general tree-edit-distance problem is O(n³); React replaces it with a single depth-first pass that makes two assumptions: a node of a different type at the same position is a different node (replace the subtree, do not search for it elsewhere), and siblings are identified by keys (so reorders are found by lookup, not search). With those, each new node is visited once and each parent's children are reconciled in linear time. The cases where the assumptions are wrong (a subtree moved across levels, a wrapper inserted) cost a remount, which is correct and merely suboptimal.

the walk at one node

Compare types. Old fiber's type (a string for host elements, a function or class for components) against the new element's. Different → delete the old fiber's subtree, create a new fiber for the element; done with this position. Same → proceed.
Check for a bailout (chapter 4): same props by reference, no pending lanes, no context change → clone and skip the render; descend only if a descendant has pending work.
Render: call the component (or compute host props); the output is a new array of child elements.
Reconcile children: single child → compare directly; array → the keyed algorithm (chapter 3). The result is the next layer of fibers with Placement, Update or Deletion flags.
Continue to the first child; on completion, to the sibling; then up (chapter 2's traversal).

the assumptions' failure cases

Type change with identical children: <div><Form/></div> becoming <section><Form/></section> remounts Form; its state is lost. Keep wrappers stable, or lift the state.
Conditional wrapper: {cond ? <Wrapper><Child/></Wrapper> : <Child/>} remounts Child when cond flips (different type at that position). Render the wrapper always, or key the Child to force identity.
Cross-parent move: an item dragged from list A to list B is a delete and an insert. Unavoidable in this model; keep the moved item's state outside it.
Component identity by function reference: a component defined inside another component's render is a new function each render: a new type every time: a remount every render. The most common accidental remount.

FROM O(n³) TO O(n)

the two assumptions that make tree diffing linear

swipe the figure sideways, or tap expand for full screen

1/6

the general problem

Two trees: the previous render's fibers and the new element tree from render. The general problem: find the cheapest sequence of operations turning one into the other, where a subtree may have moved anywhere. Known algorithms (Zhang-Shasha and successors) are O(n³) or worse for unordered trees. 1,000 nodes: a billion operations.

The fiber tree: a traversal you can pause

React's data structure for the tree is chosen for one property: the traversal state must live on the heap, not the native stack, so that rendering can stop after any unit of work and resume later. Child, sibling and return pointers turn depth-first traversal into a loop over a single pointer.

the representation

Left-child, right-sibling: an n-ary tree stored with two pointers per node (first child, next sibling) plus a parent pointer (return). The classic encoding of an arbitrary tree as a binary one.
The loop: next = beginWork(fiber) returns the first child (or null). If null, completeUnitOfWork: complete the fiber, then try the sibling; if none, go to return and complete that; repeat until a sibling exists or the root is completed.
The state: one variable, workInProgress. Stop the loop at any point; the variable says where to continue.
Two trees: current (committed) and workInProgress (being built), linked by alternate. Fibers are reused across renders through the alternate; a mount allocates, an update reuses. Commit sets root.current to the finished work-in-progress tree. A discarded render discards only work-in-progress fibers that were newly created; alternates stay.

what the representation costs and buys

Buys: interruptibility (part 5), the ability to restart with a different lane set, and effect lists built during completion so commit does not re-walk the tree.
Costs: ~30 fields per fiber (a few hundred bytes); pointer chasing rather than array iteration; allocation on mount for every element (not reused until the next render). A 10,000-element tree is 10,000 fibers × 2 (alternates) in memory.
Why not recursion: a recursive reconciler (React 15's stack reconciler) could not yield mid-tree: the position was in native frames. Unwinding to yield would have lost the work. The fiber rewrite (2017) existed for this.

the general technique

Any recursive traversal can be made resumable by moving its stack into the heap: an explicit stack of frames, or, as here, parent pointers so no stack is needed. Generators do the same with the engine's help (the JS course part 9), which is why some schedulers are written as generators.

THE FIBER TREE AS A LINKED TRAVERSAL

child, sibling, return: resumable depth-first without a stack

swipe the figure sideways, or tap expand for full screen

1/6

the pointers

The tree: App > [Header, Main > [List > [Item, Item], Aside]]. As fibers: App.child = Header; Header.sibling = Main; Main.child = List; List.child = Item1; Item1.sibling = Item2; List.sibling = Aside; every node's return points to its parent.

Keyed reconciliation, step by step

code

// reconcileChildrenArray, in outline (ReactChildFiber.js): the keyed diff from part 1, specialised
function reconcileChildrenArray(returnFiber, currentFirstChild, newChildren) {
  let oldFiber = currentFirstChild, lastPlacedIndex = 0, newIdx = 0, resultingFirstChild = null, prev = null
  // pass 1: walk both lists in order while keys match (the common case: nothing moved)
  for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
    const newFiber = updateSlot(returnFiber, oldFiber, newChildren[newIdx])   // same key & type → reuse; else null
    if (newFiber === null) break
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx)             // marks Placement if it moved backwards
    prev ? (prev.sibling = newFiber) : (resultingFirstChild = newFiber); prev = newFiber; oldFiber = oldFiber.sibling
  }
  if (newIdx === newChildren.length) { deleteRemainingChildren(returnFiber, oldFiber); return resultingFirstChild }  // old list longer: delete the tail
  if (oldFiber === null) { for (; newIdx < newChildren.length; newIdx++) /* create and place the rest */ ; return resultingFirstChild }  // new list longer: insert the tail
  // pass 2: something moved. index the remaining old children by key, then walk the rest of the new list
  const existing = mapRemainingChildren(oldFiber)                              // Map<key | index, fiber>
  for (; newIdx < newChildren.length; newIdx++) {
    const newFiber = updateFromMap(existing, returnFiber, newIdx, newChildren[newIdx])   // reuse by key, else create
    if (newFiber.alternate !== null) existing.delete(newFiber.key ?? newIdx)
    lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx)             // the last-placed-index heuristic for moves
    /* link */
  }
  existing.forEach(child => deleteChild(returnFiber, child))                    // whatever was not reused is deleted
  return resultingFirstChild
}
// placeChild: if the reused fiber's old index < lastPlacedIndex → it moved → Placement; else lastPlacedIndex = old index.
// O(n) with no LIS: items that moved "forward" past the last placed one stay; the rest are marked as moves. one extra move in the worst case vs LIS.

the two passes

Pass 1, the fast path: walk old fibers and new elements in lockstep while keys (and types) match. For a list where nothing moved (the overwhelmingly common update: a prop changed on some items), this pass handles everything in O(n) with no Map.
The two early exits: new list exhausted → delete the remaining old fibers (items removed from the end). Old list exhausted → create fibers for the remaining new elements (items appended).
Pass 2, the keyed path: on the first mismatch, put the remaining old fibers in a Map by key (or index, for unkeyed), then for each remaining new element: take the fiber from the Map if present (an update, possibly a move) or create one (an insert). Whatever remains in the Map is deleted.
Moves: placeChild tracks lastPlacedIndex, the old index of the last fiber that stayed in place. A reused fiber whose old index is less than that has moved backwards relative to something already placed: mark it Placement (it will be re-inserted in commit). Otherwise it stays and becomes the new lastPlacedIndex. This is the O(n) heuristic standing in for LIS (part 1): it can mark one more move than necessary when an item jumps far forward, and is otherwise optimal.

what it means for how you render lists

Stable keys from data (ids). Index keys make pass 1 match by position, so an insert at the front reuses every fiber with the wrong data: state (input values, scroll positions, animations) attaches to the wrong items.
Appending is the cheapest change; prepending triggers pass 2 for the whole list (every key mismatches at its position) and marks everything after the new item as moved under the heuristic. Still O(n), but with a Map and n Placement effects. For a chat log that prepends, reversing the array once and rendering with flex-direction: column-reverse turns prepends into appends.
Keys reset state on purpose: changing a component's key forces a remount: the idiom for "reset this form when the selected record changes".
Fragments and arrays: a <> with keyed children reconciles as an array; nested arrays reconcile recursively with their own passes.

the sizes

A 1,000-item list where one item's prop changed: pass 1 matches all 1,000 keys, 999 bail out (chapter 4), one re-renders. Prepending one item: pass 1 breaks at index 0; pass 2 builds a Map of 1,000, matches 1,000, marks up to 1,000 Placements; commit moves 1,000 DOM nodes. Both O(n); the second is a hundred times the constant.

Bailouts: rendering only what changed

Visiting the whole tree per update would make every keystroke O(tree). The reconciler avoids it by skipping subtrees whose inputs did not change, and the inputs are checked by reference, which is why "stable references" is the central performance discipline in React.

the checks at each fiber, in beginWork

Props identity: workInProgress.pendingProps === current.memoizedProps. True when the parent did not re-render (it passed the same element objects). False when the parent re-rendered, even if the contents are equal.
Pending lanes: (fiber.lanes & renderLanes) !== 0: this fiber has its own update (state or forced).
Context: a context this fiber consumes changed (propagated by the provider when its value's reference changed).
Legacy: shouldComponentUpdate, PureComponent's shallow compare.
Bailout: none of the above → do not call the component. If childLanes is zero, return null (skip the subtree). Else clone the child fibers and continue down (a descendant has work).

memoisation primitives, as what they do to the checks

React.memo(C): replaces the props identity check with a shallow comparison (Object.is per key). Turns "parent re-rendered" into "parent re-rendered with different values". O(props) per render attempt.
useMemo, useCallback: keep a value's or function's reference stable across renders while its dependencies are Object.is-equal, so that children receiving it pass the identity check (plain or memo'd). Each costs a dependency comparison per render and the stored value's memory.
useContext with a memoised value: the provider's value reference changes only when its inputs change, so consumers are not marked on every parent render.
The React Compiler: inserts the equivalent of useMemo/useCallback around values and JSX automatically, based on a static analysis of which inputs each output depends on; the bailouts then hold without hand-written memo.

the anti-patterns, as check failures

Inline objects, arrays, and functions as props to a memo'd child: new reference every render; the shallow compare fails on that key.
A context value built inline (value={{ user, setUser }}): every provider render re-marks every consumer.
Children as a prop (<Layout>{...}</Layout>): the children elements are created by the parent each render, so Layout's props change each time; Layout itself cannot bail out, but its subtree can if the children elements' own props are stable (they are, when the grandparent did not re-render).
State in a high ancestor (a form's value in the page component): every keystroke re-renders the page; every child without memo re-renders. Move state down, or memo the expensive siblings.

BAILOUTS: SKIPPING SUBTREES

what makes a render O(changed), not O(tree)

swipe the figure sideways, or tap expand for full screen

1/6

a deep change

A state change in Item3 (deep in the tree). The root is marked (childLanes up the path). The render starts at the root: App has no pending lanes and the same props: bailout, but childLanes says a descendant has work: clone App and descend.

Alternatives: compiled diffs and no diffs at all

code

// four strategies for "the state changed; update the view"
// 1. virtual DOM diff (React, Preact, Vue 2):   render → element tree → diff vs previous → patch.   O(rendered subtree) per update; bailouts prune.
// 2. compiled block diff (Vue 3):               template → render with static hoisting + patch flags; diff only the dynamic bindings per block.
//                                                O(dynamic bindings) in the re-rendered component; the structure is known at compile time.
// 3. fine-grained reactivity (Solid, Svelte 5):  no tree diff. each DOM binding subscribes to the signals it reads; a change runs exactly those
//                                                bindings' update closures. O(affected bindings). lists still need a keyed diff (part 1) when the array changes.
// 4. direct DOM (vanilla, morphdom):             rebuild HTML or mutate directly; morph diffs the live DOM against new HTML by walking both: O(nodes).
// the cost centres differ: 1 and 2 pay in component re-renders and are pruned by memo and compile-time knowledge; 3 pays in subscriptions
// (memory per binding, a dependency graph to maintain) and wins on updates; 4 pays in your discipline.

Vue 3: block tree and patch flags

Compile-time knowledge: the template compiler knows which parts of a template are static (hoisted once, never diffed), which bindings are dynamic (a patch flag per element: TEXT, CLASS, STYLE, PROPS with the prop names), and the structure between structural directives (v-if, v-for) is a "block".
At update: a block diffs only its dynamic children (a flat array collected at render), checking only the flagged bindings on each. The tree structure is not re-walked; O(dynamic bindings) per re-rendered component rather than O(elements).
Lists: the keyed algorithm with a longest-increasing-subsequence for minimal moves (part 1).
The trade: templates, not arbitrary JSX, so the compiler can see the structure. Render functions fall back to a full diff.

Solid and Svelte 5: fine-grained reactivity

No virtual tree: a component function runs once, creating real DOM; each dynamic expression in the template becomes an effect subscribed to the signals it reads (dependency tracking by running the expression under a tracking context: the Proxy or getter-based reactivity from the JS course part 13).
At update: set a signal → run its subscribers (the effects that read it) → each updates its one DOM binding. O(subscribers of the changed signal). No tree walk, no bailout checks, no component re-render.
Lists: a keyed reconciliation over the array when the array identity changes (the same algorithm, usually with LIS), with each row's bindings fine-grained inside.
The trade: a subscription graph in memory (an effect object per binding, a subscriber list per signal), and a rule that reactivity is lost if a signal is read outside a tracking context (destructuring props too early is the classic Solid mistake). Updates are as cheap as they can be; mounts carry the graph construction cost.

choosing by workload

Mount-heavy (many fresh pages, little interaction): the virtual DOM's mount is a tree creation like any other; fine-grained reactivity pays extra for the subscription graph.
Update-heavy (dashboards, editors, live data): fine-grained wins by not walking; compiled block diffs are close; a virtual DOM needs disciplined memoisation to approach them.
Large lists in all models: virtualise (part 1); the diff is not the cost, the DOM is.
The constant that matters most is usually the one you control: how much of the tree re-renders per update, which is a question of where state lives, in every framework.

Measuring reconciliation

Question	Tool	What to read
Which components rendered, and why?	React DevTools Profiler → a commit → "Why did this render?" (enable in settings)	Props changed (which), state, context, parent rendered; the hooks that changed
How much of the tree rendered?	Profiler → flame chart per commit; grey = bailed out	A keystroke lighting up the whole tree means state is too high or memo is missing
Which props defeated memo?	Profiler "why did this render" prop list; `useWhyDidYouUpdate`-style hooks in development	Inline objects and functions; a context value rebuilt per render
Did a list prepend move everything?	Profiler commit → Placement effects count; Rendering → Paint flashing on the list	Every row flashing on a single insert
Is a remount happening?	Profiler: a component with a mount (not update) on every commit; `useEffect` cleanups firing	A component defined inside render; a changing key; a conditional wrapper
Which lane rendered, and was it interrupted?	Profiler commit lanes; "Highlight updates" overlay; scheduling profiler (React DevTools Timeline)	Sync renders for things that should be transitions; repeated discards
Is reconciliation the cost at all?	Chrome Performance: time in React's `performUnitOfWork` / `renderRootSync` versus in your components versus in commit (DOM) and after (layout, paint)	Usually the components or the DOM, not the walk
In Vue / Solid	Vue DevTools component render tracking; Solid's dev-mode signal graph	The same questions: what re-ran, and what dependency caused it

the pointer

Part 8 is compilers: tokenising as a state machine, recursive descent and Pratt parsing, SSA and the optimisations over it, register allocation, and tree shaking as reachability. The reconciler is a diff over trees; a compiler is a sequence of rewrites over trees and graphs, and the bundler you run is one.