《游戏引擎实现原理》17.3 与 Job System 的对接

// file: src/render/thread/render-jobs.ts
// tier: L1
// verify: npx vitest run src/render/thread/render-jobs.test.ts
//
// helio 渲染卷 17.3：把一帧的绘制项切成若干「录制作业」，分给 Job System 的
// worker 并行录成各自的命令缓冲，再由主线程按顺序合并提交。本节只做两件事：
//   1) 合并的正确性——并行录出的分块合并后必须与单线程顺序录制逐条相等；
//   2) 调度的代价——用一个确定性 list-scheduling 模型算出 makespan。
// 与卷一 14/15 章共用同一套「任务 → 依赖 → 合并」的思路，这里换成渲染命令。

import type { RenderCommand } from './command-buffer.ts';

export interface DrawItem {
  readonly id: number;
  readonly material: number;
  readonly vertexCount: number;
}

/** 单线程顺序录制一批绘制项：材质变化时插一条 setPipeline。 */
export function recordItems(items: readonly DrawItem[]): RenderCommand[] {
  const out: RenderCommand[] = [];
  let current = -1;
  for (const it of items) {
    if (it.material !== current) {
      out.push({ op: 'setPipeline', name: `material-${it.material}` });
      current = it.material;
    }
    out.push({ op: 'setBindGroup', index: 0, name: `bg-${it.id}` });
    out.push({ op: 'draw', vertexCount: it.vertexCount });
  }
  return out;
}

/** 把数组按顺序切成至多 k 个连续分块（前若干块各多 1 个，不丢不重）。 */
export function partitionEvenly<T>(items: readonly T[], k: number): T[][] {
  if (k < 1) throw new RangeError('k 至少为 1');
  const n = items.length;
  const parts = Math.min(k, n);
  const chunks: T[][] = [];
  let start = 0;
  for (let i = 0; i < parts; i++) {
    const size = Math.floor(n / parts) + (i < n % parts ? 1 : 0);
    chunks.push(items.slice(start, start + size));
    start += size;
  }
  return chunks;
}

/** 合并各分块录出的命令：按分块顺序首尾相接。 */
export function mergeCommands(chunks: readonly (readonly RenderCommand[])[]): RenderCommand[] {
  const out: RenderCommand[] = [];
  for (const c of chunks) out.push(...c);
  return out;
}

/**
 * 取出命令流里的绘制序列（draw / setBindGroup）。分块边界可能让相邻两块
 * 各录一次相同的 setPipeline（材质没变也重设一次），这是并行录制的预期开销；
 * 但绘制序列本身必须与单线程顺序录制逐条相等。
 */
export function drawSequence(cmds: readonly RenderCommand[]): RenderCommand[] {
  return cmds.filter((c) => c.op === 'draw' || c.op === 'setBindGroup');
}

/**
 * 模拟「录一个分块」的真实 CPU 成本：逐项算一个打包排序键（多次位运算），
 * 再累加成一个校验和。串行录整帧与分块并行录的校验和必须相等。
 */
export function recordChunkWork(items: readonly DrawItem[], iterations: number): number {
  let acc = 0;
  for (const it of items) {
    let h = (it.id + 1) * 2654435761;
    for (let i = 0; i < iterations; i++) h = (h ^ (h >>> 13)) * 1274126177;
    acc = (acc + (h >>> 0)) % 2147483647;
  }
  return acc;
}

export interface Job {
  readonly id: number;
  readonly cost: number;
}

export interface JobPlacement {
  readonly id: number;
  readonly worker: number;
  readonly start: number;
  readonly end: number;
}

export interface Schedule {
  readonly placements: readonly JobPlacement[];
  readonly makespan: number;
}

/** 确定性 list-scheduling：每个作业放到最早空闲的 worker 上。 */
export function listSchedule(jobs: readonly Job[], workers: number): Schedule {
  if (workers < 1) throw new RangeError('workers 至少为 1');
  const free = new Array<number>(workers).fill(0);
  const placements: JobPlacement[] = [];
  for (const job of jobs) {
    let pick = 0;
    for (let w = 1; w < workers; w++) if (free[w]! < free[pick]!) pick = w;
    const start = free[pick]!;
    const end = start + job.cost;
    free[pick] = end;
    placements.push({ id: job.id, worker: pick, start, end });
  }
  return { placements, makespan: Math.max(0, ...free) };
}

// file: src/render/thread/record-worker.ts
// tier: L1
// verify: node src/render/thread/render-jobs-demo.ts
//
// Job System 的 worker：收到一个绘制项分块与迭代次数，在子线程里「录制」
// 这个分块（算打包排序键），把校验和回传主线程。主线程负责按分块顺序合并。

import { parentPort } from 'node:worker_threads';
import { recordChunkWork, type DrawItem } from './render-jobs.ts';

interface WorkRequest {
  readonly chunk: readonly DrawItem[];
  readonly iterations: number;
}

parentPort?.on('message', (raw: unknown) => {
  const req = raw as WorkRequest;
  const checksum = recordChunkWork(req.chunk, req.iterations);
  parentPort?.postMessage({ checksum });
});

// file: src/render/thread/render-jobs-demo.ts
// tier: L1
// verify: node src/render/thread/render-jobs-demo.ts
//
// 真跑：把一帧的绘制项分成 W 块，用 worker_threads 并行「录制」，与单线程
// 顺序录制对比墙钟耗时。校验和相等说明并行录制没有改变结果；耗时差说明
// 分块并行确实把 CPU 录制的墙钟压了下来。

import { availableParallelism } from 'node:os';
import { performance } from 'node:perf_hooks';
import { Worker } from 'node:worker_threads';
import {
  partitionEvenly, recordChunkWork, type DrawItem,
} from './render-jobs.ts';

const ITEMS = 4096;
const ITERATIONS = 20000;

function makeItems(n: number): DrawItem[] {
  const out: DrawItem[] = [];
  for (let i = 0; i < n; i++) out.push({ id: i, material: i % 7, vertexCount: 3 + (i % 5) });
  return out;
}

function serial(items: readonly DrawItem[]): { ms: number; checksum: number } {
  const t0 = performance.now();
  const checksum = recordChunkWork(items, ITERATIONS);
  return { ms: performance.now() - t0, checksum };
}

async function parallel(items: readonly DrawItem[], workers: number): Promise<{ ms: number; checksum: number }> {
  const chunks = partitionEvenly(items, workers);
  const t0 = performance.now();
  const results = await Promise.all(chunks.map((chunk) => new Promise<number>((resolve, reject) => {
    const w = new Worker(new URL('./record-worker.ts', import.meta.url));
    w.once('message', (m: unknown) => { resolve((m as { checksum: number }).checksum); void w.terminate(); });
    w.once('error', reject);
    w.postMessage({ chunk, iterations: ITERATIONS });
  })));
  const ms = performance.now() - t0;
  const checksum = results.reduce((a, b) => (a + b) % 2147483647, 0);
  return { ms, checksum };
}

const items = makeItems(ITEMS);
const workers = Math.min(4, availableParallelism());
const s = serial(items);
const p = await parallel(items, workers);
console.log(`items=${ITEMS} iterations=${ITERATIONS} workers=${workers}`);
console.log(`serial:   ${s.ms.toFixed(1)} ms  checksum=${s.checksum}`);
console.log(`parallel: ${p.ms.toFixed(1)} ms  checksum=${p.checksum}`);
console.log(`checksum equal: ${s.checksum === p.checksum}`);
console.log(`speedup: ${(s.ms / p.ms).toFixed(2)}x`);

items=4096 iterations=20000 workers=4
serial:   576.4 ms  checksum=359992271
parallel: 212.4 ms  checksum=359992271
checksum equal: true
speedup: 2.71x