前言
我們常常關注程式的性能，而程式性能的一個重要參考就是:運作時間，同時，我們都知道，這也是衡量一個算法好壞的重要标準。在一個程式保證正确的前提下，其運作得快慢往往決定了其性能的好壞。當然，并不是所有的程式都有很嚴格的性能要求，往往這些程式更加傾向于保證程式的正确性及穩定性，性能是其次需要考慮的。但對于某些實時性要求比較高的程式，性能成為影響其功能和使用者體驗的重要因素。是以，優化和提高程式的性能的方法對我們每個編碼者尤為重要。
我所知道的可以提高程式的三種方法是：一、在程式中使用一組合适的資料結構、高效算法二、編寫出編譯器能夠有效優化而轉換成高效可執行代碼的源代碼三、将程式劃分成多個部分，這些部分可以得到并行計算和處理。而本篇所講的内容隻跟方法二有關，即如何寫出編譯器能夠有效優化的源代碼。後面我們會介紹多個可能的方法做到這點。
1. 優化編譯器的能力和局限性
編譯器本身就具有優化代碼的能力，并且分類有嚴格的等級，例如，在使用GCC編譯器時可以在指令中使用-O1指令開啟最基本的優化，同樣在MS下的CL編譯工具也具有類似的優化指令。當然，編譯器對程式進行優化的前提都是一樣，即必須保證優化後和優化之前的程式行為一樣。即所謂優化是一種安全的優化，這就意味着程式員必須花費更大的力氣寫出程式使編譯器能夠将之轉換成有效機器代碼。下面我們就看下對編譯器來說，程式轉換是否安全的難度：
Void twiddle1(int * xp ,int *yp)
{
*xp+=*yp;
*xp+=*yp;
}
Void twiddle2(int* xp,int *yp)
{
*xp+=2**yp;
}
咋一看，這兩個過程似乎有相同的行為。不過，函數twiddle2效率更高一些。它隻需要3次存儲器引用(讀*xp,讀*yp，寫*xp)，而twiddle1需要6次(2次讀*xp,2次讀*yp,2次*xp)。我們對比編譯器産生也可以明顯看的出。
不過，既然兩個程式的行為相同，而讀寫效率又有這麼大的差異，那為什麼編譯器不把twiddle2風格的代碼作為twiddle1的優化版本呢？
因為，這裡存在一個安全的隐患，我們忽略了xp等于yp的情況。此時，函數twiddl1會執行下面的計算:
*xp+=*xp;
*xp+=*xp;
結果是xp的值會增加4倍，而twiddle2會執行：
*xp+=2*xp;
結果是xp的值會增加3倍。而這顯然是不能被允許的，這與前面所提的編譯器優化原則即優化前後必須保證行為一緻相背離。這種兩個指針可能指向同一個存儲位置的情況被稱為存儲器别名使用。在隻執行安全的優化中，編譯器必須假設不同的指針可能會指向存儲器中同一個位置。進而限制了可能的優化政策。
第二個妨礙優化的因素是函數調用。我們先看下面的例子：
Int f();
Int fun1()
{
Return f()+f()+f()+f();
}
Int fun2()
{
Return 4*f();
}
最初看上去兩個過程計算的都是相同結果，但是func2隻調用f 一次，而fun1隻調用4次，以func1作為源時，會很想産生fun2風格的代碼。
不過，考慮下面的f代碼：
Int counter = 0;
Int f()
{
Return counter++;
}
假設開始時全局變量為0，對func1的調用會傳回0+1+2+3=6,而對fun2的調用會傳回4*0=0。大多數編譯器不會試圖判斷一個函數u是否沒有副作用，相反，編譯器會假設最糟的情況，并保持所有的函數調用不變。
2.表示程式性能
傳統的我們會用類似gettickcount,gettime等擷取時間的方法來計算程式段的運作時間進而估算其行能。在這裡我們一個更加準确的标準度量每元素的周期數(CyclesPer Element,CPE)，作為一種表示程式性能并指導我們改進代碼的方法。
許多過程含有一組元素上疊代的循環，如下面的函數psum1和psum2計算的都是一個長度為n的向量的前置和。函數psum1每次疊代計算結果向量的一個元素。第二個函數使用循環展開的技術，每次疊代計算兩個元素。
Void psum1(float a[],float p[],long int n)
{
Long int I;
P[0]=a[0];
For(I =1;i<n;i++){
P[i]=p[i-1]+a[i];
}
}
Void psum2(float a[],float p[],long int n)
{
Long int I ;
P[0]=a[0];
For(i=1;i<n-1;i+=2){
Float mid_val = p[i-1]+a[i];
P[i]=mid_val;
P[i+1]=mid_val+a[i+1];
}
If(i<n)
P[i]=p[i-1]+a[i];
}
我們取一定傳回内的n值分别計算兩個函數的運作周期數。使用最小二乘拟合我們發現psum1和psum2的運作時間分别近似等式496+10.0n和500+6.5n.。這兩個等式表明代碼計時和初始化過程、準備循環以及完成過程的開銷為496~500個周期加上每個元素6.5或者10.0的線性因子，對于較大的n值，顯然其運作時間是由線性因子來決定的。這些項中的系數就稱為每元素的周期數(CPE)。在這裡我們更願意用每個元素的周期數而不是每次循環的周期數來度量，是因為像循環展開這樣的技術使得我們能夠用較少的循環完成計算，而我們最終關心的是，對于給定的n，程式運作得速度如何。
根據這個度量标準。Psum2的CPE為6.5，由于CPE為10.0的psum1。
3.未優化的原始程式
這是一個簡單的資料結構，其用資料類型data_t作為基本元素的資料類型。
typedef struct {
Long int len;
Data_t *data;
}vec_rec,*vec_ptr;
然後定義兩個宏變量INENT 和OP分别對應不同運算時所應取的值。
#define INENT 0
# define OP +
和
#defineINENT 1
#define OP*
//建立一個新的結構對象
Vec_ptrnew_vec(long int len)
{
Vec_ptr result = (vec_ptr)malloc(szieof(vec_rec));
If(!result){
Return Null;
}
Result->len = len;
If(len>0){
Data_t*data=(data_t*)calloc(len,sizeof(data_t));
If(!data){
Free(result);
Return NULL;
}
Result->data=data;
}else{
Result->data =NULL;
}
Return result;
}
//取值
Intget_vec_element(vec_ptr v,long int index,data_t *dest)
{
If(index<0|| index>=v->len)
Return0;
*dest=v->data[index];
Return 1;
}
//取長度
Long int vec_length(vec_ptr v)
{
Return v->len;
}
//合并運算
Void combine1(vec_ptr v,data_t *dest)
{
Long int I;
*dest =IDENT;
For(i=0;i<vec_length(v);i++){
Data_vval;
Get_vec_element(v,I,&val);
*dest=*destOP val;
}
}
我們下面的資料都是在一個擁有Inter core i7處理器的機器上測試得到的CPE值。首先等到的一組資料是combine1和其優化版本的比較，我們發現簡單實用指令行選項-O1進行一些基本優化就能顯著的提高程式性能。
4.消除循環的低效率
可以看到，過程combine1調用函數vec_length作為for循環的測試條件。而每次調用vec_length的值都是相同的。為此，我們隻計算一次向量的長度，然後在for循環的中使用這個值，這樣避免多次對同一個方法進行調用。下面是上個版本的修訂版Combine2：
Void combine2(vec_ptr v,data_t *dest)
{
Long int I;
Long intlength =vec_length(v);
*dest =IDENT;
For(i=0;i<length;i++){
Data_tval;
Get_vec_elemen(v,I,&val);
*dest= *dest OP val;
}
}
這是改進後的性能提升：
這是一種稱為“代碼移動”的優化方法，這類優化将循環中多次執行，但是結果不會改變的值，是以可以将其移動到多次執行的代碼前面先進行計算。優化編譯器可能會嘗試進行代碼移動，但是通常會非常小心，因為它們不能可靠的發現一個函數是否會有副作用(像之前介紹的)，因而會假設會有副作用。是以時需要我們幫助其顯示地完成代碼移動。
5.減少過程調用
過程調用會帶來相當大的開銷，而且妨礙了程式的優化。從combine2的代碼可以看出，每次循環疊代都會調用get_vec_element來擷取下一個向量元素。在該方法内部，會對每個向量索引i做越界比較，造成一定的低效率。然而對程式進行簡單的分析後，發現每次調用并不一定需要這樣的檢查。作為替代，我們可以添加一個get_vec_start的函數，傳回向量數組的其實位址這樣我們就可以對其進一步優化，得到combine3:
Data_t*get_vec_start(vec_ptr v) {
Returnv->data;
}
Void combine3(vec_ptr v,data_t *dest)
{
Long int I;
Long int length = vec_length(v);
Data_t *data = get_vec_start(v);
*dest = IDENT;
For(i=0;i<length;i++){
*dest = *dest OP data[i];
}
}
不過從原則上來說，這種方法嚴重損害了程式的子產品性，因為向量抽象資料類型的使用者不需要知道向量的内容是作為數組來存儲的。不過，對于性能至關重要的應用來說，為了速度，必須經常犧牲和損害一些子產品性和抽象性。
我們看下提升的性能CPE：
我們發現，隻提高了整數求和的性能，也就是說combine2中的邊界檢查并沒有我們預測的那麼差。這個原因的分析後面再做說明。
6.減少不必要的存儲器引用
Combine3将合并運算計算的值累計在指針dest指定的位置，通過檢視其産生的彙編代碼，我們看到在循環的疊代中存儲器的讀寫主要發生在對于dest和data的一次讀以及對dest的一次寫操作。
對于我們combine3的優化版本，我們将而每次疊代計算的值放入一個臨時變量，計算完成時再寫入記憶體中。
Void combine4(vec_ptr v,data_t *dest)
{
Long int I ;
Long int length = vec_length(v);
Data_t *data = get_vec_start(v);
Data_t acc = IDENT;
For(i=0;i<length;i++){
Acc=acc OP data[i];
}
*dest =acc;
}
這樣産生的彙編代碼如下,可以看到比上個版本的存儲器通路少了兩次，隻有一次讀操作。
最後，我們再看優化後的性能提升：
可以看到，消除循環内不必要的存儲器引用可以顯著的提高程式性能。而這個跟存儲器系統的結構相關。在後面的篇節中我會對其進行介紹。
7.現代處理器
到目前為止，我們運用的優化都不依賴于目标機器的任何特性，這些優化隻是簡單的降低了過程調用，并消除了妨礙編譯器優化的一些因素，如果想要充分的提高性能，我們需要考慮利用微處理器結構的優化。這将要求我們在特定機器上對程式進行性能優化，這裡我不對處理器結構及其硬體結構多做說明，因為不同處理器的結構可能并不相同且難于了解。是以我們隻對影響程式性能的關鍵要素做出簡單說明，如果據此不能夠充分了解，可以檢視本書第四章<處理器體系結構>及本章的詳細介紹。
在現代處理器中，大都具備了指令級并行的處理能力。比如有100條指令，采用一些精細的機制來確定并行執行的行為，它們采用複雜而奇異的微處理結構，其中，多條指令可以并行地執行，同時又呈現一種簡單地順序執行指令的表象。
現在處理器同時采用了一種分支預測的技術，當程式中出現分支時，處理器會猜測是否會選擇分支，同時還預測分支的目标位址。使用投機執行的技術，處理器會開始取出位于它預測的分支會跳到的地方的指令，并對指令譯碼，甚至在它确定分支預測是否正确之前就開始執行這些操作。如果過後确定分支預測錯誤，會将狀态重新設定到分支點的狀态，并開始取出和執行另一個方向的指令。
延遲界限—當一系列擦偶偶必須按照嚴格順序執行時，在下一條指令開始之前，這條指令必須結束。當代碼中的資料相關限制了處理器利用指令級并行的能力時，延遲界限能夠限定程式性能。
吞吐量界限—刻畫處理器功能單元的原始計算能力,是程式性能的終極限制。
下面我們介紹的優化方法都跟現代處理器具有的這些特性相關，是以在不同機器上的表現并不相同，你需要經過多次的測試找到合适的值來對程式進行最充分的優化。
8.循環展開
循環展開是一種程式變換，通過增加每次疊代計算的元素的數量，減少循環的疊代次數。它主要從兩方面提高程式的性能。首先，它減少了不直接有助于程式結果的操作的數量，例如循環索引計算和條件分治。其次，它提供了一些方法，可以進一步變化代碼，減少整個計算中關鍵路徑上的操作數量。
對于k次循環展開，上限設為n-k+1,在循環内對元素i到i+k-1應用合并計算。每次疊代，循環是以i加k。那麼最大循環索引i+k-1<(n-k+1)+k-1=n;
是以，我們combine5的循環展開版本，這裡k=2
Void combine5(vec_ptr v,data_t *dest)
{
Long int I;
Long int length = vec_length(v);
Long int limit = length-1;
Data_t *data = get_vec_start(v);
Data_t acc = IDENT;
For(i=0;i<limit;i+=2){
Acc = (acc OP data[i] ) OP data[i+1];
}
For(;i<length;i++){
Acc = acc OP data[i];
}
*dest =a cc;
}
下面我們看下相比上個版本的CPE值：
我們看到相對combine4整數運算的性能有所提升，但是并不是很好，無論對于2次還是3次展開，對于浮點運算沒有幫助，但是對于整數加法合成法，CPE降至1.00.我們知道了這些優化的結果是依賴于處理器複雜的指令級并行能力。而對于浮點運算我們隻需明白其CPE受限于延遲界限。
9.提高并行性
在此，程式是受限于運算單的延遲的。不過，還行加法和乘法的功能單元是完全流水化的，這意味着它們可以每個時鐘周期開始一個新操作，而combine5的代碼沒能利用這種能力，這是因為我們将累積值放在一個單獨的acc中。在一次流水線上的計算完成之前，都不能計算acc的新值。雖然功能單元能夠每L個時鐘周期開始一條新操作，這裡L是合并的延遲。下面，我們将破這種順序相關，得到比延遲界限更好的性能方法。
9.1多個累計變量
先看我們改進的Combine6方法：
Void combine6(vec_ptr v,data_t *dest)
{
Long int I;
Long int length = vec_length(v);
Long int limit =length-1;
Data_t * data = get_vec_start(v);
Data_t acc0 = IDENT;
Data_t acc1 = IDENT;
For(i=0;i<limit ;i+=2){
Acc0 = acc0 OP data[i];
Acc1 = acc1 OP data[i+1];
}
For(;i<length;i++){
Acc0 = acc0 OPdata[i];
}
*dest = acc0 OP acc1;
}
我們使用了一種帶有多路并行的循環展開方法，來充分的利用處理器的并行能力。對于上述代碼，可以對比combine5我們可以說，combine6在流出線的處理過程獲得了兩條關鍵路徑。進而将使用率提高了2倍。
9.2 重新結合變換
這種方法也可以打破順序相關進而使性能提升到延遲界限之外的方法。我們對combine5的代碼做微小的改動，就可以做到這點。
Void combine5(vec_ptr v,data_t *dest)
{
Long int I;
Long int length = vec_length(v);
Long int limit = length-1;
Data_t *data = get_vec_start(v);
Data_t acc = IDENT;
For(i=0;i<limit;i+=2){
Acc = acc OP (data[i] OP data[i+1]);
}
For(;i<length;i++){
Acc = acc OP data[i];
}
*dest =a cc;
}
我們可以看到令人吃驚的結果，僅僅是改變一個計算時的結合順序就能是性能提高這麼大。這主要是因為每次疊代内的第一個乘法都不需要等待前一次疊代的累計值就可以執行，流水線的每個關鍵路徑上都有1/2個操作，有點類似2路并行的情況。總得來說，重新結合變換減少了計算中關鍵路徑上的操作的數量，能通過更好地利用功能單元的流水線能力得到更好的性能。
10.一些限制因素
可能我們了解了上面優化的方法，可能會有這樣的疑問：是不是循環展開和多路并行的次數越大對于程式性能提升越有幫助？答案顯然不是，我們知道循環展開和多路并行都以來了處理器的對于指令的并行處理能力。而這個能力受限于其對應彙編指令集的能力，簡單來說，IA32指令集隻有很少量的寄存器來存放累計的值。如果我們的并行度超過了可用的寄存器數量，那麼編譯器會訴諸溢出，将某些臨時值存放在棧中。一旦出現這種情況，性能就會急劇下降。
同時，我們前面提到過現代處理器具有分支預測能力。在一個使用投機執行的處理器中，處理器會開始執行預測的分支目标處的指令。如果預測結果正确，那麼處理器會根據預測的結果繼續執行，否則，就必須丢棄所有投機執行的結果，在正确的位置，重新開始取指令的過程。對于這種預測錯誤，處理器會得到處罰，對于Inter Core i7 來說，有将近44個時鐘周期。在這裡，讓我們回顧下combine2變化到combine3時的情況，我們把函數get_vec_element從函數内循環中拿了出來，我們發現對應于combine2，CPE并沒有多大的變化，即使這個函數使用了兩個條件語句來檢查向量索引是否在界限内。這些檢測總是确定索引是在界限之内的，是以是高度可預測的。像這種在合并函數中閉合循環的分支通常會被預測為選擇分支，而隻在最後一次會導緻預測錯誤處罰。是以預測分支并沒有我們想象的那麼糟糕，現代處理器中的分支預測邏輯非常善于辨識不同的分支指令有規律的模式和長期的趨勢。
11.Amdahl定律
Amdahl定律對于我們對于系統優化有一定的指導意義。其主要思想是當我們加快系統一個部分的速度時，對系統整體性能的影響依賴于這個部分有多重要和速度提高了多少。考慮一個系統，在其中執行某個應用程式需要Told.假設系統的某個部分需要這個時間的百分比為a,而我們将他的性能提高到了k倍。也就是，這部分原來需要時間aTold,而現在需要時間(aTold)/k,是以整個執行時間會是
例如系統原來被占用60%(a=0.6)的部分被提高到了3(k=3)倍。那麼加速比為1[0.4+0.6/3]=1.67
是以，計時我們大幅度改進了系統的一個主要部分，淨加速比還是很小。這就是Amdahl定律的主要觀點——要想大幅度提高整個系統的速度，我們必須提高整個系統很大一部分的速度。根據Amdahl定律 ，我們知道要想提高整個系統的速度，必須對程式進行剖析，進而了解整個系統的最影響程式性能的部分。
如果想要知道程式中哪一部分占用了很大的比重，我們可以通過在Unix系統中，通過一個剖析程式GPROF來進行分析。首先，它去掉程式中每個函數花費了多少CPU時間，其次，它計算每個函數被調用的次數，以執行調用的函數進行分類。
用GPROF進行剖析需要3個步驟，比如我們要對程式test.c進行剖析
1> 程式必須為剖析而編譯和連結。使用GCC，在指令行上簡單地包括運作時辨別‘-pg’
gcc –O1 –pg test.c – test
2>然後程式像往常一樣執行：
./test file.txt
它會産生一個檔案gmon.out
3>調用GPROF來分析gmon.out中的資料。
gprof ./test
分析的結果是以函數進行分類的，記錄了每個函數花費的時間占總時間的百分比，函數被調用的次數等資訊。
好了，本篇的介紹到這裡就結束了,想了解詳細内容請參見<優化程式性能>一章。