Virtual DOM diffing complexity

Summary

Reconciliation compares trees keyed by element type and key — O(n) heuristics, not optimal edit distance. Unstable keys (array index on reorderable lists) cause unnecessary unmount/remount. Large flat lists without virtualization still pay diff cost even if output DOM is unchanged. Profile before assuming "Virtual DOM is free."

Code example

// Stable keys avoid remounting on reorder
function TodoList({ items }) {
  return items.map((item) => (
    <li key={item.id}>{item.text}</li>
  ));
}
// key={index} on sortable lists causes O(n) DOM churn

Key points

• Reconciliation compares trees keyed by element type and key — O(n) heuristics, not optimal edit distance.
• Unstable keys (array index on reorderable lists) cause unnecessary unmount/remount.
• Large flat lists without virtualization still pay diff cost even if output DOM is unchanged.
• Profile before assuming "Virtual DOM is free."

Further reading

• Preserving and resetting state
• Rendering lists

Related concepts

• Hydration
• Event loop (macro vs microtasks)