C++高效程序设计

最近开发的一个程序，对代码的速度要求很高，同时由于已实现的代码速度不能满足要求，因此进行了搜索。收藏此篇。

文章来源：http://www.kuqin.com/language/20090314/39898.html

摘要
不管是否愿意承认，每个人都希望程序的运行速度越快越好。每天人们都你追我赶，好像明天就是末日。而同时，公关部的那些家伙则不停的吼叫着，说他们的新引擎比其他人的更“快”更“好”。

我并不打算告诉你如何让你的代码跑得比别人的快。我只是想告诉你，如何让你的代码更快、更高效，当然，是跟你原来的代码相比。
我讲述的内容主要涉及三个概念，这三者之间的关系相当复杂：
1、代码执行时间
2、代码/程序大小
3、程序设计本身的开支
我始终坚信应该保持这三者之间的平衡，尤其在某些情况下，2、3两项直接影响了代码的执行时间。

在本文中，我将讲述一些可能有助于你提高代码执行效率的方法。我会从最简单的优化方法开始，然后逐渐深入到那些比较复杂的技术。现在我们首先从一个不太显眼的地方开始：编译器。

考虑到读者中有一些经验丰富的程序员，我的叙述会尽可能简单，以避免因为细节太多而显得杂乱不堪。

第一节 公欲善其事，必先利其器
这一节的内容似乎不说也罢，不过仔细想想，你对你手中的编译器到底了解多少？你知道它可以为哪些处理器生成代码吗？你知道它可以进行哪些类型的优化吗？你知道它的语言不兼容性吗？
当你想要写出点什么的时候，尤其是当你希望你的代码运行如飞的时候，了解这些内容将是至关重要的。
举例来说，最近在GameDev的讨论组里有人问关于Microsoft Visual C++的“Release Mode”的问题。这是一个标准编译器选项，如果你使用特定的编译器，你就应该知道它的意思。如果你不知道，那很遗憾，你并不真正会使用你花费了大量的金钱买来的东西。简单来说，“Release Mode”会删除所有debug用的代码，进行所有可能的编译代码优化，生成更小的可执行文件，还让这个文件运行的更快。它可能还会有一些其它的功能，如果你感兴趣，请阅读编译器的相关文档。

看到了吧，如果你以前并不知道这个“Release Mode”，我现在就可以告诉你一个让你的代码运行更快的方法，而且这个方法不需要你修改任何代码！

目标平台也是非常重要的。现在，你遇到的最低档的可能就是Intel Pentium处理器了，不过如果你使用10年前的编译器，那么它不会做任何针对Pentium的优化。去找一个最新的编译器，它可能会大大提高程序的运行速度，同样，也不需要你对代码做任何的修改。

另外还要注意一些事：你的编译器有没有代码分析（profiling）工具？如果你连这个都不知道，那么你就不要指望编写出更快的代码了。如果你还不知道什么是代码分析工具，那么你还需要更多的学习。一个代码分析工具就是一个用来获得程序的运行时间的东东。你在代码分析器（profiler）中运行你的程序，做一些操作，然后再从你的程序中退出，就可以获得一个关于每个函数耗时的报告。你可以根据这个报告找到代码的运行瓶颈——就是你的代码中花费时间最多的部分。对这些部分作一些特定的优化比随随便便的在每个地方都做一点优化效果要好多了。

不要说“但是我知道我的瓶颈在哪！”它们可不是光用脑子就可以找到的，尤其是在使用第三方API和程序库时。几个星期前我还遇到一个类似的问题，在一个视频程序里，显示每一帧时都会莫名其妙的产生状态切换，而这个动作占用了总执行时间的25%。通过简单的添加一条测试语句（测试状态是否已经被设置），我把相应的那个函数从分析得到的50个最昂贵的函数列表中剔除了。

看上去在大多数情况下，使用分析器可以很容易达到目的，但事实上并非如此。你必须找到程序中的关键路径。所谓关键路径就是程序大部分运行时间都在执行的路径。对关键路径进行优化可以显著的提高运行效率，你的用户也会因此而高兴。

另一种情况是，也许你发现在某个函数中，时间开支最大的步骤是装载一个特定的文件，但是你知道这种情况只会在应用程序启动时发生一次。对这个函数进行优化也许可以让程序的总运行时间减少几秒钟，但不会提升正常使用时的效率。事实上，这表明你没有进行足够的代码分析，因为在正常使用时，这个函数所占用的时间百分比将会越来越低，而你的关键路径所占用的时间百分比将会一路飙升。

我想以上这些内容能够使你对这些工具有了一些了解。

代码分析工具实在是太好了，记得一定要用！

如果你还没有代码分析器，你可以试试Intel的VTune profiler。你可以免费试用它一个月。在下面这个网址下载它http://developer.intel.com/vtune/analyzer/。

在本文的下一部分，我将告诉你如何让你的C/C++编译器做你想让它做的事。

第二节 Inlining，inline关键字

什么是inlining？我会通过描述inline关键字来回答这个问题。

Inline关键字告诉编译器“在适当的地方展开函数”，它工作起来很像是C和C++中的宏（#define），但是有一点不同。Inline函数是类型安全的，其主要作用是帮助编译器进行代码优化。有了它，你就可以同时具有宏的速度（没有函数调用的额外开销）和函数的类型安全性，以及一大堆其它好处。

还有什么好处呢？大多数编译器在同一时间内只能优化一个模块中的代码。通常就是一个.h/.cpp文件对。使用inline函数，就使得编译器对在不同的模块中的函数也可以进行代码优化，比如消除返回值拷贝，消除多余的临时变量，等等。如果你想要了解更多关于编译器优化的内容，请参考本文结尾处给出的参考文献，尤其是那本讲述C++高效编程的书。

可怕的inline关键字。我不得不这样说，因为关于它的误解实在太多了。Inline关键字并不强迫编译器inline特定的函数，而只是建议编译器这样做。以下内容引自MSDN：

“The inline keyword tells the compiler that inline expansion is preferred. However, the compiler can create a separate instance of the function (instantiate) and create standard calling linkages instead of inserting the code inline.”（inline关键字告诉编译器最好进行inline扩展。但是，编译器可能会创建一个独立的函数实例和一个标准的调用连接，而不是将代码内联的插入。）

某些情况下编译器会忽略你的inline请求，这些情况包括：在inline函数中使用了循环；在inline函数中调用其它inline函数；递归。

上面引用的那段话还隐含着其它一些内容：一个声明为inline的函数，必须进行内部连接。这就是说，如果你的inline函数在另一个object文件中实现，你的连接器在连接这个函数时就会卡壳。ANSI标准倒是提供了一种方法解决这个问题，可惜的是目前为止Visual C++（6.0）尚不支持这种解决办法。

“那么，”你要问了，“到底应该怎么办呢？”答案很简单：总是在同一个模块中实现inline函数。这个方法做起来很简单，只要将整个函数实现写到.h文件中，并且在所有用到这个函数的模块中包含这个.h文件。也许这并不想你想象中的那么美好，不过它的确可以正常工作。

事实上，考虑到隐藏实现的问题（我是个面向对象偏执狂），我并不喜欢这个方法。但是最近我的确使用这个方法编写了很多类。有一个好处是，我不需要输入inline这个关键字——如果你把整个函数定义放进类定义中，编译器会自动的把它看成inline函数。如果一个类的所有函数都应该是inline的，那么我就把整个类定义及实现都写进头文件中。我建议你只在真正迫切的需要提高运行速度时才这样做，当然，你也不在意太多的人share你的代码。


第三节 搭乘类高速列车
设计执行速度快的类是C++程序设计的关键。我用一个3d向量类来说明这个问题（这在我的工作中是很常见的类）。事实上，就在前几个星期，我刚刚完成了一个向量类。在编写这个类的一个月里，我犯下了太多错误。

一个向量类是必须的，因为工作中有大量的向量数学运算，显然每次都要反复书写相同的内容。如果你想提高编码效率，同时又不想牺牲代码运行速度，那么就要编写一个向量类，我的这一个叫作CVector3f（3f的意思是三个float数据）。为了提高代码的可读性和可维护性，我希望利用C++伟大的特性之一——运算符重载（operator overloading）实现一些运算符函数（+，-，*）。

在最初的设计中，我很快的实现了一个构造函数、一个拷贝构造函数、一个析构函数以及上面提到的那三个运算符。设计过程中，我没有特别考虑效率的问题，也没有使用inline函数，只是简单的把函数声明放入头文件，把函数实现放入.cpp文件中。

下一步是让它跑得更快。我做的第一件事是在头文件中将所有成员函数声明为inline函数。如果编译器真的将它们处理成inline函数，那么我们就可以节省下函数调用的额外开销。对于我的向量类中的那些小函数来说，执行速度有了显著的提升，不过对于那些较大的函数来说，这样做可能不会有明显的效果。

我想到的第二件事是：我们真的需要析构函数吗？正常情况下编译器会为我们生成一个空的析构函数，通常它会比我们写的析构函数效率更高。在我们的向量类中，并没有什么东西需要析构，那么为什么还要浪费时间？

运算符也可以跑得更快。先前的运算符函数大致如下：

CVector3f operator+( CVector3f v )
{
CVector3f returnVector;
returnVector.m_x = m_x + v.m_x;
returnVector.m_y = m_y + v.m_y;
returnVector.m_z = m_z + v.m_z;

return returnVector;
}

这段代码隐藏着众多的多余代码，着实令人烦恼。我们来仔细看看这段代码，代码的第一行声明并构造了一个临时变量。这就是说，这个对象的默认构造函数被调用，但是我们并不需要初始化它，因为我们将要给它赋一个全新的值。

代码结尾处的return语句也是一样——returnVector是一个局部变量，所以不能被马上用于return。此时，拷贝构造函数将被调用，这将会占用相当多的处理器时间，尤其对于这样的小函数更是如此。另一个隐藏的更深的家伙是传递到函数的参数。这个参数同样是一个实参的拷贝，于是更多的内存被占用，更多的拷贝构造函数被调用。如果我们编写一个新的构造函数——它接受x、y、z三个参数，并且这样使用它：


CVector3f operator+( const CVector3f &v ) const
{
return CVector3f( m_x + v.m_x, m_y + v.m_y, m_z + v.m_z )
}

那又会怎么样呢？

这样做将会去掉两个拷贝构造函数的调用，进步很大，不是吗？注意我为这个函数加上了const关键字。这样做不是出于速度方面的考虑，而是为了增加代码的安全性。另一点要指出的是（涉及到编译器的内部实现），我所编写的这个函数允许编译器更容易的进行它自己的代码优化。这个函数中几乎所有内容都是很清楚的，不需要什么前提条件，因而它是一个很好的inline候选函数，编译器还可能会对它进行一些其它的优化，如“返回值优化”（参见本文结尾处的参考文献）。

本节我想要说明的主要问题是，在C++代码中可能存在着很多“隐藏的”开销。构造函数/析构函数、继承以及聚合类型（数组等）的使用都可能产生一个看似简单、私下却执行着复杂的初始化工作的函数。了解这种情况何时会发生，了解如何避免或降低它的消耗，这些都无疑是C++学习过程中一个重要的组成部分。

熟悉你的语言，这是唯一可以真正帮助你自己的。

第四节 刨根问底

于是现在你有了一个漂亮的、运行速度飞快的类，但是你仍然不开心。时间过得太快了。

1、循环优化
解除循环曾经是一件“大事情”。这是什么意思呢？就是说，一些循环可以简单的去掉。比如：

for( int i = 0; i < 3; i++ ) array[i] = i;

在逻辑上这就等同于

array[0] = 0; array[1] = 1, array[2] = 2;

而第二个版本会稍微快一点，因为不需要建立一个循环——i的初始化和自加会消耗一点时间。大部分编译器已经可以完成这样的工作，所以在大多数情况下，你可能不会得到太多的好处，同时代码却会大大的膨胀。我的建议是，如果你再也找不出其它增加速度的方法，那么就试试这个，但是不要对它希望太大。

2、移位（bit shifting）
移位只对整数运算起作用。通过移位进行2的整数次幂的乘除法要比直接进行乘法运算快很多（当然比除法运算更快），这是一个基本常识。
为了理解它的用法，考虑下面这几个公式：

x << y = x * 2 y
x >> y = x / 2 y

Andr LaMothe在他的《Tricks of the Game Programming Gurus》一书中大量的阐述了这方面的内容。在某些情况下，这种方法可以带来巨大的回报。思考下面的这段简化了的代码：

i* = 256;

与之对应的

i = i << 8;

在逻辑上它们完全相同。对于这个简单的例子，编译器很可能会自动将第一条语句转换为第二句，但是当你进行更复杂的计算时（比如i = i << 8 + i << 4等于i *= 272），编译器可能就无能为力了。

3、指针解引用（dereference）操作的地狱
你的代码中有类似下面的内容吗？

for( int i = 0; i < numPixels; i++ )
{
rendering_context->back_buffer->surface->bits[i] = some_value;
}

这也许有些夸张，但是可以说明问题。这是一个很长的循环，而且所有指针的解引用操作耗费了大量的时间。
你可能会认为这是一个不实际的例子，但是我曾经在许多网上发布的代码中见过与之类似的内容。
为什么不这样做？

unsigned char *back_surface_bits = rendering_context->back_buffer->surface->bits;
for( int i = 0; i < numPixels; i++ )
{
back_surface_bits[i] = some_value;
}

这样你就避免了大量的解引用操作，这会大大的提高运行速度，何乐而不为。

在Gamedev.net上，Goltrpoat给出了一个更快的方法，这个方法非常有效，强烈推荐：

unsigned char *back_surface_bits = rendering_context->back_buffer->surface->bits;
for( int i = 0; i < numPixels; i++,back_surface_bits++ )
{
*back_surface_bits = some_value;
}

面的内容只是下面内容的一个特例（虽然经常出现）：

4、循环中进行不必要的运算
考虑下面这个循环的代码：

for( int i = 0; i < numPixels; i++ )
{
float brighten_value = view_direction*light_brightness*( 1 / view_distance );
back_surface_bits[i] *= brighten_value;
}

计算brighten_value不仅代价昂贵，而且也是完全不必要的。这个计算完全不受循环的影响，所以可以简单的移动到循环外，而在循环中只需反复使用brighten_value的值即可。
这个问题也可能以另一种形式出现——在被循环或者对象构造函数反复调用的函数中进行不必要的初始化。谨慎的对待你的代码，要不断的问自己“我真的需要做这些事吗？”。

5、内嵌汇编代码
最后一种方法，如果你真的、真的明白自己在做什么，并且知道为什么它会变得更快，你可以使用内嵌汇编代码，或者甚至是使用C风格链接方式的纯汇编代码（这样它可以被你的C/C++程序调用）。不管怎样，如果你使用内嵌汇编，那么要不然使用条件编译（测试你编写的汇编代码是否被你的编译平台支持），要不然放弃代码兼容性。对于普通的80x86汇编，你可能不用考虑太多，但是如果你使用MMX、SSE或3DNow!指令，就限制了代码的平台兼容性。

当你不得不进行这项工作时，一个反编译工具可能会有用。你可以让大多数编译器生成汇编代码，然后你就可以仔细的检查它，看看是否能手动的提高代码的效率。

再说一次，这里又涉及到第一节中讲到的问题。在Visual Studio中，你可以使用/FA和/Fa编译器开关来生成汇编代码文件。

第五节 数学优化
1、使用简单的数学表达式以提高效率

下面列举的只是你所能做到的事情中的一部分，显而易见但决不可忽视的问题。

·a*b + a*c = a*(b+c);在不改变表达式含义的情况下，等号左边的表达式比右边的少一次乘法运算；

·b/a + c/a = (1/a)*(b+c);这是上一种形式的一种变形，不过这一次是以一个乘法和一个除法运算取代两个除法运算。在我所知道的硬件平台上，除法运算都要比乘法运算慢；

·(a || b ) && c ) = c && ( a || b );这也许不是那么明显，不过C++标准采用惰性比较。对于等号左边的情况，不管c是否为真，( a || b )表达式都会被计算，而等号右边的表达式则在c为假时不再计算( a || b )，因为此时整个表达式的值已不可能为真。
以上是一些极简单也极常见的例子，但远不是完全的，所以如果你知道一些其它的情况，不要忘记告诉我一声。

2、扬长避短
假设你有一个非常好的PentiumIII平台用于你的程序设计，那么你就拥有了32位的寄存器，但是你却要执行16位数据的操作。在某些情况下——依赖于操作的类型和溢出的可能性——你可以一次在一个寄存器中执行两次操作。这就是所谓的SIMD（Single Instruction，Multiple Data——单指令，多数据）——比如SSE，3DNOW!以及MMX——产生的原因。

在这方面我还算不上一个专家，所以我无法给出详细的例子，但是我想最好告诉你这一点，因为它可能对你有帮助。


第六节 结论：调动你的大脑

有些时候，现存的所有代码优化的方法都不能让你的程序跑得更快。有些时候，优化的主攻方向是错误的。那么退一步，重新想想你的算法，试试以另外的方式完成它。谁知道你会遇到什么事！

作为一个例子，想想排序。不管是怎样的程序设计技术，冒泡排序总是要慢于快速排序，即使它们完成的是相同的功能。