The Diffing Algorithm

A state change produces a whole new vtree. Rendering it verbatim would replace the page. Instead the framework compares it with the previous tree and applies only the differences.

The two heuristics

Real tree edit distance is O(n^3) - far too slow to run 60 times a second. React gets to O(n) by assuming two things, and both are assumptions, not proofs:

Different type means different subtree. A div that became a span gets replaced whole, without looking inside. Descending would almost never pay off.

Same position means same thing. old.children[i] is compared with new.children[i]. This is the assumption that breaks.

Where position breaks

Prepend one row to a list of a thousand. Every child now sits one slot later than before, so every pairwise comparison disagrees and the reconciler patches all thousand nodes - along with any DOM state they held: a focused input, a scroll offset, a half-finished CSS transition.

The fix is a key: a stable id, unique among siblings, that says which old child a new child is.

With keys, the reconciler matches by key instead of by index: unchanged items are left alone, missing keys are removed, new keys are inserted, and the survivors are moved. Note what a key is not - it never reaches the DOM, it is not an id attribute, and it only has to be unique among siblings.

Vue 3 runs the same idea and then applies a longest-increasing-subsequence pass to minimise the number of moves. Solid and Svelte skip diffing entirely: their compilers already know which expression feeds which node.

The exercise ahead implements the position-based version first, so you can feel precisely which case the keyed version fixes.