迴圈結構是結構化程式設計中的三種基本結構之一,也是程式設計的基礎。文主要介紹了C語言中對於迴圈結構優化的一些入門級方法,包括演算法設計的改進來提高一些並行性等方法,供參考學習,感興趣的小夥伴們可以參考一下!想了解更多相關資訊請持續關注我們應屆畢業生考試網!
一.程式碼移動
將在迴圈裡面多次計算,但是結果不會改變的計算,移到迴圈外面去。
例子:
優化前:
void lower1(char *s){
int i;
for(i=0;i<strlen(s);++i)
if(s[i]>='A'&&s[i]<='Z')
s[i]-=('A'-'a');
}
優化後:
void lower2(char *s){
int i;
int len=strlen(s);
for(int i=0;i<len;++i)
if(s[i]>='A'&&s[i]<='Z')
s[i]-=('A'-'a');
}
優化前的版本,由於每次迴圈都要呼叫strlen計算s的長度,實際上的複雜度成了O(n2)了,而優化後的版本只需計算一次s的長度,因此效能上比優化前版本要好。
二.減少函式呼叫
例子:
優化前:
void sum1(vec_ptr v,data_t *dest){
int i;
int len=vec_length(v);
*dest=0;
for(i=0;i<len;++i){
data_t val;
get_vec_element(v,i,&val);
*dest+=val;
}
}
優化後:
data_t get_vec_start(vec_ptr v){
return v->data;
}
void sum2(vec_ptr v,data_t *dest){
int i;
int len=vec_length(v);
data_t *data=get_vec_start(v);
*dest=0;
for(i=0;i<len;++i)
*dest+=data[i];
}
優化前的版本在每次迴圈中都要呼叫一次get_vec_element獲得相應的項,而優化後的版本只需在迴圈外呼叫一次get_vec_start獲得開始的記憶體地址,迴圈內直接訪問記憶體,無需呼叫函式。
三.減少記憶體訪問
例子:
優化前:
void sum2(vec_ptr v,data_t *dest){
int i;
int len=vec_length(v);
data_t *data=get_vec_start(v);
*dest=0;
for(i=0;i<len;++i)
*dest+=data[i];
}
優化後:
void sum3(vec_ptr v,data_t *dest){
int i;
int len=vec_length(v);
data_t *data=get_vec_start(v);
data_t acc=0;
for(i=0;i<len;++i)
acc+=data[i];
*dest=acc;
}
優化前的版本每次迭代都要從dest讀出值再加上data[i],再將結果寫回dest。這樣的讀寫很浪費,因此每次迭代開始從dest讀出的值就是上次迭代寫回dest的指。優化後的版本通過加入acc臨時變數,它迴圈中累積計算出的結果,迴圈結束後再寫回。
這裡給出兩個版本相應的彙編結果就可以很清楚看出區別:
優化前:
優化前的版本每次迭代都要從dest讀出值再加上data[i],再將結果寫回dest。這樣的讀寫很浪費,因此每次迭代開始從dest讀出的值就是上次迭代寫回dest的指。優化後的版本通過加入acc臨時變數,它迴圈中累積計算出的結果,迴圈結束後再寫回。
第二行和第四行分別對dest進行了讀寫。
優化後:
從彙編結果可以看出編譯器將acc直接放在了暫存器裡,迴圈中無需對記憶體進行讀寫。
四.迴圈展開
迴圈展開可以減少迴圈的次數,對程式的效能帶了兩方面的提高。一是減少了對迴圈沒有直接貢獻的計算,比如迴圈計數變數的計算,分支跳轉指令的執行等。二是提供了進一步利用機器特性進行的優化的機會。
例子:
優化前的程式碼見前一篇部落格裡的`sum3.
優化後:
void sum4(vec_ptr v,data_t *dest){
int i;
int len=vec_length(v);
int limit=len-3;
data_t *data=get_vec_start(v);
data_t acc=0;
for(i=0;i<limit;i+=4){
acc=acc+data[i]+data[i+1];
acc=acc+data[i+2]+data[i+3];
}
for(;i<len;++i)
acc+=data[i];
*dest=acc;
}
通過迴圈展開,每次迭代將累加4個元素,減少了迴圈次數,從而減少了總的執行時間(單獨使用這種優化方法,對浮點數累乘幾乎沒有提高,但是整數累乘得益於編譯器的重關聯程式碼變化會有大幅度提高)。
這種優化可以直接利用編譯器完成,將優化level設定到較高,編譯器會自動進行迴圈展開。使用gcc,可以顯式使用-funroll-loops選項。
五.提高並行性
現代處理器大多采用了流水線、超標量等技術,可以實現指令級並行。我們可以利用這個特性對程式碼做進一步的優化。
2.1使用多個累積變數
優化程式碼示例
void sum5(vec_ptr v,data_t *dest){
int i;
int len=vec_length(v);
int limit=len-1;
data_t *data=get_vec_start(v);
data_t acc0=0;
data_t acc1=0;
for(i=0;i<limit;i+=2){
acc0+=data[i];
acc1+=data[i+1];
}
for(;i<len;++i)
acc0+=data[i];
*dest=acc0+acc1;
}
這裡同時使用了迴圈展開和使用多個累加變數,一方面減少了迴圈次數,另一方面指令級並行的特性使得每次迭代的兩次加法可以並行執行。基於這兩點可以顯著減少程式執行的時間。通過增加展開的次數和累加變數的個數,可以進一步提高程式的效能,直到機器指令執行的吞吐量的極限。
2.2重結合變換
除了使用多個累積變數顯式利用機器的指令級並行特性外,還可以對運算重新結合變換,打破順序相關性來享受指令級並行帶來的好處。
在sum4中,acc=acc+data[i]+data[i+1]的結合順序是acc=(acc+data[i])+data[i+1];
我們將之變成acc=acc+(data[i]+data[i+1]);
程式碼如下:
void sum6(vec_ptr v,data_t *dest){
int i;
int len=vec_length(v);
int limit=len-3;
data_t *data=get_vec_start(v);
data_t acc=0;
for(i=0;i<limit;i+=4){
acc=acc+(data[i]+data[i+1]);
acc=acc+(data[i+2]+data[i+3]);
}
for(;i<len;++i)
acc+=data[i];
*dest=acc;
}
進一步增加迴圈展開的次數,可以進一步提高程式效能,最終也可以達到機器指令執行的吞吐量的極限。(在迴圈展示提到的整數乘法的效能提高就在於編譯器隱式採取了這種變換,但是由於浮點數不具備結合性,所以編譯器沒有采用,但是程式設計師在保證程式結果正確性的情況下,可以顯式使用這一點)。