React Diffing

Diffing two arbitrary trees has a complexity of O(n³). React gets away with O(n) by using a heuristic algorithm built on two assumptions:

1. Two elements of different types will produce different trees.
2. The developer can hint at which child elements may be stable across different renders with a key prop.

In practice these assumptions hold for almost all real-world UIs, which is why the shortcut works.

Elements of different types

Whenever the root elements have different types, React will tear down the old tree and build the new tree from scratch. Going from <a> to <img>, or from <Article> to <Comment>, or even from <Button> to <div> — any of those leads to a full rebuild.

When tearing down a tree, old DOM nodes are destroyed, and cleanup functions returned from useEffect get called. Components below the root are unmounted along with it, so any state associated with the old tree is lost.

When building up the new tree, new DOM nodes are inserted into the DOM, and functions passed to useEffect get called on mount.

Same type

Two situations.

DOM elements

When comparing two React DOM elements of the same type, React looks at the attributes of both, keeps the same underlying DOM node, and only updates the changed attributes:

<div className="before" title="stuff" style={{ color: 'red', fontWeight: 'bold' }} />

<div className="after" title="stuff" style={{ color: 'green', fontWeight: 'bold' }} />

Here React only modifies className and style.color on the existing node — title and fontWeight are untouched. Even style is patched property by property rather than rewritten as a whole.

After handling the node itself, React recurses on the children.

Component elements

When a component updates and its type stays the same, the instance stays the same, so state is maintained across renders. React updates the props to match the new element and re-renders the component.

Note that this is an update, not a remount: cleanup functions do not run "because the tree changed". Whether an effect re-fires is decided by its own dependency array — if the deps changed, React runs the previous cleanup first and then the effect again; if not, the effect is skipped entirely. Unmount-style cleanup only happens in the tear-down case above.

Recursing on children

By default, when recursing on the children of a DOM node, React just iterates over both lists of children at the same time and generates a mutation whenever there is a difference. The index-by-index matching is cheap, but it is also where things can go wrong.

Appending at the end works fine:

<ul>
  <li>first</li>
  <li>second</li>
</ul>

<ul>
  <li>first</li>
  <li>second</li>
  <li>third</li>
</ul>

React matches the two first trees, matches the two second trees, and then inserts the third tree. One insertion, nothing else touched.

Inserting at the beginning is where the naive matching falls apart:

<ul>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

<ul>
  <li>Connecticut</li>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

React compares by position: Duke against Connecticut, Villanova against Duke. It doesn't realize the last two items simply moved down one slot, so it mutates every existing child and then appends one more — instead of performing a single insertion.

Keys

To solve this, React supports a key attribute. When children have keys, React matches children in the two trees by key instead of by index:

<ul>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

<ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

Now React knows that the element with key 2014 is the new one, and 2015 and 2016 have just moved.

Usually you would use IDs from your data as keys. When that's not the case, you can add an ID property to your model or hash some parts of the content to generate one. The key only has to be unique among its siblings, not globally unique.

As a last resort, you can pass an item's index in the array as a key. This works if the items are never reordered, but reorders will be slow — and worse, they cause state bugs. Component instances are updated and reused based on their key; if the key is an index, moving an item changes its key, and state for things like uncontrolled inputs gets mixed up in unexpected ways.

This example shows the bug live: add a few items, type something into their inputs, then sort — the typed text stays at its old position instead of following the item it belongs to.

Tradeoffs

The heuristics only pay off when the assumptions hold, so it's worth keeping them true in your own code:

• Don't alternate between two component types that render nearly the same output — the diff treats them as entirely different trees and remounts everything.
• Keys should be stable, predictable, and unique. Unstable keys (like Math.random()) recreate component instances and DOM nodes on every render, which means lost state and worse performance.

---

Reading notes on the Reconciliation page of the React docs.