C++性能优化技术导论

C++性能优化技术导论来源：作者：冲出宇宙【介绍】本文完整的描述了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_tpreTime=GetTime();//代码段uint64_ttimeUsed=GetTime()-preTime;//改进的计算方式structTimeHelper{uint64_tpreTime;TimeHelper():preTime(GetTime()){}~TimeHelper(){g_timeUsed=GetTime()-preTime;}};//调用{TimeHelperth;//代码段}//g_timeUsed保存了耗时//得到cpu的tickcount，cpuid（重整时钟周期）消耗约300周期（如果不需要特别精确的精度，可以不执行cpuidinlineuint64_tGetTickCPU(){uint32_top;//input:eaxuint32_teax;//output:eaxasmvolatile(pushl%%ebx\n\tcpuid\n\tpopl%%ebx\n\t:=a(eax):a(op):cc);uint64_tret;asmvolatile(rdtsc:=A(ret));returnret;}//得到cpu的主频,本函数第一次调用会耗时0.01秒钟inlineuint64_tGetCpuTickPerSecond(){staticuint64_tret=0;if(ret==0){constuint64_tgap=1000000/100;uint64_tendTime=GetTimeUS()+gap;uint64_tcurTime=0;uint64_ttickStart=GetTickCPU();do{curTime=GetTimeUS();}while(curTimeendTime);uint64_ttickCount=GetTickCPU()-tickStart;ret=tickCount*1000000L/(curTime-endTime+gap);}returnret;}1.2、其他策略除了基本的计算执行次数和时间外，还有如下几种分析性能的策略：a、基于概率通过不断的中断程序，查看程序中断的位置所在的函数，出现次数最多的函数即为耗时最严重的函数。b、基于事件当发生一次cpu硬件事件的时候，某些cup会通知进程。如果事件包括L1失效多少次这种，我们就能知道程序跑的慢的原因。c、避免干扰性能测试最忌讳外界干扰。比如，内存不足，读内存变成了磁盘操作。1.3、性能分析工具-callgrindvalgrind系列工具因为免费，所以在linux系统上面最常见。callgrind是valgrind工具里面的一员，它的主要功能是模拟cpu的cache，能够计算多级cache的有效、失效次数，以及每个函数的调用耗时统计。callgrind的实现机理（基于外部中断）决定了它有不少缺点。比如，会导致程序严重变慢、不支持高度优化的程序、耗时统计的结果误差较大等等。我们编写了一个简单的测试程序，用它来测试常见性能分析工具。代码如下：//计算最大公约数inlineintgcd(intm,intn){PERFOMANCE(gcd);//全局计算耗时的defineintd=0;do{d=m%n;m=n;n=d;}while(d0);returnm;}//主函数intmain(){intg=0;uint64_tpretime=GetTickCPU();for(intidx=1;idx1000000;idx++)g+=gcd(1234134,idx);uint64_ttime=GetTickCPU()-pretime;printf(%d,%lld\n,g,time);return0;}callgrind运行的结果如下：我们把输出的结果在windows下用callgrind的工具分析，得到如下结果：1.4、g++性能分析gprof是g++自带的性能分析工具（gnuprofile）。它通过内嵌代码到各个函数里面来计算函数耗时。按理说它应该对高度优化代码很有效，但实际上它对-O2的代码并不友好，这个可能和它的实现位置有关系（在代码优化之后）。gprof的原理决定了它对程序影响较小。下图是同样的程序，用gprof检查的结果：我们可以看到，这个结果比callgrind计算的要精确很多。在前一章，我们对分析代码和函数性能的策略进行了介绍。本章将介绍算法在程序性能方面的作用。如果没有看过第一章的兄弟，在这里查看：第一章性能分析原理。2算法为王算法是程序的核心，一个程序的好坏，大部分是看起算法的好坏。对于一般的程序员来讲，我们无法改变系统和库的调用，只能根据规则来使用它们，我们可以改变的是我们自己核心代码的算法。算法能够十倍甚至百倍的提高程序性能。如快排和冒泡排序，在上千万规模的时候，后者比前者慢几千倍。通常情况下，有如下一些领域的算法：A）常见数据结构和算法B）输入输出C）内存操作D）字符串操作E）加密解密、压缩解压F）数学函数本文不是讲解算法和数据结构，所以，我们不展开。2.1选择算法程序里面使用最多的是检索和排序。map是一种很通用的结构（如c++里面的std::map或者java的TreeMap），一般的语言都是用红黑树来实现。红黑树是一种读写性能比较均衡的平衡二叉树。对于排序来说，std::sort采用的是改进的quicksort算法，即introsort。这种算法在递归层次较深的时候，改用堆排序，从而避免了快排进入“陷阱”（即O(N)复杂度）。Introsort是公认的最好的快速排序算法。平常的排序用introsort即可，但在遇到大规模字符串排序的时候，更好的一个策略是采用基数排序。笔者的经验是，千万量级时，基数排序在字符串领域比introsort快几十倍。有很多研究论文探讨基数排序在字符串领域的应用，大家可以去看看，如：EfficientTrie-BasedSortingofLargeSetsOfStrings。在某些情况下，如果数组基本有序的话，可能希尔排序也是一个好选择。希尔排序最重要的是其每次选择的数据间隔，这个方面有专门的研究可以参考。至于其他的特殊算法，如多个有序数组归并等等，大家可以在实际情况中灵活应变。2.2算法应用优化策略在实际应用中，有一些基本的优化策略可以借鉴。如：A）数组化这条策略的逻辑很简单：访问数组比访问其他结构（如指针）更快。基于这种考虑，我们可以把树结构变成数组结构。数组平衡树，它把一个通常的平衡树修改为数组的形式，但编程比较复杂。双数组Trie树，用2个或者多个数组来描述Trie树，因为trie树是一个多叉树，变成数组后，性能可以提高10多倍。数组hash，hash表用数组描述，最方面最有名的结构是bloomfilter和cuckoohash。参考：双数组Trie树参考：bloom-filterB）大节点化如果一个节点（树或者链表等）长度太小，那么单个数据命中cpucache的概率就很低。考虑到cpucacheline的长度（如64字节），我们需要尽量把一个节点存放更多的数据。B树就是这样的一种结构，它一个节点保存了大量连续数据，能有效利用cache。JudyArray也是通过谨慎安排树节点的长度来利用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.1gcc支持的优化技术1)函数内联函数调用的过程是：压入参数到堆栈、保护现场、调用函数代码、恢复现场。当一个函数被大量调用的时候，函数调用的开销特别巨大。函数内联是指把这些开销都去除，而直接调用代码。函数内联的不好之处是难以调试，因为函数实际上已经不