从《LOL》谈游戏中的随机动作优化

让我来告诉你如何使用这个工具：上面的图是一个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 <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对象调用。

We changed the AnimatedVariable class to look like this:

改动后的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
{
    in 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的内存，并且使计算粒子运动轨迹的线程速度快了一到两秒，从而使主线程的执行也变得更快了。

文中提到的三个阶段，虽然看似明显，但在程序员寻求优化代码的过程中却常常被忽视，所以再重申一下：

1. 识别：分析应用程序，并确定表现最差的部分。
2. 理解：理解代码为什么这么写，以及为何它这么慢。
3. 迭代：根据第2步的分析修改代码，然后测试检查效果。这样的操作可能需要不断重复，直到性能问题得到解决。

上面的解决方案还不是最快的，但它的思路和方向应该是正确的，只有沿着正确的方向进行迭代才能保证最终的成功。