国外开发者谈游戏中的随机动作优化，以《英雄联盟》为例

在游戏开发中，优化工作通常分为以下几个关键步骤：首先是通过性能分析（Profile）确定游戏中常见的问题；接着进行分析（Analyze），明确性能优化的方向；最后尝试解决（Solve）这些问题。

在开发过程中，游戏开发者往往面对的是持续演进的软件产品，例如《英雄联盟》（League of Legends，以下简称LOL，由美国Riot游戏公司开发的3D大型竞技场网游）。随着剧情的推进，游戏内部的有限状态机不断添加新内容。新内容不仅使逻辑实现更加复杂，还因增加纹理绘制和仿真计算，导致内存消耗上升和性能下降。若忽视这些问题或实现过程中出现错误，将损害游戏运行性能，降低玩家体验。游戏动画中的任何延迟或阻塞，都会让玩家感到沮丧。

我所在的团队致力于改善LOL的性能。我们通过测试游戏的客户端和服务器端，找出影响性能的代码并加以改进。同时，将研究成果反馈给其他团队，并提供分析工具和测量指标，帮助他们尽早发现性能问题。我们持续提升LOL的性能，为游戏情节设计师和艺术家们创造更多空间，添加更有趣的新元素。我们的目标是让游戏运行得更快，而他们的工作是让游戏更具趣味性。

这是系列文章的第一篇，将介绍我们的团队如何在游戏内容不断增加的情况下优化游戏运行速度。这是一项极具挑战性的任务。本文将深入探讨在提高游戏粒子系统（particle system）性能时遇到的有趣问题，以下动画展示了粒子系统在游戏软件中的重要作用。

LOL游戏中高密度粒子运动动画场景的例子

优化并非简单地重写代码，虽然有时确实需要这样做。我们修改代码的目的不仅是提升性能，还要确保代码的正确性，并尽可能提高其可维护性。可维护性至关重要，因为可读性和可维护性差的代码会给项目带来潜在问题。

优化现有代码时，我们遵循三个基本步骤：识别、理解和迭代。

第一步：识别

在进行优化之前，我们需要确认代码是否真的需要优化。有些代码看似运行效率低，但如果对系统整体性能影响极小，就无需浪费精力修改。我们借助代码分析工具和测试样本来识别低效代码。

第二步：理解

一旦识别出低效代码，我们会深入研究，了解其具体功能和原始设计意图，从而找出代码成为瓶颈的原因。

第三步：迭代

当我们了解代码低效的原因和目的后，就可以设计并实现可能的解决方案。利用第一步中使用的分析工具和样本数据，对比新代码和老代码的性能。如果新解决方案足够快，且经过全面测试未引入新错误，我们就为进一步的内部测试做好了准备。若新改动未显著提升性能，我们会不断迭代解决方案，直至达到理想效果。

下面以我最近对LOL粒子系统的优化工作为例，详细介绍这一过程。

第一步：识别

Riot公司（著名的Riot Games，美国网游开发商，成立于2006年，代表作品LOL《英雄联盟》，2011年被腾讯收购）的工程师们使用各种分析工具检查游戏客户端和服务器的性能。其中一款名为Waffles的内部分析工具，可通过有选择地测试指定函数，检查客户端的帧刷新速度，并提供图形化分析数据。Waffles还可用于触发调试事件、检查游戏数据（如导航网格），以及暂停或减慢游戏运行。

Waffles

Waffles能动态显示详细的性能信息。上图展示了客户端性能数据，上方的绿色竖条表示采样点的帧速（单位为毫秒），竖条越长，帧速越慢。游戏中帧速异常慢的点被称为“结点”（hitches）。绿色竖条下方是对应采样点的函数调用详细信息，以层次结构展示。点击任意绿色竖条，可查看该采样点的详细信息，从而直观了解哪些代码块影响了整体运行效率。

在代码（本文作者使用的编程语言应为C++）中，我们定义了一个简单的宏，用于提取代码中重要函数的运行时性能参数。在正式发布版本中，该宏不起作用；但在内部调试版本中，它会构造一个小类，函数调用时创建该类对象，该对象会生成一条消息并输出到缓存中，用于事后分析。消息通常包含字符串标识符、线程号、时间戳以及其他必要信息（如函数执行过程中分配的内存大小）。对象超出作用范围后，其析构函数会计算对象生存时长，并更新到缓存中。缓存数据可由另一个进程导出，以尽量减少对游戏运行的影响。

基于Chrome的可视化跟踪分析插件

在本例中，缓存内容将被导出为JSON格式的文件，可导入到集成在Chrome浏览器中的可视化跟踪工具中。（你可以在Chrome浏览器中输入“chrome://tracing/”试用该工具。）该图形化分析工具可帮助我们找出运行较慢的函数，或发现大量小函数连续调用的情况（连续大量小函数调用会导致频繁的函数压栈和出栈，降低CPU运行效率），这两种情况都需要优化。

下面介绍该工具的使用方法：上图是Chrome中显示的跟踪视图，展示了客户端运行的两个线程，上方是主线程，负责主要处理逻辑；下方是粒子线程，用于粒子处理。每个彩条代表一个函数，彩条长度表示函数执行时间。函数调用关系通过彩条上下位置表示，调用函数位于被调用函数上方。这种展示方式清晰呈现了函数执行调用的复杂关系和执行时间。当我们怀疑某段代码存在问题时，可放大特定区域查看更多细节。

放大后的跟踪显示

放大图的中间部分，观察主线程，可看到一个漫长的等待“Wait”过程，其结束位置对应下方线程中Simulate函数的结束点。Simulate函数包含大量不同的函数调用（见Simulate色带下方的彩色栏），这些函数是粒子系统的更新函数，用于更新每个粒子对象的位置、方向和其他显示特征。一种明显的优化方法是使用多线程实现Simulate函数，但本文主要关注优化Simulate函数的代码本身。

找到影响性能的大致区域后，我们可以使用采样分析方法更准确地定位性能改进点。该方法周期性读取程序计数器（program counter）的内容并记录，甚至访问运行中的进程栈。经过一段时间运行，统计信息可大致勾勒出代码中指令运行的随机过程状态（即通过查看PC统计程序运行中某些指令的执行频度，或通过查看程序栈了解函数调用情况）。对于运行较慢的函数，由于停留时间长，采样结果更多出现在这些函数中。该方法还适用于指令级别，可检测出消耗时间较长的指令段。这样，我们不仅能发现执行最慢的函数，还能找到执行最慢的代码。有许多优秀的采样分析软件，从免费的Very Sleepy到功能更强大的商业软件，如Intel的VTune。

通过在游戏客户端上运行VTune检查粒子线程，我们得到了运行最慢的函数列表如下。

VTune中显示的运行最慢的函数列表

上表列出了一些与粒子处理相关的函数。前两个函数花费时间最多，但功能也较多，主要用于更新与每个粒子位置和方向相关的各种矩阵信息和状态。在这里，我将特别关注列表的第三项和第九项，即AnimatedVariableWithRandomFactor<>类的成员函数Evaluate。与前两个函数相比，该函数规模较小，容易理解，但运行时间却不短。

第二步：理解

现在，我们选择了一个需要优化的函数，接下来要了解它的功能和设计原因。在上述例子中，AnimatedVariables类是LOL游戏情节设计师用于定义粒子特征点随时间变化的工具。设计师先为特定粒子对象定义关键帧的位置数据，然后通过代码对这些数据进行插值拟合，生成运动轨迹曲线。插值方法可以是线性插值、一阶或二阶积分插值。在游戏中，动态曲线被广泛使用，例如在“Summoner’s Rift”场景中，需要计算近40,000处，包括粒子的颜色、尺寸和运动速度。在一次游戏中，Evaluate函数被调用高达数亿次。需要注意的是，在LOL中，粒子的定义是游戏的关键部分，其行为不能随意改变。

经过优化，该类使用了一个查找表（以数组形式），为每个关键帧存储预先计算的值。运行时直接读取，避免了频繁计算。这是一个合理的选择，因为一阶和二阶积分计算曲线轨迹非常消耗CPU资源。如果在每个系统中对每个粒子的每个动画都进行此类计算，将显著降低游戏运行速度。

动态变化曲线查询表

在分析性能问题时，我们通常会在极端条件下进行测试和验证。为了模拟粒子的慢动作运行，我创建了一个单人游戏，包含九个中等技能水平的自动机器人（bots），并在游戏的下路（bottom lane）引发了一场大规模团战。在战斗过程中，我在客户端运行VTune，记录各种数据。对Evaluate函数的代码分析结果如下所示。

VTune中的分析例子

下面详细解释VTune显示内容的含义：上图以图形化方式展示了函数在采样分析运行过程中的结果。右边的红色条状表示采样命中的频度，红色条越长，命中频度越高，说明该行代码运行越慢。条状物右边显示的时间是CPU运行该行代码大致花费的时间。你也可以选择以汇编方式查看每个函数，从而在机器指令级别识别拖慢函数执行的具体指令。

不出所料，第95行是问题所在。但这行代码只是将一个Vertor3f对象从查找表中拷贝出来，为何拷贝一个12字节的数据会如此缓慢呢？

答案在于现代CPU访问内存的方式。处理器的处理速度遵循摩尔定律，每年增长约60％，而内存增长速度相对较慢，每年仅约10％。

CPU和内存处理速度的走势图，由John L. Hennessy, David A. Patterson, Andrea C. Arpaci - Dusseau提供

缓存（Cache）可以弥补这种性能差距。大多数LOL游戏运行在具有三级缓存的CPU上：一级缓存最快但容量最小，三级缓存最慢但容量最大。从一级缓存读取数据大约需要4个周期，而从主存（三级缓存）读取可能需要300个周期以上。300个周期足够CPU完成很多任务。

优化前的查找算法存在问题：如果按顺序从查询表读取数据，速度相当快（基于硬件预取功能），但游戏中处理的粒子数据并非按时间顺序存储，导致查找总是随机进行。这使得CPU不得不经常等待数据从主存储器读取。虽然300个周期可能比一阶或二阶积分计算的机器周期少，但我们仍需了解这种延迟在游戏中发生的频率。

为了找到答案，我们添加了辅助代码，统计AnimatedVariables对象的创建次数和每次创建的类型。我们发现，在近38000次AnimatedVariables对象的创建和销毁过程中：

• 有37500次是线性插值；100次是一阶积分插值，400次是二阶积分插值。
• 有31500次查询表中只有一项；2500次有3项；1500次有2项或4项。

因此，大部分情况处理的是单项。但代码每次都会创建一个查找表，显然大部分情况下该表只包含一项。每次建表查找（总是返回相同的值）通常会刷新高速缓存，导致内存和CPU处理周期的浪费。

代码中的效率瓶颈通常由以下四个原因造成：

• 函数调用过于频繁。
• 选择了错误的算法，例如可以使用O(n)复杂度的算法，却使用了O(n^2)复杂度的算法。
• 做了不必要的工作，或者工作虽必要但执行过于频繁。
• 数据问题，如数据过多或数据存储和访问方式不佳。

这里的问题并非设计或编码失误导致。解决方案本身没有问题，但在程序开发阶段，有些情况是无法预知的。例如，游戏软件情节经设计师不断修改后，大部分场景下某些计算数据变成了单一值（无需建表查询）。

顺便说一句，作为程序员，我领悟到的重要一点是要尊重现有代码。有些代码可能看起来令人抓狂，但它的设计可能有其原因。在不深入研究的情况下放弃并重构现有代码是不明智的，修改代码前必须确保完全理解其使用方式和设计意图。

第三步：迭代

现在我们已经明确了问题所在、代码的功能以及运行缓慢的原因，可以开始制定解决方案。首先，我们发现程序最常见的执行路径对应单变量，重新设计时需考虑这一点。其次，如果插值点较少，线性插值速度会非常快（只需读取少量高速缓存数据并进行简单计算），这也是需要考虑的因素。最后，我们认为只有极少数情况需要为计算积分曲线建立查找表并进行查找。

由于大部分情况无需查表，我们无需每次计算都创建查询表，从而释放大量内存（绝大多数表至少有256项，每项最多12个字节，相当于每张表约占3K字节）。释放的内存可部分用于缓存少量表项或单一变量。

原来的代码如下：

template <typename T>
class AnimatedVariable
{
// <snip>
private:
std::vector<float> mTimes;
std::vector<T>     mValues;
};

template <typename T>
class AnimatedVariablePrecomputed
{
// <snip>
private:
std::vector<T> mPrecomutedValues;
};

AnimatedVariablePrecomputed对象由AnimatedVariable对象构造，用于内插和建立指定大小的表。Evaluate()函数仅由AnimatedVariablePrecomputed对象调用。

改动后的AnimatedVariable类如下：

template <typename T>
class AnimatedVariable
{
// <snip>
private:
int mNumValues;
T mSingleValue;

struct Key
{
float mTime;
T     mvalue;
};
std::vector<Key> mKeys;
AnimatedVariablePrecomputed<T> *mPrecomputed;
};

我们增加了一个缓存值mSingleValue，并添加了变量mNumValues，用于判断何时使用mSingleValue。如果mNumValues的值为1（单键情况），Evaluate()函数将立即返回mSingleValue，无需进一步处理。同时，我们将分开定义的两个数组mTimes和mValues组合成一个新的结构体数组mKeys，避免了实际匹配的Time和Value在各自数组中位置不对应的问题，从而降低了缓存不命中的概率。

不考虑数组mKeys（实质是指针数组）所指向的实际数据大小，由于模版T（mSingleValue的类型）的实际类型不定，这个类现在的大小在24至36个字节之间（具体取决于CPU架构类型和数组mKeys的元素个数）。

最初的Evaluate()函数如下：

template <typename T>
T AnimatedVariablePrecomputed<T>::Evaluate(float time) const
{
int numValues = mPrecomputedValues.size();
RIOT_ASSERT(numValues > 1);

int index = static_cast<int>(time * numValues);
// clamp to valid table entry to handle the 1.0 boundary or out of bounds input
index = Clamp(index, 0, numValues - 1);
return mPrecomputedValues[index];
}

经过改造的新Evaluate()函数如下，通过运行VTune，可看到三种情况下的运行情况：单值（红色）、线性插值（蓝色）、积分查表插值（绿色）。

VTune改进后的代码示例

改进后的代码运行速度大致提高了三倍：在运行最慢的函数列表中，从原来的排名第3降到了第22位！不仅速度更快，使用的内存也减少了约750KB。此外，执行线性插值也更加准确了！

由于篇幅限制，本文未介绍改进过程中遇到的曲折。我曾尝试基于粒子的生命周期减少插值点表的大小，该方法效果不错，但较小的表会导致快速移动的粒子显示出现锯齿状条纹。幸运的是，这个问题被及时发现，最终我采用了本文介绍的解决方案。还有一些其他的数据和代码修改，但对运行效率提升不大，有些修改甚至导致运行速度变慢。

总结

我们完成了一次对LOL代码库中一段代码的典型优化过程。这些简单的改变节省了750KB的内存，使计算粒子运动轨迹的线程速度加快了一到两秒，进而加快了主线程的执行速度。

文中提到的三个优化阶段看似简单，但在程序员优化代码的过程中常常被忽视。再次强调：

• 识别：分析应用程序，确定性能最差的部分。
• 理解：理解代码的设计意图和运行缓慢的原因。
• 迭代：根据第二步的分析修改代码，然后测试效果。可能需要多次迭代，直到解决性能问题。

上述解决方案并非最快的，但思路和方向是正确的。只有沿着正确的方向迭代，才能确保最终成功。