转载

DOOM3 技术点滴

今天下午读到一组 DOOM 3 相关的技术文章，这些文章描述的是十年前 (2006) 的技术，但依然有较强的参考价值。其中的一份技术记录描述了 DOOM3 BFG 开发过程中遇到的一些特定的性能问题。

这里的记录和描述非常简略和仓促，更详细的解释可参考原文。

[注] DOOM3 BFG 是 DOOM3 的全平台资料片。

DOOM3 技术点滴

技术背景

DOOM3 在发售时 (2004) 的性能状况是，在最低配的机器上效果全关 640*480 的情况下维持在 20fps，而资料片 DOOM 3 BFG 的目标是在 2012 年的机器上 1280*720 下平稳地地运行在 60 fps 上，这意味着使用原版的 1/3 的时间绘制 3 倍于原版的像素数量。

硬件变化上，这些年中 CPU 频率变化不大，但多核化使得多线程能够更有效率 (而 DOOM3 原版是单线程)；GPU 发展很快，使用新功能来优化特定的渲染特性 (比如用 coarse Z-Cull / Hierarchical-Z 来优化 Stencil Shadow Volumes)就很重要；内存的性能提高不大，导致单次内存访问对应的可执行指令数提高了，利用这一点可以做很多对应的优化。

内存约束

从 DOOM3 到 DOOM3 BFG 的一大困扰是缓存颠簸 ( cache thrashing )，由于 DOOM 的光影模型及由此导致的特殊的内存访问模式，使得内存带宽问题一直比较严重。

DOOM3 通常会惰性地对“可能不需要的运算”做尽可能的延迟，这就需要在代码中用一些特定的标记来保存状态信息 (某一样东西算过没有，是否需要重算，等等) 而对多核更友好的则是现在比较流行的流式编程模型 (streaming programming model) ([注]也是曾提到的向无状态的 functional 的思维转换)。

角色的可见部分和阴影体 (visible meshes and shadow volumes) 的蒙皮都在 GPU 上完成，这些 GPU 上的顶点避免了运行时拷贝。而 CPU 这边也同样需要动态生成的索引来生成角色的 shadow volume 及 light volume 内的部分，这个动态的数据量还是挺大的，在 Mars City 1 的过场中，每帧 shadow volume / light culling 的数据需求在 6MB 左右，数据生成在 2.5MB 左右。这里生成的索引使用了合并写 ( write-combined buffer ) 由于这些线程存在不同线程内不同时序的读，很容易造成大量的缓存颠簸。这种颠簸的结果是，即使在使用了流式模型的 x86 上，也很难达到与 Cell SPU 处理器 (PS3) 匹配的吞吐量。这类读取使用了 SSE4.1 的一个指令 _mm_stream_load_si128() 来在合并写上尽可能地做合并读而不经过缓存。虽然合并写及其上的读取被认为是效率低下，但好在这里都是静态数据（也就是仅写入一次）。

用即时运算替代“预计算+存储”

在首节末尾提到，CPU和内存演化速率不同是可以被利用的。这里用蒙皮来做一个非常典型的实例。在原版 DOOM3 里每个角色每帧只蒙一次皮，运算结果存下来给需要的场合用（构建 shadow volume 和渲染）；而 DOOM3 BFG 内同一个角色在一帧内可能会蒙皮多次，仅仅是因为这样做速度更快。(在 GPU 上) 对一个 mesh 蒙皮的运算开销已经小于从内存中读取“未蒙皮版”的源数据的开销了。也就是说， 每次都即时蒙皮的开销并不比去内存里读已蒙皮的数据高 了。更何况还有如下几个巨大的优势：

如果是用于渲染的话，读取和蒙皮都发生在 GPU 上，不需要通过总线，能获得较大的总线带宽节省
未蒙皮的源数据可以所有相同的模型共享一份，而蒙过皮的话是每个角色都得存一份，内存开销是 1:n，能获得较大内存带宽的节省
在多线程读的情况下，读同样的数据可以降低缓存颠簸的几率

DOOM3 BFG 的 shadow volume 本质上是一组(针对未蒙皮数据即时生成的)索引。举个例子，如果一个蒙皮角色与两个投影光源交互，就会做 7 次蒙皮：2*2 次分别是两个 shadow volumes 的生成和渲染；1 次是正常的渲染，剩下两次是两个 light surfaces 的渲染。由于前面提到的诸多原因，7 次蒙皮的性能比 DOOM3 原版的 1 次蒙皮后到处使用还要高，而且随着时间的推移，优势还会被进一步放大。

这再一次凸显了 functional 的潜在巨大优势（跟直觉相反，即使考虑较大数据量，无状态仍然是更优的）而且由于不再维护一个 skinned version，代码更清晰和易懂了，理解和调试的成本降低许多。无状态也使得很多操作（如 shadow volumes 的构建）可以完全并行化。（关于 id 在 functional programming 的实践上更多的细节看这里(John Carmack: In-depth: Functional programming in C++) ）

内存-缓存友好的数据结构

这里总得来说是把之前实现的一些要么冗余，要么 cache-unfriendly 的一些数据结构改写为对缓存更友好的版本。总得来说其实我不太理解为啥在原始版本中很多可以用数组的地方需要用链表，而文中也一再表示所谓改好了的 'idList' 本质上也就是 resizable heap array（跟 vector 区别不大了）

结语

最重要的几句话，可以直接摘录了：

if these threads touch a significant amount of memory then cache thrashing may occur while many CPUs are poorly equipped to avoid large scale cache pollution. Without additional instructions to manage or bypass the cache, a shared cache between all CPU cores can result in less than ideal performance .
various data structures that exhibit poor performance on today's hardware. These data structures tend to result in poor memory access patterns and excessive cache misses .

其它技术点

Slerping Clock Cycles 这一篇描述了怎么使用 SSE 来对两个四元数做平滑的 Slerp (球面线性插值) （最近对 Unity 项目做优化的时候发现 Unity 的对应函数实在是效率不高，很想翻出来自己实现一把，转念一想跨平台的巨坑赶紧忍住了）
From Quaternion to Matrix and Back 用 SSE 来优化四元数和矩阵互转的数学运算
Fast Skinning 依然是用 SSE 来优化 CPU 上的蒙皮

这几篇都是附代码的，顺便说一下，这些汇编代码非常清晰，连我这种汇编苦手都能基本看清脉络（主要是很久以前用 SSE2 实现过矩阵的基础运算），很适合用来熟悉 Intel SSE 指令集。