最快的代码，是不运行的代码

前言

当性能是一项特性时，缓慢就是一个 Bug。找到缓慢的源头就像是追踪 Bug，一旦你找到缓慢代码，通常有三种方式可以加速代码：

让内部循环运行更快。这包括了缓存优化、减少分支和优化SIMD。
用更多的处理器运行内部循环。在多个处理器的多个内核，或是多台机器上共同运行。
减少内部循环运行次数。这包括了从早期测试到算法革新的一系列手段来改善计算复杂度（big-O）。

故事是关于内部循环已经高度优化，并且也同步运行了，但是一些列严重的设计缺陷使得系统运行远慢于预期。

背景

2014年初，我在箭头游戏工作室工作，当时我们打算重新启动经典的街机游戏Gauntlet。事件发生在我们打算首次公布该游戏的前一周。我们想要让玩家可以任意选择游戏关卡，最后一周里大家都忙于修复漏洞、改善游戏设置，以及提升视觉效果。看起来一切顺利，但是最后一周出现了一些情况：帧率从预期的60FPS下降到了20-25FPS的龟速。这引起了极大的恐慌。哪里出错了？我们还有时间修复吗？

调查

我们马上把怀疑方向转向了三维场景的光照。近期刚增加了大量的全方位阴影投射灯，光影效果的开销从来都是比较大的。

Gauntlet的开发利用了第三方BitSquid引擎（原名叫StingRay）。我们用阴影贴图来使用一个延迟着色管线。这篇博客就不详细阐述阴影贴图的工作原理了，不过这里是一个简短的概述，可以看出在BitSquid中如何完成全方面的阴影映射：

每个全向光模拟为六个聚光灯走向的正负x、y、z轴。对于每个“虚拟聚光灯”，引擎会把附近的几何图形呈现在阴影贴图上，这是一个屏幕外的缓冲区，包含了从灯光到最近几何图形的距离。这些阴影贴图之后会被用来确定场景中的各个像素是否需要被阴影投射所遮挡。

关掉阴影上的所有投射灯之后确实让帧率重回60FPSl ,但是这也破坏了这个游戏的整体感觉。在最后的两天里，我决定追查问题的来源。

我开始尝试改动阴影贴图设置。尤其是，我将分辨率从1024² 大幅地调整到了16²。这不会对帧率速度造成任何影响。这一点提醒了我，有一些地方出了大错。在加强游戏内部探查器之后我发现了罪魁祸首：阴影投射的剔除。

问题

在绘制阴影贴图的时候，我们不能只是简单地把所有的几何图形发送给渲染器，因为这可能会导致阴影贴图渲染速度非常低。相反的，渲染器会首先剔除掉几何图形。就是这种剔除过程耗时太长。事实上，这会耗费长达25毫秒！我们为一个帧率稳定在60 FPS 的游戏，每帧的预算为16ms。这16毫秒里需要做所有事：游戏逻辑、物理模拟、阴影渲染、场景渲染、场景照明和后期处理等。16毫秒来做这一切，而现在光做一件事就需要25毫秒。该死的！

这是在周三发现的。周五我们就要让最终版本开始运行。在周四早上我做出了一个大胆的承诺：今天结束的时候，帧率会加倍。然后我就去上班了。

值得庆幸的是，我们拥有BitSquid的源代码许可证，我习惯于优化引擎并修复漏洞。看了这些代码之后发现BitSquid单纯地把所有的几何图形在整体水平上进行剔除，在每一次的阴影投射聚光灯和每六次的全方位灯光时进行。此外，这种剔除是通过耗时的OBB（面向定界框）和锥测试的斗争中完成的。这就意味着在水平上有N个几何图形和L个全方位灯，就会有N*L*6个OBB-锥测试。就是这些测试花费了25毫秒。很显然，BitSquid已经有人意识到这部分代码可能变成一个瓶颈，因为这样的OBB-锥测试是SIMD优化的，并且在数个工作路线中并行处理。这也意味着我不可以让这些代码运行的更快，或是用更多的处理器去运行它。所以我只剩下了唯一一条路：让代码少运行几次。

解决方案

我只剩下一天时间来提高性能了，所以我采取的方法都对引擎（我只是大概了解的）产生了最小的改变。

早期

BitSquid的所有几何图形都有一个已经预先计算好的OBB包围盒，但是OBB测试总是很慢。我决定在每一个几何图形和接口上增加一个很粗糙、但是运行更快的原始定界框：一个球体。测试彼此排斥的两个球体开销要小得多，这在很大程度上让我们免于耗时的OBB测试，也节省了大量时间。然而，我还没有时间去修改引擎和所有的工具，来为每个几何图形增加一个预先计算好的最小包围球。相反的，我决定来计算从OBB出来的最小包围半径。这个长宽高分别为W、H、D的包围盒外包围球的最小半径是 √((W/2)² + (H/2)² + (D/2)²), 但是这个平方根有点大。所以我决定让这个包围球稍微大一点，计算后得出半径为√3/2 * max(W, H, D)（其中√3/2可以重复使用）。

我还计算出所有灯光的包围球，这对于全方位投影灯来说当然微不足道，但是对聚光灯来说这也稍显复杂，但是我想到了一个快速逼近的办法，不过还没有想出具体的细节。

预先计算一组潜在的阴影投射

把遥远的几何图形送去剔除完全是在浪费时间。大多数的游戏引擎都在某种形式的层次结构（如BSP）中存储游戏关卡，这使得引擎能大段大段地远距离剔除。BitSquid却没有这样的功能，我也没有时间在一天之内加上这样一个结构。所以我在帧的开头添加了额外的步骤，这样我就可以在所有相交的相机阴影投射灯周围加上边界框。这形成了一个包含一切的边界框，这就可以在我们的视野范围内投射一个接口。然后，我就可以预先剔除拥有这个边界框场景中的一切，从而选出一组潜在的阴影投射。这就意味着，在之后的剔除过程中，我们只需要测试该场景中的几何图形，而不是所有的。

把全向光看作一个整体

如前所述，BitSquid把每个全向光看做六个聚光灯，并且单独为每个聚光灯进行剔除。我增加了一个预处理，在那我剔除潜在阴影投射中每一个有包围球的泛光灯，从而挑选出靠近泛光灯的几何图形。只有通过这项粗略测试之后，我才会把这些几何图形发送去进一步测试，也就是使用原始的OBB-锥测试代码对六个虚拟聚光灯进行的测试。