Riot工程师:三步让你的游戏更新更快更小

【Gamelook专稿，转载请注明出处】

Gamelook报道/对于一个在线游戏的开发商来说，你总是需要不断增加新的内容保持玩家的新鲜感和黏性，但随之而来的问题是，新内容的出现和老版本之间往往会造成冲突，经年累月的代码积累很容易出现游戏延迟甚至卡顿，游戏运行时间越长，这种问题解决起来越棘手。最近，Riot工程师Tony Albrecht在其开发者博客讲述了全球最流行的MOBA游戏《英雄联盟》新内容增加之后出现的问题是如何解决的，他在博客中提出了三步让游戏更新更快、占内存更小的方法，以下是Gamelook编译的博客内容：

做个像《英雄联盟》一样需要持续更新的游戏常常会让开发者们经常面对非常头疼的编码问题，日益增多的游戏内容和有限的机器配置总会遇到冲突。新内容的增加通常会带来隐藏成本，除了新内容植入成本外，还包括由更多纹理、模拟以及处理所导致的内存和性能成本增加，如果我们忽视（或者说错估）这个成本，那么游戏性能就会下降，《英雄联盟》的乐趣就会减少，玩家黏性就会降低，游戏延迟就会增加，掉帧的现象是让人很沮丧的。

我是专门负责提高《英雄联盟》游戏性能团队的一员，我们负责客户端和服务器方面的优化，寻找问题（性能以及其他方面）然后解决它们。我们还会把自己得到的问题反馈给其他团队，并且为他们提供工具和数据来帮助他们在尚未影响玩家体验之前确定性能问题。我们不断的提高LOL的性能，好让美术师和设计师们为游戏增加更多更酷的东西，简而言之：在他们把 游戏变得更大更好的同时，我们让游戏变得更快。

这是我们团队在优化《英雄联盟》经验系列的第一篇技术博客，随着新内容以及修复问题数量的增加，优化工作变得非常困难，但这同时也是非常具有价值的挑战。这篇文章会讲述一些我们在做粒子系统（Particle System）所遇到的一些有趣的挑战，从下面的动画你们可以看出，粒子系统在游戏中起到了非常重要的作用。

优化工作并不只是重写一大堆的代码，虽然有时候的确是这样。我们所做的改变不仅提高了游戏性能还保持了正确性，如果有可能的情况下还会提高代码的可读性，最后一点很重要，任何不可读而且不可维护的代码都会给未来的游戏更新带来技术困难。

在优化现有代码库的时候我们采用了3个基本的步骤，分别是：确定问题、理解问题和优化解决。

第一步是确定问题：在任何优化开始之前，我们首先要确定代码是否需要优化，如果对于整体性能的影响不大，那么优化大量的代码是没有多大好处的，特别是这个时间用在其他方面会更好的情况下，我们使用代码工具和样本分析来帮助确认不影响性能的代码。

第二步是理解问题：一旦我们知道了代码库的哪个部分影响速度，我们会更深层的审查这些代码，以了解问题所在，我们需要知道这些代码是做什么用的，还要知道当初为什么要写这些代码，然后就可以确定为什么这些代码是导致瓶颈出现的原因。

第三步是优化解决：当我们了解了代码为什么很慢以及它的用途之后，我们就有了足够的信息去分析和得出可行性方案，通过确定问题步骤所用的工具和分析数据，我们对比新旧代码之间的性能差异，如果解决方案可以让游戏变快，我们就进行完整的测试，以确保新代码没有带来新的bug，一旦确定没有问题，我们就开始进行内部测试。如果新代码依然不够快，我们就一直调整直到满意为止。

下面，我们来看看《英雄联盟》代码库的处理过程并且一步步的讲述最近我们对粒子系统所做的一次优化。

第一步：确认问题

Riot工程师们用一系列的分析工具检测游戏客户端和服务器的性能，我们首先使用内部工具Waffles看客户端的帧率以及高级分析信息（通过工具的特定函数获得的输出信息），这个工具可以让我们内部的客户端和服务器版本相通，其实，Waffles还可以用于其他事，比如测试中触发debug活动，检测像导航网格之类的游戏内数据并暂停或者减缓游戏玩法等等。

Riot公司的内部工具Waffles

Waffles可以提供一个实时显示的界面，以及详细的性能信息，下图展示了客户端性能表现的经典例子，上边的图片（绿色）代表着以毫秒为单位的帧率周期，数值越高，帧速就越慢，非常慢的帧速是可以直接在游戏中看得到的，也就是游戏出了故障。图片的下部是重要函数的分层视图，通过点击任意的绿色条，工程师们都可以收到最新的详细帧数信息，通过这个信息，我们可以很好的了解哪部分代码是导致问题的关键。

我们使用简单的宏（macro）在代码库内自动检测重要函数，以提供性能相关的信息。在公用游戏版本中这个宏是被编译出去了的，但在测试版本中包含了一个很小的class，它可以创造一个指令（event）放到一个大的概要文件缓冲区（profile buffer）。这个指令包含一个字符串识别码（string identifier）、一个线程ID（thread ID）、一个timestamp和其他必须的信息，比如它还可以存储所有时间发生的内存配置数。当这个指令超出范围之后，destructor会在这个缓冲区更新指令自construction之后的运行时间。随后，这个概要文件缓冲区可以被输出和剖析，理想情况下放到另一个程序中以减少对游戏本身的影响。

Chrome Tracing

在我们的案例中，我们把这个概要文件缓冲区输出到一个文件上，并且把它转化到可视化工具中，这个工具内置于Chrome浏览器中（你可以在Chrome浏览器中输入‘chrome://tracing/’进行尝试，它主要用于网页解析，但输入解析数据的格式是json，可以从你的数据中很容易构建）。从这里我们可以看出哪些函数是缓慢的，或者哪里有大量的小函数在序列中，这些情况都可能是次优代码（suboptimal code）的征兆。

这里我来展示如何去做：上面的视图是典型的Chrome Tracing视图，展示了客户端上两个运行的线程，上面的一个是主线程，负责大多数的处理工作，地步的是粒子线程（particle thread），每一个有颜色的条都代表对应的函数，条的长度代表的是执行时间。被调用的函数由垂直叠加区展示，母函数在子函数之上。它非常神奇而可视化的展示了执行复杂度以及帧签名时间（time signature），当我们发现一个带有次优代码的区域时，我们可以把粒子截面（particle section）放大，这样可以看到更多的细节。

Chrome Tracing放大之后

我们放大图表的中间部分，从上面的线我们可以看到很长的等待时间，直到粒子Simulate函数在底线完成的时候才终结。Simulate包含大量不同的函数指令（带颜色的条），每个都是粒子系统更新函数（particle system update function），该系统的每个粒子的位置、方向以及其他可视化数据都会被更新。一个最明显的优化就是把Simulate函数多线程化，让其在主线程和粒子线程上都可以运行，但在这个案例中，我们只看Simulate代码本身的优化。

既然我们知道希望在哪里寻找性能问题，那么就可以直接转向样本分析。这种分析会阶段性的读取和存储程序计数器，有选择性的读取和存储运行过程的堆叠。一段时间之后，这个信息可以给出一个随机概述（stochastic overview），告诉我们代码库中的时间使用。较慢的函数会出现更多的样本，更有用的是，用时最长的单个指令可以指出更多的样本。这样，我们不仅可以看出哪些函数是最慢的，还可以知道那几行的代码是最慢的。如今有很多不错的样本分析工具，从免费版的Very Sleepy到功能齐全的商业版本英特尔VTune等等。

通过在游戏客户端运行VTune并检查粒子线程，我们可以看出如下最慢的函数列表

上面的这个表格展示了一系列的粒子函数。供大家参考的是，顶部的2个是比较大的函数，每个都更新大量的数据和状态，在这个案例中，我将主要关注entries 3和9处AnimatedVariableWithRandomFactor<>当中的Evaluate函数，因为它非常小（所以比较容易理解）但解决起来代价又非常高。

第二步：理解问题

既然我们选择了需要优化的函数，那么我们就要理解它是做什么的，为什么要优化。在这个案例中，AnimatedVariables被《英雄联盟》美术师们用来定义粒子特征是如何随着时间变化的。在一名美术师为特殊粒子确定的关键帧值（key-frame value）之后，代码就会基于这个数据插值，产生一个曲线，插值方式通常是线性插值或者一级/二级集成（Integration）。动画曲线（Animation curves）被广泛使用，单单召唤师峡谷中有接近4万个，Evaluate()函数在每次游戏中都被调用数百万次，另外，《英雄联盟》中的粒子对于玩法是非常重要的，因此它们的特性必须是不能改变的。

这个class已经用查询表（lookup table）优化过了，它是一个为每个timestep都准备了预先计算值的数列，所以计算过程可以被减少到只读一个值就可以了。这是一个非常敏感的选择，因为曲线的一级和二级集成代价很昂贵，为每个系统里的每个例子上的动画变量进行这个操作会导致处理过程大大减缓。

当我们看一个性能问题的时候，通过找到最严重的案例把问题夸大化通常是有用的，为了模拟粒子减速，我开了一局单机游戏，加入了9个中等水平的电脑，并且在下路发起了大规模团战。然后战斗的时候我在客户端运行了VTune并且记录了大量的解析数据，所以就得出了Evaluate代码形式的样本归因（sample attribution）如下：

我现在来说第90行提到的Evaluate()函数中的内容，也就是91-95行代码，这样可以更好的展示所说的情形。

对于不熟悉VTune的人来说，其实这个试图展示的就是解析期间所收集样本的代码，右边的红色条指示的点击次数，条越长就意味着点击次数越多，所以这行代码就越慢挨着该条的时间是处理这行代码所用的预估时间，你还可以把它用到特殊的函数中分析减速的原因。

如果大红条需要分析的话，第95行代码就是问题所在。但它所做的就只是从拼写失误的查询表中复制了一个Vector3f，所以，为什么它是这个函数中最慢的部分呢？为什么拷贝12个字节如此之慢呢？

答案是因为现代CPU处理内存的方式，CPU都非常忠实的遵循了摩尔定律，每年都会提速60%，而内存速度每年的增速只有可怜的10%。

电脑架构：量化方式增长

缓存可以减小性能差别，运行《英雄联盟》的大多数CPU都有3级缓存，一级缓存最快但也最小，三级缓存最大也最慢，从一级缓存读取数据只需要4个周期，而读取主存储器却需要大约300个周期甚至更多，你可以在300个周期内做大量的处理工作。

最初的查询式解决方案的问题是，按照顺序读取查询表中的值速度很快（由于硬件预读），然而我们要处理的粒子并不是按时间顺序存储的，所以查询起来是随机顺序的，这通常会在CPU等待从主存储设备读取数据时导致延迟，虽然300个周期比一级或者二级集成的代价更低，但我们还需要知道的是，这个函数在游戏中的使用频率非常的高，所以仍然会带来大量的延迟问题。

为了找到问题所在，我们快速增加了一些代码，用于核对AnimatedVariables的数量和类型（接近3.8万个AnimatedVariables）：

其中3.75万个是线性插值，100个是一级，400个是二级；

其中3.15万个只有一个关键值（key），2500个拥有3个关键值，1500个包含2或者4个关键值。所以比较常见的路径是单个关键值的，由于代码总是生成一个查询表，这就产生了一个不需要传播的单数值表，这就意味着每次查询（返回同样数值）都会产生缓存丢失，进而导致大量的内存和CPU周期浪费。

通常情况下，代码成为瓶颈问题的原因有以下1-4个：

被调用次数太频繁；选择了比较差的算法（algorithm，比如O(n^2) vs O(n)）；做了不必要的工作或者频繁做必要工作；数据不好：数据太多或者分布于访问模式太差。

这个问题和代码设计不足或者使用都没有关系，解决方案也很好。但是被美术师们大量的使用之后，普通路径是针对单个数值的，有些问题在使用过程中是很不明显的。

顺便说一句，作为一个程序员我学到最重要的事就是尊重你所使用的代码，代码虽然看起来写的比较疯狂，但很可能是出于非常好的原因。在完全理解代码的用途和设计意图之前不要撇开现有代码。

通俗版解释

第三步：优化解决

现在，我们知道了问题代码所在，代码的用途以及它速度慢的原因，是时候做出一个解决方案了。由于每个常见的执行路径都是为单独变量设计，我们需要在考虑这种情况的基础上进行重新设计。我们还知道少数key的线性插值会更快，所以我们也需要把这种情况考虑进去。最后我们可以回到前面integrated曲线中的预计算查找（precomputed lookup）。

在不适用查询表的情况下是没有必要首先创造这么一个表的，所以这会留出大量的内存，所以我们可以在一系列的entries以及被存储的单个值的缓存中使用多一点的内存。

最初的代码数据看起来是这样的：

AnimatedVariablePrecomputed对象是从AnimatedVariable对象中构造的，并且从中插值和构建了特殊大小的table，Evaluate()只是在预计算对象上被调用。

我们把AnimatedVariable类改成了这样：

我们增加的缓存值mSingleValue和一个数字mNumValues，这样可以知道什么时候使用这个值，如果mNumValue是1，Evaluate()就会直接返回mSingleValue，不再需要任何后续的处理，你还可以发现它减少了缓存丢失。

最初的Evaluate() method是这样的：

我们的新Evaluate () method如下图VTune中所示，你可以看到三个可能的执行方案：单数值（红色）、线性插值（蓝色）和预处理查询（绿色）。

这个新代码运行速度几乎快了3倍：现在这个函数在最慢的函数列表排名中从第三降低到了第22，不仅速度更快，它使用的内存也更少了，已经低于750kb。这还不算完，它不仅变得更小更快，对于线性插值变得也更加精确，可以说是一石三鸟。

我这里没有展示的（本文已经太长了）是获得这个方案所经历的调整过程，我第一次调整的时候是尝试在粒子周期的基础上降低样本tables的大小，由于有更小的样本table，一些快速移动的带粒子（ribbon particles）出现了锯齿。幸运的是这个情况很早就被发现了，我也及时换成了这里所展示的版本，我们还做了一些不改变性能的数据和代码调整。

总结

我们这里所讲的是《英雄联盟》小部分代码优化的典型案例，这些简单的改变节约了内存使用而且提高了粒子线程的运行速度，从而让主线程执行起来更快。

这里提到的三个步骤虽然看起来很显而易见，但经常会被程序员们在做优化的时候所忽略。这里再重复一次：

确定问题：分析并找出表现最差的部分；理解问题：了解这部分代码的作用以及为什么会慢；优化解决：基于步骤二改变代码然后重新分析。如果没有变得更快，就不断的重复这个过程。以上的解决方案可能并不是最快的版本，但至少它的解决方向是正确的，这是通过优化获得性能提高的最安全的方法。