C++性能优化技术导论.doc

C+性能优化技术导论来源：/a/zh_CN/date/20110824作者：冲出宇宙【介绍】本文完整的描述了C+语言的性能优化方法，从编译器、算法、语言特性、硬件、Linux等多个角度去考虑问题，文章技术含量很高，值得一看。【目录】第一章 性能优化原理第二章 善用编译器第三章 算法为王第四章 c+语言特性第五章 理解硬件第六章 linux系统1、性能优化原理在谈论性能优化技术之前，有几点大家一定要明确。第一点是必须有编写良好的代码，编写的很混乱的代码（如注释缺乏、命名模糊），很难进行优化。第二点是良好的构架设计，性能优化只能优化单个程序，并不能够优化蹩脚的构架。不过，网络如此发达，只要不是自己乱想的构架，只要去积极分析别人的成功构架，大家几乎不会遇到蹩脚的构架。 1.1、计算函数、代码段调用次数和耗时函数的调用次数比较好说，用一个简单的计数器即可。一个更加通用的框架可能是维护一个全局计数，每次进入函数或者代码段的时候，给存储的对应计数增加1。为了精确的计算一段代码的耗时，我们需要极高精度的时间函数。gettimeofday是其中一个不错的选择，它的精度在1us，每秒可以调用几十万次。注意到现代cpu每秒能够处理上G的指令，所以1us内cpu可以处理几千甚至上万条指令。对于代码长度少于百行的函数来说，其单次执行时间很可能小于1us。目前最精确的计时方式是cpu自己提供的指令：rdtsc。它可以精确到一个时钟周期（1条指令需要消耗cpu几个时钟周期）。我们注意到，系统在调度程序的时候，可能会把程序放到不同的cpu核心上面运行，而每个cpu核心上面运行的周期不同，从而导致了采用rdtsc时，计算的结果不正确。解决方案是调用linux系统的sched_setaffinity来强制进程只在固定的cpu核心上运行。有关耗时计算的参考代码：/ 通常计算代码耗时uint64_t preTime = GetTime();/代码段uint64_t timeUsed = GetTime() - preTime;/ 改进的计算方式struct TimeHelperuint64_t preTime;TimeHelper():preTime(GetTime()TimeHelper()g_timeUsed = GetTime() - preTime;/ 调用TimeHelper th;/ 代码段/ g_timeUsed保存了耗时/ 得到cpu的tick count，cpuid（重整时钟周期）消耗约300周期（如果不需要特别精确的精度，可以不执行cpuidinline uint64_t GetTickCPU()uint32_t op; / input: eaxuint32_t eax; / output: eaxasm volatile( pushl %ebx ntcpuid nt popl %ebx nt : =a(eax) : a(op) : cc );uint64_t ret;asm volatile (rdtsc : =A (ret);return ret;/ 得到cpu的主频, 本函数第一次调用会耗时0.01秒钟inline uint64_t GetCpuTickPerSecond()static uint64_t ret = 0;if(ret = 0)const uint64_t gap = 1000000 / 100;uint64_t endTime = GetTimeUS() + gap;uint64_t curTime = 0;uint64_t tickStart = GetTickCPU();docurTime = GetTimeUS();while(curTime 0);return m;/ 主函数int main()int g = 0;uint64_t pretime = GetTickCPU();for(int idx = 1; idx 1000000;idx +)g += gcd(1234134,idx);uint64_t time = GetTickCPU() - pretime;printf(%d,%lldn, g, time);return 0;callgrind运行的结果如下：我们把输出的结果在windows下用callgrind的工具分析，得到如下结果：1.4、g+性能分析gprof是g+自带的性能分析工具（gnu profile）。它通过内嵌代码到各个函数里面来计算函数耗时。按理说它应该对高度优化代码很有效，但实际上它对-O2的代码并不友好，这个可能和它的实现位置有关系（在代码优化之后）。gprof的原理决定了它对程序影响较小。下图是同样的程序，用gprof检查的结果： 我们可以看到，这个结果比callgrind计算的要精确很多。在前一章，我们对分析代码和函数性能的策略进行了介绍。本章将介绍算法在程序性能方面的作用。如果没有看过第一章的兄弟，在这里查看：第一章 性能分析原理。2 算法为王算法是程序的核心，一个程序的好坏，大部分是看起算法的好坏。对于一般的程序员来讲，我们无法改变系统和库的调用，只能根据规则来使用它们，我们可以改变的是我们自己核心代码的算法。算法能够十倍甚至百倍的提高程序性能。如快排和冒泡排序，在上千万规模的时候，后者比前者慢几千倍。通常情况下，有如下一些领域的算法：A）常见数据结构和算法B）输入输出C）内存操作D）字符串操作E）加密解密、压缩解压F）数学函数本文不是讲解算法和数据结构，所以，我们不展开。2.1 选择算法程序里面使用最多的是检索和排序。map是一种很通用的结构（如c+里面的std:map或者java的TreeMap），一般的语言都是用红黑树来实现。红黑树是一种读写性能比较均衡的平衡二叉树。对于排序来说，std:sort采用的是改进的quicksort算法，即intro sort。这种算法在递归层次较深的时候，改用堆排序，从而避免了快排进入“陷阱”（即O(N)复杂度）。Introsort是公认的最好的快速排序算法。平常的排序用introsort即可，但在遇到大规模字符串排序的时候，更好的一个策略是采用基数排序。笔者的经验是，千万量级时，基数排序在字符串领域比introsort快几十倍。有很多研究论文探讨基数排序在字符串领域的应用，大家可以去看看，如：Efficient Trie-Based Sorting of Large Sets Of Strings。在某些情况下，如果数组基本有序的话，可能希尔排序也是一个好选择。希尔排序最重要的是其每次选择的数据间隔，这个方面有专门的研究可以参考。至于其他的特殊算法，如多个有序数组归并等等，大家可以在实际情况中灵活应变。2.2 算法应用优化策略在实际应用中，有一些基本的优化策略可以借鉴。如：A）数组化这条策略的逻辑很简单：访问数组比访问其他结构（如指针）更快。基于这种考虑，我们可以把树结构变成数组结构。数组平衡树，它把一个通常的平衡树修改为数组的形式，但编程比较复杂。双数组Trie树，用2个或者多个数组来描述Trie树，因为trie树是一个多叉树，变成数组后，性能可以提高10多倍。数组hash，hash表用数组描述，最方面最有名的结构是bloom filter和cuckoo hash。参考：双数组Trie树参考：bloom-filterB）大节点化如果一个节点（树或者链表等）长度太小，那么单个数据命中cpu cache的概率就很低。考虑到cpu cache line的长度（如64字节），我们需要尽量把一个节点存放更多的数据。B树就是这样的一种结构，它一个节点保存了大量连续数据，能有效利用cache。Judy Array也是通过谨慎安排树节点的长度来利用cache。列表结构，一个节点存放多个数据，也能提高cache命中率。2.3 内存管理算法常见的内存管理算法有很多，如First-Fit、Best-Fit、Buddy-system、Hal-Fit。每个程序根据自己的特点会采用不同的算法，没有绝对好的算法。比如，内核可能采用Buddy-System。有1个比较经典的算法大家需要清楚，即c语言的内存分配malloc算法。我们目前在各种系统中看到的算法，比如memcached、nginx等，都是这种算法的简单变形。参考：mallocmalloc算法根据空闲内存块大小进行分段，每个段有一个字节范围，在这个范围内的空闲内存块都挂在对应链表上面。分配内存的时候，先找到对应的段，然后取链表的第一个内存块分配即可。TLSF算法是号称最好的内存分配算法。它也是malloc算法的一种变形。参考：tlsf2.4 库的选择毫无疑问，首选glibc/stl库，因为他们被论证多年，并且，同样的算法，很难写出更好更快的代码。第二可以考虑boost库，但建议只用那些最常见的功能。ACML和MKL也是一种高性能的库，他们对向量计算很友好。对于各种开源库，如glib/apr/ace/gsl/crypto+等等，必须考虑它们开源的协议，避免使用商业收费的协议。对于安装服务器比例不高的库，也尽量不要使用，因为开源库代码都不加什么注释，出错很难查。在前一章，我们对常见算法的选择做了些简单的说明。本章将介绍g+编译器在性能优化中的重要作用。如果没有看过第二章的兄弟，在这里查看：第二章 算法为王。3 善用编译器算法能够十倍、几十倍的提高程序性能，但当算法已经很难改进时，还有一种简单的办法提高程序性能，那就是微调编译器。利用编译器提供的各种功能，你能够轻松的提高几倍的程序性能。大家要记住的是，编译器绝对比想象的要强大的多。编写编译器的人大都是十年、几十年代码编写经验的科学家！你能简单想到的，他们都已经想到过了。普通的编译器，可以支持大部分已知的优化策略以及多媒体指令。至于哪个编译器更好？大部分人的观点是：intel。Intel毕竟是最优秀的cpu提供者，他们的编译器考虑了很多cpu的特性，跑的更快。但目前intel编译器有一些比较弱智的地方，即它只识别自己的cpu，不是自己的cpu，就认为是最差的i386-i686机器，从而不能在amd等平台上面支持sse功能。我们在linux上面写代码，一般更加喜欢流行的编译器，比如gcc。Gcc的优点是它更新快，开源，bug修改迅速。正因为他更新快，所以它能够支持部分C03的规范。3.1 gcc支持的优化技术1) 函数内联函数调用的过程是：压入参数到堆栈、保护现场、调用函数代码、恢复现场。当一个函数被大量调用的时候，函数调用的开销特别巨大。函数内联是指把这些开销都去除，而直接调用代码。函数内联的不好之处是难以调试，因为函数实际上已经不存在了。2) 常量预先计算a=b+1000*16对于这段代码，程序会预先计算1000*16，从而变成：a=b+160003) 相同子串提取a=(b+1)*(b+1)这里，b+1需要计算2次，可以只用计算一次：tmp=b+1a=tmp*tmp4) 生存周期分析这是一个比较高级的技术。假设有代码：a=b+1c=a+1在执行的时候，因为第二句依赖第一句，所以2句是线性执行。但编译器其实可以知道，c就是等于b+2，所以代码变成：a=b+1c=b+2这样，这2句就没有任何关系来了，执行的时候，cpu可以并行执行它们。5) 清除跳转看如下代码：int func()int ret = 0;if(xxx)ret=5;else if(yyy)ret=6;return ret;当条件xxx满足的时候，程序还会跳到下面执行，但其实是没有必要的。编译器会把它变成：int func()if(xxx)return 5;else if(yyy)return 6;6) 循环展开循环由几个部分组成：计数器赋值、计算器比较、跳转。每次循环，后面2步都是必须的消耗。把循环内的代码拷贝多份，可以大大减少循环的次数，节约后面2步的耗时。参考：for(int counter=0;counter4;count+)xxx;可以变成：xxx;xxx;xxx;xxx;编译器不仅仅可以展开普通循环，它还能展开递归函数。原理是一样的，递归其实是一个不定长的借用了堆栈的循环。7) 循环内常量移除for(int idx=0;idx100;idx+)aidx=aidx*b*b;因为b*b在循环体内的值固定（常量），所以代码可以变成：tmp=b*b;for(int idx=0;idx100;idx+)aidx=aidx*tmp;8) 并行计算大家都知道，现代cpu支持超流水线技术，同时可以执行多条语句。多条语句能否同时执行的限制是不能互相依赖。编译器会自动帮我们把看起来单线程执行的代码，变成并行计算，参考：d=a+b;e=a+d+f;可以变成：tmp=a+f;d=a+b;e=d+tmp;9) 表达式简化当年笔者在学习离散数学和数字电路的时候，总被眼花缭乱的布尔运算简化题目难倒。gcc终于让我松了一口气。参考：!a & !b这句需要3步执行，但变成：!(a | b)只需要2步执行。3.2 gcc重要优化选项1) 内联 -finline-small-functions内联比较小的函数。-O2选项可以打开。 -findirect-inlining间接内联，可以内联多层次的函数调用。-O2选项可以打开。 -finline-functions内联所有可以内联的函数。-O3选项可以打开。 -finline-limit=N可以进行内联的函数的最小代码长度。注意，这里是伪代码，不是真实代码长度。伪代码是编译器经过处理后的代码。带inline等标志的函数，默认300行代码即可内联，不带的默认50行代码。和这个相关的选项是max-inline-insns-single和max-inline-insns-auto。 max-inline-insns-recursive-auto内联递归函数时，函数的最大代码长度。 large-function-insns、large-function-growth、large-unit-insns等函数内联的副作用是它导致代码变多，程序变长。这里的几个参数可以控制代码的总长度，避免编译后出现巨大的程序，影响性能和浪费资源。2) -fomit-frame-pointer不采用标准的ebp来记录堆栈指针，节省了一个寄存器，并且代码会更短。但据说在某些机器上面会导致debug模式出错。实际测试表明，在gcc4.2.4以下，O2和O3都无法打开这个选项。3) -fwhole-program把代码当做一个最终交付的程序来编译，即明确指定了不是编译库。这个时候，编译器可以使用更多的static变量，来加快程序速度。4) mmx/ssex/avx多媒体指令，主要支持向量计算。一般来说，-march=i686、-mmx、-msse、-msse2是目前机器都支持的指令。除了基本的多媒体支持外，gcc编译器还支持-ftree-vectorize，这个选项告诉编译器自动进行向量化，也是-O3支持的选项。多说几句。在平常的使用中，多媒体指令不是很常见（除非游戏）。如果你有几个位表（bitset），它们需要进行各种位操作的话，多媒体指令还是挺有效果滴。3.3 gcc大杀器-profile driven optimize这是比较晚才出现的技术。其基本原理是：根据实际运行情况，缩短hot路径的长度。编译器通过加入各种计数器来监控程序的运行，然后根据计算出来的实际访问路径情况，来分析hot路径，并且缩短其长度。根据gcc开发者的说法，这种技术可以提高20-30%的运行效率。其使用方式为： 编译代码，加上-fprofile-generate选项 到正式环境一段时间 当程序退出后，会产生一个分析文件 利用这个分析文件，加上-fprofile-use，重新编译一次程序举个例子来说：a=b*5;如果编译发现b经常等于10，那么它可以把代码变成：a=50;if(b != 10)a=b*5;从而在大多数情况下，避免了乘法消耗。3.4 gcc支持的优化属性（_attribute_） aligned可以设置对齐到64字节，和cpu的cache line看齐 fastcall如果函数调用的前面2个参数是整数类型的话，这个选项可以用寄存器来传递参数，而不是用常规的堆栈 pure函数是纯粹的函数，任何时刻，同样的输入，都会有同样的输出。可以很方便依据概率来优化它。3.5 gcc其他优化技术 #pragma pack()对齐到一个字节，节省内存 _builtin_expect直接告诉编译器表达式最可能的结果，方便优化 编译带debug信息的小文件以下代码能够大大减少编译后程序大小，同时保留debug信息。其原理是外链一个带debug的版本。g+ tst.cpp -g -O2 -pipecopy a.out a.gdbstrip -strip-debug a.outobjcopy -add-gnu-debuglink=a.gdb a.out在前一章，我们对gcc编译器的性能优化策略进行了简单描述。本章将介绍和c+语言相关的性能优化技术。如果没有看过第二章的兄弟，在这里查看：第二章 善用编译器。4 C+代码优化C+语言博大精深，作为一个不到10年的使用者，笔者并没有多少经验，只能通过学习，看源码来形成一些自己的想法。4.1 变量存储1、数据区可执行文件包含多个区域，有代码区，数据区等。一般的c+编译器，会把全局变量、static变量、float/double/string常量、switch跳表、初始化变量列表、虚函数表等存放到数据区域。int变量一般会存储在代码区，和指令放到一起。略解释一下初始化变量列表：int d=1,2,3;2、堆栈区堆栈区域保存函数调用、上下文、局部变量。因为局部变量存储在堆栈区，所以访问局部变量很可能会命中cpu的cache，其速度很快。3、堆申请的内存（如通过new）。4.2 变量优化1、使用成员初始化和构造初始化列表它们都可以避免2次赋值（即初始化后再赋值）。如：pubilc C(): x(10)和std:string str(java);避免使用：std:string str=java;2、堆栈最快上面已经说过，因为cache的原因，堆栈变量访问速度很快。 缩短变量周期让变量更快速的结束，有2个好处：占用的位置可以给下面的变量使用、编译器甚至可以用寄存器来存储变量。 延期申请变量距离上一个使用过的变量近，被cache概率高。3、参数传递为了降低函数调用的开销，当有多个参数时，最好把参数组合成一个结构。4、返回变量 返回构造形式避免2次拷贝。如：return string(java);要比return java;更快。 用引用代替返回避免构造对象。在函数调用的时候，把需要返回的对象都用引用传递进来。如：void func(Object& retObj);5、变量紧密定义关联度很高的变量可以定义在一起。举例来说：int aN,bN;for(int idx=0;idxN;idx+)aidx = bidx;修改成：struct int a,b; dN;for(int idx=0;idxN;idx+)didx.a=didx.b;后者因为a,b紧密定义在一起，其访问对cache更友好。6、类/结构成员顺序因为默认对齐的原因，成员变量的顺序对对象的空间占用有一定影响。一般把变量按照字节大小从前往后放。比如：structdouble d;int i;short s;bool b;其size是16字节。但：structbool b;double d;short s;int i;其size是20字节。例外的是数组成员。一般认为数组成员应该往后放。这是因为访问其他变量的时候，相对偏移（结构的初始位置）比较小，代码更短。如：mov eax, ebp+10h 显然比 mov eax, ebp+256h 实际代码要短。4.3 函数内联函数内联作为编译器最大最好的优化选项，无论在哪里都值得探讨一番。函数内联的好处是节省了保护现场和返回值的开销。编译器并不是万能的，有些函数很容易进行内联，有些函数则很难进行内联。对编译器友好的函数，一般代码比较短，函数没有递归逻辑。对编译器不友好的函数，显然就是指：函数指针调用、深度递归、虚函数。函数指针调用，会让编译器不知道真实的函数在哪里，既然都不知道函数在哪里，自然无法内联了。虚函数也是一样的问题，编译器不清楚调用的方法在哪里。有一种策略可以把虚函数变成可以内联的函数，下面在重点讨论这个策略。假设我们的程序如下：struct CParent virtual int f() return 0;struct CChild1: CParentint f()return 1;struct CChild2: CParentint f()return 2;调用语句如下：int count=0;vector ds;vector:iterator iter=ds.begin();while( iter !=ds.end()count += (*iter)-f();iter +;毫无疑问，程序在编译的时候，不可能知道f函数到底是CChild1:f还是CChild2:f。我们通过加一个内置的type，来明确告诉编译器到底是f是哪个真正的函数：struct CParent int type; virtual int f() return 0;struct CChild1: CParent CChild1()type=1; int f()return 1;struct CChild2: CParent CChild2() type=2; int f()return 2;inline int f(CParent* p)switch(p-type)case 1:return (CChild1*)p)-CChild1:f();case 2:return (CChild2*)p)-CChild2:f();return 0;/ 调用代码int count=0;vector ds;vector:iterator iter=ds.begin();while( iter !=ds.end()count += f(*iter);iter +;我们仅用一个switch语句就节约了函数调用的各种开销，很值得。事实证明，这种策略可以极大的提高程序效率。4.4 switch优化switch有3种替换模式： if用if来替换switch。当switch的判断值数量少时，这种策略比较高效。 Jump table，跳表用一个数组存储case包含的代码，而直接用case的值来跳转到代码位置。如：switch(d)case 0:xxx;break;case 1:yyy;break;.变成：addr=addr_xxx, addr_yyy;jump addrd;但这个策略只适合判断的值比较连续的情况，这是因为数组下标连续。 Lookup table，查找表查找表适合简单的逻辑，可以预先计算结果，然后直接根据某种逻辑返回结果。但一般需要编程者自己完成设计。比如：ret =a,b,creturn retd;最后大家看一下switch语句的独特用法：4.5 最大概率路径最短化这次策略的思想我们多次提到。有几种常见的方式来达到这个目的： switch/if/?x:y把最常见的情况放在前面，减少其比较次数。 布尔表达式在&表达式时，把最不容易为true的放在前面。在|表达式时，把最容易为true的放在前面。 函数内cache可以用一个变量存储最常见的返回结果。如：static int comm_input, comm_output;if(input = comm_input)return comm_output;xxx;考虑到计算最常见的输入需要很多额外操作，故我们可以只存储最上一次的结果。4.6 异常C+的异常有不少诟病，比如没有finally，出错时难以释放资源。它还需要大量额外的资源，因为需要保存那些变量没有被析构等信息。我们的建议是不使用异常，尽量通过自定义log以及assert的方式来处理程序异常。在前一章，我们对c+语言和性能有关的部分进行了简单描述。本章将介绍和和cpu硬件相关的性能优化技术。5 理解硬件 Intel的cpu外部结构由著名的CPU、南北桥组成。北桥连接的都是快速设备，如内存和显卡。南桥则是低速设备，如磁盘、声卡等等。图 支持intel的主板 图intel cpu基本构架图 AMD的cpu外部结构有所不同。其socket的接口为AM3，其内存控制器在cpu里面，可以直接连接内存。图 支持AMD的主板 图 amd K10构架 5.1 理解内存我们现在使用的一般是DDR3代内存条，台式机的内存一般有240针，但内存的实际数据位数只有64位，即8个字节。 图 台式机内存脚的说明 一般来说，内存的速度比cpu的速度慢。为了提高内存的数据传输速度，有人设计了多通道模式。在这种模式下，内存的传输速度可以加倍。多通道有双通道和三通道之说，后者仅最新的Intel cpu支持。多通道又分为Ganged和Unganged模式。前者每次提供128位数据，后者每次提供64位数据，但容许同时读取。实际结果表明，后者对多核多线程的服务器更加有效。（注：cpuz会把unganged模式识别为单通道+） 图 多通道 5.2 理解cpu cache现代cpu包含多级cache，一般为L1-L3共3级。下图是笔者对cpu cache的分析图： 图 cpu cache分析 从图中我们可以看到，内存控制器（IMC）通过多个通道和内存（memory stick）连接。每个通道的位宽是64。内存控制器和L3 cache的位宽是96。为啥是94位呢？这是因为在双通道模式下，内存控制器的进入位宽是128，而IMC的频率一般为内存频率的1.5倍（实际数据），如果出位宽是96，则IMC的频率差不多刚好够用（需要为内存频率的1.33倍）。 5.3 cache line的解释有几点大家要明白：n 内存位宽是64；n Cpu Lx cache line是64字节；Cache每次消耗8个时钟读取一个数据（从内存中）。在双通道ganged模式下，只需要4个时钟的读取时间。n Lx cache N-way的概念内存中的数据，只能固定存储在Lx cache中的某些位置。对于32way的cache来说，每块内存中的数据（即把内存按照cache line的长度切分）只能在32个位置中出现。这样的目的是加快cache的查找。 5.4 内存速度内存的速度很难计算，毕竟不是所有的指令都能让cpu和内存之间的通道全速工作。好在mov/movq指令可以比较全面的利用cpu流水线，能够测试出大概的内存速度。对于DDR3 1333的内存和北桥（或者IMC）速度为1995M的cpu，我们大致可以计算如下： DDR3 1333, unganged dual channel理论带宽：1333*8*2=21G/s，访问延迟：几十个ns。 L3 cache, NB-speed(1995M), on-die, 48-way理论带宽：1995*8=16G/s，访问延迟：10ns。 L2 cache, full-speed, on-die理论带宽2800*8=22G/s，访问延迟：几ns。 L1 cache理论带宽未知，访问延迟/proc/sys/vm/drop_caches第一条语句是建议系统不要使用swap，第二条语句是让系统清理cache，以便释放更多内存。但第一条并不能够绝对阻止swap（因为只是建议）。mlockall是程序比较常用的锁定内存的函数。它能够防止内存页被置换到swap。6.4 避免多线程写磁盘多线程大量写入磁盘文件，如果是同一个文件有多个写入者，会导致同步的麻烦；如果是不同的文件，也会因为大量IO导致机器假死（如不接收网络连接）。通过调低vm.dirty_ratio和vm.dirty_background_ratio参数来降低系统文件写缓存能力，减少写入时大量的cpu耗用。题外