游戏对象并发更新

并发的引擎子系统

渲染、动画、音频、物理这些对性能最关键的部分最能受益于并行处理；无论对象模型单线程还是多核更新，都要能与多线程的底层系统交互（卷 II 17.7.1）。

• 有通用作业系统（卷 I 8.6.4，见 作业系统）时，每个子系统每帧可以作为一个作业启动；更好的是每个子系统启动多个作业，例如动画系统为每个需要动画混合的对象启动一个作业，之后计算世界矩阵和蒙皮矩阵时再用分散/汇集分给可用的核。
• 子系统接口必须线程安全，外部客户之间、客户与子系统内部都不能发生数据竞争，通常要给所有外部调用加锁。
• 作业系统用用户级线程（协程或纤程）时要用自旋锁；子系统由 OS 线程更新时互斥锁也可行（见 线程同步原语、进程、线程与纤程）。
• 如果确定某子系统只在游戏循环的某个阶段运行，可以用**"无需加锁"断言**代替真正加锁（卷 I 4.9.7.5）。
• 也可以用无锁数据结构实现关键共享数据，但很难实现，有些数据结构至今没有已知的无锁实现，所以最好只用于性能要求最严苛的子系统（见 无锁编程与内存序）。

异步程序设计

与并发子系统交互时应避免阻塞函数（在调用线程上下文中直接完成工作，阻塞该线程或作业直到完成）；尽量调用非阻塞函数，把请求交给另一个线程、核或处理器执行并立即返回，调用方继续做无关工作（比如更新其他对象），同一帧稍后或下一帧再取结果（卷 II 17.7.2）。以判断玩家与敌人之间是否有视线的射线检测为例：

// 同步：立即得到结果
RayCastResult r = castRay(playerPos, enemyPos);
if (r.hitSomething() && isEnemy(r.getHitObject())) { /* 玩家看到了敌人 */ }

// 异步：同一帧内发起、稍后等待
RayCastResult r;
requestRayCast(playerPos, enemyPos, &r);
// ……做其他无关工作……
waitForRayCastResults(&r);   // 已完成则立即返回，否则主线程空等
if (r.hitSomething() && isEnemy(r.getHitObject())) { /* ... */ }

// 跨帧：取上一帧的结果，再为下一帧发起新请求
RayCastResult r; bool rayJobPending = false;
SomeGameObject::Update() {
    if (rayJobPending) {
        waitForRayCastResults(&r);
        if (r.hitSomething() && isEnemy(r.getHitObject())) { /* ... */ }
    }
    rayJobPending = true;
    requestRayCast(playerPos, enemyPos, &r);
}

何时发起、何时取结果（卷 II 17.7.2.1）：

• 最早能多早发起？ 越早发起，需要时越可能已完成，主线程越不会空等。对每个请求找出帧内已有足够信息的最早时刻，在那里发起。
• 最晚能多晚用结果？ 也许可以把操作的后半段挪到更新循环后面；也许能容忍一帧延迟，用上一帧结果更新本帧状态（AI 等每几秒才更新的子系统能容忍更长延迟）。稍加思考、重构代码、再缓存些中间数据，很多使用结果的代码都能推迟到帧的后面。

作业依赖与并行度

游戏循环的每次迭代可能有成百上千个并发作业，作业间的依赖会降低核的利用率：B 以 A 产出的数据为输入，就必须等 A 完成（卷 II 17.7.3）。

• 并行度 (degree of parallelism, DOP)，也叫并发度 (DOC)：任一时刻理论上最多能并行运行的作业数。画出依赖图（作业为节点，父子关系为依赖），GEA 说树的叶子数就是这组作业的 DOP（图 17.17 给出 DOP 为 4、1、6 的三棵树）。
• DOP 恰好等于核数时吞吐量最大；大于核数时有些作业要串行，吞吐量下降但没有核闲着；小于核数时有些核无事可做。
• 同步点 (sync point)：作业被迫等待依赖的作业完成时就产生同步点，每个同步点都可能浪费 CPU（图 17.18：D 依赖 C，F 依赖 A、B、D、E）。
• 对策：减少依赖以提高 DOP；在空闲期找其他无关工作；推迟同步点：D 依赖 A、B、C，若紧接着 C 调度 D，核 2 会空等 B；把 D 推迟到 A、B、C 都完成很久之后再运行，核 2 就能先跑别的作业，D 也不必等待（图 17.19）。Mike Acton 在演讲 "Diving Down the Concurrency Rabbit Hole" 中说："优化并发设计的秘诀是延迟。"

注：GEA 用"依赖树的叶子数"定义 DOP，对树形依赖成立；但它紧接着给出的图 17.18 里 F 同时依赖 A、B、D、E，已经不是树而是一般的有向无环图，此时不能直接数叶子，需要看图中能同时运行的最大作业集合。在偏序/DAG 理论里，能同时运行的最大作业集合是"最大反链"，其大小称为 DAG 的宽度（Dilworth 定理，见 Wikipedia "Dilworth's theorem"）；对树而言最大反链恰好就是全部叶子，所以 GEA 的说法是这一一般定义在树上的特例。阅读时注意适用范围。

并行化对象模型本身

对象模型出了名地难以并行：对象之间高度相互依赖，又依赖众多子系统；它们在更新中多次通信、互查状态，通信模式难以预测，并且对玩家输入和世界中发生的事件高度敏感（卷 II 17.7.4）。但并非不可能：Naughty Dog 在为《最后生还者 重制版》把引擎从 PS3 移植到 PS4 时实现了并发对象模型。GEA 强调这些只是一种方案，其他引擎可能不同。

对象更新即作业（卷 II 17.7.4.1）：把所有对象分成 N 个桶，使桶 B 中的对象只依赖桶 0 到 B − 1 中的对象（分桶思想见 游戏对象的实时更新），然后把每个桶内的对象更新作为作业启动，由作业系统调度到各个核上（并与其他正在运行的作业穿插），这大致就是 Naughty Dog 引擎的做法：

void UpdateBucket(int iBucket) {
    job::Declaration aDecl[kMaxObjectsPerBucket];
    const int count = GetNumObjectsInBucket(iBucket);
    for (int jObject = 0; jObject < count; ++jObject) {
        job::Declaration& decl = aDecl[jObject];
        decl.m_pEntryPoint = UpdateGameObjectJob;
        decl.m_param = reinterpret_cast<uintptr_t>(GetGameObjectInBucket(iBucket, jObject));
    }
    job::KickJobsAndWait(aDecl, count);
}

原书问题：已核对排版页卷 II p.610，原书这段代码的 for 循环体确实没有花括号（只靠缩进表示循环体）。按 C++ 语法，for 的循环体只是紧随其后的一条语句（cppreference "for loop"），所以只有 job::Declaration& decl = aDecl[jObject]; 在循环里，后面两行引用的 decl 已出了作用域，照抄无法编译。上面的代码按作者意图补上了花括号。

另一种做法是显式声明依赖（如 A 依赖 B、C、D），形成有向图：先为没有依赖的对象启动更新作业，每个作业完成后走到依赖它的对象，等它所依赖的对象全部完成再启动，直到整张图更新完。若图中有环，相关对象不能简单按依赖顺序更新：要么改变对象交互方式消除环、使图成为有向无环图 (DAG)，要么把这些循环依赖的"团块"隔离出来，在单个核上串行更新。

异步对象更新（卷 II 17.7.4.2）：对象自身并发更新时，异步请求照样适用。若作业系统基于用户级线程（协程或纤程），阻塞调用也重新可行：协程能让出并在之后从原处继续；Naughty Dog 的纤程作业不是协程，但同样能在执行中途"睡眠"、之后被"唤醒"继续。

SomeGameObject::Update() {
    RayCastResult r = castRayAndWait(playerPos, enemyPos);  // zzz……结果就绪时醒来
    if (r.hitSomething() && isEnemy(r.getHitObject())) { /* ... */ }
}

这看起来几乎和前面"不要这样做"的同步写法一样，但作业实际被劈成射线调用前后两段（图 17.20）。作业系统的 WaitForCounter()、KickJobsAndWait() 正是靠这种机制让作业睡眠、在计数器归零前让其他作业运行（见 作业系统 的作业计数器一节）。

原书问题：原文写作 "WaitForCounter() KickJobsAndWait()"，两个函数名之间漏了 "and"（已核对排版页卷 II p.612）。另外本节开头（p.611）说"我们在 17.7.1 节说过对象更新通常是异步的"，但异步请求的讨论实际在 17.7.2 节。

对象更新中的加锁

分桶保证了正确的全局更新顺序（例如火车车厢先于坐在上面的对象更新），也有助于对象间状态查询：桶 B 中的对象可以安全查询桶 B − Δ 和 B + Δ（Δ > 0）中的对象，因为它们不会与桶 B 并发更新，跨桶访问不需要任何锁。但仍有一帧问题：第 N 帧查询 B − Δ 看到的是第 N 帧状态，查询 B + Δ 看到的是第 N − 1 帧状态（卷 II 17.7.4.3）。

同一桶内的对象互相交互或查询时又会有竞争条件：

• 单一全局锁：每个对象获取锁、更新、释放，能保证没有数据竞争，但会把桶内所有对象的更新串行化，即使两个对象毫无交互，"并发"更新实际退化为单线程。
• 解引用句柄时才加锁：Naughty Dog 早期尝试过。他们的引擎用句柄而不是裸指针引用对象，以支持内存碎片整理（见 游戏对象引用与查询），要拿到裸指针必须先解引用句柄，这正是检测"一个对象打算与另一个交互"的时机。只在交互可能发生时加锁恢复了一定的并发度，但这套锁系统复杂、难用，桶更新期间 CPU 核的利用率仍然不高。

对象快照

分析真实引擎中的对象依赖后发现：对象间的绝大多数交互是状态查询，A 只需要 B、C 的状态的只读副本，不需要与这些（可能正在并发更新的）对象本身交互。于是让每个对象提供一份相关状态的快照 (snapshot)，任何对象都可以无锁、无数据竞争地查询。快照其实就是状态缓存的一个实例。Naughty Dog 在《最后生还者 重制版》《神秘海域 4：盗贼末路》《神秘海域：失落的遗产》《最后生还者 第二部》中使用了这种方法（卷 II 17.7.4.4）。

Naughty Dog 引擎中的流程：每个桶更新开始时，让每个对象更新快照；这些更新从不查询其他对象，所以能无锁并发运行。全部完成后，再启动并发作业更新对象的内部状态。桶 B 中的对象查询其他对象时：

1. 查询桶 B − Δ 中的对象：可以直接查对象，也可以查快照；
2. 查询桶 B 中的对象：查快照；
3. 查询桶 B + Δ 中的对象：同样可以查对象本身或快照。

sequenceDiagram
  participant S as 桶 B 开始
  participant SN as 快照更新作业（并发、不互查）
  participant U as 对象更新作业（并发）
  S->>SN: 每个对象更新自己的快照
  SN-->>S: 全部完成
  S->>U: 启动对象内部状态更新
  U->>U: 读同桶对象只读快照；跨桶可直接读对象
  U-->>S: 桶 B 完成（同步点），进入桶 B+1

上图按时间顺序表示一个桶内两轮并发作业之间的关系。

处理对象间的修改

快照只解决读取，不解决同桶内一个对象修改另一个对象状态时的数据竞争。Naughty Dog 结合使用以下经验规则和技术（卷 II 17.7.4.5）：

• 尽可能减少对象间修改；
• 跨桶的对象间修改是安全的；
• 桶内的对象间修改必须小心处理：要么加锁；要么把修改请求放进请求队列而不是立即应用，队列本身由锁保护，请求在桶更新完成后再处理（延迟处理的思路见 事件队列）；
• 在下一个桶中生成一个专门同步这些修改操作的作业：推迟到后面的桶，就能确定相关对象已完成更新、不会与这项工作并发。Naughty Dog 用它处理玩家与 NPC 之间同步的近战动作。

不足与改进方向

GEA 坦言这套系统远非完美（卷 II 17.7.4.6）：

• 每次桶切换都给游戏循环引入一个同步点，部分核可能闲着等桶内所有对象完成；
• 快照只处理只读查询，对象间修改仍需加锁；快照本身更新也可能很贵，一个容易实施的优化是只为需要的对象生成快照。

GEA 认为找到并发更新对象的最佳方法要靠实验。

与 UE5 的对照

• UE 的 Tick 依赖只给真正相关的对象设先后关系，同一 Tick 组内其他对象仍可并行更新，官方明确说这比把一批对象挪到更晚的组更高效，见 委托与 Tick 机制；这与 GEA "显式声明依赖、减少同步点"的方向一致（对比归纳）。
• UE 的通用任务并行见 任务系统；MassEntity 数据导向框架 用无状态处理器批量处理片段，从数据布局上回避了"对象互相查询"的问题，这是另一条路线（对比归纳）。