分享9個(gè)提高代碼運(yùn)行效率的小技巧！
我們寫程序的目的就是使它在任何情況下都可以穩(wěn)定工作。一個(gè)運(yùn)行的很快但是結(jié)果錯(cuò)誤的程序并沒(méi)有任何用處。在程序開發(fā)和優(yōu)化的過(guò)程中，我們必須考慮代碼使用的方式，以及影響它的關(guān)鍵因素。通常，我們必須在程序的簡(jiǎn)潔性與它的運(yùn)行速度之間做出權(quán)衡。今天我們就來(lái)聊一聊如何優(yōu)化程序的性能。
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為步長(zhǎng)，這樣就減小了外循環(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展開后會(huì)發(fā)現(xiàn)四格表達(dá)式中都有i*n + j。因此，可以提取出公共部分，再通過(guò)加減運(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 ...
對(duì)于GCC編譯器來(lái)說(shuō)，編譯器可以根據(jù)不同的優(yōu)化等級(jí)，有不同的優(yōu)化方式，會(huì)自動(dòng)完成以上的優(yōu)化操作。下面我們介紹下，那些必須是我們要手動(dòng)優(yōu)化的。
3. 消除循環(huán)中低效代碼
3.1 示例代碼
程序看起來(lái)沒(méi)什么問(wèn)題，一個(gè)很平常的大小寫轉(zhuǎn)換的代碼，但是為什么隨著字符串輸入長(zhǎng)度的變長(zhǎng)，代碼的執(zhí)行時(shí)間會(huì)呈指數(shù)式增長(zhǎng)呢？
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 分析代碼
那么我們就測(cè)試下代碼，輸入一系列字符串。
lower1代碼性能測(cè)試
當(dāng)輸入字符串長(zhǎng)度低于100000時(shí)，程序運(yùn)行時(shí)間差別不大。但是，隨著字符串長(zhǎng)度的增加，程序的運(yùn)行時(shí)間呈指數(shù)時(shí)增長(zhǎng)。
我們把代碼轉(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行），測(cè)試（第4行），更新（第9，10行）三部分。初始化只會(huì)執(zhí)行一次。但是測(cè)試和更新每次都會(huì)執(zhí)行。每進(jìn)行一次循環(huán)，都會(huì)對(duì)strlen調(diào)用一次。
下面我們看下strlen函數(shù)的源碼是如何計(jì)算字符串長(zhǎng)度的。
size_t strlen(const char *s) { size_t length = 0; while (*s != '\0') { s++; length++; } return length; }
strlen函數(shù)計(jì)算字符串長(zhǎng)度的原理為：遍歷字符串，直到遇到‘\0’才會(huì)停止。因此，strlen函數(shù)的時(shí)間復(fù)雜度為O（N）。lower1中，對(duì)于長(zhǎng)度為N的字符串來(lái)說(shuō)，strlen 的調(diào)用次數(shù)為N,N-1,N-2 ... 1。對(duì)于一個(gè)線性時(shí)間的函數(shù)調(diào)用N次，其時(shí)間復(fù)雜度接近于O（N2）。
3.3 改進(jìn)代碼
對(duì)于循環(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ù)對(duì)比下，如下圖所示。lower2函數(shù)的執(zhí)行時(shí)間得到明顯提升。
lower1和lower2代碼效率
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)存中讀取出來(lá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í)變量來(lái)保存中間結(jié)果，只有在最后的值計(jì)算出來(lái)時(shí)，才將結(jié)果存放到數(shù)組或全局變量中。
5. 減小不必要的調(diào)用
5.1 示例代碼
為了方便舉例，我們定義一個(gè)包含數(shù)組和數(shù)組長(zhǎng)度的結(jié)構(gòu)體，主要是為了防止數(shù)組訪問(wèn)越界，data_t可以是int，long等類型。具體如下所示。
typedef struct{ size_t len; data_t *data; } vec;
vec向量示意圖
get_vec_element函數(shù)的作用是遍歷data數(shù)組中元素并存儲(chǔ)在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)行就會(huì)造成效率降低。
5.3 改進(jìn)代碼
我們可以把求向量長(zhǎng)度的代碼移到循環(huán)體外，同時(shí)抽象數(shù)據(jù)類型增加一個(gè)函數(shù)get_vec_start。這個(gè)函數(shù)返回?cái)?shù)組的起始地址。這樣在循環(huán)體中就沒(méi)有了函數(shù)調(diào)用，而是直接訪問(wèn)數(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 示例代碼
我們?cè)赾ombine2的代碼上進(jìn)行改進(jìn)。
6.2 分析代碼
循環(huán)展開是通過(guò)增加每次迭代計(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，在一次迭代中，對(duì)數(shù)組元素i和i+1使用合并運(yùn)算。一般我們稱這種為2×1循環(huán)展開，這種變換能減小循環(huán)開銷的影響。
注意訪問(wèn)不要越界，正確設(shè)置limit，n個(gè)元素，一般設(shè)置界限n-1
7. 累計(jì)變量，多路并行
7.1 示例代碼
我們?cè)赾ombine3的代碼上進(jìn)行改進(jìn)。
7.2 分析代碼
對(duì)于一個(gè)可結(jié)合和可交換的合并運(yùn)算來(lái)說(shuō)，比如說(shuō)整數(shù)加法或乘法，我們可以通過(guò)將一組合并運(yùn)算分割成兩個(gè)或更多的部分，并在最后合并結(jié)果來(lái)提高性能。
特別注意：不要輕易對(duì)浮點(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)展開。通過(guò)維護(hù)多個(gè)累積變量，這種方法利用了多個(gè)功能單元以及它們的流水線能力
8. 重新結(jié)合變換
8.1 示例代碼
我們?cè)赾ombine3的代碼上進(jìn)行改進(jìn)。
8.2 分析代碼
到這里其實(shí)代碼的性能已經(jīng)基本接近極限了，就算做再多的循環(huán)展開性能提升已經(jīng)不明顯了。我們需要換個(gè)思路，注意下combine3代碼中第12行的代碼，我們可以改變下向量元素合并的順序（浮點(diǎn)數(shù)不適用）。重新結(jié)合前combine3代碼的關(guān)鍵路徑如下圖所示。
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 OP (data[i] OP data[i+1]); } /* Finish any remaining elements */ for (; i < length; i++) { acc = acc OP data[i]; } *dest = acc; }
重新結(jié)合變換能夠減少計(jì)算中關(guān)鍵路徑上操作的數(shù)量，這種方法增加了可以并行執(zhí)行的操作數(shù)量了，更好地利用功能單元的流水線能力得到更好的性能。重新結(jié)合后關(guān)鍵路徑如下所示。
combine3重新結(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ù)測(cè)在遇到比較指令時(shí)會(huì)進(jìn)行預(yù)測(cè)下一步跳轉(zhuǎn)到哪里。如果預(yù)測(cè)錯(cuò)誤，就要重新回到分支跳轉(zhuǎn)的原地。分支預(yù)測(cè)錯(cuò)誤會(huì)嚴(yán)重影響程序的執(zhí)行效率。因此，我們應(yīng)該編寫讓處理器預(yù)測(cè)準(zhǔn)確率提高的代碼，即使用條件傳送指令。我們用條件操作來(lái)計(jì)算值，然后用這些值來(lái)更新程序狀態(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行中，需要對(duì)a[i]和b[i]進(jìn)行比較，再進(jìn)行下一步操作，這樣的后果是每次都要進(jìn)行預(yù)測(cè)。改進(jìn)后的代碼實(shí)現(xiàn)這個(gè)函數(shù)是計(jì)算每個(gè)位置i的最大值和最小值，然后將這些值分別賦給a[i]和b[i]，而不是進(jìn)行分支預(yù)測(cè)。
10. 總結(jié)
我們介紹了幾種提高代碼效率的技巧，有些是編譯器可以自動(dòng)優(yōu)化的，有些是需要我們自己實(shí)現(xiàn)的?，F(xiàn)總結(jié)如下。
-
消除連續(xù)的函數(shù)調(diào)用。在可能時(shí)，將計(jì)算移到循環(huán)外?？紤]有選擇地妥協(xié)程序的模塊性以獲得更大的效率。
-
消除不必要的內(nèi)存引用。引入臨時(shí)變量來(lái)保存中間結(jié)果。只有在最后的值計(jì)算出來(lái)時(shí)，才將結(jié)果存放到數(shù)組或全局變量中。
-
展開循環(huán)，降低開銷，并且使得進(jìn)一步的優(yōu)化成為可能。
-
通過(guò)使用例如多個(gè)累積變量和重新結(jié)合等技術(shù)，找到方法 提高指令級(jí)并行。
-
用功能性的風(fēng)格重寫條件操作，使得編譯采用條件數(shù)據(jù)傳送。
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問(wèn)題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
