C++性能優(yōu)化技術(shù)導(dǎo)論

1、C+生能優(yōu)化技術(shù)導(dǎo)論來源：http:/www.whysearch.Org/a/zh_CN/date/20110824作者：沖出宇宙【介紹】本文完整的描述了 C+語(yǔ)言的性能優(yōu)化方法，從編譯器、算法、語(yǔ)言特性、硬件、Linux等多個(gè)角度去考慮問題，文章技術(shù)含量很高，值得一看?！灸夸洝康谝徽滦阅軆?yōu)化原理第二章善用編譯器第三章算法為王第四章C+語(yǔ)言特性第五章理解硬件第六章linux系統(tǒng)1、性能優(yōu)化原理在談?wù)撔阅軆?yōu)化技術(shù)之前，有幾點(diǎn)大家一定要明確。第一點(diǎn)是必須有編寫良好的代碼， 編寫的很混亂的代碼 （如注釋缺乏、命名模糊），很難進(jìn)行優(yōu)化。第二點(diǎn)是良好的構(gòu)架設(shè)計(jì)， 性能優(yōu)化只能優(yōu)化單個(gè)程序，并不能夠優(yōu)化蹩

2、腳的構(gòu)架。不過，網(wǎng)絡(luò)如此發(fā)達(dá)，只要不是自己亂想的構(gòu)架，只要去積極分析別人的成功構(gòu)架，大家?guī)缀醪粫?huì)遇到蹩腳的構(gòu)架。1.1、計(jì)算函數(shù)、代碼段調(diào)用次數(shù)和耗時(shí)函數(shù)的調(diào)用次數(shù)比較好說，用一個(gè)簡(jiǎn)單的計(jì)數(shù)器即可。一個(gè)更加通用的框架可能是維護(hù) 一個(gè)全局計(jì)數(shù)，每次進(jìn)入函數(shù)或者代碼段的時(shí)候，給存儲(chǔ)的對(duì)應(yīng)計(jì)數(shù)增加1。為了精確的計(jì)算一段代碼的耗時(shí)，我們需要極高精度的時(shí)間函數(shù)。gettimeofday是其中一個(gè)不錯(cuò)的選擇，它的精度在1us,每秒可以調(diào)用幾十萬次。注意到現(xiàn)代cpu每秒能夠處理上G的指令，所以1us內(nèi)cpu可以處理幾千甚至上萬條指令。對(duì)于代碼長(zhǎng)度少于百行的函數(shù)來說，其單次執(zhí)行時(shí)間很可能小于 1us。目前最精

3、確的計(jì)時(shí)方式是cpu自己提供的指令：rdtsco它可以精確到一個(gè)時(shí)鐘周期（1條指令需要消耗cpu幾個(gè)時(shí)鐘周期）。我們注意到，系統(tǒng)在調(diào)度程序的時(shí)候，可能會(huì)把程序放到不同的cpu核心上面運(yùn)行，每個(gè)cpu核心上面運(yùn)行的周期不同，從而導(dǎo)致了采用rdtsc時(shí)，計(jì)算的結(jié)果不正確。解決方案是調(diào)用linux系統(tǒng)的sched_setaffinity來強(qiáng)制進(jìn)程只在固定的cpu核心上運(yùn)行。有關(guān)耗時(shí)計(jì)算的參考代碼：II通常計(jì)算代碼耗時(shí)uint64_t preTime = GetTime();II代碼段uint64_t timeUsed = GetTime() - preTime;II改進(jìn)的計(jì)算方式struct Tim

4、eHelper uint64_t preTime;TimeHelper():preTime(GetTime()TimeHelper()g_timeUsed = GetTime() - preTime;；/調(diào)用TimeHelper th;/代碼段/ g_timeUsed 保存了耗時(shí)/得到cpu的tick count, cpuid (重整時(shí)鐘周期)消耗約300周期(如果不需要特別精確的精度，可以不執(zhí)行cpuidinline uint64_t GetTickCPU()uint32_t op; / input: eaxuint32_t eax; / output: eaxasm volatile(&q

5、uot;pushl %ebxnt""cpuidnt""popl %ebxnt":"=a"(eax): "a"(op): "cc");uint64_t ret;asm volatile ("rdtsc" : "=A" (ret);return ret;/得到cpu的主頻，本函數(shù)第一次調(diào)用會(huì)耗時(shí) 0.01秒鐘inline uint64_t GetCpuTickPerSecond()static uint64_t ret = 0;if(ret = 0)

6、const uint64_t gap = 1000000 / 100;uint64_t endTime = GetTimeUS() + gap;uint64_t curTime = 0;uint64_t tickStart = GetTickCPU();docurTime = GetTimeUS();while(curTime < endTime);uint64_t tickCount = GetTickCPU() - tickStart;ret = tickCount * 1000000L / (curTime - endTime + gap); return ret;1.2、其他策略

7、除了基本的計(jì)算執(zhí)行次數(shù)和時(shí)間外，還有如下幾種分析性能的策略：a、基于概率通過不斷的中斷程序， 查看程序中斷的位置所在的函數(shù)，出現(xiàn)次數(shù)最多的函數(shù)即為耗時(shí)最嚴(yán)重的函數(shù)。b基于事件當(dāng)發(fā)生一次cpu硬件事件的時(shí)候，某些 cup會(huì)通知進(jìn)程。如果事件包括 L1失效多 少次這種，我們就能知道程序跑的慢的原因。c、避免干擾性能測(cè)試最忌諱外界干擾。比如，內(nèi)存不足，讀內(nèi)存變成了磁盤操作。性能分析原理0基于概率0每隔一段時(shí)間（幾ms ）中斷一次（如加入int$3）0原理：訪問多的代碼段中斷的次數(shù)也多0基于事件0 cache失效若干次時(shí)產(chǎn)生 0如L1失效1000次0 般需要cpu支持0避免干擾0內(nèi)存缺頁(yè)0足夠內(nèi) 存+

8、預(yù)先讀取0 10等待0網(wǎng)絡(luò).磁盤、用戶I13、性能分析工具-callgrindvalgrind 系列工具因?yàn)槊赓M(fèi)，所以在 linux系統(tǒng)上面最常見。callgrind是valgrind工具里面的一員，它的主要功能是模擬cpu的cache,能夠計(jì)算多級(jí) cache的有效、失效次數(shù),以及每個(gè)函數(shù)的調(diào)用耗時(shí)統(tǒng)計(jì)。callgri nd 的實(shí)現(xiàn)機(jī)理(基于外部中斷)決定了它有不少缺點(diǎn)。比如，會(huì)導(dǎo)致程序嚴(yán)重 變慢、不支持高度優(yōu)化的程序、耗時(shí)統(tǒng)計(jì)的結(jié)果誤差較大等等。性能分析工具ca llgrind0 valgrind+calfgrind0功能0 模擬L1” Dt IL2 cache ( L3不彳0計(jì)算函數(shù)調(diào)月

9、目次數(shù)，耗時(shí)比例0缺點(diǎn)0 很慢 20-100f0對(duì)optimize版肆0耗時(shí)計(jì)算很不卡青確電子商務(wù)投盍弓I粘我們編寫了一個(gè)簡(jiǎn)單的測(cè)試程序，用它來測(cè)試常見性能分析工具。代碼如下: /計(jì)算最大公約數(shù)inline int gcd(int m, int n)PERFOMANCEC'gcd"); /全局計(jì)算耗時(shí)的 defineint d = 0;dod = m % n;m = n; n = d;while(d > 0);return m;/主函數(shù)int main()int g = 0;uint64_t pretime = GetTickCPU(); for(int idx = 1

10、; idx < 1000000;idx +) g += gcd(1234134,idx);uint64_t time = GetTickCPU() - pretime;printf("%d,%lldn", g, time); return 0;callgri nd 運(yùn)行的結(jié)果如下：W- -S' *' a- >"warchad» iH?aiop-jh*211: Zdat a/searchd«t*> vslfrird toai-c*lltnnd *cacheui?yes Zdat*/sewchdat*/a hout

11、 29481= Cdllind a calleraph genertinfi profiler *=29481=二 Capyrifht (C) 2002-20C8> and GNU GFVcL by Josef Heidencbrfer et al,=24Sh= Uiing UbVEH re 1970, a library Fortrimsj=29461= Copyntfit (C) 2004-2006, and GNU GPLd 旳 Oenhor+<s LLPt -=29481= Usinf (rirxl-3*dt0, » dtamc binary 1幗1廣5已毗蚊15

12、 "anewa" * =29481= Ckipyrifiht <C) 20002006, And Q<J GPL'cL by Julian Sevard et al* =29481= For »q常 Retail竿* rervn-v=294fll=w=29481= For interactive control, run F call fir ind.control -+/M999e2,H%9035428,1000000cpu speed： 1 町450旳49=29481*=29461= Events： Ir Dr Dw I Imp Dlur

13、DImi I&r D2nr AoCosti 事 1 AcCottS SfCobsS=29481= CollecM : 106416195 5403161 7232194 1124 1146£ 50% 1101 4270 4790 46C6269 62E2G6 1023956 175664=29481= Iref 5：1O6>416J0E總別81“IIMisses：1.124294:1= L21丄 sses：1.10129481II155 rate：sectt*294SlssL21rate：o,ox23481=-=2481=Dref$：a 15375(5.483.181

14、rd97J3L194 wr>2481DI*1M«；1M62(11.466 rd5,0% wr 1L2dRiuel：9,060(4,270 rd札790 Hr-29461=DIrate：o.ix0.2X。皿）=29481= L2diuss rate；O.OOC(0.0X>0.0X >亦冷481"=2 驅(qū) 1=二L2 refs：17,6%(12,5% rd#5,0% wr)B驅(qū)1斗L2 i£tes:WU1(5,371 rd4.790 yr2481= L2 rxs rate；0,0C0亦0.09()我們把輸出的結(jié)果在windows下用callgrind

15、的工具分析，得到如下結(jié)果:電子商務(wù)玻索弓I補(bǔ)1.4、g+性能分析gprof是g+自帶的性能分析工具(gnu profile )。它通過內(nèi)嵌代碼到各個(gè)函數(shù)里面來計(jì) 算函數(shù)耗時(shí)。按理說它應(yīng)該對(duì)高度優(yōu)化代碼很有效，但實(shí)際上它對(duì)-02的代碼并不友好，這個(gè)可能和它的實(shí)現(xiàn)位置有關(guān)系(在代碼優(yōu)化之后)。gprof的原理決定了它對(duì)程序影響較小。F圖是同樣的程序，用gprof檢查的結(jié)果:我們可以看到，這個(gè)結(jié)果比callgri nd計(jì)算的要精確很多。本章將介紹算法在程序性能在前一章，我們對(duì)分析代碼和函數(shù)性能的策略進(jìn)行了介紹。 方面的作用。如果沒有看過第一章的兄弟，在這里查看：第一章性能分析原理。2算法為王算法是程

16、序的核心， 一個(gè)程序的好壞，大部分是看起算法的好壞。 對(duì)于一般的程序員來 講，我們無法改變系統(tǒng)和庫(kù)的調(diào)用， 只能根據(jù)規(guī)則來使用它們， 我們可以改變的是我們自己 核心代碼的算法。算法能夠十倍甚至百倍的提高程序性能。如快排和冒泡排序，在上千萬規(guī)模的時(shí)候，后者比前者慢幾千倍。通常情況下，有如下一些領(lǐng)域的算法：A）常見數(shù)據(jù)結(jié)構(gòu)和算法B）輸入輸出C）內(nèi)存操作D）字符串操作E）加密解密、壓縮解壓F）數(shù)學(xué)函數(shù)本文不是講解算法和數(shù)據(jù)結(jié)構(gòu)，所以，我們不展開。2.1選擇算法程序里面使用最多的是檢索和排序。map是一種很通用的結(jié)構(gòu)（如 C+里面的std:map或者java的TreeMap），一般的語(yǔ)言 都是用紅黑樹

17、來實(shí)現(xiàn)。紅黑樹是一種讀寫性能比較均衡的平衡二叉樹。對(duì)于排序來說，std:sort采用的是改進(jìn)的quicksort算法，即intro sort。這種算法在遞歸 層次較深的時(shí)候，改用堆排序，從而避免了快排進(jìn)入“陷阱”（即0（N）復(fù)雜度）。Introsort是公認(rèn)的最好的快速排序算法。平常的排序用introsort即可，但在遇到大規(guī)模字符串排序的時(shí)候，更好的一個(gè)策略是采用基數(shù)排序。筆者的經(jīng)驗(yàn)是，千萬量級(jí)時(shí)，基數(shù)排序在字符串領(lǐng)域比introsort快幾十倍。有很多研究論文探討基數(shù)排序在字符串領(lǐng)域的應(yīng)用，大家可以去看看，女口： Efficient Trie-BasedSorting of Large S

18、ets Of Strings 。在某些情況下，如果數(shù)組基本有序的話，可能希爾排序也是一個(gè)好選擇。希爾排序最重要的是其每次選擇的數(shù)據(jù)間隔，這個(gè)方面有專門的研究可以參考。至于其他的特殊算法，如多個(gè)有序數(shù)組歸并等等，大家可以在實(shí)際情況中靈活應(yīng)變。2.2算法應(yīng)用優(yōu)化策略在實(shí)際應(yīng)用中，有一些基本的優(yōu)化策略可以借鑒。如：A）數(shù)組化這條策略的邏輯很簡(jiǎn)單：訪問數(shù)組比訪問其他結(jié)構(gòu)（如指針）更快?；谶@種考慮， 我們可以把樹結(jié)構(gòu)變成數(shù)組結(jié)構(gòu)。數(shù)組平衡樹，它把一個(gè)通常的平衡樹修改為數(shù)組的形式，但編程比較復(fù)雜。雙數(shù)組Trie樹，用2個(gè)或者多個(gè)數(shù)組來描述 Trie樹，因?yàn)閠rie樹是一個(gè)多叉樹，變成數(shù)組后，性能可以提高

19、10多倍。數(shù)組hash，hash表用數(shù)組描述，最方面最有名的結(jié)構(gòu)是bloom filter和cuckoo hash。參考：雙數(shù)組Trie樹1579389-10【-1030-1033-1000301°00000000參考：bloom-filterHashiHash：0100001000001000001Bloom Filter由若干個(gè)Hash函數(shù)和一個(gè)bitmap數(shù)聖組或二其操作過程如 加入Key：設(shè)置bitmap的第Has加(Key)位為1這里i=L 2,k： 査詢Key是否存在：如果bitmap的第Hashk(Key)(E均為1 ?就認(rèn)為在Set中存在這里匸1,2,匕刪除Key：沒

20、有辦法B)大節(jié)點(diǎn)化如果一個(gè)節(jié)點(diǎn)(樹或者鏈表等)長(zhǎng)度太小，那么單個(gè)數(shù)據(jù)命中cpu cache的概率就很低?？紤]到cpu cache line的長(zhǎng)度(如64字節(jié))，我們需要盡量把一個(gè)節(jié)點(diǎn)存放更多的 數(shù)據(jù)。B樹就是這樣的一種結(jié)構(gòu)，它一個(gè)節(jié)點(diǎn)保存了大量連續(xù)數(shù)據(jù)，能有效利用cache。Judy Array也是通過謹(jǐn)慎安排樹節(jié)點(diǎn)的長(zhǎng)度來利用cache。列表結(jié)構(gòu)，一個(gè)節(jié)點(diǎn)存放多個(gè)數(shù)據(jù)，也能提高 cache命中率。2.3內(nèi)存管理算法常見的內(nèi)存管理算法有很多，如First-Fit、Best-Fit、Buddy-system> Hal-Fit。每個(gè)程序根據(jù)自己的特點(diǎn)會(huì)采用不同的算法，沒有絕對(duì)好的算法。比如，

21、內(nèi)核可能采用Buddy-System。有1個(gè)比較經(jīng)典的算法大家需要清楚，即c語(yǔ)言的內(nèi)存分配 malloc算法。我們目前在各種系統(tǒng)中看到的算法，比如memcached、nginx等，都是這種算法的簡(jiǎn)單變形。參考：mallocmalloc算法根據(jù)空閑內(nèi)存塊大小進(jìn)行分段，每個(gè)段有一個(gè)字節(jié)范圍，在這個(gè)范圍內(nèi)的空閑內(nèi)存塊都掛在對(duì)應(yīng)鏈表上面。分配內(nèi)存的時(shí)候，先找到對(duì)應(yīng)的段，然后取鏈表的第一個(gè)內(nèi)存塊分配即可。TLSF算法是號(hào)稱最好的內(nèi)存分配算法。它也是 malloc算法的一種變形。參考：tlsf2.4庫(kù)的選擇毫無疑問，首選glibc/stl庫(kù)，因?yàn)樗麄儽徽撟C多年，并且，同樣的算法，很難寫出更好 更快的代碼。

22、第二可以考慮boost庫(kù)，但建議只用那些最常見的功能。ACM1和MKL也是一種高性能的庫(kù)，他們對(duì)向量計(jì)算很友好。對(duì)于各種開源庫(kù)，如glib/apr/ace/gsl/crypto+等等，必須考慮它們開源的協(xié)議，避免使用商業(yè)收費(fèi)的協(xié)議。對(duì)于安裝服務(wù)器比例不高的庫(kù)，也盡量不要使用，因?yàn)殚_源庫(kù)代碼都不加什么注釋，出錯(cuò)很難查。在前一章，我們對(duì)常見算法的選擇做了些簡(jiǎn)單的說明。本章將介紹g+編譯器在性能優(yōu)化中的重要作用。如果沒有看過第二章的兄弟，在這里查看：第二章算法為王。3善用編譯器算法能夠十倍、幾十倍的提高程序性能，但當(dāng)算法已經(jīng)很難改進(jìn)時(shí)，還有一種簡(jiǎn)單的辦 法提高程序性能，那就是微調(diào)編譯器。利用編譯器提

23、供的各種功能，你能夠輕松的提高幾倍 的程序性能。大家要記住的是，編譯器絕對(duì)比想象的要強(qiáng)大的多。編寫編譯器的人大都是十年、幾十年代碼編寫經(jīng)驗(yàn)的科學(xué)家！你能簡(jiǎn)單想到的，他們都已經(jīng)想到過了。普通的編譯器，可以支持大部分已知的優(yōu)化策略以及多媒體指令。至于哪個(gè)編譯器更好？大部分人的觀點(diǎn)是：in tel。I ntel畢竟是最優(yōu)秀的cpu提供者，他們的編譯器考慮了很多 cpu的特性，跑的更快。但目前 intel編譯器有一些比較弱智的地方， 即它只識(shí)別自己的 cpu，不是自己的cpu，就認(rèn)為是最差的i386-i686機(jī)器，從而不能在 amd 等平臺(tái)上面支持sse功能。我們?cè)趌inux上面寫代碼，一般更加喜歡流

24、行的編譯器，比如gcc。Gcc的優(yōu)點(diǎn)是它更新快，開源，bug修改迅速。正因?yàn)樗驴欤运軌蛑С植糠諧03的規(guī)范。3.1 gcc支持的優(yōu)化技術(shù)1) 函數(shù)內(nèi)聯(lián)函數(shù)調(diào)用的過程是：壓入?yún)?shù)到堆棧、保護(hù)現(xiàn)場(chǎng)、調(diào)用函數(shù)代碼、恢復(fù)現(xiàn)場(chǎng)。當(dāng)一個(gè)函 數(shù)被大量調(diào)用的時(shí)候，函數(shù)調(diào)用的開銷特別巨大。函數(shù)內(nèi)聯(lián)是指把這些開銷都去除，而直接調(diào)用代碼。函數(shù)內(nèi)聯(lián)的不好之處是難以調(diào)試，因?yàn)楹瘮?shù)實(shí)際上已經(jīng)不存在了。2) 常量預(yù)先計(jì)算a=b+1000*16對(duì)于這段代碼，程序會(huì)預(yù)先計(jì)算1000*16，從而變成：a=b+160003) 相同子串提取a=(b+1)*(b+1)這里，b+1需要計(jì)算2次，可以只用計(jì)算一次：tmp=b+1

25、a=tmp*tmp4) 生存周期分析這是一個(gè)比較高級(jí)的技術(shù)。假設(shè)有代碼：a=b+1c=a+1在執(zhí)行的時(shí)候，因?yàn)榈诙湟蕾嚨谝痪洌?句是線性執(zhí)行。但編譯器其實(shí)可以知道，c就是等于b+2，所以代碼變成：a=b+1c=b+2這樣，這2句就沒有任何關(guān)系來了，執(zhí)行的時(shí)候， cpu可以并行執(zhí)行它們。5) 清除跳轉(zhuǎn)看如下代碼：int func()int ret = 0;if(xxx)ret=5;else if(yyy)ret=6;return ret;當(dāng)條件xxx滿足的時(shí)候，程序還會(huì)跳到下面執(zhí)行，但其實(shí)是沒有必要的。編譯器會(huì)把它變成：int func()if(xxx)return 5;else if(y

26、yy)return 6;6) 循環(huán)展開循環(huán)由幾個(gè)部分組成：計(jì)數(shù)器賦值、計(jì)算器比較、跳轉(zhuǎn)。每次循環(huán)，后面2步都是必須的消耗。把循環(huán)內(nèi)的代碼拷貝多份，可以大大減少循環(huán)的次數(shù)，節(jié)約后面2步的耗時(shí)。參考：for(int counter=0;counter<4;count+)xxx;可以變成：xxx;xxx;xxx;xxx;編譯器不僅僅可以展開普通循環(huán)，它還能展開遞歸函數(shù)。原理是一樣的，遞歸其實(shí)是一個(gè)不定長(zhǎng)的借用了堆棧的循環(huán)。7) 循環(huán)內(nèi)常量移除for(i nt idx=0;idx<100;idx+)aidx=aidx*b*b;因?yàn)閎*b在循環(huán)體內(nèi)的值固定(常量)，所以代碼可以變成：tmp=

27、b*b;for(i nt idx=0;idx<100;idx+)aidx=aidx*tmp;8) 并行計(jì)算大家都知道，現(xiàn)代cpu支持超流水線技術(shù)，同時(shí)可以執(zhí)行多條語(yǔ)句。多條語(yǔ)句能否同時(shí)執(zhí)行的限制是不能互相依賴。編譯器會(huì)自動(dòng)幫我們把看起來單線程執(zhí)行的代碼，變成并行計(jì)d=a+b; e=a+d+f;可以變成：tmp=a+f;d=a+b;e=d+tmp;9）表達(dá)式簡(jiǎn)化當(dāng)年筆者在學(xué)習(xí)離散數(shù)學(xué)和數(shù)字電路的時(shí)候，總被眼花繚亂的布爾運(yùn)算簡(jiǎn)化題目難倒。gcc終于讓我松了一口氣。參考：!a && !b這句需要3步執(zhí)行，但變成：!（a | b）只需要2步執(zhí)行。3.2 gcc重要優(yōu)化選項(xiàng)1）內(nèi)聯(lián)

28、-finlin e-small-fu nctio ns內(nèi)聯(lián)比較小的函數(shù)。-02選項(xiàng)可以打開。-fin direct-i nlining間接內(nèi)聯(lián)，可以內(nèi)聯(lián)多層次的函數(shù)調(diào)用。-O2選項(xiàng)可以打開。-fin li ne-fu ncti ons內(nèi)聯(lián)所有可以內(nèi)聯(lián)的函數(shù)。-O3選項(xiàng)可以打開。-fin li ne-limit=N可以進(jìn)行內(nèi)聯(lián)的函數(shù)的最小代碼長(zhǎng)度。注意，這里是偽代碼，不是真實(shí)代碼長(zhǎng)度。偽代碼是編譯器經(jīng)過處理后的代碼。帶inline等標(biāo)志的函數(shù)，默認(rèn)300行代碼即可內(nèi)聯(lián)，不帶 的默認(rèn)50行代碼。和這個(gè) 相關(guān)的 選項(xiàng)是 max-inline-insns-single和max-i nli ne-i n

29、sn s-auto。max-i nli ne-i nsn s-recursive-auto內(nèi)聯(lián)遞歸函數(shù)時(shí)，函數(shù)的最大代碼長(zhǎng)度。large-function-insns、large-function-growth、large-unit-insns 等函數(shù)內(nèi)聯(lián)的副作用是它導(dǎo)致代碼變多，程序變長(zhǎng)。這里的幾個(gè)參數(shù)可以控制代碼的總長(zhǎng)度，避免編譯后出現(xiàn)巨大的程序，影響性能和浪費(fèi)資源。2）-fomit-frame-pointer不采用標(biāo)準(zhǔn)的ebp來記錄堆棧指針，節(jié)省了一個(gè)寄存器，并且代碼會(huì)更短。但據(jù)說在某 些機(jī)器上面會(huì)導(dǎo)致 debug模式出錯(cuò)。實(shí)際測(cè)試表明，在 gcc4.2.4以下，O2和O3都無法打開 這

30、個(gè)選項(xiàng)。3）-fwhole-program把代碼當(dāng)做一個(gè)最終交付的程序來編譯，即明確指定了不是編譯庫(kù)。這個(gè)時(shí)候，編譯器可以使用更多的static變量，來加快程序速度。4）mmx/ssex/avx多媒體指令，主要支持向量計(jì)算。一般來說，-march=i686、-mmx、-msse、-msse2是目前機(jī)器都支持的指令。除了基本的多媒體支持外，gcc編譯器還支持-ftree-vectorize，這個(gè)選項(xiàng)告訴編譯器自動(dòng)進(jìn)行向量化，也是-O3支持的選項(xiàng)。多說幾句。在平常的使用中，多媒體指令不是很常見（除非游戲）。如果你有幾個(gè)位表（bitset），它們需要進(jìn)行各種位操作的話，多媒體指令還是挺有效果滴。3.

31、3 gcc大殺器-profile driven optimize這是比較晚才出現(xiàn)的技術(shù)。其基本原理是：根據(jù)實(shí)際運(yùn)行情況，縮短hot路徑的長(zhǎng)度。編譯器通過加入各種計(jì)數(shù)器來監(jiān)控程序的運(yùn)行，然后根據(jù)計(jì)算出來的實(shí)際訪問路徑情況，來分析hot路徑，并且縮短其長(zhǎng)度。根據(jù)gcc開發(fā)者的說法，這種技術(shù)可以提高20-30%的運(yùn)行效率。其使用方式為：編譯代碼，加上-fprofile-generate選項(xiàng)到正式環(huán)境一段時(shí)間當(dāng)程序退出后，會(huì)產(chǎn)生一個(gè)分析文件利用這個(gè)分析文件，加上-fprofile-use，重新編譯一次程序舉個(gè)例子來說：a=b*5;如果編譯發(fā)現(xiàn)b經(jīng)常等于10,那么它可以把代碼變成：a=50;if(b !

32、= 10) a=b*5;從而在大多數(shù)情況下，避免了乘法消耗。3.4 gcc支持的優(yōu)化屬性(_attribute_)? aligned可以設(shè)置對(duì)齊到64字節(jié)，和cpu的cache line看齊? fastcall如果函數(shù)調(diào)用的前面2個(gè)參數(shù)是整數(shù)類型的話，這個(gè)選項(xiàng)可以用寄存器來傳遞參數(shù)，而 不是用常規(guī)的堆棧? pure函數(shù)是純粹的函數(shù)，任何時(shí)刻，同樣的輸入，都會(huì)有同樣的輸出。可以很方便依據(jù)概率來優(yōu)化它。3.5 gcc其他優(yōu)化技術(shù)#pragma pack()對(duì)齊到一個(gè)字節(jié)，節(jié)省內(nèi)存_built in _expect直接告訴編譯器表達(dá)式最可能的結(jié)果，方便優(yōu)化編譯帶debug信息的小文件以下代碼能夠大大

33、減少編譯后程序大小，同時(shí)保留debug信息。其原理是外鏈一個(gè)帶debug的版本。g+ tst.cpp -g -O2 -pipecopy a.out a.gdbstrip -strip-debug a.outobjcopy -add-g nu-debugli nk=a.gdb a.out在前一章，我們對(duì)gcc編譯器的性能優(yōu)化策略進(jìn)行了簡(jiǎn)單描述。本章將介紹和C+語(yǔ)言相關(guān)的性能優(yōu)化技術(shù)。如果沒有看過第二章的兄弟，在這里查看：第二章善用編譯器。C+語(yǔ)言博大精深，作為一個(gè)不到10年的使用者，筆者并沒有多少經(jīng)驗(yàn)，只能通過學(xué)習(xí)，看源碼來形成一些自己的想法。4.1變量存儲(chǔ)1、數(shù)據(jù)區(qū)可執(zhí)行文件包含多個(gè)區(qū)域，有代

34、碼區(qū)，數(shù)據(jù)區(qū)等。一般的C+編譯器，會(huì)把全局變量、static變量、float/double/string常量、switch跳表、初始化變量列表、虛函數(shù)表等存放到數(shù)據(jù) 區(qū)域。int變量一般會(huì)存儲(chǔ)在代碼區(qū)，和指令放到一起。略解釋一下初始化變量列表：int d=1,2,3;2、堆棧區(qū)堆棧區(qū)域保存函數(shù)調(diào)用、上下文、局部變量。因?yàn)榫植孔兞看鎯?chǔ)在堆棧區(qū)，所以訪問局部變量很可能會(huì)命中 cpu的cache，其速度很快。3、堆申請(qǐng)的內(nèi)存(如通過 new)。4.2變量?jī)?yōu)化1、使用成員初始化和構(gòu)造初始化列表它們都可以避免2次賦值(即初始化后再賦值)。如：pubilc C(): x(10)和std:stri ng s

35、tr("java");避免使用：std:stri ng str="java"2、堆棧最快上面已經(jīng)說過，因?yàn)?cache的原因，堆棧變量訪問速度很快。?縮短變量周期讓變量更快速的結(jié)束，有2個(gè)好處：占用的位置可以給下面的變量使用、編譯器甚至可以用寄存器來存儲(chǔ)變量。?延期申請(qǐng) 變量距離上一個(gè)使用過的變量近，被cache概率高。3、參數(shù)傳遞為了降低函數(shù)調(diào)用的開銷，當(dāng)有多個(gè)參數(shù)時(shí)，最好把參數(shù)組合成一個(gè)結(jié)構(gòu)。4、返回變量?返回構(gòu)造形式避免2次拷貝。如：retur n stri ng("java");要比retur n "java&quo

36、t;更快。?用引用代替返回避免構(gòu)造對(duì)象。在函數(shù)調(diào)用的時(shí)候，把需要返回的對(duì)象都用引用傳遞進(jìn)來。如： void fun c(Object & retObj);5、變量緊密定義關(guān)聯(lián)度很高的變量可以定義在一起。舉例來說：int aN,bN;for(i nt idx=O;idx<N;idx+)aidx = bidx;修改成：struct int a,b; dN;for(i nt idx=0;idx<N;idx+) didx.a=didx.b;后者因?yàn)閍,b緊密定義在一起，其訪問對(duì)cache更友好。6、類/結(jié)構(gòu)成員順序因?yàn)槟J(rèn)對(duì)齊的原因，成員變量的順序?qū)?duì)象的空間占用有一定影響。一般把

37、變量按照字節(jié)大小從前往后放。比如：structdouble d;int i;short s;bool b;其size是16字節(jié)。但：structbool b;double d;short s;int i;其size是20字節(jié)。例外的是數(shù)組成員。一般認(rèn)為數(shù)組成員應(yīng)該往后放。這是因?yàn)樵L問其他變量的時(shí)候，相 對(duì)偏移(結(jié)構(gòu)的初始位置)比較小，代碼更短。如：mov eax, ebp+10h 顯然比 mov eax, ebp+256h實(shí)際代碼要短。4.3函數(shù)內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)作為編譯器最大最好的優(yōu)化選項(xiàng)，無論在哪里都值得探討一番。函數(shù)內(nèi)聯(lián)的好處是節(jié)省了保護(hù)現(xiàn)場(chǎng)和返回值的開銷。編譯器并不是萬能的，有些函數(shù)很容易進(jìn)

38、行內(nèi)聯(lián)， 有些函數(shù)則很難進(jìn)行內(nèi)聯(lián)。對(duì)編譯器友好的函數(shù)，一般代碼比較短，函數(shù)沒有遞歸邏輯。對(duì)編譯器不友好的函數(shù)， 顯然就是指：函數(shù)指針調(diào)用、深度遞歸、虛函數(shù)。函數(shù)指針調(diào)用，會(huì)讓編譯器不知道真實(shí)的 函數(shù)在哪里，既然都不知道函數(shù)在哪里， 自然無法內(nèi)聯(lián)了。虛函數(shù)也是一樣的問題，編譯器 不清楚調(diào)用的方法在哪里。有一種策略可以把虛函數(shù)變成可以內(nèi)聯(lián)的函數(shù)，下面在重點(diǎn)討論這個(gè)策略。假設(shè)我們的程序如下：struct CPare ntvirtual int f() return 0;struct CChild1: CPare ntint f()return 1;struct CChild2: CPare ntin

39、t f()return 2;調(diào)用語(yǔ)句如下：int coun t=0;vector<CPare nt*> ds;vector<CPare nt*>:iterator iter=ds.begi n();while( iter !=ds.e nd()count += (*iter)->f();iter +;毫無疑問，程序在編譯的時(shí)候，不可能知道f函數(shù)到底是 CChild1:f還是CChild2:f。我們通過加一個(gè)內(nèi)置的type，來明確告訴編譯器到底是f是哪個(gè)真正的函數(shù)：struct CPare ntint type;virtual int f()return 0; ;s

40、truct CChildl: CPare ntCChild1()type=1;int f()return 1;struct CChild2: CPare ntCChild2()type=2;int f()return 2;inline int f(CPare nt* p)switch(p_>type)case 1:return (CChild1*)p)->CChild1:f();case 2:return (CChild2*)p)->CChild2:f();return 0;/調(diào)用代碼int coun t=0;vector<CPare nt*> ds;vector

41、<CPare nt*>:iterator iter=ds.begi n();while( iter !=ds.e nd()count += f(*iter);iter +;我們僅用一個(gè) switch語(yǔ)句就節(jié)約了函數(shù)調(diào)用的各種開銷，很值得。事實(shí)證明，這種策 略可以極大的提高程序效率。4.4 switch 優(yōu)化switch有3種替換模式：? if用if來替換switch。當(dāng)switch的判斷值數(shù)量少時(shí)，這種策略比較高效。? Jump table，跳表用一個(gè)數(shù)組存儲(chǔ) case包含的代碼，而直接用case的值來跳轉(zhuǎn)到代碼位置。如:switch(d)case 0: xxx; break;ca

42、se 1:yyy; break;變成：addr=addr_xxx, addr_yyy;jump addrd;但這個(gè)策略只適合判斷的值比較連續(xù)的情況，這是因?yàn)閿?shù)組下標(biāo)連續(xù)。? Lookup table，查找表查找表適合簡(jiǎn)單的邏輯，可以預(yù)先計(jì)算結(jié)果，然后直接根據(jù)某種邏輯返回結(jié)果。 一般需要編程者自己完成設(shè)計(jì)。比如：ret ="a","b","c"return retd;最后大家看一下switch語(yǔ)句的獨(dú)特用法：Duffs Device/ 內(nèi)存拷貝，arrayA arrayB void copy(int *arrayA, int *arra

43、yB, int ent) switch (ent % 4)while(cnt != 0)case 0:arrayAcnt = arrayBcnt-; case 3:arrayAcnt = arrayBcnt-; case 2:arrayAcnt = arrayBcnt-; case 1:arrayAcnt = arrayBcnt-;在我們的開發(fā)機(jī)上面， 其速度比memepy快 10-25%.匯編代碼為:moviOxIfffffc,XedxmovXeax,OxffffffeS(Xebp>mov0x10(Xesi,Xedx,4>,XeaxmovZeax,0x10(Zedi,Zedx#

44、4 >movOxc(Xesi Xedx* 4 打 Xeaxm ovXeax,Oxc(XediAZedx,4)mov0x8(XesiZedxA4>xZeaxm ovXeax . 0x8 < Zedi 以e de 4nov0x4(XesiXedx,4),XeaxmovXeax.0x4<Xedi,Xedx* 4 >sub<0x4,XedxcmpiOxfXedxjne0x8048600<main+160>4.5最大概率路徑最短化這次策略的思想我們多次提到。有幾種常見的方式來達(dá)到這個(gè)目的:? switch/if/?x:y把最常見的情況放在前面，減少其比較次

45、數(shù)。?布爾表達(dá)式在&&表達(dá)式時(shí)，把最不容易為true的放在前面。在|表達(dá)式時(shí)，把最容易為true的放在前面。?函數(shù)內(nèi)cache可以用一個(gè)變量存儲(chǔ)最常見的返回結(jié)果。如：static int comm_ in put, comm_output;if(in put = comm_ in put)return comm_output;xxx;考慮到計(jì)算最常見的輸入需要很多額外操作，故我們可以只存儲(chǔ)最上一次的結(jié)果。4.6異常C+啲異常有不少詬病，比如沒有fin ally，出錯(cuò)時(shí)難以釋放資源。它還需要大量額外的資源，因?yàn)樾枰４婺切┳兞繘]有被析構(gòu)等信息。我們的建議是不使用異常，盡量通過自定

46、義log以及assert的方式來處理程序異常。在前一章，我們對(duì)C+語(yǔ)言和性能有關(guān)的部分進(jìn)行了簡(jiǎn)單描述。本章將介紹和和cpu硬件相關(guān)的性能優(yōu)化技術(shù)。5理解硬件Intel的cpu外部結(jié)構(gòu)由著名的 CPU、南北橋組成。北橋連接的都是快速設(shè)備，如內(nèi)存和顯卡。南橋則是低速設(shè)備，如磁盤、聲卡等等。圖支持in tel的主板圖intel cpu基本構(gòu)架圖AMD的cpu'外部結(jié)構(gòu)有所不同。 以直接連接內(nèi)存。其socket的接口為AM3，其內(nèi)存控制器在 cpu里面，可圖支持AMD的主板圖amd K10構(gòu)架5.1理解內(nèi)存我們現(xiàn)在使用的一般是DDR3代內(nèi)存條，臺(tái)式機(jī)的內(nèi)存一般有 240針，但內(nèi)存的實(shí)際數(shù)據(jù)位數(shù)

47、只有64位，即8個(gè)字節(jié)。圖臺(tái)式機(jī)內(nèi)存腳的說明理解硬件MemoryDDR3 RAMPm DescriptionPin NameDescriptionPin NameDescriptionCK0.CK1Cock Inputs, positive lineDQ0-DQ63Data inpuVoutputCiock inputs, negative lineDQSO-DOS7Data strobesCKEOb CKE1CSoek EnableDQSO-DQS?Data strobes complefnantRASRot- Address SuobeDM0-DM7Data MasksCSSColumn

48、Address StrobeE7ERTTemperature event pinWEWrite EnableRESETReset pin酚前Chip SelectsInpuVOutpu! ReferenceA0-A9. A11, A13Address InputsVddsPOSPD and Temp sensor powerA10/APAddress Input/Auto-PrechargeSAO. SA1Serial Presence Detect Address InputsA12/BCAddress InpuVBurst ChopVttTermination voltageBA0-BA2

49、SDRAM Bank Address InputsGroundGOTO. ODT1Active termination control linesVqcCore and I O powerSCLSerial Presence Detect Clock InputNCNo ConnectSDASerial Presence Detect Oata inputautputNote: Al 3 Is for 2GB modules only.電子商務(wù)搜索9*I一般來說，內(nèi)存的速度比cpu的速度慢。為了提高內(nèi)存的數(shù)據(jù)傳輸速度，有人設(shè)計(jì)了多通道模式。在這種模式下，內(nèi)存的傳輸速度可以加倍。多通道有雙通道和

50、三通道之說，后者僅最新的In tel cpu支持。多通道又分為Ga nged和Ungan ged模式。前者每次提供128位數(shù)據(jù), 后者每次提供64位數(shù)據(jù)，但容許同時(shí)讀取。實(shí)際結(jié)果表明，后者對(duì)多核多線程的服務(wù)器更加 有效。（注：cpuz會(huì)把unganged模式識(shí)別為單通道+）圖多通道5.2 理解 cpu cachecpu cache的分析圖:現(xiàn)代cpu包含多級(jí)cache, 般為L(zhǎng)1-L3共3級(jí)。下圖是筆者對(duì)圖cpu cache分析從圖中我們可以看到，內(nèi)存控制器（IMC ）通過多個(gè)通道和內(nèi)存（memory stick ）連接。 每個(gè)通道的位寬是64。內(nèi)存控制器和 L3 cache的位寬是96。為啥

51、是94位呢？這是因?yàn)樵陔p 通道模式下，內(nèi)存控制器的進(jìn)入位寬是128，而IMC的頻率一般為內(nèi)存頻率的1.5倍（實(shí)際數(shù)據(jù)），如果出位寬是96,則IMC的頻率差不多剛好夠用（需要為內(nèi)存頻率的1.33倍）。5.3 cache line 的解釋有幾點(diǎn)大家要明白：內(nèi)存位寬是64；Cpu Lx cache line是 64 字節(jié)；Cache每次消耗8個(gè)時(shí)鐘讀取一個(gè)數(shù)據(jù)（從內(nèi)存中）。在雙通道ganged模式下，只需要4個(gè)時(shí)鐘的讀取時(shí)間。Lx cache N-way 的概念內(nèi)存中的數(shù)據(jù)，只能固定存儲(chǔ)在 Lx cache中的某些位置。對(duì)于32way的cache來說， 每塊內(nèi)存中的數(shù)據(jù)（即把內(nèi)存按照 cache l

52、ine的長(zhǎng)度切分）只能在32個(gè)位置中出現(xiàn)。這 樣的目的是加快 cache的查找。5.4內(nèi)存速度 內(nèi)存的速度很難計(jì)算， 畢竟不是所有的指令都能讓cpu和內(nèi)存之間的通道全速工作。好在mov/movq指令可以比較全面的利用cpu流水線，能夠測(cè)試出大概的內(nèi)存速度。對(duì)于DDR3 1333的內(nèi)存和北橋（或者 IMC ）速度為1995M的cpu,我們大致可以計(jì)算 如下：DDR3 1333, un ga nged dual cha nnel理論帶寬：1333*8*2=21G/s，訪問延遲：幾十個(gè)ns。L3 cache, NB-speed（1995M）, on-die, 48-way理論帶寬：1995*8=16

53、G/s，訪問延遲：10ns。L2 cache, full-speed, on-die理論帶寬2800*8=22G/s，訪問延遲：幾 ns。L1 cache理論帶寬未知，訪問延遲 <1n s。下面的圖是EVEREST的測(cè)試結(jié)果：5.5幾個(gè)簡(jiǎn)單應(yīng)用第一個(gè)應(yīng)用：快速2分查找。2分查找的主要問題是訪問隨機(jī)，對(duì)cache很不友好。我們根據(jù)查找樹把元素重新排列，增加每個(gè)節(jié)點(diǎn)的數(shù)據(jù)個(gè)數(shù)。從而提高了cache的命中率。圖快速2分查找第二個(gè)應(yīng)用：最快速的內(nèi)存拷貝。主要是3個(gè)步驟：1）預(yù)先讀取指令，把數(shù)據(jù)讀取到cpu cache里面；2）采用mmx緩存器，有效利用 cpu流水線；3）movn指令，直接寫內(nèi)存, 不存放在Lx cache里面。圖 最快的 memory copy5.5多核的問題 圖代碼圖問題在多核的情況下，cpu需要經(jīng)常同步他們之間的cache。而每次同步都是以一個(gè) cache line為單位。當(dāng)多個(gè)核心 cache 了同樣的line時(shí)，如果你不小心修改了line中的一個(gè)字節(jié)，也會(huì)導(dǎo)致整個(gè)line被同步。這就導(dǎo)致了本來和其他線程無關(guān)的數(shù)據(jù)，也會(huì)經(jīng)常的被同步給它們。 所以，我們建議在定義變量的時(shí)候，每個(gè)線程只寫入位置超過一個(gè)line長(zhǎng)度的變量。5.6 cpu指令集介紹386:支持少量寄存器；x64: