---
title: Reconciliation
source: 'https://academia.sh/en/courses/component-based-development/reconciliation'
course: 'Component-Based Interface Development'
language: en
updated: '2026-08-17T18:11:04+00:00'
license: 'CC BY-SA 4.0'
---

# Reconciliation

Comparing the new view description against the previous one; the virtual tree, the three assumptions that make comparison linear, producing the patch list, and a measured comparison against approaches that update without comparing.

The previous lesson built the matching rule at the list level: a key determines which
record corresponds to which node. What happens after matching was left open — how
attributes are compared, in what order children are visited, what happens when the
type changes.

This lesson gathers all of these rules into a single algorithm. The algorithm is
called **reconciliation**: its input is two view descriptions, its output is the list
of operations to apply to the tree.

## Reconciliation's Input and Output

The framework keeps the last view description it produced in memory. This stored
description is called the **virtual tree**: a copy of the document tree's current
state, made of plain data.

When state changes, a new description is produced and the two descriptions are
compared. The result of the comparison is a **patch list** — create a node, remove it,
move it, write an attribute, write text. Only this list is applied to the document
tree.

This is the reason the virtual tree exists. If the comparison were done on the
document tree, every step would read from the tree; reading from the tree can trigger
a layout calculation and produces the layout thrashing from the Performance Recording
lesson. Comparing over a copy made of plain data eliminates these reads.

## Three Assumptions That Make Comparison Cheap

Finding the smallest sequence of transformations between two ordered trees is a job
of cubic order in tree size. It is too expensive to do on every frame. Reconciliation
reduces this problem to linear with three assumptions.

**The subtree of a node whose type changes is not compared.** If a section element
appears in a position where a list item used to be, the old subtree is discarded
entirely and the new one is built from scratch. The assumption's rationale is that two
elements of different types are expected to produce different structures. Its cost is
that switching between two different wrappers carrying the same content rebuilds the
entire subtree — and the state inside it.

**Comparison is done level by level.** Whether a node might have moved to a different
level is never tried. A row leaving a table and entering a disclosure panel is seen as
a removal and a creation, not a move.

**Siblings match by key.** The previous lesson's rule is the algorithm's
child-visiting step. Siblings without a key match by position.

## The Algorithm

The implementation below applies these three assumptions and produces the patch list.

```js
// reconciliation.mjs — compares two view descriptions and produces a patch list
const element = (name, attrs = {}, children = [], key = null) =>
  ({ name, attrs, children, key });

function view(state) {
  return element("section", { class: "dashboard" }, [
    element("h2", {}, [`North Slope — ${state.measurements.length} measurements`]),
    element("ul", { class: "table" }, state.measurements.map((m) =>
      element("li", { class: m.value >= m.threshold ? "badge exceeded" : "badge" },
        [`${m.name}: ${m.value} ${m.unit}`], m.id))),
  ]);
}

// Longest increasing subsequence of the old ordering: nodes that can stay in place.
function longestIncreasingSubsequence(array) {
  const tails = [], prev = [];
  for (const [i, value] of array.entries()) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (array[tails[mid]] < value) lo = mid + 1; else hi = mid;
    }
    prev[i] = lo > 0 ? tails[lo - 1] : -1;
    tails[lo] = i;
  }
  const result = new Set();
  for (let i = tails.at(-1); i !== undefined && i !== -1; i = prev[i]) result.add(i);
  return result;
}

function reconcile(old, next, path, patches) {
  if (typeof old === "string" || typeof next === "string") {
    if (old !== next) patches.push(`TEXT     ${path}  ${JSON.stringify(next)}`);
    return;
  }
  // 1. If the type or key differs, the subtree is not compared; it is replaced with the new one.
  if (old.name !== next.name || old.key !== next.key) {
    patches.push(`REPLACE  ${path}  <${old.name}> → <${next.name}>`);
    return;
  }
  // 2. Attributes are compared in both directions.
  for (const [k, v] of Object.entries(next.attrs))
    if (old.attrs[k] !== v) patches.push(`ATTR     ${path}  ${k}=${JSON.stringify(v)}`);
  for (const k of Object.keys(old.attrs))
    if (!(k in next.attrs)) patches.push(`DEL-ATTR ${path}  ${k}`);
  // 3. Children: keyed ones match by key, unkeyed ones match by position.
  const oldIndex = new Map();
  old.children.forEach((c, i) =>
    oldIndex.set(typeof c === "string" || c.key === null ? `#${i}` : c.key, i));
  const matched = [];
  next.children.forEach((c, i) => {
    const key = typeof c === "string" || c.key === null ? `#${i}` : c.key;
    const oldIdx = oldIndex.get(key);
    if (oldIdx === undefined) patches.push(`CREATE   ${path}/${i}  ${key}`);
    else matched.push({ i, oldIdx, key });
  });
  for (const [key, i] of oldIndex)
    if (!matched.some((e) => e.key === key))
      patches.push(`REMOVE   ${path}/${i}  ${key}`);
  const keep = longestIncreasingSubsequence(matched.map((e) => e.oldIdx));
  matched.forEach((e, k) => {
    if (!keep.has(k)) patches.push(`MOVE     ${path}/${e.oldIdx} → ${path}/${e.i}  ${e.key}`);
    reconcile(old.children[e.oldIdx], next.children[e.i], `${path}/${e.i}`, patches);
  });
}

const M = (id, name, value, unit, threshold) => ({ id, name, value, unit, threshold });
const BEFORE = { measurements: [
  M("s1", "Temperature", -4.2, "°C", 30), M("n1", "Relative humidity", 72, "%", 90),
  M("r1", "Wind speed", 11.4, "m/s", 25), M("k1", "Snow depth", 38, "cm", 60),
] };
const AFTER = { measurements: [
  M("k1", "Snow depth", 38, "cm", 60), M("s1", "Temperature", -4.2, "°C", 30),
  M("n1", "Relative humidity", 94, "%", 90), M("b1", "Pressure", 964, "hPa", 1050),
] };

const patches = [];
reconcile(view(BEFORE), view(AFTER), "root", patches);
const countNodes = (description) => typeof description === "string"
  ? 1 : 1 + description.children.reduce((t, c) => t + countNodes(c), 0);
console.log(`nodes in the description: ${countNodes(view(AFTER))}`);
console.log(`patches produced        : ${patches.length}\n`);
console.log(patches.join("\n"));
```

```
nodes in the description: 12
patches produced        : 5

CREATE   root/1/3  b1
REMOVE   root/1/2  r1
MOVE     root/1/3 → root/1/0  k1
ATTR     root/1/2  class="badge exceeded"
TEXT     root/1/2/0  "Relative humidity: 94 %"
```

Four things changed at once: a measurement was added, one was removed, the list was
reordered, and one measurement's value crossed the threshold. Five patches were
produced for a twelve-node description.

**A single move is enough.** Even though the order of all four rows changed, the rows
found in the longest increasing subsequence of the old ordering were left in place,
and only the snow depth row was moved.

**Crossing the threshold produced two separate patches.** The relative humidity's
class and text are separate fields; each field goes through its own comparison. This
separation is kept because writing an attribute has a different cost than writing
text.

**The heading produced no patch at all.** Because the measurement count stayed at
four, the heading's text did not change; the comparison saw this and wrote no
operation. This is the difference between comparing a field and writing it: comparison
is cheap, writing is expensive.

**The changed measurement itself was never moved.** Because removal, creation, and
moving are resolved by key, the updated row stayed in its own node even though it
changed position in the list. Without a key, this row would have been rewritten too.

## Where the Cost Lies

Reconciliation is linear in the size of the produced description. A practical
conclusion follows: the way to reduce cost is not to speed up the comparison but to
**produce a smaller description**.

What determines the size of the description is the re-render area measured in the
third lesson. When state at the root changes, the entire tree re-renders and the
entire description is produced and compared. Keeping state as low as possible,
skipping the production of subtrees whose input has not changed, and caching the
result of expensive computations are the tools that narrow this area; the last two are
covered in later topics of the course.

## Approaches That Do Not Compare

Reconciliation resolves the question of "which value affects which node" all over
again every time. Solving the same question once and storing the answer is also
possible, and this is the fundamental design difference that separates framework
families.

```js
// approaches.mjs — the work three approaches do when a single measurement value changes
const N = 12;
const MEASUREMENTS = Array.from({ length: N }, (_, i) => ({
  id: `s${i}`, name: `Sensor ${String(i + 1).padStart(2, "0")}`, value: 10 + i,
}));
const CHANGED = 6, NEW_VALUE = 17.5;
const rowText = (m) => `${m.name}: ${m.value}`;

// --- A) Virtual tree: regenerate the description, compare against the old one ---
let produced = 0, compared = 0, writesA = 0;
const node = (name, children) => { produced++; return { name, children }; };
const text = (s) => { produced++; return s; };
const view = (measurements) =>
  node("ul", measurements.map((m) => node("li", [text(rowText(m))])));

function reconcile(old, next, tree) {
  compared++;
  if (typeof next === "string") {
    if (old !== next) { tree.texts[tree.k] = next; writesA++; }
    tree.k++;
    return;
  }
  old.children.forEach((c, i) => reconcile(c, next.children[i], tree));
}

const treeA = { texts: MEASUREMENTS.map(rowText), k: 0 };
const oldDescription = view(MEASUREMENTS);
produced = 0;                                    // the initial render is not counted
const nextMeasurements = MEASUREMENTS.map((m, i) =>
  i === CHANGED ? { ...m, value: NEW_VALUE } : m);
reconcile(oldDescription, view(nextMeasurements), treeA);

// --- B) Fine-grained reactivity: a binding subscribes to the cell it reads ---
let subscriptionsB = 0, writesB = 0;
const treeB = { texts: MEASUREMENTS.map(rowText) };
const cells = MEASUREMENTS.map((m, i) => {
  const cell = { value: m.value, subscribers: [] };
  cell.subscribers.push((v) => { treeB.texts[i] = `${m.name}: ${v}`; writesB++; });
  subscriptionsB++;                               // one subscription recorded at setup
  return cell;
});
const writeCell = (i, v) => {
  cells[i].value = v;
  for (const subscriber of cells[i].subscribers) subscriber(v);
};
writeCell(CHANGED, NEW_VALUE);

// --- C) Compile-time reactivity: the mapping comes from the compiler ---
// The compiler reads the template: row text depends only on the "value" field.
let writesC = 0;
const treeC = { texts: MEASUREMENTS.map(rowText) };
const COMPILED = {
  value: (i, v) => { treeC.texts[i] = `${MEASUREMENTS[i].name}: ${v}`; writesC++; },
};
COMPILED.value(CHANGED, NEW_VALUE);

// --- Result ------------------------------------------------------------------
const expected = nextMeasurements.map(rowText);
const same = (texts) => JSON.stringify(texts) === JSON.stringify(expected);
console.log(`one measurement value changed in a ${N}-row table\n`);
console.log("approach".padEnd(26) + "setup    produced  compared       writes  result");
console.log(`${"virtual tree".padEnd(26)}${String(0).padEnd(9)}${String(produced).padEnd(8)}` +
  `${String(compared).padEnd(15)}${String(writesA).padEnd(7)}${same(treeA.texts)}`);
console.log(`${"fine-grained reactivity".padEnd(26)}${String(subscriptionsB).padEnd(9)}${String(0).padEnd(8)}` +
  `${String(0).padEnd(15)}${String(writesB).padEnd(7)}${same(treeB.texts)}`);
console.log(`${"compile-time".padEnd(26)}${String(0).padEnd(9)}${String(0).padEnd(8)}` +
  `${String(0).padEnd(15)}${String(writesC).padEnd(7)}${same(treeC.texts)}`);
```

```
one measurement value changed in a 12-row table

approach                  setup    produced  compared       writes  result
virtual tree              0        25      25             1      true
fine-grained reactivity   12       0       0              1      true
compile-time              0        0       0              1      true
```

The three approaches produce the same result; the work they do differs.

**The approach that keeps a virtual tree** produces and walks the entire description
on every update: twenty-five node productions, twenty-five comparisons, one write. In
return, it records nothing and places no restriction on the view function —
conditionals, loops, helper functions, all of it is ordinary code.

**The approach that does fine-grained dependency tracking** records at setup which
binding reads which value. On update, it produces no description and does no
comparison; it runs the relevant binding directly. Its cost is the record kept for
every binding and the requirement that reads be trackable: values are accessed not
directly, but through a tracked wrapper.

**The approach that reactivates at compile time** builds the same mapping not at
runtime but in the compiler. Which part of the template reads which field is known at
compile time; the output is code that writes that field directly. Neither a record is
kept nor a comparison is done at runtime. Its cost is that a compilation step becomes
mandatory and the template language has to stay restricted enough to remain
analyzable: dynamic structures the compiler cannot see fall outside this mapping.

One more trade-off does not show up in the table. In the virtual-tree approach,
update cost is proportional to **the re-render area**; in the other two, it is
proportional to **the number of changed values**. In a small interface, the
difference cannot be measured; it becomes clear in a dashboard where fifteen badges
update several times a second. This number alone does not determine the choice — the
course's final topic covers the full set of criteria.

## Summary

- Reconciliation compares the new view description against the stored previous one
  and produces a patch list; the stored description is called the virtual tree, and it
  prevents reads from the document tree.
- Finding the smallest transformation between two ordered trees is of cubic order;
  three assumptions — discarding the subtree on a type change, comparing level by
  level, matching siblings by key — reduce the problem to linear.
- The assumptions have a cost: changing a wrapper's type rebuilds the subtree and its
  state; a node that changes level is not moved, it is removed and re-created.
- Comparison is cheap, writing is expensive; no patch is produced for fields that do
  not change.
- Reconciliation's cost depends on the size of the produced description; the way to
  reduce it is to produce a smaller description, that is, to narrow the re-render
  area.
- Fine-grained dependency tracking solves the same problem with a record kept at
  setup, and the compile-time approach with a mapping built in the compiler; the first
  requires trackable access, the second a restricted template language and a
  compilation step.

## Next Step

This topic built how the interface is produced from state and how what is produced is
reflected onto the tree: the view is a function, the component is a contractual piece
of that function, the template binds markup to data, the key preserves identity,
reconciliation turns the difference into a patch. One thing remains unresolved: state
itself. Reconciliation always runs after a re-render — so what triggers the
re-render? When an event handler updates two values back to back, does it render
twice, or are the updates batched together? Where exactly does a component's local
state live, and what does the call that updates it return when read on the very next
line? The next topic, Component Lifecycle and State, begins with these questions in
the Local State lesson.