Virtual-Tree-Based Frameworks

Throughout the previous topic, components were composed on paper: a function produced a tree, trees nested inside each other, props merged. How the produced tree reaches the document was never examined.

There is no single answer. Frameworks take distinct paths to find which part of the document needs updating when state changes, and that path shapes everything about the framework, from its learning curve to its performance profile. This topic covers all four paths. The first treats updating as a comparison problem.

The Re-Render Unit Is the Component

The model works like this. A component’s state changes; the framework reruns that component’s function, which produces a new tree from the current state. This tree is not the document — it is an in-memory structure describing the document, called the virtual tree. The framework compares the new tree with the previous one, finds the differences, and writes only those to the document.

The model’s gain is that whoever writes the component never touches the document. The one-way flow from the Declarative Rendering lesson holds here in its full sense: there is a function from state to view, and no function the other way.

The cost is captured in one sentence: the re-render unit is the component. A change in one component’s state causes the entire tree that component produces to be regenerated and compared, no matter how small the changed part is.

The Cost of a One-Cell Change

The measurement table on the station page has two hundred rows. A single sensor’s value is updated. The work this produces can be counted.

// virtual-tree.mjs — re-render, diffing, and the cost of a one-cell change
let counter;
const reset = () => (counter = { component: 0, node: 0, attribute: 0, patch: 0, skipped: 0 });

const h = (name, attrs = {}, ...children) => ({ name, attrs, children: children.flat().filter((c) => c != null) });
const text = (value) => ({ name: "#text", attrs: {}, children: [], text: String(value) });

// --- Components: rerun on every render and produce a new tree ---
const Cell = ({ value }) => { counter.component++; return h("td", { class: "value" }, text(`${value.toFixed(1)} °C`)); };
const Row = ({ name, value }) => {
  counter.component++;
  return h("tr", { key: name }, h("th", { scope: "row" }, text(name)), Cell({ value }));
};
const Table = ({ rows, draw }) => {
  counter.component++;
  return h("table", { class: "measurement" },
    h("caption", {}, text("North Slope")),
    h("tbody", {}, ...rows.map(draw)));
};

// --- Memoization: a component whose props have not changed returns its previous tree unchanged ---
function memoize(component) {
  const cache = new Map();
  return (o) => {
    const key = o.name;
    const entry = cache.get(key);
    if (entry && Object.keys(o).every((a) => entry.props[a] === o[a])) { counter.skipped++; return entry.tree; }
    const tree = component(o);
    cache.set(key, { props: { ...o }, tree });
    return tree;
  };
}

// --- Diffing ---
function diff(old, next) {
  if (old === next) { counter.node++; return; }        // same reference: subtree is never visited
  counter.node++;
  if (old.name !== next.name) { counter.patch++; return; }
  if (old.text !== undefined || next.text !== undefined) {
    if (old.text !== next.text) counter.patch++;
    return;
  }
  for (const a of new Set([...Object.keys(old.attrs), ...Object.keys(next.attrs)])) {
    counter.attribute++;
    if (old.attrs[a] !== next.attrs[a]) counter.patch++;
  }
  const keyed = next.children.length > 0 && next.children.every((c) => c.attrs?.key !== undefined);
  if (!keyed) {
    const n = Math.max(old.children.length, next.children.length);
    for (let i = 0; i < n; i++) {
      if (!old.children[i] || !next.children[i]) { counter.patch++; continue; }
      diff(old.children[i], next.children[i]);
    }
    return;
  }
  const oldMap = new Map(old.children.map((c, i) => [c.attrs.key, { node: c, index: i }]));
  const oldOrder = next.children.map((c) => oldMap.get(c.attrs.key)?.index ?? -1);
  const keep = longestIncreasingSubsequence(oldOrder);   // nodes that do not need to move
  next.children.forEach((c, i) => {
    const found = oldMap.get(c.attrs.key);
    if (!found) { counter.patch++; return; }            // new node: inserted
    if (!keep.has(i)) counter.patch++;                  // minimal number of moves
    diff(found.node, c);
    oldMap.delete(c.attrs.key);
  });
  counter.patch += oldMap.size;                          // remaining ones are removed
}

// Longest increasing subsequence: gives the indices of the nodes that do not need to move.
function longestIncreasingSubsequence(array) {
  const prev = new Array(array.length).fill(-1);
  const tails = [];
  for (let i = 0; i < array.length; i++) {
    if (array[i] < 0) continue;
    let lo = 0, hi = tails.length;
    while (lo < hi) { const mid = (lo + hi) >> 1; if (array[tails[mid]] < array[i]) lo = mid + 1; else hi = mid; }
    if (lo > 0) prev[i] = tails[lo - 1];
    tails[lo] = i;
  }
  const result = new Set();
  for (let k = tails[tails.length - 1]; k !== undefined && k !== -1; k = prev[k]) result.add(k);
  return result;
}

const report = (label) =>
  console.log(`${label.padEnd(36)} ${String(counter.component).padStart(9)} ${String(counter.skipped).padStart(8)} ` +
    `${String(counter.node).padStart(9)} ${String(counter.attribute).padStart(11)} ${String(counter.patch).padStart(5)}`);

const ROW_COUNT = 200;
const data = (shift = 0) =>
  Array.from({ length: ROW_COUNT }, (_, i) => ({ name: `sensor-${String(i).padStart(3, "0")}`, value: -10 + i * 0.1 + shift }));

console.log("scenario                            component  skipped      node    attribute  patch");

// 1. No memoization: a single cell changes.
reset();
const v1 = data();
const old1 = Table({ rows: v1, draw: Row });
const v2 = v1.map((s, i) => (i === 120 ? { ...s, value: 42.5 } : s));
const next1 = Table({ rows: v2, draw: Row });
diff(old1, next1);
report("no memoization, one cell changed");

// 2. Memoization: rows whose props have not changed are skipped.
reset();
const memoizedRow = memoize(Row);
const old2 = Table({ rows: v1, draw: memoizedRow });
const next2 = Table({ rows: v2, draw: memoizedRow });
diff(old2, next2);
report("memoized, one cell changed");

// 3. Nothing changed (the parent component rendered for another reason).
reset();
const old3 = Table({ rows: v1, draw: Row });
const next3 = Table({ rows: v1, draw: Row });
diff(old3, next3);
report("no memoization, nothing changed");

// 4. A row was prepended — keyed reconciliation.
reset();
const newRow = { name: "sensor-new", value: 3.3 };
const old4 = Table({ rows: v1, draw: Row });
const next4 = Table({ rows: [newRow, ...v1], draw: Row });
diff(old4, next4);
report("row prepended (keyed)");

// 5. The same insertion, without a key: every row shifts, so the comparison does not match.
reset();
const UnkeyedRow = ({ name, value }) => {
  counter.component++;
  return h("tr", {}, h("th", { scope: "row" }, text(name)), Cell({ value }));
};
const old5 = Table({ rows: v1, draw: UnkeyedRow });
const next5 = Table({ rows: [newRow, ...v1], draw: UnkeyedRow });
diff(old5, next5);
report("row prepended (unkeyed)");

scenario                            component  skipped      node    attribute  patch
no memoization, one cell changed           802        0      1004         601     1
memoized, one cell changed                 404      199       208           4     1
no memoization, nothing changed            802        0      1004         601     0
row prepended (keyed)                      804        0      1004         601     1
row prepended (unkeyed)                    804        0      1004         401   401

Reading the Numbers

The first row summarizes the model. A single patch is written to the document; reaching it took 802 component calls, 1004 node comparisons, and 601 attribute comparisons — roughly sixteen hundred to one.

This is not a flaw; it is the model’s definition. The framework does not know what changed; it compares to find out. The cost of comparison is proportional not to the size of the change but to the size of the produced tree.

The third row shows this most clearly: nothing changed, yet the same 802 calls and 1004 comparisons happen — only the patch count comes out to zero. Absence of change does not reduce the work.

The numbers hold two more components. Component calls measure rebuilding the produced tree — each call allocates new objects and works the heap. Node comparison measures traversing the tree. They are counted separately because they are reduced separately.

The Key Is Reconciliation’s Input

The difference between the fourth and fifth rows shows the most concrete decision point in this family.

When a row is prepended and there is a key, reconciliation matches every row by identity. The 200 old rows keep the same relative order in the new list, so no node needs to move; the single patch is the new row’s insertion. (The move count here comes from a longest-increasing-subsequence calculation: it finds the largest set of nodes that can stay put and moves only the rest.)

Without a key, comparison goes by position: the new list’s first item matches the old list’s first, the second matches the second, and so on. Prepending shifts every row by one position, so no match holds — all 200 rows come out with a different name and value, producing 401 patches. Only one row was actually inserted, yet 401 writes happen.

There is a side effect beyond the result: because nodes matched by position are reused, the document state attached to them — focus, scroll position, an input field’s typed content — stays on the wrong row. This is why keys in lists are a correctness requirement, not a performance preference.

Memoization’s Trade-off

The second row shows the reduction. Once the row component is memoized, the 199 rows whose props have not changed skip rerunning and return their previous tree. When diffing reaches these nodes, it sees identical references and never descends: node comparison drops from 1004 to 208, attribute comparison from 601 to 4.

The gain is large but conditional: memoization only works when a prop’s identity is preserved. If the parent produces a new object or function on every render and passes it as a prop, the shallow comparison fails every time and memoization gains nothing — it only adds comparison cost. The referential-stability problem from the Derived Values lesson becomes a performance tool in this family.

The second cost is visibility: memoization is manual — a human decides which component to memoize and whose identity to preserve. A wrong decision produces not an error but a silent slowdown.

The Family’s Profile

A few points capture this family’s profile and set up the comparison in the lessons ahead.

The update unit is the component; granularity stops at the component boundary. The runtime must carry the diffing algorithm and the tree representation — a fixed slice of the downloaded code. Because the component function is a pure transformation, the work is divisible: the framework can split comparison into chunks and interleave other work, since the virtual tree has no visible effect before it reaches the document. That same purity means no ledger records where a change came from; the information is rebuilt through comparison on every update.

Summary

• In this family, updating means producing a new tree from state and comparing it with the previous one; the re-render unit is the component.
• The cost of comparison is proportional to the size of the produced tree, not the size of the change: in a two-hundred-row table, a one-cell change produced 802 component calls and 1004 node comparisons, and a single patch was written to the document.
• The same work happens even when nothing changes; only the patch count comes out to zero.
• The key is reconciliation’s identity input: in a keyed list, prepending produced a single patch; in an unkeyed list, it produced 401 patches, and document state on nodes matched by position stays on the wrong row.
• Memoization ensures subtrees whose props have not changed are never descended into; in the example, node comparison dropped from 1004 to 208.
• Memoization depends on the referential stability of props and is applied manually; when misapplied, it stays silently ineffective.

Next Step

The work in this family traced back to one gap: the framework did not know what changed, so it compared to find out. Knowing would remove the need to compare. The way to know is to record where a value is read at the moment it is read — then, when the value is written, the list of places to update is already at hand. The next lesson covers the family that keeps this ledger at runtime, and compares its work on the same two-hundred-row table against the numbers here.