Chapter 15: Do Not Search Ten Thousand Children One by One

Start with a game a five-year-old can understand

The one truth in this chapter: performance optimization starts by finding which step is slow, not by memorizing optimization tricks.

Place 10,000 children’s cards across a playground and ask the teacher to find “Xiaoyu.” Method A reads every card from first to last. Method B first checks the city box, then the school box, the classroom compartment, and finally the seat. Predict this: if only 40 of the 10,000 cards are in the classroom currently in view, does the teacher need to color the other 9,960 when drawing the seating chart? No. Now predict whether 2,000 cards must be faster than 100,000 simple dots if every card requires a large photo, shadow, transparent sheet, and animated name. Not necessarily.

Give the teacher a segmented stopwatch. Press it once for each stage: receiving the question, updating the roster, finding candidate classrooms, checking names, drawing seats, and placing the paper in view. If p95 “check names” takes 12ms, a prettier paintbrush will not help. If the real bottleneck is decoding large photos, a deeper seat directory will not help either.

An average hides a small number of terrible experiences. If 95 of 100 Drags take 4ms and five take 80ms, the average may seem acceptable, yet the interface visibly hitches every so often. Inspect p50, p95, and p99 together, and retain raw samples and Traces from representative devices.

Translate the toys into Canvas

Where the analogy stops: a real spatial index is not an infinitely nested filing cabinet. It has update cost, overlapping bounds, memory use, and degenerate cases. Culling does not delete anything from the Document; it merely avoids visiting invisible Shapes in the current Render Pass. LOD must not change semantic or Hit Testing truth, only visual detail. GPU behavior cannot be inferred from a main-thread flame chart alone; it requires browser/GPU tooling and measurement.

Kill the wrong intuitions first

• “There are many Canvas objects, so drawing is slow.” Total objects, visible objects, path complexity, pixel area, transparent layers, text, images, and change frequency all contribute to cost.
• “Switch to WebGL/WebGPU first.” If p95 is dominated by Document cloning, Geometry queries, or synchronous readback, a different Renderer may be worse.
• “A Spatial Index is always faster.” Maintaining the index while every Shape moves each frame can cost more than scanning. Measure the query/update ratio.
• “More Cache always means more speed.” Without invalidation it draws stale content; without eviction it retains Bitmaps, creates memory pressure, and triggers GC. Cache hit rate and bytes must be visible.
• “It reaches 60 FPS on a development machine, so it is done.” A blank Document on a high-end desktop is not a Representative Device/Scene. Budgets must cover low-end hardware, high DPR, large displays, and real content distributions.
• “An 8ms average passes.” p99 may be 140ms. Interaction Latency includes input queueing and is not the same as render duration alone.
• “getImageData() is only one function call.” Synchronous Readback may force the pipeline to wait. Keep it out of hot paths.
• “Allocating a few objects each time does not matter.” High-frequency Allocation accumulates and causes GC Spikes, visible as periodic Drag hitches.

Production backpack

Prerequisites

Chapter 5’s Document supplies stable records and a change set. Chapter 6’s Scheduler supports Invalidation instead of always redrawing. Chapter 8’s GeometryKernel supplies bounds, precise hit testing, and a spatial-query interface. Without these boundaries, a Profile shows only one giant pointermove; it cannot reveal whether the model, query, or drawing is slow.

Formal knowledge

Measurement. Frame Time is the total time spent in all stages of a frame. Interaction Latency runs from the input event until the next related pixels are presented. Distinguish three clocks: synchronous performance.now() measures only the wrapped CPU function; User Timing measures custom stages; browser Event Timing/Trace can include input queueing, the handler, rendering, and the next paint in an interaction definition. A requestAnimationFrame callback occurs before paint, so its arrival time cannot be presented as “pixels are now visible.” Collect p50/p95/p99 instead of reporting only an average. A Long Task indicates main-thread blocking. DevTools separates Scripting, Rendering, Painting, and Compositing; GPU tools add texture-upload and fill-rate evidence. For Memory, distinguish Allocation rate, GC pause, Heap, estimated ArrayBuffer/Bitmap bytes, and Retained Objects. Fix the browser, device, power mode, DPR, viewport, font/asset cache state, and data seed in a benchmark. Write a Performance Budget such as “on the representative device, Drag p95 ≤ 16ms, Hit Test p95 ≤ 4ms, and heap growth after ten stable minutes ≤ 10%.”

Optimization order. First avoid invalid Document Updates. Next, let the change set drive Invalidation. Then add Viewport Culling so off-screen objects skip fine geometry and drawing. If Broad Phase scanning is still slow, introduce a Spatial Index. It produces candidates only; GeometryKernel’s Narrow Phase and Z-Order still determine the final Hit Result. After that, add LOD based on on-screen size, Batching by style/material, and Layer Separation between static backgrounds and dynamic Overlays.

A cache key must match what is cached. A Path2D that contains only world-space geometry usually uses {shapeId, geometryRevision}. A cache of rasterized pixels must also include {styleRevision, scaleBucket, dpr, colorSpace}. Invalidate both precisely from the change set; do not force one memorized key formula onto every cache. An Image Atlas reduces texture switches for many small images but must handle padding, updates, and maximum texture dimensions. Use Dirty Rectangles only when overlap, transparency, and compositing can be derived correctly; never omit the old position. Reuse arrays and temporary vectors to reduce Allocation. Limit effective DPR and Backing Pixel Area so a large display does not square the pixel cost. Ban synchronous Readback from hot paths.

The memory budget must cover Document, Spatial Index, Path/Bitmap caches, image decode, and Export tiles. Control LRU/Eviction by estimated bytes, not entry count. Bitmap size can be estimated from width × height × bytes per pixel. Browser-internal Path2D memory has no exact standardized reading, so constrain it with a controlled estimate, an entry limit, and representative-device soak/heap data together. Never treat the example’s 96 as a real measurement. Degrade proactively when the page becomes hidden or the system reports Memory Pressure. Cache Invalidation correctness matters more than hit rate: redraw rather than showing an old Shape.

A scene with 100,000 simple Shapes but only 200 visible is dominated by index/query and culling. A scene with 2,000 fully visible Shapes containing shadow, text, alpha, image, and animation may be dominated by paint, pixel fill, fonts, and image upload. One “object count” graph cannot justify conclusions for both.

Evidence and compatibility (verified 2026-08-29)

Use the User Timing API for high-resolution marks and measures. Standardized entries from an event to the next paint are described by W3C Event Timing; still feature-detect by browser and event type. Observe Long Tasks through the Long Tasks API with feature detection. See MDN requestAnimationFrame for callback timing and background throttling. Memory API availability and semantics vary. performance.measureUserAgentSpecificMemory() still requires a secure context and compatibility checks; see MDN. When unsupported, use Heap Snapshots, process metrics, and cache self-reported bytes—never a fabricated zero.

Engineering increment for this chapter

Starting point: Chapter 14 can test correctness and collect Render Time, but every frame still scans everything. Finish line: the same deterministic scene has four implementations and one Benchmark: full, Invalidation, Culling, and Spatial Index + Cache + LOD. Reports include Document/Visible counts, Frame, Hit, Drag, Heap, and Export Memory.

Add these files and interfaces:

• src/engine/perf/scenes.ts: generate 100,000 simple objects and 2,000 complex objects from fixed seeds;
• src/engine/spatial/GridIndex.ts: Broad-Phase index;
• src/engine/render/strategies.ts: four strategies sharing one Renderer contract;
• src/engine/cache/LruByteCache.ts: Path/Bitmap cache with a byte limit;
• bench/canvas.bench.ts: warmup, samples, percentile, and environment metadata;
• src/engine/perf/__tests__/index-equivalence.test.ts: indexed-query results equal full-scan results.

The complete minimal implementation below demonstrates indexing, culling, LOD, cache invalidation, and measurement semantics. It uses a grid index; production can replace it with an R-tree for the data distribution without changing the query protocol:

type Bounds = Readonly<{ minX: number; minY: number; maxX: number; maxY: number }>;
type Shape = Readonly<{
  id: string;
  rev: number;
  x: number;
  y: number;
  w: number;
  h: number;
  label: string;
}>;
const boundsOf = (s: Shape): Bounds => ({ minX: s.x, minY: s.y, maxX: s.x + s.w, maxY: s.y + s.h });
const overlaps = (a: Bounds, b: Bounds) =>
  a.minX <= b.maxX && a.maxX >= b.minX && a.minY <= b.maxY && a.maxY >= b.minY;

export class GridIndex {
  private cells = new Map<string, Set<string>>();
  private entries = new Map<string, Bounds>();
  constructor(private readonly cellSize = 512) {}
  private keys(b: Bounds) {
    const keys: string[] = [];
    for (let y = Math.floor(b.minY / this.cellSize); y <= Math.floor(b.maxY / this.cellSize); y++)
      for (let x = Math.floor(b.minX / this.cellSize); x <= Math.floor(b.maxX / this.cellSize); x++)
        keys.push(`${x}:${y}`);
    return keys;
  }
  upsert(id: string, bounds: Bounds) {
    this.remove(id);
    this.entries.set(id, bounds);
    for (const key of this.keys(bounds)) {
      const cell = this.cells.get(key) ?? new Set<string>();
      cell.add(id);
      this.cells.set(key, cell);
    }
  }
  remove(id: string) {
    const old = this.entries.get(id);
    if (!old) return;
    for (const key of this.keys(old)) {
      const cell = this.cells.get(key);
      cell?.delete(id);
      if (cell?.size === 0) this.cells.delete(key);
    }
    this.entries.delete(id);
  }
  query(area: Bounds) {
    const ids = new Set<string>();
    for (const key of this.keys(area))
      for (const id of this.cells.get(key) ?? [])
        if (overlaps(this.entries.get(id)!, area)) ids.add(id);
    return [...ids];
  }
}

class LruPathCache {
  private map = new Map<string, { path: Path2D; bytes: number }>();
  private used = 0;
  constructor(private readonly budgetBytes: number) {}
  get(key: string) {
    const item = this.map.get(key);
    if (!item) return;
    this.map.delete(key);
    this.map.set(key, item);
    return item.path;
  }
  set(key: string, path: Path2D, bytes: number) {
    const old = this.map.get(key);
    if (old) {
      this.used -= old.bytes;
      this.map.delete(key);
    }
    this.map.set(key, { path, bytes });
    this.used += bytes;
    while (this.used > this.budgetBytes) {
      const first = this.map.keys().next().value as string | undefined;
      if (!first) break;
      this.used -= this.map.get(first)!.bytes;
      this.map.delete(first);
    }
  }
  invalidateShape(id: string) {
    for (const [key, item] of this.map)
      if (key.startsWith(`${id}:`)) {
        this.used -= item.bytes;
        this.map.delete(key);
      }
  }
  bytes() {
    return this.used;
  }
}

type Strategy = 'full' | 'invalidated' | 'culled' | 'indexed-cached-lod';
export class SceneRenderer {
  private index = new GridIndex();
  private cache = new LruPathCache(16 * 1024 * 1024);
  private dirty = new Set<string>();
  private shapes = new Map<string, Shape>();
  upsert(shape: Shape) {
    this.shapes.set(shape.id, shape);
    this.index.upsert(shape.id, boundsOf(shape));
    this.cache.invalidateShape(shape.id);
    this.dirty.add(shape.id);
  }
  render(ctx: CanvasRenderingContext2D, viewport: Bounds, zoom: number, strategy: Strategy) {
    if (strategy === 'invalidated' && this.dirty.size === 0)
      return { candidates: 0, drawn: 0, cacheBytes: this.cache.bytes() };
    // Before entering this function, Host has cleared the full bitmap using the Camera. In this example, invalidation optimizes only whether to schedule a frame; it is not a Dirty Rect.
    const candidates =
      strategy === 'full' || strategy === 'invalidated'
        ? [...this.shapes.keys()]
        : strategy === 'culled'
          ? [...this.shapes.values()]
              .filter((s) => overlaps(boundsOf(s), viewport))
              .map((s) => s.id)
          : this.index.query(viewport);
    let drawn = 0;
    for (const id of candidates) {
      const s = this.shapes.get(id)!;
      if (!overlaps(boundsOf(s), viewport)) continue;
      const simple = strategy === 'indexed-cached-lod' && Math.max(s.w, s.h) * zoom < 12;
      const key = `${s.id}:${s.rev}:${simple ? 'low' : 'high'}`;
      let path = strategy === 'indexed-cached-lod' ? this.cache.get(key) : undefined;
      if (!path) {
        path = new Path2D();
        path.rect(s.x, s.y, s.w, s.h);
        if (strategy === 'indexed-cached-lod') this.cache.set(key, path, 96);
      }
      ctx.fillStyle = '#e2e8f0';
      ctx.fill(path);
      ctx.strokeStyle = '#334155';
      ctx.stroke(path);
      if (!simple) {
        ctx.fillStyle = '#0f172a';
        ctx.fillText(s.label, s.x + 4, s.y + 14);
      }
      drawn++;
    }
    this.dirty.clear();
    return { candidates: candidates.length, drawn, cacheBytes: this.cache.bytes() };
  }
}

export function percentile(samples: readonly number[], p: number) {
  if (!samples.length) throw new Error('NO_SAMPLES');
  const sorted = [...samples].sort((a, b) => a - b);
  return sorted[Math.min(sorted.length - 1, Math.ceil(p * sorted.length) - 1)];
}
export async function benchmarkCpuStage(name: string, rounds: number, task: () => void) {
  for (let i = 0; i < 30; i++) task();
  const samples: number[] = [];
  for (let i = 0; i < rounds; i++) {
    const start = performance.now();
    task();
    samples.push(performance.now() - start);
    await Promise.resolve();
  }
  return {
    name,
    samples,
    p50: percentile(samples, 0.5),
    p95: percentile(samples, 0.95),
    p99: percentile(samples, 0.99),
  };
}

Back to the search game: query(viewport) opens only classroom boxes that intersect the window; overlaps is the final confirmation. The cache is a set of copied cards; a revision change tears up an old copy immediately. When the LRU exceeds 16MB, it removes the least recently used cards first. benchmarkCpuStage can answer only “how long did this synchronous work take?” Its results must not be labeled Frame/Drag/Present; those require real browser input, Event Timing, and Trace. Every link in the chain has a count, so “it feels faster” is never the evidence.

Equivalence tests prevent optimization from changing results; Budget tests prevent performance from regressing silently:

import { expect, test } from 'vitest';
import { GridIndex, percentile } from '../performance';

test('spatial-index query is exactly equivalent to a full Broad Phase scan', () => {
  const index = new GridIndex(64);
  const items = Array.from({ length: 10_000 }, (_, i) => ({
    id: `s-${i}`,
    minX: (i % 100) * 20,
    minY: Math.floor(i / 100) * 20,
    maxX: (i % 100) * 20 + 12,
    maxY: Math.floor(i / 100) * 20 + 12,
  }));
  for (const { id, ...bounds } of items) index.upsert(id, bounds);
  const area = { minX: 180, minY: 240, maxX: 820, maxY: 760 };
  const scan = items
    .filter(
      (s) =>
        s.minX <= area.maxX && s.maxX >= area.minX && s.minY <= area.maxY && s.maxY >= area.minY,
    )
    .map((s) => s.id)
    .sort();
  expect(index.query(area).sort()).toEqual(scan);
});

test('nearest-rank percentile gate is correct for a recorded fixture', () => {
  const samples = [7.2, 8.1, 8.4, 9.0, 9.2, 10.1, 11.4, 12.0, 12.8, 14.9];
  expect(percentile(samples, 0.95)).toBeLessThanOrEqual(16);
});

The ten numbers above verify only the percentile implementation; they are not performance evidence from a representative device. When running npm run benchmark -- --scene=100k-simple --device=representative, the real harness should report documentSize, visibleShapes, cpuStage, frame.p50/p95/p99, hitTest, drag, heap, cacheEstimatedBytes, exportPeakBytes, and browser/DPR/viewport/seed. It must label whether each metric came from a microbenchmark, Event Timing, or Trace. All four strategies must use the same Scene. The expectation is not “strategy four always wins,” but a report that states benefit and cost explicitly, for example full p95 42ms → indexed p95 9ms, while index update p95 remains within budget. Run npm exec vitest run src/engine/perf; expect indexed and scanned queries to be equivalent, cache revision updates never to return an old Path, and both the LRU estimate budget and entry limit to hold.

Break it on purpose

Pass with evidence

• Data from full, invalidated, culled, and indexed+cache+LOD are comparable for the same Scene.
• Reports contain Document Size and Visible Shapes, not just “object count.”
• Frame, Hit, and Drag include p50/p95/p99; Heap and Export Peak are recorded separately.
• Every optimization has a correctness-equivalence test and a disable switch.
• Cache has keys, invalidation, byte budget, eviction, and hit metrics.
• Conclusions identify the Trace stage and numbers; “Canvas drawing is slow” is forbidden.

Explain it to a five-year-old

Do not say “p95,” “Culling,” “Spatial Index,” “Cache,” or “LOD.” Explain why the teacher should not inspect every child in the world. Why might only 2,000 cards still be slow? Why can copied cards help but also overflow the cabinet?