Reconciliation: Turning a Declarative Description into Minimal Mutations

A declarative interface is written as a function that returns a description of what should be on screen. The platform underneath is not declarative. UIKit holds a tree of UIView objects with mutable frames and a retained backing store; the Android view system holds View instances attached to a ViewGroup; a browser holds a DOM. None of these can be handed a fresh description and asked to adopt it. Somewhere between the description and the pixels there is a component whose job is to compare the new description with the one currently mounted and to emit the imperative calls that close the gap.

That component is the reconciler, and the interesting engineering question is how much of the comparison it actually performs. The honest answer for every mainstream mobile framework is: far less than the problem allows, on purpose.

The cost of rebuilding instead of comparing

Suppose an interface is described by 2000 nodes and a single label inside one of them changes. The simplest implementation of a declarative API throws away the mounted tree and builds a new one. That is correct, and it is what some early declarative systems did with coarse-grained invalidation. Its cost is not the construction of 2000 description objects, which is cheap and ephemeral. The cost is on the platform side: 2000 view allocations, 2000 attachments to parents, a full measure and layout pass over the new hierarchy, a full redraw, and the loss of everything the old tree carried that was never part of the description. Scroll offsets, text selection, keyboard focus, in-flight animations, video playback position, and the internal state of any platform widget all belong to the retained objects. Replacing the objects destroys them.

So the reconciler exists to preserve retained objects across rebuilds and to mutate only what the description says changed. This is the same problem as computing the difference between two ordered trees, which has an exact solution and an exact solution is unusable here.

Why exact tree differencing is the wrong algorithm

The minimal edit script between two trees, under insert, delete, and relabel operations, can be computed. The classical ordered-tree algorithm of Zhang and Shasha runs in time proportional to the product of the two tree sizes multiplied by the minimum depths and leaf counts of the trees, which in the worst case is quartic in the size of a single tree; the unordered variant, where sibling order is not part of the tree’s identity, is NP-hard. Even the friendlier ordered case costs on the order of a million table entries for two trees of a thousand nodes, and the budget for producing a frame is 16.6 milliseconds at 60 Hz, shared with layout, text, and drawing.

Worse, minimality is not the property the framework wants. A minimal edit script will happily move a subtree three levels up and two siblings left if that saves one insertion, and every move costs a detach and reattach on the platform side, which invalidates layout and often resets internal widget state. The property that matters is stability: nodes that a human would call the same thing must keep their identity. Minimality is a proxy for that, and a bad one.

Mainstream reconcilers therefore use a linear heuristic with two assumptions, both stated in the React documentation: two elements of different types produce different trees, and the developer can mark which children are stable across renders with a key. Under those assumptions the comparison degenerates into a single simultaneous walk, and the expensive cases simply do not arise.

The walk

The core rule is a type check. At each position the reconciler compares the type of the new description with the type of the mounted one. Same type means the platform object is reused and its properties are updated in place. Different type means the old subtree is unmounted and a new one is mounted, and there is no attempt to find a correspondence between them. A <Switch> that becomes a <Slider> is a different control; pretending otherwise produces nonsense property updates.

For a single child the rule is enough. For a list of children it is not, because a list can be reordered, and a positional walk would relabel every position after the first change, causing a cascade of property updates and, if any of those children hold state, a cascade of state migrations.

The list algorithm is where the linear bound is earned. The reconciler builds a map from key to mounted child for the previous list, then walks the new list once, looking each child up by key. A hit reuses the mounted object; a miss mounts a new one; keys present in the map but absent from the new list are unmounted at the end. One pass over the new list, one pass over the old, a hash lookup per child. A simplified version of the same idea:

def reconcile_children(old, new):
    index = {child.key: child for child in old}
    used, result = set(), []

    for description in new:
        candidate = index.get(description.key)
        # Type must match as well as key; a key is an identity, not a promise
        # that the two descriptions denote the same kind of thing.
        if candidate is not None and candidate.type is description.type:
            candidate.update(description.props)
            used.add(description.key)
            result.append(candidate)
        else:
            result.append(mount(description))

    for child in old:
        if child.key not in used:
            unmount(child)
    return result

The pass does not compute an optimal sequence of moves. If three children rotate, the map lookup reuses all three objects and the framework then emits whatever reordering the platform requires, typically a sequence of index moves or a single keyed reorder operation. In React’s implementation the same walk also tracks the last index it placed a reused child at, so that a child whose position moved forward is flagged as a move rather than a plain insert. The details differ between frameworks; the shape does not.

Component boundaries and the bailout

A reconciler does not compare the rendered output of a child component with the output it produced last time. It compares the description the parent returned. When a parent re-renders, it produces new child descriptions, and those descriptions are compared by type and key as above. If a child description is the identical object as before (same reference, not merely equal properties), the framework skips that subtree entirely. React calls this a bailout, and it is why immutable data and memoization interact so directly with reconciliation cost: an inline object literal created during render is a new reference on every pass, so a child memoized on referential equality never bails out.

Flutter inverts the mechanism while keeping the identity rule. Widgets there are immutable description objects, rebuilt freely and discarded immediately. What persists is the element, and the test for reusing an element is exactly runtime type plus key, the same predicate the reconciler applies. Because the widget is immutable, Flutter does not need to diff properties at all: a rebuilt widget is simply adopted by the retained element, which then marks the corresponding render object dirty. The comparison that React performs across a tree is compressed into a per-node identity check, and the mutation set is expressed as invalidation of layout and paint rather than as insert and remove operations.

The contrast is instructive. Both systems answer the same question, whether this description denotes the same mounted thing as that one, and both answer it with type plus optional key. Everything else about their architecture follows from how much of the tree they are willing to walk.

Where the identity rule produces wrong answers

The failure modes are all cases where the developer’s key does not mean what the framework assumes it means.

Using the array index as a key is the common one. It is correct as long as the list only grows at the end. Insert an item at the head and every subsequent item’s key shifts by one, so the reconciler concludes that item at index 0 changed content rather than that a new item arrived, and the state attached to index 0 stays with position 0 while the text it described moves to index 1. In a list of text fields, typed input appears in the wrong row. The behaviour is not a bug in the framework; the key said the row at position 0 is the same row.

Generating keys during render, from a counter or a random value, is worse. Every pass produces keys that match nothing in the old map, so every child is unmounted and remounted. The result is a full rebuild with extra bookkeeping, and the symptom is usually a text field that loses focus on each keystroke.

Duplicated keys break the map. Two children with the same key cannot both be looked up, so one is silently reused for the wrong description or the framework reports the duplicate and falls back to positional matching.

A conditional early return that changes the root type of a subtree resets that subtree. A screen that returns a spinner while loading and a scrollable list when loaded has two different types at the same position, so the list is mounted fresh each time the state flips, and its scroll offset starts at zero. Hoisting the condition inside a stable container, or keeping both branches mounted and hiding one, preserves the offset.

The last edge case is a state that lives outside the tree. Reordering with keys preserves the mounted object and its state, but a scroll position owned by the platform’s list view may still be reset by the reorder operation itself, because the platform’s contract for a bulk move is not a contract about scroll anchoring. Reconcilers are careful about identity, not about every piece of retained state; the next layer down, described in Element Identity and State Retention, is where that distinction becomes visible.

What the linear bound buys

The heuristic runs in time proportional to the number of described nodes plus the number of list children, with a hash map sized to the old child count, and the mutations it produces are then priced by the layout work they trigger, as described in Constraints Down, Sizes Up: Why Layout Is a Single Pass. It performs no work at all on subtrees whose descriptions did not change by reference, and it produces mutations proportional to the number of actual changes rather than to the size of the tree. The price is a class of bugs that the developer must avoid by supplying honest keys, and a loss of optimality in cases where an exotic reorder could have been expressed more cheaply. Neither price is close to the cost of the exact algorithm, which is why no production mobile framework pays it.