《游戏引擎实现原理》15.2 任务图构建与帧内调度

// file: src/core/frame-scheduler.ts
// tier: L1
// verify: npx vitest run src/core/frame-scheduler.test.ts
//
// helio 内核：每帧重建任务图并求出帧内调度计划。
// 模板任务固定存在；动态任务随本帧场景变化（如可见区块数）临时加入。
// 计划 = 分层拓扑序；同一层内的任务互不依赖，可以丢给工作线程并行执行。

import { TaskGraph } from './task-graph.ts';
import type { TaskId } from './task-graph.ts';

/** 帧内任务声明。cost 是相对耗时（毫秒），只用于估算帧内关键路径。 */
export interface FrameTask {
  readonly id: TaskId;
  readonly after: readonly TaskId[];
  readonly cost: number;
}

/** 一帧的调度计划。 */
export interface FramePlan {
  readonly frame: number;
  readonly taskCount: number;
  readonly order: readonly TaskId[];
  readonly levels: readonly (readonly TaskId[])[];
  readonly parallelism: readonly number[];
  readonly maxParallelism: number;
  readonly criticalPathMs: number;
}

/**
 * 帧调度器。持有「模板任务」，每帧把模板与动态任务合并成一张新图，
 * 再跑一次拓扑分层。整个过程每帧重复一遍，所以它本身的耗时要可控。
 */
export class FrameScheduler {
  readonly #template: readonly FrameTask[];

  constructor(template: readonly FrameTask[]) {
    this.#template = template;
  }

  /** 生成第 frame 帧的计划。dynamic 是本帧临时出现的任务。 */
  plan(frame: number, dynamic: readonly FrameTask[] = []): FramePlan {
    const graph = new TaskGraph();
    const cost = new Map<TaskId, number>();
    for (const t of this.#template) {
      graph.add({ id: t.id, after: t.after, run: () => {} });
      cost.set(t.id, t.cost);
    }
    for (const t of dynamic) {
      graph.add({ id: t.id, after: t.after, run: () => {} });
      cost.set(t.id, t.cost);
    }
    const topo = graph.plan();
    const parallelism = topo.levels.map((l) => l.length);
    // 关键路径估计：层内并行只算最慢任务，层与层串行相加。这是理想打包下的下界。
    let criticalPathMs = 0;
    for (const level of topo.levels) {
      let slowest = 0;
      for (const id of level) slowest = Math.max(slowest, cost.get(id) ?? 0);
      criticalPathMs += slowest;
    }
    return {
      frame,
      taskCount: graph.size,
      order: topo.order,
      levels: topo.levels,
      parallelism,
      maxParallelism: topo.maxParallelism,
      criticalPathMs,
    };
  }
}

/**
 * 造出 glimmer-isle 第「chunks 个可见区块」这一帧的完整任务表。
 * 每帧都从头拼一次：区块数会变，任务集合随之变化——这正是「每帧重建图」的来源。
 * cost 是模拟耗时（毫秒），只用于关键路径估计，不是实测。
 */
export function buildFrameTasks(chunks: number): FrameTask[] {
  const tasks: FrameTask[] = [
    { id: 'input', after: [], cost: 0.4 },
    { id: 'sim-physics', after: ['input'], cost: 1.8 },
    { id: 'sim-ai', after: ['input'], cost: 1.2 },
    { id: 'sim-anim', after: ['sim-physics'], cost: 0.9 },
  ];
  const chunkIds: string[] = [];
  for (let i = 0; i < chunks; i++) {
    const id = `chunk-${i}`;
    tasks.push({ id, after: ['input'], cost: 0.6 });
    chunkIds.push(id);
  }
  tasks.push({ id: 'render-list', after: ['sim-anim', 'sim-ai', ...chunkIds], cost: 0.5 });
  tasks.push({ id: 'cull', after: ['render-list'], cost: 0.7 });
  tasks.push({ id: 'submit', after: ['cull'], cost: 0.3 });
  return tasks;
}

// file: bench/frame-rebuild.ts
// tier: B
// verify: node bench/frame-rebuild.ts
//
// 两件事：(1) 模拟 5 帧，打印每帧的执行顺序与并行度；
// (2) 测量「每帧重建任务图 + 拓扑分层」本身的开销，随任务数的变化。

import { performance } from 'node:perf_hooks';
import { FrameScheduler, buildFrameTasks } from '../src/core/frame-scheduler.ts';

const sched = new FrameScheduler([]);

console.log('=== 每帧执行顺序与并行度 ===');
const chunksPerFrame = [0, 1, 3, 3, 2];
for (let frame = 0; frame < chunksPerFrame.length; frame++) {
  const plan = sched.plan(frame, buildFrameTasks(chunksPerFrame[frame]!));
  console.log(
    `frame ${frame}  tasks=${plan.taskCount}  maxParallel=${plan.maxParallelism}` +
      `  parallelism=[${plan.parallelism.join(',')}]`,
  );
  console.log(`          order: ${plan.order.join(' -> ')}`);
}

console.log('\n=== 重建开销（plan() 一次） ===');
function benchRebuild(chunks: number, iters: number): number {
  // 预热，让 JIT 先编译。
  for (let i = 0; i < 2000; i++) sched.plan(i, buildFrameTasks(chunks));
  const t0 = performance.now();
  for (let i = 0; i < iters; i++) sched.plan(i, buildFrameTasks(chunks));
  const t1 = performance.now();
  return ((t1 - t0) / iters) * 1000; // 微秒/次
}

for (const chunks of [0, 3, 100, 1000]) {
  const iters = chunks >= 1000 ? 20000 : 200000;
  const us = benchRebuild(chunks, iters);
  const tasks = buildFrameTasks(chunks).length;
  console.log(`chunks=${String(chunks).padStart(4)}  tasks=${String(tasks).padStart(4)}  rebuild=${us.toFixed(2)} µs/帧`);
}

frame 0  tasks=7   maxParallel=2  parallelism=[1,2,1,1,1,1]
frame 1  tasks=8   maxParallel=3  parallelism=[1,3,1,1,1,1]
frame 2  tasks=10  maxParallel=5  parallelism=[1,5,1,1,1,1]
frame 3  tasks=10  maxParallel=5  parallelism=[1,5,1,1,1,1]
frame 4  tasks=9   maxParallel=4  parallelism=[1,4,1,1,1,1]

input 0.4 + max(sim-physics 1.8, sim-ai 1.2) + sim-anim 0.9
      + render-list 0.5 + cull 0.7 + submit 0.3 = 4.6 ms

// snippet: 把分层计划派发到线程池（示意，完整实现见第 14 章）
for (const level of plan.levels) {
  // 层内任务互不依赖，可以一起提交。
  const pending = level.map((id) => pool.submit(tasks.get(id)!.run));
  await Promise.all(pending); // 本层全部完成 = 进入下一层前的一道屏障
}