- 相關(guān)推薦
C語言中循環(huán)結(jié)構(gòu)優(yōu)化入門級方法介紹
循環(huán)結(jié)構(gòu)是結(jié)構(gòu)化程序設(shè)計中的三種基本結(jié)構(gòu)之一,也是程序設(shè)計的基礎(chǔ)。文主要介紹了C語言中對于循環(huán)結(jié)構(gòu)優(yōu)化的一些入門級方法,包括算法設(shè)計的改進來提高一些并行性等方法,供參考學(xué)習(xí),感興趣的小伙伴們可以參考一下!想了解更多相關(guān)信息請持續(xù)關(guān)注我們應(yīng)屆畢業(yè)生考試網(wǎng)!
一.代碼移動
將在循環(huán)里面多次計算,但是結(jié)果不會改變的計算,移到循環(huán)外面去。
例子:
優(yōu)化前:
void lower1(char *s){
int i;
for(i=0;i<strlen(s);++i)
if(s[i]>='A'&&s[i]<='Z')
s[i]-=('A'-'a');
}
優(yōu)化后:
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');
}
優(yōu)化前的版本,由于每次循環(huán)都要調(diào)用strlen計算s的長度,實際上的復(fù)雜度成了O(n2)了,而優(yōu)化后的版本只需計算一次s的長度,因此性能上比優(yōu)化前版本要好。
二.減少函數(shù)調(diào)用
例子:
優(yōu)化前:
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;
}
}
優(yōu)化后:
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];
}
優(yōu)化前的版本在每次循環(huán)中都要調(diào)用一次get_vec_element獲得相應(yīng)的項,而優(yōu)化后的版本只需在循環(huán)外調(diào)用一次get_vec_start獲得開始的內(nèi)存地址,循環(huán)內(nèi)直接訪問內(nèi)存,無需調(diào)用函數(shù)。
三.減少內(nèi)存訪問
例子:
優(yōu)化前:
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];
}
優(yōu)化后:
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;
}
優(yōu)化前的版本每次迭代都要從dest讀出值再加上data[i],再將結(jié)果寫回dest。這樣的讀寫很浪費,因此每次迭代開始從dest讀出的值就是上次迭代寫回dest的指。優(yōu)化后的版本通過加入acc臨時變量,它循環(huán)中累積計算出的結(jié)果,循環(huán)結(jié)束后再寫回。
這里給出兩個版本相應(yīng)的匯編結(jié)果就可以很清楚看出區(qū)別:
優(yōu)化前:
優(yōu)化前的版本每次迭代都要從dest讀出值再加上data[i],再將結(jié)果寫回dest。這樣的讀寫很浪費,因此每次迭代開始從dest讀出的值就是上次迭代寫回dest的指。優(yōu)化后的版本通過加入acc臨時變量,它循環(huán)中累積計算出的結(jié)果,循環(huán)結(jié)束后再寫回。
第二行和第四行分別對dest進行了讀寫。
優(yōu)化后:
從匯編結(jié)果可以看出編譯器將acc直接放在了寄存器里,循環(huán)中無需對內(nèi)存進行讀寫。
四.循環(huán)展開
循環(huán)展開可以減少循環(huán)的次數(shù),對程序的性能帶了兩方面的提高。一是減少了對循環(huán)沒有直接貢獻的計算,比如循環(huán)計數(shù)變量的計算,分支跳轉(zhuǎn)指令的執(zhí)行等。二是提供了進一步利用機器特性進行的優(yōu)化的機會。
例子:
優(yōu)化前的代碼見前一篇博客里的sum3.
優(yōu)化后:
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;
}
通過循環(huán)展開,每次迭代將累加4個元素,減少了循環(huán)次數(shù),從而減少了總的執(zhí)行時間(單獨使用這種優(yōu)化方法,對浮點數(shù)累乘幾乎沒有提高,但是整數(shù)累乘得益于編譯器的重關(guān)聯(lián)代碼變化會有大幅度提高)。
這種優(yōu)化可以直接利用編譯器完成,將優(yōu)化level設(shè)定到較高,編譯器會自動進行循環(huán)展開。使用gcc,可以顯式使用-funroll-loops選項。
五.提高并行性
現(xiàn)代處理器大多采用了流水線、超標(biāo)量等技術(shù),可以實現(xiàn)指令級并行。我們可以利用這個特性對代碼做進一步的優(yōu)化。
2.1使用多個累積變量
優(yōu)化代碼示例
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;
}
這里同時使用了循環(huán)展開和使用多個累加變量,一方面減少了循環(huán)次數(shù),另一方面指令級并行的特性使得每次迭代的兩次加法可以并行執(zhí)行;谶@兩點可以顯著減少程序執(zhí)行的時間。通過增加展開的次數(shù)和累加變量的個數(shù),可以進一步提高程序的性能,直到機器指令執(zhí)行的吞吐量的極限。
2.2重結(jié)合變換
除了使用多個累積變量顯式利用機器的指令級并行特性外,還可以對運算重新結(jié)合變換,打破順序相關(guān)性來享受指令級并行帶來的好處。
在sum4中,acc=acc+data[i]+data[i+1]的結(jié)合順序是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;
}
進一步增加循環(huán)展開的次數(shù),可以進一步提高程序性能,最終也可以達到機器指令執(zhí)行的吞吐量的極限。(在循環(huán)展示提到的整數(shù)乘法的性能提高就在于編譯器隱式采取了這種變換,但是由于浮點數(shù)不具備結(jié)合性,所以編譯器沒有采用,但是程序員在保證程序結(jié)果正確性的情況下,可以顯式使用這一點)。
【C語言中循環(huán)結(jié)構(gòu)優(yōu)化入門級方法介紹】相關(guān)文章:
關(guān)于c++語言中的循環(huán)語言08-16
C語言循環(huán)結(jié)構(gòu)的嵌套06-18
C語言基礎(chǔ)循環(huán)結(jié)構(gòu)07-28
C語言中while循環(huán)和do...while循環(huán)07-19
C語言中define的全部使用方法介紹10-15
C語言循環(huán)結(jié)構(gòu)知識點07-16
Java 循環(huán)結(jié)構(gòu)介紹08-13
C語言中define的使用方法10-07