List Performance

In the previous lesson, the animation ran on the native side. The advancing value never entered the tree as a prop, so the node stayed kept. A list is the opposite case: what changes is the elements of the tree themselves, and a single insertion can affect the fate of every row. This lesson does not ask how fast a list scrolls. It asks what happens to each row node when an item is added.

The course’s question is the same: what does this update do to the node in the view tree? The answer has four forms. A node that stays in place with the same props is kept; if its props changed, it is updated. A node with no counterpart in the previous tree is mounted, and a node left with no counterpart in the new tree is unmounted. The work an update sends to the native side is the sum of the three fates other than kept, and that sum is called the commands. The rule below gives the fate, not a label. Producing the tree again from state is called a render. The rule compares two trees by matching their children by key, or by position when there is no key.

// fate.mjs — classifies what an update does to each node of the view tree
export const FATES = ["kept", "updated", "mounted", "unmounted"];

export function el(type, props = {}, children = [], key = null) {
  return { type, props, children, key };
}

function segment(node) {
  return node.key === null ? node.type : `${node.type}[${node.key}]`;
}

function identity(node, index) {
  return node.key === null ? `#${index}` : `key:${node.key}`;
}

function sameProps(a, b) {
  const names = [...new Set([...Object.keys(a), ...Object.keys(b)])].sort();
  return names.every((n) => JSON.stringify(a[n]) === JSON.stringify(b[n]));
}

function whole(node, path, fate, ops) {
  const here = `${path}/${segment(node)}`;
  ops.push({ fate, path: here });
  node.children.forEach((child) => whole(child, here, fate, ops));
}

export function reconcile(prev, next, path = "", ops = []) {
  if (prev === null) {
    whole(next, path, "mounted", ops);
    return ops;
  }
  if (next === null) {
    whole(prev, path, "unmounted", ops);
    return ops;
  }
  if (prev.type !== next.type || prev.key !== next.key) {
    whole(prev, path, "unmounted", ops);
    whole(next, path, "mounted", ops);
    return ops;
  }
  const here = `${path}/${segment(next)}`;
  ops.push({ fate: sameProps(prev.props, next.props) ? "kept" : "updated", path: here });
  const before = new Map(prev.children.map((child, i) => [identity(child, i), child]));
  const matched = new Set();
  next.children.forEach((child, i) => {
    const id = identity(child, i);
    matched.add(id);
    reconcile(before.has(id) ? before.get(id) : null, child, here, ops);
  });
  prev.children.forEach((child, i) => {
    if (!matched.has(identity(child, i))) reconcile(child, null, here, ops);
  });
  return ops;
}

export function printOps(ops) {
  ops.forEach((op) => console.log(`${op.fate}: ${op.path}`));
}

export function countFates(ops) {
  for (const name of FATES) {
    console.log(`${name}: ${ops.filter((op) => op.fate === name).length}`);
  }
  console.log(`commands: ${ops.filter((op) => op.fate !== "kept").length}`);
}

The part of the rule that matters in this lesson is the identity function. A child with a key is recognized by its key, and a child without a key by its position. Children carrying the same identity in the two trees form a pair; if the pair has the same type and key, their props are compared.

The function that turns the list into a tree lives in a separate file. renderInbox turns the items into row nodes. If its second parameter is true, it gives each row the item id as a key; if false, the row stays without a key.

// inbox.mjs — turns an inbox into a view tree
import { el } from "./fate.mjs";

export const ITEMS = [
  { id: "a", title: "Meeting" },
  { id: "b", title: "Invoice" },
  { id: "c", title: "Invite" },
];

export const FRESH = { id: "d", title: "Announcement" };

export function renderInbox(items, useKeys) {
  const rows = items.map((item) =>
    el("Row", { title: item.title }, [], useKeys ? item.id : null));
  return el("Inbox", {}, rows);
}

The inbox has three items, and a fourth, Announcement, arrives at the front of the list. Seeing the new item at the top is the behavior the user expects: the newest message stays at the top.

Matching by Index

In the first measurement, the rows are given no keys. The old tree has three rows and the new tree has four. The rule matches the rows by position: the first row of the old tree pairs with the first row of the new one, the second with the second, the third with the third. The fourth row of the new tree has no counterpart in the old one.

// main.mjs
import { reconcile, printOps } from "./fate.mjs";
import { renderInbox, ITEMS, FRESH } from "./inbox.mjs";

const before = renderInbox(ITEMS, false);
const after = renderInbox([FRESH, ...ITEMS], false);
printOps(reconcile(before, after));

kept: /Inbox
updated: /Inbox/Row
updated: /Inbox/Row
updated: /Inbox/Row
mounted: /Inbox/Row

Three rows came out updated and the last row came out mounted. The added item was at the front, but the new row in the tree was born at the end. The first row used to show Meeting and now shows Announcement; the second row shows Meeting where it showed Invoice, and the third row shows Invoice where it showed Invite. No row was mounted to represent the new item: the existing rows shifted the items down by one place and the surplus was added at the end. Because the props of three rows changed, three updates went out. The root node /Inbox has no props and stayed kept.

The paths of the rows without keys are all the same, /Inbox/Row, because a path is built only from the type and the key. The output does not say which row is which; the order does. Inside the rule, each one is recognized by the identity #0, #1, #2.

This is not only extra commands. In a real list, a row also has state of its own: being selected, a detail left open, a half-written reply. With index matching, the row node is kept but moves on to another item. The state stays in the row while the item shifts; the half-written reply in the first row suddenly becomes the reply to the Announcement item. What is called identity preservation breaks here: a kept or updated node carries on its identity, and the identity is now attached to the wrong item.

Stable Key

The second measurement makes the same insertion, but the rows are given the item id as a key. A key recognizes an item independently of its position: item a stays a whatever place it takes in the list. Such a key is called a stable key.

// main.mjs
import { reconcile, printOps } from "./fate.mjs";
import { renderInbox, ITEMS, FRESH } from "./inbox.mjs";

const before = renderInbox(ITEMS, true);
const after = renderInbox([FRESH, ...ITEMS], true);
printOps(reconcile(before, after));

kept: /Inbox
mounted: /Inbox/Row[d]
kept: /Inbox/Row[a]
kept: /Inbox/Row[b]
kept: /Inbox/Row[c]

Now a single row was mounted: the new item’s own row, /Inbox/Row[d]. The three old rows matched by their keys, and since their props stayed the same, all of them came out kept. The new row is at the front only by its position in the tree; the output of the rule prints it first as well. Identity preservation is also correct this time: the row of item a continues as the same row, together with the state inside it.

The key must be stable. If the position in the list is given as the key, the key is tied to the position and the situation of the first measurement returns. If the key is regenerated at every update, for example from a random number, every row loses its old identity each time; all the old rows come out unmounted and all the new rows mounted.

In the real framework, the key is derived from an item id in the function that produces the row. In a virtualized list, this is the job of the key extractor function. The snippet below shows the source form of the list; the model does not run this snippet.

// Platform code: Inbox
function Inbox({ items }) {
  return (
    <FlatList
      data={items}
      keyExtractor={(item) => item.id}
      renderItem={({ item }) => <Row title={item.title} />}
    />
  );
}

keyExtractor extracts a key from each item; the model represents this with the useKeys parameter. If no key extractor is defined, the real list may choose this fallback behavior on its own; the model measures only the two ends, with no keys and with keys.

Deleting from the Middle

Since the insertion was made at the front, the shift was the extreme case. Deletion belongs to the same class, and an item deleted from the middle separates the two matchings of the rule even further. Item b, Invoice, is removed from the list. The two remaining items, a and c, stay where they are.

// main.mjs
import { reconcile, countFates } from "./fate.mjs";
import { renderInbox, ITEMS } from "./inbox.mjs";

const remaining = ITEMS.filter((item) => item.id !== "b");
for (const useKeys of [false, true]) {
  console.log(useKeys ? "keyed matching" : "index matching");
  countFates(reconcile(renderInbox(ITEMS, useKeys), renderInbox(remaining, useKeys)));
}

index matching
kept: 2
updated: 1
mounted: 0
unmounted: 1
commands: 2
keyed matching
kept: 3
updated: 0
mounted: 0
unmounted: 1
commands: 1

With index matching, although the deleted item is b, the unmounted row is the last row: the second row was updated to show the Invite item, and the third row was left without a pair and was unmounted. With a stable key, the unmounted row is the deleted item’s own row, /Inbox/Row[b]; the other rows are kept. The command count dropped from two to one.

The common lesson of these two measurements is this: in a list without keys, the tree cannot tell which item was added or removed; it can only tell by how many rows the end grew or shrank. A key adds the identity of the item to the tree. If the list items can be sorted, filtered, or reordered by the user, this identity is not optional at all.

Window and Virtualization

The rule sees all the items of the list in the tree. A real virtualized list does not work that way. In a list of thousands of items, native views are mounted only for the rows visible on the screen and their immediate surroundings; this range is called the window. As the user scrolls, the rows leaving the window are unmounted on the native side and the rows entering it are mounted. For this reason, the performance of the list depends on the width of the window more than on the number of rows in the tree.

The settings of the window are written in the source of the list. If the height of a row is known in advance, the list can compute its position without mounting it; the window width and the number of items to render at first launch are also settings.

// Platform code: InboxTuned
function InboxTuned({ items }) {
  return (
    <FlatList
      data={items}
      keyExtractor={(item) => item.id}
      getItemLayout={(_, index) => ({ length: 64, offset: 64 * index, index })}
      windowSize={5}
      initialNumToRender={8}
      renderItem={({ item }) => <Row title={item.title} />}
    />
  );
}

The numbers written here are the settings of one list; they are not measurements. Which value works is shown by the profiler; the next lesson covers that tool. What matters in this lesson is that none of these settings is an input of the rule. The tree does not change while the window mounts and unmounts rows on the native side.

The Bounding Measurement

The two matchings are put side by side. The same insertion is made in two runs, and countFates prints the fate counts of each. What is compared is the command count, that is, the units of work going to the native side.

// main.mjs
import { reconcile, countFates } from "./fate.mjs";
import { renderInbox, ITEMS, FRESH } from "./inbox.mjs";

for (const useKeys of [false, true]) {
  console.log(useKeys ? "keyed matching" : "index matching");
  const before = renderInbox(ITEMS, useKeys);
  const after = renderInbox([FRESH, ...ITEMS], useKeys);
  countFates(reconcile(before, after));
}

index matching
kept: 1
updated: 3
mounted: 1
unmounted: 0
commands: 4
keyed matching
kept: 4
updated: 0
mounted: 1
unmounted: 0
commands: 1

Index matching gave four commands, and keyed matching gave one command. For the same insertion, that is four commands against one. In a list of three items the difference looks small; it grows as the list gets longer, because with index matching every item added at the front shifts every row after it down by one place. With a stable key, the command count does not depend on the length of the list.

The focus node is the first row of index matching, /Inbox/Row. All the records carrying the same path are filtered.

// main.mjs
import { reconcile, printOps } from "./fate.mjs";
import { renderInbox, ITEMS, FRESH } from "./inbox.mjs";

const ops = reconcile(renderInbox(ITEMS, false), renderInbox([FRESH, ...ITEMS], false));
printOps(ops.filter((op) => op.path === "/Inbox/Row"));

updated: /Inbox/Row
updated: /Inbox/Row
updated: /Inbox/Row
mounted: /Inbox/Row

The first record is updated: the first row stayed in place but now shows another item. This record is the lesson’s fate.

There are two things the rule does not see. The rule sees all the items in the tree, but not the window; in a real list, not all four of these commands may be needed on the native side, because the rows outside the window have no native view. The second is that the work a command holds on the native side is not in the model: changing the text of a row and reloading the image inside the row are the same number of commands. Telling the two apart falls to the profiler.

PP1. The model builds this fate’s rule; the model is not the framework itself. In the model the list has three items, there is no window, and every item is a row node in the tree. A real list mounts native views only for the items inside the window, chooses its own fallback behavior if no key extractor is defined, and can memoize a row to skip the re-render of a row whose props did not change; the model builds none of these. The model matches a child without a key by position and a child with a key by its key, and it does not interpret the behavior between the two ends it measures.

Summary

• This lesson’s fate: updated. With index matching, the /Inbox/Row node stayed in place when an item was added at the front, but was updated to show another item.
• With index matching, an item added at the front updated three rows and mounted one row at the end; the command count became four.
• With a stable key, the same insertion mounted a single /Inbox/Row[d] node, and the three old rows stayed kept; the command count became one.
• With index matching, the state of a row gets attached to the wrong item; a stable key keeps the identity together with the item.
• The rule sees all the items in the tree; it does not see the window or the native side’s work.

Next Step

In this lesson the tree changed and the commands were counted. It has also been seen that a render does not always produce commands: with a stable key, three rows gave no commands even though the tree was produced again. The next lesson, Frame Rate and Profiling, measures that an update that produces the tree three times can give zero commands.