我們寫程序的目的就是使它在任何情況下都可以穩(wěn)定工作领舰。一個(gè)運(yùn)行的很快但是結(jié)果錯(cuò)誤的程序并沒有任何用處夫嗓。在程序開發(fā)和優(yōu)化的過程中迟螺，我們必須考慮代碼使用的方式，以及影響它的關(guān)鍵因素舍咖。通常矩父，我們必須在程序的簡潔性與它的運(yùn)行速度之間做出權(quán)衡。今天我們就來聊一聊如何優(yōu)化程序的性能排霉。
@[toc]
1. 減小程序計(jì)算量
1.1 示例代碼
for (i = 0; i < n; i++) {
int ni = n*i;
for (j = 0; j < n; j++)
a[ni + j] = b[j];
}
1.2 分析代碼
??代碼如上所示窍株，外循環(huán)每執(zhí)行一次，我們要進(jìn)行一次乘法計(jì)算攻柠。i = 0球订，ni = 0；i = 1瑰钮，ni = n冒滩；i = 2，ni = 2n浪谴。因此开睡，我們可以把乘法換成加法，以n為步長苟耻，這樣就減小了外循環(huán)的代碼量篇恒。
1.3 改進(jìn)代碼
int ni = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
a[ni + j] = b[j];
ni += n; //乘法改加法
}
計(jì)算機(jī)中加法指令要比乘法指令快得多。
2. 提取代碼中的公共部分
2.1 示例代碼
??想象一下凶杖，我們有一個(gè)圖像胁艰，我們把圖像表示為二維數(shù)組，數(shù)組元素代表像素點(diǎn)。我們想要得到給定像素的東腾么、南醋虏、西、北四個(gè)鄰居的總和哮翘。并求他們的平均值或他們的和颈嚼。代碼如下所示。
up = val[(i-1)*n + j ];
down = val[(i+1)*n + j ];
left = val[i*n + j-1];
right = val[i*n + j+1];
sum = up + down + left + right;
2.2 分析代碼
??將以上代碼編譯后得到匯編代碼如下所示饭寺，注意下3,4,5行阻课，有三個(gè)乘以n的乘法運(yùn)算。我們把上面的up和down展開后會發(fā)現(xiàn)四格表達(dá)式中都有i*n + j艰匙。因此限煞，可以提取出公共部分，再通過加減運(yùn)算分別得出up员凝、down等的值署驻。
leaq 1(%rsi), %rax # i+1
leaq -1(%rsi), %r8 # i-1
imulq %rcx, %rsi # i*n
imulq %rcx, %rax # (i+1)*n
imulq %rcx, %r8 # (i-1)*n
addq %rdx, %rsi # i*n+j
addq %rdx, %rax # (i+1)*n+j
addq %rdx, %r8 # (i-1)*n+j
2.3 改進(jìn)代碼
long inj = i*n + j;
up = val[inj - n];
down = val[inj + n];
left = val[inj - 1];
right = val[inj + 1];
sum = up + down + left + right;
??改進(jìn)后的代碼的匯編如下所示。編譯后只有一個(gè)乘法健霹。減少了6個(gè)時(shí)鐘周期（一個(gè)乘法周期大約為3個(gè)時(shí)鐘周期）旺上。
imulq %rcx, %rsi # i*n
addq %rdx, %rsi # i*n+j
movq %rsi, %rax # i*n+j
subq %rcx, %rax # i*n+j-n
leaq (%rsi,%rcx), %rcx # i*n+j+n
...
??對于GCC編譯器來說，編譯器可以根據(jù)不同的優(yōu)化等級糖埋，有不同的優(yōu)化方式宣吱，會自動(dòng)完成以上的優(yōu)化操作。下面我們介紹下瞳别，那些必須是我們要手動(dòng)優(yōu)化的征候。
3. 消除循環(huán)中低效代碼
3.1 示例代碼
??程序看起來沒什么問題，一個(gè)很平常的大小寫轉(zhuǎn)換的代碼祟敛，但是為什么隨著字符串輸入長度的變長疤坝，代碼的執(zhí)行時(shí)間會呈指數(shù)式增長呢？
void lower1(char *s)
{
size_t i;
for (i = 0; i < strlen(s); i++)
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
}
3.2 分析代碼
??那么我們就測試下代碼馆铁，輸入一系列字符串跑揉。
??當(dāng)輸入字符串長度低于100000時(shí)，程序運(yùn)行時(shí)間差別不大叼架。但是畔裕，隨著字符串長度的增加，程序的運(yùn)行時(shí)間呈指數(shù)時(shí)增長乖订。
??我們把代碼轉(zhuǎn)換成goto形式看下扮饶。
void lower1(char *s)
{
size_t i = 0;
if (i >= strlen(s))
goto done;
loop:
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
i++;
if (i < strlen(s))
goto loop;
done:
}
??以上代碼分為初始化（第3行），測試（第4行）乍构，更新（第9甜无，10行）三部分扛点。初始化只會執(zhí)行一次。但是測試和更新每次都會執(zhí)行岂丘。每進(jìn)行一次循環(huán)陵究，都會對strlen調(diào)用一次。
??下面我們看下strlen函數(shù)的源碼是如何計(jì)算字符串長度的奥帘。
size_t strlen(const char *s)
{
size_t length = 0;
while (*s != '\0') {
s++;
length++;
}
return length;
}
??strlen函數(shù)計(jì)算字符串長度的原理為：遍歷字符串铜邮，直到遇到‘\0’才會停止。因此寨蹋，strlen函數(shù)的時(shí)間復(fù)雜度為O（N）松蒜。lower1中，對于長度為N的字符串來說已旧，strlen 的調(diào)用次數(shù)為N,N-1,N-2 ... 1秸苗。對于一個(gè)線性時(shí)間的函數(shù)調(diào)用N次，其時(shí)間復(fù)雜度接近于O（N2）运褪。
版權(quán)聲明：本文為博主原創(chuàng)文章惊楼，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接和本聲明秸讹。本文鏈接：https://blog.csdn.net/qq_16933601/article/details/111639650
3.3 改進(jìn)代碼
??對于循環(huán)中出現(xiàn)的這種冗余調(diào)用檀咙，我們可以將其移動(dòng)到循環(huán)外。將計(jì)算結(jié)果用于循環(huán)中嗦枢。改進(jìn)后的代碼如下所示攀芯。
void lower2(char *s)
{
size_t i;
size_t len = strlen(s);
for (i = 0; i < len; i++)
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] -= ('A' - 'a');
}
??將兩個(gè)函數(shù)對比下，如下圖所示文虏。lower2函數(shù)的執(zhí)行時(shí)間得到明顯提升。
4. 消除不必要的內(nèi)存引用
4.1 示例代碼
??以下代碼作用為殖演，計(jì)算a數(shù)組中每一行所有元素的和存在b[i]中氧秘。
void sum_rows1(double *a, double *b, long n) {
long i, j;
for (i = 0; i < n; i++) {
b[i] = 0;
for (j = 0; j < n; j++)
b[i] += a[i*n + j];
}
}
4.2 分析代碼
??匯編代碼如下所示。
# sum_rows1 inner loop
.L4:
movsd (%rsi,%rax,8), %xmm0 # 從內(nèi)存中讀取某個(gè)值放到%xmm0
addsd (%rdi), %xmm0 # %xmm0 加上某個(gè)值
movsd %xmm0, (%rsi,%rax,8) # %xmm0 的值寫回內(nèi)存趴久，其實(shí)就是b[i]
addq $8, %rdi
cmpq %rcx, %rdi
jne .L4
??這意味著每次循環(huán)都需要從內(nèi)存中讀取b[i]丸相，然后再把b[i]寫回內(nèi)存 。 b[i] += b[i] + a[i*n + j]; 其實(shí)每次循環(huán)開始的時(shí)候彼棍，b[i]就是上一次的值灭忠。為什么每次都要從內(nèi)存中讀取出來再寫回呢？
4.3 改進(jìn)代碼
/* Sum rows is of n X n matrix a
and store in vector b */
void sum_rows2(double *a, double *b, long n) {
long i, j;
for (i = 0; i < n; i++) {
double val = 0;
for (j = 0; j < n; j++)
val += a[i*n + j];
b[i] = val;
}
}
??匯編如下所示座硕。
# sum_rows2 inner loop
.L10:
addsd (%rdi), %xmm0 # FP load + add
addq $8, %rdi
cmpq %rax, %rdi
jne .L10
??改進(jìn)后的代碼引入了臨時(shí)變量來保存中間結(jié)果弛作，只有在最后的值計(jì)算出來時(shí)，才將結(jié)果存放到數(shù)組或全局變量中华匾。
5. 減小不必要的調(diào)用
5.1 示例代碼
??為了方便舉例映琳，我們定義一個(gè)包含數(shù)組和數(shù)組長度的結(jié)構(gòu)體，主要是為了防止數(shù)組訪問越界，data_t可以是int萨西，long等類型有鹿。具體如下所示。
typedef struct{
size_t len;
data_t *data;
} vec;
??get_vec_element函數(shù)的作用是遍歷data數(shù)組中元素并存儲在val中谎脯。
int get_vec_element (*vec v, size_t idx, data_t *val)
{
if (idx >= v->len)
return 0;
*val = v->data[idx];
return 1;
}
??我們將以以下代碼為例開始一步步優(yōu)化程序葱跋。
void combine1(vec_ptr v, data_t *dest)
{
long int i;
*dest = NULL;
for (i = 0; i < vec_length(v); i++) {
data_t val;
get_vec_element(v, i, &val);
*dest = *dest * val;
}
}
5.2 分析代碼
??get_vec_element函數(shù)的作用是獲取下一個(gè)元素，在get_vec_element函數(shù)中源梭，每次循環(huán)都要與v->len作比較年局，防止越界。進(jìn)行邊界檢查是個(gè)好習(xí)慣咸产，但是每次都進(jìn)行就會造成效率降低矢否。
5.3 改進(jìn)代碼
??我們可以把求向量長度的代碼移到循環(huán)體外，同時(shí)抽象數(shù)據(jù)類型增加一個(gè)函數(shù)get_vec_start脑溢。這個(gè)函數(shù)返回?cái)?shù)組的起始地址僵朗。這樣在循環(huán)體中就沒有了函數(shù)調(diào)用，而是直接訪問數(shù)組屑彻。
data_t *get_vec_start(vec_ptr v)
{
return v->data;
}
void combine2 (vec_ptr v, data_t *dest)
{
long i;
long length = vec_length(v);
data_t *data = get_vec_start(v);
*dest = NULL;
for (i=0;i < length;i++)
{
*dest = *dest * data[i];
}
}
6. 循環(huán)展開
6.1 示例代碼
??我們在combine2的代碼上進(jìn)行改進(jìn)验庙。
6.2 分析代碼
??循環(huán)展開是通過增加每次迭代計(jì)算的元素的數(shù)量，減少循環(huán)的迭代次數(shù)社牲。
6.3 改進(jìn)代碼
void combine3(vec_ptr v, data_t *dest)
{
long i;
long length = vec_length(v);
long limit = length-1;
data_t *data = get_vec_start(v);
data_t acc = NULL;
/* 一次循環(huán)處理兩個(gè)元素 */
for (i = 0; i < limit; i+=2) {
acc = (acc * data[i]) * data[i+1];
}
/* 完成剩余數(shù)組元素的計(jì)算 */
for (; i < length; i++) {
acc = acc * data[i];
}
*dest = acc;
}
??在改進(jìn)后的代碼中粪薛，第一個(gè)循環(huán)每次處理數(shù)組的兩個(gè)元素。也就是每次迭代搏恤，循環(huán)索引i加2违寿，在一次迭代中，對數(shù)組元素i和i+1使用合并運(yùn)算熟空。一般我們稱這種為2×1循環(huán)展開藤巢，這種變換能減小循環(huán)開銷的影響。
注意訪問不要越界息罗，正確設(shè)置limit掂咒，n個(gè)元素，一般設(shè)置界限n-1
7. 累計(jì)變量迈喉，多路并行
7.1 示例代碼
??我們在combine3的代碼上進(jìn)行改進(jìn)绍刮。
7.2 分析代碼
??對于一個(gè)可結(jié)合和可交換的合并運(yùn)算來說，比如說整數(shù)加法或乘法挨摸，我們可以通過將一組合并運(yùn)算分割成兩個(gè)或更多的部分孩革，并在最后合并結(jié)果來提高性能。
特別注意：不要輕易對浮點(diǎn)數(shù)進(jìn)行結(jié)合油坝。浮點(diǎn)數(shù)的編碼格式和其他整型數(shù)等都不一樣嫉戚。
7.3 改進(jìn)代碼
void combine4(vec_ptr v, data_t *dest)
{
long i;
long length = vec_length(v);
long limit = length-1;
data_t *data = get_vec_start(v);
data_t acc0 = 0;
data_t acc1 = 0;
/* 循環(huán)展開刨裆，并維護(hù)兩個(gè)累計(jì)變量 */
for (i = 0; i < limit; i+=2) {
acc0 = acc0 * data[i];
acc1 = acc1 * data[i+1];
}
/* 完成剩余數(shù)組元素的計(jì)算 */
for (; i < length; i++) {
acc0 = acc0 * data[i];
}
*dest = acc0 * acc1;
}
??上述代碼用了兩次循環(huán)展開，以使每次迭代合并更多的元素彬檀，也使用了兩路并行帆啃，將索引值為偶數(shù)的元素累積在變量acc0中，而索引值為奇數(shù)的元素累積在變量acc1中窍帝。因此努潘，我們將其稱為”2×2循環(huán)展開”。運(yùn)用2×2循環(huán)展開坤学。通過維護(hù)多個(gè)累積變量疯坤，這種方法利用了多個(gè)功能單元以及它們的流水線能力
8. 重新結(jié)合變換
8.1 示例代碼
??我們在combine3的代碼上進(jìn)行改進(jìn)。
8.2 分析代碼
??到這里其實(shí)代碼的性能已經(jīng)基本接近極限了深浮，就算做再多的循環(huán)展開性能提升已經(jīng)不明顯了压怠。我們需要換個(gè)思路，注意下combine3代碼中第12行的代碼飞苇，我們可以改變下向量元素合并的順序（浮點(diǎn)數(shù)不適用）菌瘫。重新結(jié)合前combine3代碼的關(guān)鍵路徑如下圖所示。
8.3 改進(jìn)代碼
void combine7(vec_ptr v, data_t *dest)
{
long i;
long length = vec_length(v);
long limit = length-1;
data_t *data = get_vec_start(v);
data_t acc = IDENT;
/* Combine 2 elements at a time */
for (i = 0; i < limit; i+=2) {
acc = acc * (data[i] * data[i+1]);
}
/* Finish any remaining elements */
for (; i < length; i++) {
acc = acc * data[i];
}
*dest = acc;
}
??重新結(jié)合變換能夠減少計(jì)算中關(guān)鍵路徑上操作的數(shù)量布卡，這種方法增加了可以并行執(zhí)行的操作數(shù)量了雨让，更好地利用功能單元的流水線能力得到更好的性能。重新結(jié)合后關(guān)鍵路徑如下所示忿等。
9 條件傳送風(fēng)格的代碼
9.1 示例代碼
void minmax1(long a[],long b[],long n){
long i;
for(i = 0;i,n;i++){
if(a[i]>b[i]){
long t = a[i];
a[i] = b[i];
b[i] = t;
}
}
}
9.2 分析代碼
??現(xiàn)代處理器的流水線性能使得處理器的工作遠(yuǎn)遠(yuǎn)超前于當(dāng)前正在執(zhí)行的指令栖忠。處理器中的分支預(yù)測在遇到比較指令時(shí)會進(jìn)行預(yù)測下一步跳轉(zhuǎn)到哪里。如果預(yù)測錯(cuò)誤贸街，就要重新回到分支跳轉(zhuǎn)的原地庵寞。分支預(yù)測錯(cuò)誤會嚴(yán)重影響程序的執(zhí)行效率。因此匾浪，我們應(yīng)該編寫讓處理器預(yù)測準(zhǔn)確率提高的代碼皇帮，即使用條件傳送指令。我們用條件操作來計(jì)算值蛋辈，然后用這些值來更新程序狀態(tài)，具體如改進(jìn)后的代碼所示将谊。
9.3 改進(jìn)代碼
void minmax2(long a[],long b[],long n){
long i;
for(i = 0;i,n;i++){
long min = a[i] < b[i] ? a[i]:b[i];
long max = a[i] < b[i] ? b[i]:a[i];
a[i] = min;
b[i] = max;
}
}
??在原代碼的第4行中冷溶，需要對a[i]和b[i]進(jìn)行比較，再進(jìn)行下一步操作尊浓，這樣的后果是每次都要進(jìn)行預(yù)測逞频。改進(jìn)后的代碼實(shí)現(xiàn)這個(gè)函數(shù)是計(jì)算每個(gè)位置i的最大值和最小值，然后將這些值分別賦給a[i]和b[i]栋齿，而不是進(jìn)行分支預(yù)測苗胀。
10. 總結(jié)
??我們介紹了幾種提高代碼效率的技巧襟诸，有些是編譯器可以自動(dòng)優(yōu)化的，有些是需要我們自己實(shí)現(xiàn)的』現(xiàn)總結(jié)如下歌亲。
消除連續(xù)的函數(shù)調(diào)用。在可能時(shí)澜驮，將計(jì)算移到循環(huán)外陷揪。考慮有選擇地妥協(xié)程序的模塊性以獲得更大的效率杂穷。
消除不必要的內(nèi)存引用悍缠。引入臨時(shí)變量來保存中間結(jié)果。只有在最后的值計(jì)算出來時(shí)耐量，才將結(jié)果存放到數(shù)組或全局變量中飞蚓。
展開循環(huán)，降低開銷廊蜒，并且使得進(jìn)一步的優(yōu)化成為可能趴拧。
通過使用例如多個(gè)累積變量和重新結(jié)合等技術(shù)，找到方法 提高指令級并行劲藐。
用功能性的風(fēng)格重寫條件操作八堡，使得編譯采用條件數(shù)據(jù)傳送。
??養(yǎng)成習(xí)慣聘芜，先贊后看兄渺！如果覺得寫的不錯(cuò)，歡迎關(guān)注汰现，點(diǎn)贊挂谍，在看，轉(zhuǎn)發(fā)瞎饲，謝謝口叙！
版權(quán)聲明：本文為博主原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議嗅战，轉(zhuǎn)載請附上原文出處鏈接和本聲明妄田。
本文鏈接：https://blog.csdn.net/qq_16933601/article/details/111639650
