第15章：1万人を一人ずつ探さない

5歳児にもわかるゲームから始めよう

この章の 1 つの真実: パフォーマンスの最適化は、最適化のコツを覚えることではなく、どのステップが遅いかを見つけることから始まります。

10,000 枚の子供用カードを遊び場に置き、先生に「Xiaoyu」を見つけてもらいます。方法 A は、すべてのカードを最初から最後まで読み取ります。方法 B では、まず都市ボックス、次に学校ボックス、教室コンパートメント、最後に座席をチェックします。これを予測してください。現在教室で 10,000 枚のカードのうち 40 枚だけが表示されている場合、教師は座席表を描くときに残りの 9,960 枚に色を付ける必要がありますか?いいえ、すべてのカードに大きな写真、影、透明なシート、アニメーション名が必要な場合、2,000 枚のカードのほうが 100,000 個の単純なドットよりも高速である必要があるかどうかを予測してください。必ずしもそうとは限りません。

教師にセグメント化されたストップウォッチを渡します。質問の受信、名簿の更新、候補教室の検索、名前の確認、座席の描画、紙の表示などの各段階で 1 回押します。 p95 の「名前の確認」に 12 ミリ秒かかる場合、これ以上きれいなペイントブラシを使用しても役に立ちません。実際のボトルネックが大きな写真のデコードである場合、シート ディレクトリを深くしても役に立ちません。

平均的なものには、少数のひどい経験が隠れています。 100 回のドラッグのうち 95 回のドラッグに 4 ミリ秒かかり、5 回のドラッグに 80 ミリ秒かかる場合、平均値は許容範囲内に見えるかもしれませんが、インターフェイスには目に見えて頻繁に問題が発生します。 p50、p95、および p99 を一緒に検査し、代表的なデバイスからの生のサンプルとトレースを保持します。

おもちゃを Canvas の概念に置き換える

類推はここで止まります。実際の空間インデックスは、無限にネストされたファイル キャビネットではありません。更新コスト、境界の重複、メモリ使用、および縮退のケースがあります。 Culling は Document から何も削除しません。現在の Render Pass の非表示の Shape へのアクセスを回避するだけです。 LOD は、セマンティックまたはヒット テストの真実を変更してはならず、視覚的な詳細のみを変更してはなりません。 GPU の動作は、メインスレッドのフレーム チャートだけからは推測できません。ブラウザ/GPU ツールと測定が必要です。

まず誤った思い込みを捨てる

• **「Canvasのオブジェクトが多いので描画が遅い。」**オブジェクトの総数、表示オブジェクト、パスの複雑さ、ピクセル領域、透明レイヤー、テキスト、画像、変更頻度はすべてコストに影響します。
• **「まず WebGL/WebGPU に切り替えてください。」**p95 が Document クローン作成、Geometry クエリ、または同期リードバックによって支配されている場合、別の Renderer の方が悪化する可能性があります。
• **「Spatial Index は常に高速です。」**Shape が各フレームを移動するたびにインデックスを維持すると、スキャンよりもコストがかかる可能性があります。クエリ/更新率を測定します。
• **「Cache が大きいほど、常に速度が向上します。」**無効化を行わないと、古いコンテンツが描画されます。エビクションなしではビットマップが保持され、メモリ負荷が生じ、GC がトリガーされます。 Cache のヒット率とバイト数が表示される必要があります。
• **「開発マシンでは 60 FPS に達したので、これで終わりです。」**ハイエンド デスクトップ上の空の Document は、代表デバイス/シーンではありません。予算は、ローエンドのハードウェア、高額の DPR、大型ディスプレイ、および実際のコンテンツの配信をカバーする必要があります。
• **「平均 8 ミリ秒で合格します。」**p99 は 140ms になる可能性があります。 Interaction Latency には入力キューイングが含まれており、レンダリング時間だけとは異なります。
• **「getImageData() は 1 つの関数呼び出しにすぎません。」**同期 Readback では、パイプラインが強制的に待機する可能性があります。高温の通路に置かないでください。
• **「毎回いくつかのオブジェクトを割り当てることは問題ではありません。」**高頻度の Allocation が蓄積すると、周期的なドラッグ ヒッチとして見える GC スパイクが発生します。

本番環境に必要な知識

前提条件

第 5 章の Document は、安定したレコードと変更セットを提供します。第 6 章のスケジューラは、常に再描画する代わりに無効化をサポートします。第 8 章の GeometryKernel は、境界、正確なヒット テスト、および空間クエリ インターフェイスを提供します。これらの境界がなければ、プロファイルには巨大な pointermove が 1 つだけ表示されます。モデル、クエリ、または描画が遅いかどうかを明らかにすることはできません。

体系的な知識

測定。Frame Time は、フレームのすべてのステージで費やされる合計時間です。 Interaction Latency は、入力イベントから次の関連ピクセルが表示されるまで実行されます。 3 つのクロックを区別します。同期 performance.now() はラップされた CPU 関数のみを測定します。ユーザー タイミングはカスタム ステージを測定します。ブラウザのイベント タイミング/トレースには、入力キュー、ハンドラー、レンダリング、および次のペイントをインタラクション定義に含めることができます。 requestAnimationFrame のコールバックは paint の前に実行されるため、その到着時刻を「ピクセルが表示されるようになった」ように表示することはできません。平均だけを報告するのではなく、p50/p95/p99 を収集します。 Long Task は、メインスレッドのブロックを示します。 DevTools は、スクリプト作成、レンダリング、ペイント、および合成を分離します。 GPU ツールは、テクスチャのアップロードとフィルレートの証拠を追加します。 Memory の場合、Allocation レート、GC 一時停止、Heap、推定 ArrayBuffer/Bitmap バイト、および Retained Objects を区別します。ベンチマークのブラウザー、デバイス、電源モード、DPR、ビューポート、フォント/アセット キャッシュ状態、およびデータ シードを修正します。 「代表的なデバイスで、ドラッグ p95 ≤ 16ms、ヒット テスト p95 ≤ 4ms、安定した 10 分間後のヒープ増加率 ≤ 10%」などの Performance Budget を記述します。

**最適化の順序。**まず無効な Document アップデートを避けてください。次に、変更セットで無効化を実行します。次に、Viewport Culling を追加して、画面外のオブジェクトが細かいジオメトリと描画をスキップできるようにします。 Broad Phase スキャンがまだ遅い場合は、Spatial Index を導入してください。候補者のみを生成します。 GeometryKernel の Narrow Phase と Z オーダーが最終的なヒット結果を決定します。その後、画面上のサイズに基づいて LOD を、スタイル/マテリアルに基づいて Batching を、静的な背景と動的なオーバーレイの間に Layer Separation を追加します。

キャッシュキーはキャッシュされたものと一致する必要があります。ワールド空間ジオメトリのみを含む Path2D は、通常、{shapeId, geometryRevision} を使用します。ラスター化されたピクセルのキャッシュには、{styleRevision, scaleBucket, dpr, colorSpace} も含まれている必要があります。変更セットから両方を正確に無効にします。 1 つの記憶されたキー式をすべてのキャッシュに強制しないでください。 Image Atlas は、多くの小さなイメージのテクスチャ スイッチを減らしますが、パディング、更新、およびテクスチャの最大寸法を処理する必要があります。 Dirty Rectangles は、オーバーラップ、透明度、合成を正しく導出できる場合にのみ使用します。決して古い位置を省略しないでください。配列と一時ベクトルを再利用して、Allocation を削減します。有効な DPR とバッキング ピクセル領域を制限して、大きなディスプレイがピクセルコストを二乗で増やさないようにします。同期 Readback をホット パスから禁止します。

メモリ バジェットは、Document、Spatial Index、パス/Bitmap キャッシュ、イメージ デコード、および Export タイルをカバーする必要があります。 LRU/Eviction をエントリ数ではなく推定バイト数で制御します。 Bitmap のサイズは、幅 × 高さ × ピクセルあたりのバイト数から推定できます。 Browser 内部 Path2D メモリには正確に標準化された読み取り値がないため、制御された推定値、エントリ制限、および代表デバイスのソーク/ヒープ データを一緒に使用して制限します。例の 96 を実際の測定値として決して扱わないでください。ページが非表示になった場合、またはシステムが Memory 圧力を報告した場合は、プロアクティブに機能を低下させます。 Cache Invalidation の正確性はヒット率よりも重要です。古い Shape を表示するのではなく再描画します。

100,000 個の単純なシェイプがあるが、表示されているのは 200 個だけであるシーンは、インデックス/クエリとカリングによって大部分が占められています。シャドウ、テキスト、アルファ、イメージ、アニメーションを含む 2,000 の完全に表示されたシェイプを含むシーンは、ペイント、ピクセル塗りつぶし、フォント、およびイメージのアップロードによって占められる場合があります。 1 つの「オブジェクト数」グラフで両方の結論を正当化することはできません。

根拠と互換性（確認日：2026-08-29）

高解像度のマークとメジャーには User Timing API を使用します。イベントから次のペイントまでの標準化されたエントリは、W3C Event Timing によって記述されます。ブラウザとイベント タイプによる機能検出も可能です。特徴検出を備えた Long Tasks API を介して長いタスクを監視します。コールバックのタイミングとバックグラウンドのスロットリングについては、MDN requestAnimationFrame を参照してください。 Memory API の可用性とセマンティクスは異なります。 performance.measureUserAgentSpecificMemory() では依然として安全なコンテキストと互換性チェックが必要です。 MDN を参照してください。サポートされていない場合は、Heap スナップショットを使用し、メトリクスを処理し、自己報告バイトをキャッシュします。決して捏造されたゼロではありません。

本章の実装ステップ

**出発点:**第 14 章では、正確性をテストして Render Time を収集できますが、それでもすべてのフレームがすべてスキャンされます。**フィニッシュライン:**同じ決定論的シーンには、完全、無効化、Culling、Spatial Index + Cache + LOD の 4 つの実装と 1 つのベンチマークがあります。レポートには、Document/可視カウント、フレーム、ヒット、ドラッグ、Heap、Export Memory が含まれます。

次のファイルとインターフェイスを追加します。

• src/engine/perf/scenes.ts: 固定シードから 100,000 個の単純なオブジェクトと 2,000 個の複雑なオブジェクトを生成します。
• src/engine/spatial/GridIndex.ts: ブロードフェーズインデックス。
• src/engine/render/strategies.ts: 1 つの Renderer コントラクトを共有する 4 つの戦略。
• src/engine/cache/LruByteCache.ts: バイト制限のあるパス/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() };
    // この関数に入る前に、Host は Camera に従って bitmap 全体を消去済みである。この例の invalidation はフレームを予定するかどうかだけを最適化し、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 というラベルを付けることはできません。これらには、実際のブラウザ入力、イベント タイミング、およびトレースが必要です。チェーン内のすべてのリンクにはカウントがあるため、「速く感じられる」ということが証拠になることはありません。

等価性テストにより、最適化によって結果が変更されるのを防ぎます。予算テストは、パフォーマンスがサイレントに低下するのを防ぎます。

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

test('Spatial Index のクエリ結果は Broad Phase の全件走査と完全に等価である', () => {
  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('記録済み fixture に対する nearest-rank percentile gate の計算が正しい', () => {
  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);
});

上記の 10 個の数値は、パーセンタイルの実装のみを検証します。これらは代表的なデバイスのパフォーマンスを示すものではありません。 npm run benchmark -- --scene=100k-simple --device=representative を実行する場合、実際のハーネスは documentSize、visibleShapes、cpuStage、frame.p50/p95/p99、hitTest、drag、heap、cacheEstimatedBytes、exportPeakBytes、およびブラウザ/DPR/viewport/seed をレポートする必要があります。各メトリクスがマイクロベンチマーク、イベント タイミング、またはトレースから取得されたものであるかどうかをラベル付けする必要があります。 4 つの戦略はすべて同じシーンを使用する必要があります。期待されるのは、「戦略 4 が常に勝つ」ということではなく、利益とコストを明確に記載するレポート (たとえば、full p95 42ms → indexed p95 9ms) でありながら、インデックス更新 p95 が予算内にとどまることです。 npm exec vitest run src/engine/perf を実行します。インデックス付けされたクエリとスキャンされたクエリは同等であること、キャッシュ リビジョンの更新では古いパスが返されることはなく、LRU の推定バジェットとエントリ制限の両方が保持されることが期待されます。

意図的に壊してみる

根拠を示して合格する

• 完全なデータ、無効化されたデータ、カリングされたデータ、およびインデックス付き + キャッシュ + LOD のデータは、同じシーンで比較できます。
• レポートには、「オブジェクト数」だけでなく、Document サイズと表示形状が含まれます。
• フレーム、ヒット、ドラッグには p50/p95/p99 が含まれます。 Heap と Export ピークは別々に記録されます。
• すべての最適化には、正確性同等性テストと無効化スイッチがあります。
• Cache には、キー、無効化、バイト バジェット、エビクション、およびヒット メトリックがあります。
• 結論は、トレース ステージと番号を特定します。 「Canvasの描画が遅い」は禁止です。

5歳児に説明する

「p95」、「Culling」、「Spatial Index」、「Cache」、または「LOD」とは言わないでください。なぜ教師が世界中の子供たちを検査すべきではないのか説明してください。 2,000 枚のカードだけでもまだ遅いのはなぜですか?コピーされたカードは役立つのに、キャビネットから溢れてしまうのはなぜでしょうか?