13.2 迭代顺序、变更检测与脏标记
13.1 的缓存有个致命前提：世界不变。可游戏世界里每帧都有人在动。如果每次改动都让全部查询、全部变换重算，缓存和层级更新就都成了摆设。这一节解决两件事：让迭代顺序稳定可预测，让重算只发生在真正变了的那部分数据上。
稳定的迭代顺序从哪来
「顺序」看起来是个小问题，但它决定了三件事：模拟是否可复现、缓存是否命中、遍历是否缓存友好。
- 可复现。确定性模拟要求同一份输入永远产出同一份输出。如果每帧的遍历顺序取决于哈希桶的分布或 GC 时机，两次运行的浮点累加次序就会不同，结果慢慢飘开（第 10 章讲过的确定性问题的另一半）。
- 缓存友好。13.1 的
queryUncached直接按Map的插入顺序遍历——只要不删不重加，顺序就稳定；而稀疏集的 dense 数组（6.3）给的是「紧凑且稳定」的顺序，两者都比「每次重新排序」好。 - 拓扑正确。层级结构必须「父先于子」处理，否则子节点会用到过期的父世界变换。做法很简单：父节点总是先于子节点被创建，于是节点数组的插入顺序天然就是拓扑序，不需要每次排序。
| 容器 | 迭代顺序 | 稳定性来源 |
|---|---|---|
Map | 插入顺序 | 只要不删除键，顺序不变 |
| 稀疏集 dense 数组 | 紧凑插入顺序 | swap-remove 只挪动末尾元素 |
| 变换层级节点数组 | 父先于子的拓扑序 | 先建父、后建子 |
本节的层级把节点存在扁平 TypedArray 里，另外维护一个 order 数组记录拓扑序。更新时按 order 一次线性扫描——既保证父先于子，又是连续内存访问。
脏标记：只重算变了的那棵子树
脏标记的核心只有一句话：改动发生时，把受影响的范围标记出来；更新时只处理被标记的部分。
一个变换节点被改动，受影响的只有它自己和它的所有后代——祖先和兄弟都不受影响。所以 setLocal 之后要做的，是从这个节点出发，把整棵子树标脏。updateDirty 再按拓扑序扫一遍，遇到脏节点就重算、清脏，遇到干净节点直接跳过。
这里有个容易被忽略的优化：markDirty 遇到已经脏的节点要立即返回，不再往它的子树下探。因为「子树已脏」意味着里面每个节点都已被标脏，重复下探纯属浪费。正是这条提前返回，让「先标脏子树、再标脏父节点」这类重复操作退化成一次 O(子树) 而不是 O(子树²)。
下面是完整实现，层级 L1，Node 直跑。
// file: src/core/transform-hierarchy.ts
// tier: L1
// verify: npx vitest run src/core/transform-hierarchy.test.ts
//
// 变换层级 + 脏标记：数据用扁平 TypedArray 存（SoA），
// 节点按「父先于子」的拓扑序排列。改动一个节点只把它的子树标脏，
// updateDirty 只重算被标脏的节点；updateAll 则无条件全量重算。
export interface LocalTRS {
tx: number;
ty: number;
rot: number;
scale: number;
}
export class TransformHierarchy {
#parent: Int32Array;
#tx: Float64Array;
#ty: Float64Array;
#rot: Float64Array;
#scale: Float64Array;
#wx: Float64Array;
#wy: Float64Array;
#wrot: Float64Array;
#wscale: Float64Array;
#dirty: Uint8Array;
#children: number[][];
#order: number[] = [];
#count = 0;
#recomputed = 0;
constructor(capacity: number) {
this.#parent = new Int32Array(capacity).fill(-1);
this.#tx = new Float64Array(capacity);
this.#ty = new Float64Array(capacity);
this.#rot = new Float64Array(capacity);
this.#scale = new Float64Array(capacity).fill(1);
this.#wx = new Float64Array(capacity);
this.#wy = new Float64Array(capacity);
this.#wrot = new Float64Array(capacity);
this.#wscale = new Float64Array(capacity).fill(1);
this.#dirty = new Uint8Array(capacity);
this.#children = Array.from({ length: capacity }, () => []);
}
get count(): number {
return this.#count;
}
/** 上一帧真正被重算的节点数。 */
get recomputed(): number {
return this.#recomputed;
}
/** 新增节点，parent 为 -1 表示根。返回节点 id。 */
add(parent: number, local: LocalTRS): number {
const i = this.#count++;
this.#parent[i] = parent;
this.#tx[i] = local.tx;
this.#ty[i] = local.ty;
this.#rot[i] = local.rot;
this.#scale[i] = local.scale;
if (parent >= 0) this.#children[parent].push(i);
this.#order.push(i); // 父先建、子后建 → order 天然是拓扑序
this.#dirty[i] = 1;
return i;
}
/** 设置局部变换并把该节点及其整棵子树标脏（已脏则不再下探）。 */
setLocal(i: number, local: LocalTRS): void {
this.#tx[i] = local.tx;
this.#ty[i] = local.ty;
this.#rot[i] = local.rot;
this.#scale[i] = local.scale;
this.markDirty(i);
}
markDirty(i: number): void {
if (this.#dirty[i] === 1) return; // 子树已脏，无需重复遍历
this.#dirty[i] = 1;
for (const c of this.#children[i]) this.markDirty(c);
}
#recompute(i: number): void {
const p = this.#parent[i];
if (p < 0) {
this.#wx[i] = this.#tx[i];
this.#wy[i] = this.#ty[i];
this.#wrot[i] = this.#rot[i];
this.#wscale[i] = this.#scale[i];
} else {
const c = Math.cos(this.#wrot[p]);
const s = Math.sin(this.#wrot[p]);
const ps = this.#wscale[p];
const lx = this.#tx[i] * ps;
const ly = this.#ty[i] * ps;
this.#wx[i] = this.#wx[p] + lx * c - ly * s;
this.#wy[i] = this.#wy[p] + lx * s + ly * c;
this.#wrot[i] = this.#wrot[p] + this.#rot[i];
this.#wscale[i] = ps * this.#scale[i];
}
this.#dirty[i] = 0;
this.#recomputed++;
}
/** 只重算被标脏的节点，按拓扑序一次扫描。 */
updateDirty(): void {
this.#recomputed = 0;
for (const i of this.#order) {
if (this.#dirty[i] === 1) this.#recompute(i);
}
}
/** 无条件全量重算。 */
updateAll(): void {
this.#recomputed = 0;
for (const i of this.#order) this.#recompute(i);
}
world(i: number): [number, number, number, number] {
return [this.#wx[i], this.#wy[i], this.#wrot[i], this.#wscale[i]];
}
isDirty(i: number): boolean {
return this.#dirty[i] === 1;
}
order(): readonly number[] {
return this.#order;
}
}
注意 updateDirty 和 updateAll 用的是同一段重算逻辑，区别只在「要不要检查脏位」。这让「全量」成为「脏标记」的一个退化解——脏标记不是另一套代码路径，只是给全量扫描加了一个廉价的跳过判断。
可运行产物：全量重算 vs 脏标记实测
基准脚本建一棵 10000 节点的 4 叉树，跑 1000 帧。每帧改 20 个叶子节点，然后对比两种更新方式。核心循环：
// snippet: bench/dirty-flag-bench.ts（节选）
function runFull(): number {
const h = build();
const t0 = performance.now();
for (let f = 0; f < FRAMES; f++) {
h.updateAll();
}
sink += h.recomputed;
return performance.now() - t0;
}
function runDirtyLeaf(leaves: number[]): { ms: number; recomputed: number } {
const h = build();
let seed = 99;
const t0 = performance.now();
let total = 0;
for (let f = 0; f < FRAMES; f++) {
for (let k = 0; k < CHANGES; k++) {
seed = (seed * 1103515245 + 12345) & 0x7fffffff;
const id = leaves[seed % leaves.length]!;
h.setLocal(id, { tx: 1 + (f % 7) * 0.001, ty: 0, rot: 0.01, scale: 1 });
}
h.updateDirty();
total += h.recomputed;
}
sink += total;
return { ms: performance.now() - t0, recomputed: total };
}
本机（Node 26.5.0）实跑，取 7 次重复的中位数：
N = 10000 nodes, FRAMES = 1000, CHANGES/frame = 20, leaves = 7500
[A leaf] full 193.63 ms
[A leaf] dirty 10.93 ms
[A leaf] speedup 17.71x
[A leaf] recomputed total = 19886 (full would be 10000000)
[B root] dirty 280.26 ms, recomputed total = 10000000
改叶子的场景：全量 1000 帧重算 1000 万次，脏标记只重算了 19886 次——因为 20 个叶子都没有后代，markDirty 只标记它们自己。重算次数差了 500 倍，耗时差 17.71 倍（差额来自脏标记的遍历与判断开销）。方向的结论是稳的：改动越局部，脏标记越省。
但第二条数据同样重要：如果每帧改的是根节点，整棵树都是它的子树，脏标记要重算全部 1000 万次，还要额外付出标记遍历的代价，于是 280.26 ms 比全量还慢。这戳破了一个常见的误读——脏标记不是「一定更快」，它只在改动范围小于全量时才划算。工程上要判断的是「典型帧里改动的节点占比」：小于三成，脏标记就基本稳赢；接近全量，就该老实全量重算。
测试：脏标记只重算子树
// snippet: src/core/transform-hierarchy.test.ts（节选）
it('脏标记只重算子树：改一个叶子只重算 1 个节点', () => {
const h = new TransformHierarchy(16);
const root = h.add(-1, L(0, 0));
const mid = h.add(root, L(1, 0));
const leaf = h.add(mid, L(1, 0));
h.updateAll(); // 清脏
h.setLocal(leaf, L(2, 0));
h.updateDirty();
expect(h.recomputed).toBe(1); // 只有 leaf
});
it('改父节点会重算整棵子树', () => {
const h = new TransformHierarchy(16);
const root = h.add(-1, L(0, 0));
const a = h.add(root, L(1, 0));
const b = h.add(root, L(2, 0));
const c = h.add(a, L(1, 0));
h.updateAll();
h.setLocal(root, L(5, 0));
h.updateDirty();
expect(h.recomputed).toBe(4); // root + a + b + c
});
npx vitest run src/core/transform-hierarchy.test.ts 全部通过（6 个用例）。用例直接断言 recomputed 的数值，把「只重算子树」这条性质变成了可回归的约束——一旦有人把 markDirty 的提前返回删掉，或用 updateAll 顶替 updateDirty，测试立刻红。
常见坑
- 忘记给新节点标脏。
add必须把新节点标脏，否则它第一次updateDirty会保持世界变换为 0。 markDirty不提前返回。子树反复被标脏时，重复下探会让传播从 O(子树) 退化成 O(子树²)。- 只标自己、不标后代。父节点变了后代却没标脏，后代就会用到过期的父世界变换——这是层级动画里最典型的「子物体跟不上」bug。
- 在遍历中改结构。
updateDirty扫order时如果插入/删除节点，order会错位；结构改动应放到帧边界之外。 - 把脏标记当万能药。改动覆盖大半棵树时它比全量还慢；别不看数据就上。
13.3 把「谁先谁后」这件事再推进一步：系统之间不是靠遍历顺序，而是靠声明的读写依赖自动排出并行分组。
阅读导航：上一节：13.1 查询匹配与缓存命中 · 下一节：13.3 系统依赖声明与并行调度 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。