C++性能優(yōu)化技術導論

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

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

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

4、eHelper uint64_t preTime;TimeHelper():preTime(GetTime()TimeHelper()g_timeUsed = GetTime() - preTime;；/調用TimeHelper th;/代碼段/ g_timeUsed 保存了耗時/得到cpu的tick count, cpuid (重整時鐘周期)消耗約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ù)第一次調用會耗時 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、除了基本的計算執(zhí)行次數(shù)和時間外，還有如下幾種分析性能的策略：a、基于概率通過不斷的中斷程序， 查看程序中斷的位置所在的函數(shù)，出現(xiàn)次數(shù)最多的函數(shù)即為耗時最嚴重的函數(shù)。b基于事件當發(fā)生一次cpu硬件事件的時候，某些 cup會通知進程。如果事件包括 L1失效多 少次這種，我們就能知道程序跑的慢的原因。c、避免干擾性能測試最忌諱外界干擾。比如，內存不足，讀內存變成了磁盤操作。性能分析原理0基于概率0每隔一段時間（幾ms ）中斷一次（如加入int$3）0原理：訪問多的代碼段中斷的次數(shù)也多0基于事件0 cache失效若干次時產生 0如L1失效1000次0 般需要cpu支持0避免干擾0內存缺頁0足夠內 存+

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

9、目次數(shù)，耗時比例0缺點0 很慢 20-100f0對optimize版肆0耗時計算很不卡青確電子商務投盍弓I粘我們編寫了一個簡單的測試程序，用它來測試常見性能分析工具。代碼如下: /計算最大公約數(shù)inline int gcd(int m, int n)PERFOMANCEC'gcd"); /全局計算耗時的 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 運行的結果如下：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 驅 1=二L2 refs：17,6%(12,5% rd#5,0% wr)B驅1斗L2 i£tes:WU1(5,371 rd4.790 yr2481= L2 rxs rate；0,0C0亦0.09()我們把輸出的結果在windows下用callgrind

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

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

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

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

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

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

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

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

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

24、行的編譯器，比如gcc。Gcc的優(yōu)點是它更新快，開源，bug修改迅速。正因為他更新快，所以它能夠支持部分C03的規(guī)范。3.1 gcc支持的優(yōu)化技術1) 函數(shù)內聯(lián)函數(shù)調用的過程是：壓入參數(shù)到堆棧、保護現(xiàn)場、調用函數(shù)代碼、恢復現(xiàn)場。當一個函 數(shù)被大量調用的時候，函數(shù)調用的開銷特別巨大。函數(shù)內聯(lián)是指把這些開銷都去除，而直接調用代碼。函數(shù)內聯(lián)的不好之處是難以調試，因為函數(shù)實際上已經不存在了。2) 常量預先計算a=b+1000*16對于這段代碼，程序會預先計算1000*16，從而變成：a=b+160003) 相同子串提取a=(b+1)*(b+1)這里，b+1需要計算2次，可以只用計算一次：tmp=b+1

25、a=tmp*tmp4) 生存周期分析這是一個比較高級的技術。假設有代碼：a=b+1c=a+1在執(zhí)行的時候，因為第二句依賴第一句，所以2句是線性執(zhí)行。但編譯器其實可以知道，c就是等于b+2，所以代碼變成：a=b+1c=b+2這樣，這2句就沒有任何關系來了，執(zhí)行的時候， cpu可以并行執(zhí)行它們。5) 清除跳轉看如下代碼：int func()int ret = 0;if(xxx)ret=5;else if(yyy)ret=6;return ret;當條件xxx滿足的時候，程序還會跳到下面執(zhí)行，但其實是沒有必要的。編譯器會把它變成：int func()if(xxx)return 5;else if(y

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

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

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

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

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

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

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

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

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

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

36、t;更快。?用引用代替返回避免構造對象。在函數(shù)調用的時候，把需要返回的對象都用引用傳遞進來。如： void fun c(Object & retObj);5、變量緊密定義關聯(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;后者因為a,b緊密定義在一起，其訪問對cache更友好。6、類/結構成員順序因為默認對齊的原因，成員變量的順序對對象的空間占用有一定影響。一般把

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ù)組成員。一般認為數(shù)組成員應該往后放。這是因為訪問其他變量的時候，相 對偏移(結構的初始位置)比較小，代碼更短。如：mov eax, ebp+10h 顯然比 mov eax, ebp+256h實際代碼要短。4.3函數(shù)內聯(lián)函數(shù)內聯(lián)作為編譯器最大最好的優(yōu)化選項，無論在哪里都值得探討一番。函數(shù)內聯(lián)的好處是節(jié)省了保護現(xiàn)場和返回值的開銷。編譯器并不是萬能的，有些函數(shù)很容易進

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

39、t f()return 2;調用語句如下：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 +;毫無疑問，程序在編譯的時候，不可能知道f函數(shù)到底是 CChild1:f還是CChild2:f。我們通過加一個內置的type，來明確告訴編譯器到底是f是哪個真正的函數(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;/調用代碼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 +;我們僅用一個 switch語句就節(jié)約了函數(shù)調用的各種開銷，很值得。事實證明，這種策 略可以極大的提高程序效率。4.4 switch 優(yōu)化switch有3種替換模式：? if用if來替換switch。當switch的判斷值數(shù)量少時，這種策略比較高效。? Jump table，跳表用一個數(shù)組存儲 case包含的代碼，而直接用case的值來跳轉到代碼位置。如:switch(d)case 0: xxx; break;ca

42、se 1:yyy; break;變成：addr=addr_xxx, addr_yyy;jump addrd;但這個策略只適合判斷的值比較連續(xù)的情況，這是因為數(shù)組下標連續(xù)。? Lookup table，查找表查找表適合簡單的邏輯，可以預先計算結果，然后直接根據某種邏輯返回結果。 一般需要編程者自己完成設計。比如：ret ="a","b","c"return retd;最后大家看一下switch語句的獨特用法：Duffs Device/ 內存拷貝，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ā)機上面， 其速度比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最大概率路徑最短化這次策略的思想我們多次提到。有幾種常見的方式來達到這個目的:? switch/if/?x:y把最常見的情況放在前面，減少其比較次

45、數(shù)。?布爾表達式在&&表達式時，把最不容易為true的放在前面。在|表達式時，把最容易為true的放在前面。?函數(shù)內cache可以用一個變量存儲最常見的返回結果。如：static int comm_ in put, comm_output;if(in put = comm_ in put)return comm_output;xxx;考慮到計算最常見的輸入需要很多額外操作，故我們可以只存儲最上一次的結果。4.6異常C+啲異常有不少詬病，比如沒有fin ally，出錯時難以釋放資源。它還需要大量額外的資源，因為需要保存那些變量沒有被析構等信息。我們的建議是不使用異常，盡量通過自定

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

47、只有64位，即8個字節(jié)。圖臺式機內存腳的說明理解硬件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.電子商務搜索9*I一般來說，內存的速度比cpu的速度慢。為了提高內存的數(shù)據傳輸速度，有人設計了多通道模式。在這種模式下，內存的傳輸速度可以加倍。多通道有雙通道和

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

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

52、ine的長度切分）只能在32個位置中出現(xiàn)。這 樣的目的是加快 cache的查找。5.4內存速度 內存的速度很難計算， 畢竟不是所有的指令都能讓cpu和內存之間的通道全速工作。好在mov/movq指令可以比較全面的利用cpu流水線，能夠測試出大概的內存速度。對于DDR3 1333的內存和北橋（或者 IMC ）速度為1995M的cpu,我們大致可以計算 如下：DDR3 1333, un ga nged dual cha nnel理論帶寬：1333*8*2=21G/s，訪問延遲：幾十個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的測試結果：5.5幾個簡單應用第一個應用：快速2分查找。2分查找的主要問題是訪問隨機，對cache很不友好。我們根據查找樹把元素重新排列，增加每個節(jié)點的數(shù)據個數(shù)。從而提高了cache的命中率。圖快速2分查找第二個應用：最快速的內存拷貝。主要是3個步驟：1）預先讀取指令，把數(shù)據讀取到cpu cache里面；2）采用mmx緩存器，有效利用 cpu流水線；3）movn指令，直接寫內存, 不存放在Lx cache里面。圖 最快的 memory copy5.5多核的問題 圖代碼圖問題在多核的情況下，cpu需要經常同步他們之間的cache。而每次同步都是以一個 cache line為單位。當多個核心 cache 了同樣的line時，如果你不小心修改了line中的一個字節(jié)，也會導致整個line被同步。這就導致了本來和其他線程無關的數(shù)據，也會經常的被同步給它們。 所以，我們建議在定義變量的時候，每個線程只寫入位置超過一個line長度的變量。5.6 cpu指令集介紹386:支持少量寄存器；x64: