深入理解計(jì)算機(jī)系統(tǒng)（5.1）------優(yōu)化程序性能
你能獲得的對(duì)程序最大的加速比就是當(dāng)你第一次讓它工作起來的時(shí)候。
在講解如何優(yōu)化程序性能之前，我們首先要明確寫程序最主要的目標(biāo)就是使它在所有可能的情況下都能正常工作，一個(gè)運(yùn)行的很快的程序但是卻是錯(cuò)誤的結(jié)果是沒有任何用處的，所以我們?cè)谶M(jìn)行程序性能優(yōu)化之前，首先要保證程序能正常運(yùn)行，且結(jié)果是我們需要的。
而且在很多情況下，讓程序跑的更快是我們必須要解決的問題。比如一個(gè)程序要實(shí)時(shí)處理視頻幀或者網(wǎng)絡(luò)包，那么一個(gè)運(yùn)行的很慢的程序就不能解決此問題。再比如一個(gè)計(jì)算任務(wù)計(jì)算量非常大，需要數(shù)日或者數(shù)周，如果我們哪怕只是讓它運(yùn)行的快20%也會(huì)產(chǎn)生重大影響。
1、編寫高效程序的切入點(diǎn)
①、選擇一組合適的算法和數(shù)據(jù)結(jié)構(gòu)。
②、編寫出編譯器能夠有效優(yōu)化以轉(zhuǎn)換成高效可執(zhí)行的源代碼。
③、多線程并行處理運(yùn)算。
對(duì)于第一點(diǎn)，程序=數(shù)據(jù)結(jié)構(gòu)+算法，選擇合適的數(shù)據(jù)結(jié)構(gòu)和算法無疑對(duì)于提高程序的運(yùn)行效率有很大的影響。第二點(diǎn)對(duì)于編程者則需要理解編譯器的優(yōu)化能力以及局限性，編寫程序看上去只是一點(diǎn)小小的改動(dòng)，可能都會(huì)引起編譯器優(yōu)化方式很大的變化；第三點(diǎn)技術(shù)主要這對(duì)運(yùn)算量特別大的運(yùn)算，我們將一個(gè)大的任務(wù)分成多個(gè)小任務(wù)，這些任務(wù)又可以在多核和多處理器的某種組合上并行的計(jì)算，這里我們也需要知道，即使是利用并行性，每個(gè)并行的線程都要以最高性能的方式執(zhí)行。
2、編譯器的優(yōu)化能力和局限性
正確性，正確性，正確性?。?！這個(gè)要著重提醒，所以編譯器必須很小心的對(duì)程序使用安全的優(yōu)化。限制編譯器只進(jìn)行安全的優(yōu)化，會(huì)消除一些造成錯(cuò)誤的運(yùn)行結(jié)果，但是這也意味著程序員必須花費(fèi)更大的力氣寫出程序使編譯器能夠?qū)⒅D(zhuǎn)換為有效機(jī)器代碼。
對(duì)于下面兩個(gè)程序：
void add1(int *xp,int *yp){
*xp += *yp;
*xp += *yp;
}
void add2(int *xp,int *yp){
*xp += 2* *yp;
}
對(duì)上上面兩個(gè)函數(shù)add1和add2，它們都是將存儲(chǔ)在由指針 yp 指示的位置處的值兩次加到指針 xp 指示的位置處的值。但是明顯add2的執(zhí)行效率要高，它只要求 3 次存儲(chǔ)器的引用（讀xp,讀yp,寫xp），而add1需要 6 次存儲(chǔ)器引用（2次讀xp,2次讀yp,2次寫xp）。
下面有評(píng)論指出乘法指令要比加法指令慢很多，這里的add1是兩次加法指令，而add2是一次乘法指令，按道理來講是add1要比add2快，但我這里為什么說add2要快呢？我們可以看一下匯編級(jí)別的代碼：
我們通過執(zhí)行 gcc -O0 -S add1.c 優(yōu)化級(jí)別為0，生成匯編代碼：
同理通過執(zhí)行 gcc -O0 -S add2.c 優(yōu)化級(jí)別為0，生成匯編代碼：
很明顯，add2的乘法指令被轉(zhuǎn)換成一次加法指令了，雖然乘法指令確實(shí)比加法指令慢。但是要注意這里是乘以2，如果倍數(shù)大于2，那就不一定了。
因此，如果編譯器要優(yōu)化add1,我們可以認(rèn)為add2是其優(yōu)化后的代碼。但實(shí)際上真的是這樣嗎？如果 xp 等于 yp，那么變成如下：
void add1(int *xp,int *xp){
*xp += *xp;
*xp += *xp;
}
void add2(int *xp,int *xp){
*xp += 2* *xp;
}
我們可以看到，這個(gè)時(shí)候?qū)τ?add1,xp的值會(huì)增加 4 倍，但是 add2 當(dāng)中，xp 的值只增加 3 倍。由于編譯器不知道參數(shù) xp 和 yp 是否相等，它必須假定他們有可能相等，所以不會(huì)產(chǎn)生 add2 作為 add1 的優(yōu)化版本。
在各種編譯器中，我們前面說過的 gcc 編譯器，可以通過加參數(shù)O0 -->> O1 -->> O2 -->> O3，分別是從沒有優(yōu)化到優(yōu)化級(jí)別最高。但是基本上編譯器都不會(huì)對(duì)程序進(jìn)行各種激進(jìn)的優(yōu)化，所以程序員必須以一種簡(jiǎn)化編譯器生成高效代碼的任務(wù)來編寫程序。如何編寫，請(qǐng)接著往下面看。
3、程序的性能表示
處理器活動(dòng)的順序是由時(shí)鐘控制的，時(shí)鐘提供了某個(gè)頻率的規(guī)律信號(hào)，通常用千兆赫茲（GHz），即十億周期每秒來表示。例如，當(dāng)表明一個(gè)系統(tǒng)有“4GHz”處理器，這表示處理器時(shí)鐘運(yùn)行頻率為 4*109 千兆赫茲。每個(gè)時(shí)鐘周期的時(shí)間是時(shí)鐘頻率的倒數(shù)。通常用納秒（nanosecond,1 納秒等于10-9秒），或者皮秒（picosecond，1 皮秒等于10-12秒）來表示，一個(gè) 4GHz 的十周周期為0.25納秒，或者說250皮秒。從程序員的角度來看，用時(shí)鐘周期來表示度量標(biāo)準(zhǔn)要比用納秒或者皮秒來表示有用的多。
用時(shí)鐘周期來表示，度量值表示的是執(zhí)行了多少條指令，而不是時(shí)鐘運(yùn)行的有多快。
4、提高程序的性能方法
這本書的作者講解如何優(yōu)化程序性能主要從兩個(gè)方面入手，第一個(gè)是與機(jī)器無關(guān)，第二個(gè)是與機(jī)器相關(guān)。
與機(jī)器無關(guān)： ①、消除循環(huán)的低效率：將每次循環(huán)中執(zhí)行多次但計(jì)算結(jié)果不改變的部分提出循環(huán)，這樣只需計(jì)算一次，而不用循環(huán)一次，計(jì)算一次。以此提高算法效率。
②、減少過程調(diào)用：也就是減少函數(shù)方法的調(diào)用，因?yàn)楹瘮?shù)方法的調(diào)用會(huì)帶來相當(dāng)大的開銷。但是這樣也會(huì)帶來一個(gè)缺點(diǎn)，就是破壞程序的模塊化，所以我們需要權(quán)衡利弊。
③、消除不必要的存儲(chǔ)器引用：在循環(huán)中不停地對(duì)指針?biāo)赶虻淖兞抠x值的時(shí)候，我們可以用一個(gè)中間變量代替指針，以增加速度。
④、選擇合適的算法和數(shù)據(jù)結(jié)構(gòu)：為遇到的問題選擇合適的算法和數(shù)據(jù)結(jié)構(gòu)，避免使用產(chǎn)生糟糕性能的算法或編碼技術(shù)。
與機(jī)器相關(guān)： ①、理解現(xiàn)代處理器
在代碼級(jí)上，看上去似乎是一次執(zhí)行條指令，每條指令都從寄存器或存儲(chǔ)器中取值，執(zhí)行一個(gè)操作后，并把結(jié)果存到一個(gè)寄存器或存儲(chǔ)器位置。但是實(shí)際上，在處理器中是同時(shí)對(duì)多條指令求值，稱為指令級(jí)并行?，F(xiàn)代微處理器了不起的成就就是它們采用復(fù)雜而奇異的微處理結(jié)構(gòu)，多條指令可以并行執(zhí)行，同時(shí)又呈現(xiàn)出一種簡(jiǎn)單的順序執(zhí)行指令的表象。
當(dāng)一系列操作必須按照嚴(yán)格的順序執(zhí)行時(shí)，就會(huì)遇到延遲界限，因?yàn)樵谙乱粭l指令開始之前，這條指令必須結(jié)束。當(dāng)代碼中的數(shù)據(jù)相關(guān)限制令處理器利用指令級(jí)并行的能力時(shí)，延遲界限能夠限定程序性能。吞吐量界限刻畫了處理器功能單元的原始計(jì)算能力。這個(gè)界限是程序性能的終極限制。
下圖是一個(gè)現(xiàn)代微處理器的簡(jiǎn)化示意圖：
指令控制單元（Instruction Control Unit,ICU）從指令高速緩存（instruction cache）中讀取指令，并產(chǎn)生一系列基本操作。指令高速緩存是一個(gè)特殊的高速緩存存儲(chǔ)器，它存儲(chǔ)最近訪問的指令。通常ICU會(huì)在當(dāng)前正在執(zhí)行的指令很早之前取指，這樣它才有足夠的時(shí)間對(duì)指令譯碼，并把操作發(fā)給執(zhí)行單元 EU（Execution Unit ,EU），然后由EU完成ICU產(chǎn)生的基本操作。
②、提高并行性
循環(huán)分割，利用功能單元的流水線化的能力提高代碼性能。對(duì)于一個(gè)可結(jié)合和可交換的合并操作來說，比如說整數(shù)加法和乘法，我們可以通過將一組合并操作分割成兩個(gè)或更多的部分，通過在最后合并結(jié)果來提高性能。