第 15 章：不要逐个搜索一万个孩子

从五岁孩子也能理解的游戏开始

本章唯一需要牢记的事实：性能优化应从找出哪个步骤缓慢开始，而不是背诵优化技巧。

把 10,000 张儿童卡片铺满操场，请老师找到“小雨”。方法 A 从第一张卡依次读到最后一张。方法 B 先查城市箱，再查学校箱、班级隔层，最后查到座位。先预测一下：如果 10,000 张卡中只有 40 张位于当前视野内的教室，老师绘制座位表时需要给另外 9,960 张卡上色吗？不需要。再预测一下：如果每张卡都要绘制大照片、阴影、透明薄片和动画名字，那么 2,000 张卡一定比 100,000 个简单小点更快吗？不一定。

给老师一只分段秒表。每个阶段按一次：接收问题、更新名册、寻找候选教室、核对姓名、绘制座位、把纸放进视野。如果 p95 的“核对姓名”耗时 12ms，换一把更漂亮的画笔也无济于事。如果真正的瓶颈是解码大照片，更深的座位目录同样没有帮助。

平均值会掩盖少数极差体验。如果 100 次 Drag 中有 95 次耗时 4ms，另五次耗时 80ms，平均值也许看起来可以接受，界面却会时不时明显卡顿。应同时检查 p50、p95 和 p99，并保留代表性设备上的原始样本与 Trace。

把玩具对应到 Canvas

这个类比也有边界：真实的空间索引并不是无限嵌套的档案柜。它有更新成本、重叠边界、内存占用和退化情况。Culling 不会从 Document 删除任何内容，只是在当前 Render Pass 中避免访问不可见 Shapes。LOD 只能改变视觉细节，不能改变语义或 Hit Testing 事实。仅凭主线程火焰图无法推断 GPU 行为；这还需要浏览器/GPU 工具和测量。

先消灭错误直觉

• “Canvas 对象很多，所以绘制很慢。” 总对象数、可见对象数、路径复杂度、像素面积、透明图层、文字、图像和变化频率都会影响成本。
• “先切换到 WebGL/WebGPU。” 如果 p95 主要花在 Document 克隆、Geometry 查询或同步回读上，更换 Renderer 可能反而更差。
• “Spatial Index 总是更快。” 如果每个 Shape 每帧都在移动，维护索引可能比扫描更昂贵。应测量查询/更新比。
• “Cache 越多，速度越快。” 没有失效机制会绘制过期内容；没有淘汰机制会保留 Bitmaps、制造内存压力并触发 GC。缓存命中率和字节数都必须可见。
• “开发机器上达到 60 FPS 就完成了。” 高端桌面上的空白 Document 不是 Representative Device/Scene。预算必须覆盖低端硬件、高 DPR、大显示器和真实内容分布。
• “平均 8ms 就通过。” p99 可能达到 140ms。Interaction Latency 包括输入排队，并不等于单独的渲染时长。
• “getImageData() 只是一次函数调用。” Synchronous Readback 可能迫使整条管线等待。不要在热路径中使用它。
• “每次只分配几个对象，没什么影响。” 高频 Allocation 会不断累积，引发 GC Spikes，表现为周期性的 Drag 卡顿。

生产级背包

前置条件

第 5 章的 Document 提供稳定记录和变更集。第 6 章的 Scheduler 支持 Invalidation，而不是总是重绘。第 8 章的 GeometryKernel 提供边界、精确命中测试和空间查询接口。如果没有这些边界，Profile 只会显示一个巨大的 pointermove，无法判断慢的是模型、查询还是绘制。

正式知识

测量。 Frame Time 是一帧所有阶段的总耗时。Interaction Latency 从输入事件开始，一直持续到下一组相关像素呈现。请区分三种时钟：同步 performance.now() 只测量被包裹的 CPU 函数；User Timing 测量自定义阶段；浏览器 Event Timing/Trace 则可以在一次交互定义中包含输入排队、处理器、渲染和下一次绘制。requestAnimationFrame 回调发生在绘制之前，所以回调到达时间不能被表述成“像素现在已经可见”。应收集 p50/p95/p99，而不是只报告平均值。Long Task 表示主线程受到阻塞。DevTools 将 Scripting、Rendering、Painting 和 Compositing 分开；GPU 工具则补充纹理上传与填充率证据。对于 Memory，应区分 Allocation 速率、GC 暂停、Heap、估算的 ArrayBuffer/Bitmap 字节和 Retained Objects。基准测试中应固定浏览器、设备、电源模式、DPR、viewport、字体/素材缓存状态和数据随机种子。写出明确 Performance Budget，例如“在代表性设备上，Drag p95 ≤ 16ms，Hit Test p95 ≤ 4ms，稳定运行十分钟后的 heap 增长 ≤ 10%”。

优化顺序。 首先避免无效 Document Updates。随后让变更集驱动 Invalidation。再加入 Viewport Culling，使屏幕外对象跳过精细几何和绘制。如果 Broad Phase 扫描仍然缓慢，再引入 Spatial Index。它只产生候选；最终 Hit Result 仍由 GeometryKernel 的 Narrow Phase 和 Z-Order 决定。之后再根据屏幕尺寸加入 LOD，按样式/材质执行 Batching，并用 Layer Separation 分开静态背景和动态 Overlays。

缓存键必须与被缓存内容相匹配。只包含世界空间几何的 Path2D 通常使用 {shapeId, geometryRevision}。栅格化像素缓存还必须包含 {styleRevision, scaleBucket, dpr, colorSpace}。根据变更集精确使二者失效；不要把一种背熟的键公式强加给所有缓存。Image Atlas 可以减少大量小图像的纹理切换，但必须处理 padding、更新和最大纹理尺寸。只有在能够正确推导重叠、透明度和合成时才使用 Dirty Rectangles；绝不能遗漏旧位置。重用数组和临时向量以减少 Allocation。限制有效 DPR 和 Backing Pixel Area，避免大显示器让像素成本按平方增长。禁止在热路径中同步 Readback。

内存预算必须覆盖 Document、Spatial Index、Path/Bitmap 缓存、图像解码和 Export tiles。LRU/Eviction 应按估算字节数控制，而不是按条目数。Bitmap 大小可以用宽 × 高 × 每像素字节数估算。浏览器内部 Path2D 内存没有精确的标准化读数，所以应把受控估算、条目上限与代表性设备的 soak/heap 数据结合使用。绝不能把示例中的 96 当成真实测量值。当页面隐藏或系统报告 Memory Pressure 时，应主动降级。Cache Invalidation 的正确性比命中率更重要：宁愿重绘，也不能显示旧 Shape。

一个包含 100,000 个简单 Shapes、但只有 200 个可见的场景，主要成本是索引/查询与裁剪。一个只有 2,000 个却全部可见，且包含阴影、文字、alpha、图像和动画的场景，主要成本可能是绘制、像素填充、字体和图像上传。一张“对象数量”曲线无法同时为两者提供结论。

证据与兼容性（验证于 2026-08-29）

使用 User Timing API 创建高分辨率标记和度量。W3C Event Timing 描述了从事件到下一次绘制的标准化条目；仍需按浏览器和事件类型做特性检测。通过带特性检测的 Long Tasks API 观察 Long Tasks。MDN requestAnimationFrame 说明了回调时序和后台节流。Memory API 的可用性和语义各不相同。performance.measureUserAgentSpecificMemory() 仍需要安全上下文和兼容性检查；参见 MDN。不受支持时，使用 Heap Snapshots、进程指标和缓存自报字节数——绝不能伪造一个零。

本章工程增量

起点： 第 14 章已经能够测试正确性并收集 Render Time，但每一帧仍会扫描所有内容。终点： 同一个确定性场景拥有四种实现和一个 Benchmark：full、Invalidation、Culling，以及 Spatial Index + Cache + LOD。报告包含 Document/Visible 数量、Frame、Hit、Drag、Heap 和 Export Memory。

添加以下文件和接口：

• src/engine/perf/scenes.ts：根据固定随机种子生成 100,000 个简单对象和 2,000 个复杂对象；
• src/engine/spatial/GridIndex.ts：Broad-Phase 索引；
• src/engine/render/strategies.ts：共享同一个 Renderer 契约的四种策略；
• src/engine/cache/LruByteCache.ts：带字节上限的 Path/Bitmap 缓存；
• bench/canvas.bench.ts：预热、样本、百分位数和环境元数据；
• src/engine/perf/__tests__/index-equivalence.test.ts：索引查询结果等于全量扫描结果。

下面这份完整的最小实现展示了索引、裁剪、LOD、缓存失效和测量语义。它使用网格索引；生产环境可以针对实际数据分布将其替换为 R-tree，而无需改变查询协议：

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),
  };
}

回到找人游戏：query(viewport) 只打开与窗口相交的班级箱，overlaps 负责最终确认。缓存是一组复制卡片；版本发生变化时，旧副本会立即撕毁。LRU 超过 16MB 后，会先移除最久未使用的卡片。benchmarkCpuStage 只能回答“这段同步工作花了多长时间？”它的结果不能标为 Frame/Drag/Present；这些指标需要真实浏览器输入、Event Timing 和 Trace。链路中的每一步都有计数，因此“感觉更快”永远不能作为证据。

等价性测试防止优化改变结果；预算测试防止性能悄悄回退：

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);
});

上面的十个数只验证百分位数实现；它们不是代表性设备的性能证据。运行 npm run benchmark -- --scene=100k-simple --device=representative 时，真实测试工具应报告 documentSize、visibleShapes、cpuStage、frame.p50/p95/p99、hitTest、drag、heap、cacheEstimatedBytes、exportPeakBytes，以及浏览器/DPR/viewport/seed。它必须标明每个指标来自 microbenchmark、Event Timing 还是 Trace。四种策略必须使用同一个 Scene。预期结果不是“策略四总是获胜”，而是一份明确说明收益和成本的报告，例如 full p95 42ms → indexed p95 9ms，同时 index update p95 仍在预算内。运行 npm exec vitest run src/engine/perf；应确认索引与扫描查询等价、缓存版本更新绝不会返回旧 Path，并且 LRU 估算预算和条目上限都能保持。

故意破坏它

用证据通过

• full、invalidated、culled 和 indexed+cache+LOD 的数据，针对同一个 Scene 可以比较。
• 报告包含 Document Size 和 Visible Shapes，而不只写“对象数量”。
• Frame、Hit 和 Drag 包含 p50/p95/p99；Heap 与 Export Peak 分开记录。
• 每项优化都有正确性等价测试和禁用开关。
• Cache 拥有键、失效机制、字节预算、淘汰和命中指标。
• 结论明确指出 Trace 阶段和数值；禁止使用“Canvas 绘制很慢”。

向五岁孩子解释

不要说“p95”“Culling”“Spatial Index”“Cache”或“LOD”。解释老师为什么不该检查世界上的每一个孩子。为什么只有 2,000 张卡仍可能很慢？为什么复制卡片既有帮助，也可能塞满柜子？