从《LOL》谈游戏中的随机动作优化
发表于2016-04-28
游戏开发人员面对的往往是一个长期持续演进的软件产品，如”英雄联盟”(译者注：League of Legends，以下简称LOL，是美国Riot游戏公司开发的3D大型竞技场网游)，这些游戏产品在演进过程中会随着剧情的发展在内部的有限状态机上不断地添加越来越多的内容。新加入的内容不仅导致愈加复杂的逻辑实现，同时由于需要更多的纹理绘制，仿真计算，也带来了内存消耗的增加和性能的下降。如果我们忽视这些问题（或者由于实现出现错误）的话，那么必然会损害游戏的运行性能，导致游戏的体验感下降。游戏动画中产生的任何延迟，阻塞都会直接导致玩家感到异常沮丧。
我所在团队的使命是致力于改善LOL这款游戏的性能。通过测试游戏的客户端和服务器端，找到影响性能的代码，并改进它们。同时我们也会把研究成果反馈给其他的团队，并为他们提供分析工具和测量指标，让他们能尽早发现性能上的问题。我们持续地提升LOL的性能表现，为游戏情节设计师和艺术家们腾出更多的空间来添加更酷的新东西：我们的任务是让游戏运行得更快，而他们的工作是让游戏变得更有趣，更好玩。
这篇文章是一个系列中的第一篇，介绍我们的团队是如何在游戏内容不断添加的情况下对游戏的运行速度进行优化的。这是一件非常有挑战性的任务。本文将和各位深入探讨一下在面对如何提高游戏中的粒子系统（particle system）的性能中所遇到的一些有趣的问题，正如下面的动画，其展现了粒子系统在游戏软件中所扮演的举足轻重的作用。
LOL游戏中高密度粒子运动动画场景的例子
优化不是简单地重写一段代码，尽管有时候的确需要这样。我们对代码的修改，其目的不仅是要提升性能，更要保证其正确性，并尽可能地提高代码的可维护性。最后这一点是至关重要的：任何代码，如果可读性和可维护性不好的话，都会在未来给项目带来潜在的问题。
在优化现有的代码时，我们会采取三个基本步骤：识别，理解和迭代。
第一步: 识别
在优化前，我们首先需要确认该代码的确需要优化。有些代码咋看上去运行效率是比较低，但如果它们对系统的整体性能的影响本身就微乎其微的话，那还是不要花精力去改动它（有这时间和精力还不如用在其他的地方）。我们用代码分析工具和测试样本来帮助识别低效的代码。
第二步: 理解
一旦我们识别出低效的代码，就可以更深入地研究这些代码来真正了解发生了什么事情。我们需要知道代码在干什么，以及原来实现的真实意图。然后，我们就可以明白为什么这里的代码是一个瓶颈。
第三步: 迭代
当我们明白为什么这些代码是低效的，以及它的目的是什么，我们就有足够的信息来设计并实现一个可能的解决方案。使用第一步识别步骤所提到的分析工具和样本数据，我们可以对比新代码和老代码在性能上孰优孰劣。如果新的解决方案足够的快，并且经过全面的测试确保没有引入任何新的错误，那么赶紧庆祝一下，至此我们已经为进一步的内部测试做好准备。但大部分情况下，如果新的改动并没有带来性能上的显著提高，那么我们就不断地迭代解决方案，直到它足够地快。
最近我针对LOL的粒子系统做了一次优化工作，就让我们基于这次优化一步一步地来看看这个过程是怎么实现的吧。
第一步: 识别
Riot公司(译者注: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游戏中的情节设计师（artists）用来定义粒子的特征点是如何随时间变化而变化用的。设计师首先为某个特定的粒子对象定义好所有关键帧中的位置数据，然后通过代码对这些数据插值拟合出一条运动轨迹曲线。插值方法可以用线性插值法，或者一阶，甚至二阶积分插值法。在游戏中动态曲线被大量使用 - 譬如在象“Summoner’s Rift”（译者注：LOL中一处著名的游戏场景的地名）里，光一个这样的场景中就要计算近40,000处 - 包括所有粒子的颜色，尺寸到运动速度。在一次游戏中Evaluate这个函数被调用高达数亿次。要知道，在LOL中，粒子的定义是游戏中的关键部分，它们的行为是不能随意改变的。
经过优化，这个类使用了一个查找表（以数组的形式），针对每个关键帧存放了一个预先计算好的值。在运行期间直接读取即可，避免了频繁的计算。这是一个合理的选择，因为采用一阶和二阶积分计算曲线轨迹是一个非常消耗CPU的过程。如果在每个系统中对每个粒子的每个动画都执行类似计算将导致游戏程序的运行速度显著放缓。
动态变化曲线查询表
当查看性能问题时，我们经常会在一些极端条件下进行测试和验证。为了模拟粒子运行的慢动作我新建了一个单人游戏，包括九个中等技能水平的自动机器人(bots)，并在在游戏中的下路(bottom lane)上策动了一次大规模的团战(teamfight)。在战斗的同时我在客户端运行VTune，记录下各种数据。对Evaluate这个函数的代码给出了如下分析结果（如下图所示）。
Evaluate函数中第90行涉及到一个函数调用，为了说明方便，我把函数调用中的代码复制出来放在第91-95行，同时注释掉了第90行。
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)。
· 做不必要的工作，或者虽然工作是必需的要但执行过于频繁了。
· 数据的问题：要么数据太多或者数据存储方式和访问方式不好。
这里的问题并不是由于设计或编码造成的。解决方案本身没有问题。问题在于有些事情在程序开发阶段是无法知道的，就像这里，游戏软件的情节经过设计师的不断修改后，造成了在大部分场景下某些用于计算的数据变成了一个单一值（不需要建表查询了）。
顺便说一句，作为一个程序员我所领悟到的最重要的事情之一就是要尊重你所面对的代码。有些代码可能看起来让你很抓狂，但它被写成这样可能是有原因的。不深入研究就放弃并重构现有的代码是愚蠢的行为，修改代码之前一定要保证你完全理解它是如何被使用的，以及它为什么被设计成这样。
来源：http://codesoftly.com/2010/03/ha-code-entropy-explained.html
第三步：迭代
现在知道了问题症结所在，它应该做的是什么以及为什么它那么慢。现在可以开始制定解决方案了。首先，我们发现程序最常见的执行路径对应的是单变量，在重新设计时需要考虑到这一点。其次，如果插值点很少，那么采用线性插值将非常快（因为这仅涉及读取少量的高速缓存中的数据并进行简单的计算），这也是我们需要考虑的一点。最后，我们可以认为只有很少的情况才会需要为计算积分曲线执行建表操作并进行查找。
由于大部分情况我们是不需要查表的（译者注：对应上面所说的前两点），所以并不需要每次计算时都执行创建查询表的动作，这样我们可以释放相当数量的内存（绝大多数的表有至少256项甚至更多，每项最多12个字节。这相当于大约每张表占3K字节）。释放的内存中的一小部分可以被另外用来作为缓存存放少量的表项（译者注：对应上面的第二点）或者单一变量（译者注：对应上面的第一点）。
原来的代码如下：
template class AnimatedVariable { // private: std::vector mTimes; std::vector mValues; }; template class AnimatedVariablePrecomputed { // private: std::vector mPrecomutedValues; };
AnimatedVariablePrecomputed对象由AnimatedVariable对象构造，用于内插和建立一个指定大小的表。Evaluate()函数只会被AnimatedVariablePrecomputed对象调用。
We changed the AnimatedVariable class to look like this:
改动后的AnimatedVariable类如下所示：
template class AnimatedVariable { // private: int mNumValues; T mSingleValue; struct Key { float mTime; T mvalue; }; std::vector mKeys; AnimatedVariablePrecomputed *mPrecomputed; };
我们增加了一个缓存值mSingleValue，同时增加了一个变量mNumValues用来告诉我们何时使用mSingleValue。如果mNumValues的值是1（单键的情况），Evaluate()函数就立即返回mSingleValue而不需要进一步的处理。同时我们还把分开定义的两个数组mTimes和mValues组合成一个新的结构体数组mKeys，避免了实际匹配的Time和Value在各自数组中位置不对应，这样可以减少缓存不命中的概率。
不考虑数组mKeys（实质是指针数组）所指向的实际数据的大小，由于模版T（mSingleValue的类型）的实际类型不定，这个类现在的大小在24至36个字节之间（当然具体还取决于CPU架构类型，以及数组mKeys的元素的个数多少）。
最初的Evaluate()函数是这样的：
template T AnimatedVariablePrecomputed::Evaluate(float time) const { in numValues = mPrecomputedValues.size(); RIOT_ASSERT(numValues > 1); int index = static_cast(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的内存，并且使计算粒子运动轨迹的线程速度快了一到两秒，从而使主线程的执行也变得更快了。
文中提到的三个阶段，虽然看似明显，但在程序员寻求优化代码的过程中却常常被忽视，所以再重申一下：
· 识别：分析应用程序，并确定表现最差的部分。
· 理解：理解代码为什么这么写，以及为何它这么慢。
· 迭代：根据第2步的分析修改代码，然后测试检查效果。这样的操作可能需要不断重复，直到性能问题得到解决。
上面的解决方案还不是最快的，但它的思路和方向应该是正确的，只有沿着正确的方向进行迭代才能保证最终的成功。