我們寫程式的目的就是使它在任何情況下都可以穩定工作。一個運作的很快但是結果錯誤的程式并沒有任何用處。在程式開發和優化的過程中，我們必須考慮代碼使用的方式，以及影響它的關鍵因素。通常，我們必須在程式的簡潔性與它的運作速度之間做出權衡。今天我們就來聊一聊如何優化程式的性能。
1. 減小程式計算量
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 分析代碼
代碼如上所示，外循環每執行一次，我們要進行一次乘法計算。i = 0，ni = 0；i = 1，ni = n；i = 2，ni = 2n。是以，我們可以把乘法換成加法，以n為步長，這樣就減小了外循環的代碼量。
1.3 改進代碼
int ni = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
a[ni + j] = b[j];
ni += n; //乘法改加法
} 計算機中加法指令要比乘法指令快得多。
2. 提取代碼中的公共部分
2.1 示例代碼
想象一下，我們有一個圖像，我們把圖像表示為二維數組，數組元素代表像素點。我們想要得到給定像素的東、南、西、北四個鄰居的總和。并求他們的平均值或他們的和。代碼如下所示。
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行，有三個乘以n的乘法運算。我們把上面的up和down展開後會發現四格表達式中都有
i*n + j
。是以，可以提取出公共部分 ，再通過加減運算分别得出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 改進代碼
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; 改進後的代碼的彙編如下所示。編譯後隻有一個乘法。減少了6個時鐘周期（一個乘法周期大約為3個時鐘周期）。
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編譯器來說，編譯器可以根據不同的優化等級，有不同的優化方式，會自動完成以上的優化操作。下面我們介紹下，那些必須是我們要手動優化的。
3. 消除循環中低效代碼
3.1 示例代碼
程式看起來沒什麼問題，一個很平常的大小寫轉換的代碼，但是為什麼随着字元串輸入長度的變長，代碼的執行時間會呈指數式增長呢？
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 分析代碼
那麼我們就測試下代碼，輸入一系列字元串。
當輸入字元串長度低于100000時，程式運作時間差别不大。但是，随着字元串長度的增加，程式的運作時間呈指數式增長。
我們把代碼轉換成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行）三部分。初始化隻會執行一次。但是測試和更新每次都會執行。每進行一次循環，都會對strlen調用一次。
下面我們看下strlen函數的源碼是如何計算字元串長度的。
size_t strlen(const char *s)
{
size_t length = 0;
while (*s != '\0') {
s++;
length++;
}
return length;
} strlen函數計算字元串長度的原理為：周遊字元串，直到遇到‘\0’才會停止。是以，strlen函數的時間複雜度為O（N）。lower1中，對于長度為N的字元串來說，strlen 的調用次數為N,N-1,N-2 ... 1。對于一個線性時間的函數調用N次，其時間複雜度接近于O（N2）。
3.3 改進代碼
對于循環中出現的這種備援調用，我們可以将其移動到循環外，将計算結果用于循環中。改進後的代碼如下所示。
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');
} 将兩個函數對比下，如下圖所示。lower2函數的執行時間得到明顯提升。
4. 消除不必要的記憶體引用
4.1 示例代碼
以下代碼作用為，計算a數組中每一行所有元素的和存在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 分析代碼
彙編代碼如下所示。
.L4:
movsd (%rsi,%rax,8), %xmm0 # 從記憶體中讀取某個值放到%xmm0
addsd (%rdi), %xmm0 # %xmm0 加上某個值
movsd %xmm0, (%rsi,%rax,8) # %xmm0 的值寫回記憶體，其實就是b[i]
addq $8, %rdi
cmpq %rcx, %rdi
jne .L4 分析彙編代碼可知，每次循環都需要從記憶體中讀取b[i]，然後再把b[i]寫回記憶體 。
b[i] += b[i] + a[i*n + j]
; 其實每次循環開始的時候，b[i]就是上一次的值。為什麼每次都要從記憶體中讀取出來再寫回呢？
4.3 改進代碼
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;
}
}
彙編如下所示。
.L10:
addsd (%rdi), %xmm0 # FP load + add
addq $8, %rdi
cmpq %rax, %rdi
jne .L10 改進後的代碼引入了臨時變量來儲存中間結果，隻有在最後的值計算出來時，才将結果存放到數組或全局變量中。
5. 減小不必要的調用
5.1 示例代碼
為了友善舉例，我們定義一個包含數組和數組長度的結構體，主要是為了防止數組通路越界，data_t可以是int，long等類型。具體如下所示。
typedef struct{
size_t len;
data_t *data;
} vec; get_vec_element函數的作用是周遊data數組中元素并存儲在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;
} 我們将使用以下代碼為例，開始一步步優化程式。
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函數的作用是擷取下一個元素，在get_vec_element函數中，每次循環都要與v->len作比較，防止越界。進行邊界檢查是個好習慣，但是每次都進行就會造成效率降低。
5.3 改進代碼
我們可以把求向量長度的代碼移到循環體外，同時抽象資料類型增加一個函數get_vec_start。這個函數傳回數組的起始位址。這樣在循環體中就沒有了函數調用，而是直接通路數組。
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. 循環展開
6.1 示例代碼
我們在combine2的代碼上進行改進。
6.2 分析代碼
循環展開是通過增加每次疊代計算的元素的數量，減少循環的疊代次數。
6.3 改進代碼
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;
/* 一次循環處理兩個元素 */
for (i = 0; i < limit; i+=2) {
acc = (acc * data[i]) * data[i+1];
}
/*完成剩餘數組元素的計算 */
for (; i < length; i++) {
acc = acc * data[i];
}
*dest = acc;
} 在改進後的代碼中，第一個循環每次處理數組的兩個元素。也就是每次疊代，循環索引i加2，在一次疊代中，對數組元素i和i+1使用合并運算。一般我們稱這種為2×1循環展開，這種變換能減小循環開銷的影響。
注意通路不要越界，正确設定limit，n個元素，一般設定界限n-1
7. 累計變量，多路并行
7.1 示例代碼
我們在combine3的代碼上進行改進。
7.2 分析代碼
對于一個可結合和可交換的合并運算來說，比如說整數加法或乘法，我們可以通過将一組合并運算分割成兩個或更多的部分，并在最後合并結果來提高性能。
特别注意：不要輕易對浮點數進行結合。浮點數的編碼格式和其他整型數等都不一樣。
7.3 改進代碼
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;
/* 循環展開，并維護兩個累計變量 */
for (i = 0; i < limit; i+=2) {
acc0 = acc0 * data[i];
acc1 = acc1 * data[i+1];
}
/* 完成剩餘數組元素的計算 */
for (; i < length; i++) {
acc0 = acc0 * data[i];
}
*dest = acc0 * acc1;
} 上述代碼用了兩次循環展開，以使每次疊代合并更多的元素，也使用了兩路并行，将索引值為偶數的元素累積在變量acc0中，而索引值為奇數的元素累積在變量acc1中。是以，我們将其稱為”2×2循環展開”。運用2×2循環展開。通過維護多個累積變量，這種方法利用了多個功能單元以及它們的流水線能力。
8. 重新結合變換
8.1 示例代碼
8.2 分析代碼
到這裡其實代碼的性能已經基本接近極限了，就算做再多的循環展開性能提升已經不明顯了。我們需要換個思路，注意下combine3代碼中第12行的代碼，我們可以改變下向量元素合并的順序（浮點數不适用）。重新結合前combine3代碼的關鍵路徑如下圖所示。
8.3 改進代碼
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;
/* 一次計算兩個元素 */
for (i = 0; i < limit; i+=2) {
acc = acc * (data[i] * data[i+1]);
}
/*計算剩餘部分 */
for (; i < length; i++) {
acc = acc * data[i];
}
*dest = acc;
} 重新結合變換能夠減少計算中關鍵路徑上操作的數量，這種方法增加了可以并行執行的操作數量，更好地利用功能單元的流水線能力得到更好的性能。重新結合後關鍵路徑如下所示。
9 條件傳送風格的代碼
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 分析代碼
現代處理器的流水線性能使得處理器的工作遠遠超前于目前正在執行的指令。處理器中的分支預測在遇到比較指令時會進行預測下一步跳轉到哪裡。如果預測錯誤，就要重新回到分支跳轉的原地。分支預測錯誤會嚴重影響程式的執行效率。是以，我們應該編寫讓處理器預測準确率提高的代碼，即使用條件傳送指令。我們用條件操作來計算值，然後用這些值來更新程式狀态，改進後的代碼所下所示。
9.3 改進代碼
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]進行比較，再進行下一步操作，這樣的後果是每次都要進行預測。改進後的代碼實作這個函數是計算每個位置i的最大值和最小值，然後将這些值分别賦給a[i]和b[i]，而不是進行分支預測。
10. 總結
我們介紹了幾種提高代碼效率的技巧，有些是編譯器可以自動優化的，有些是需要我們自己實作的。現總結如下。
1.消除連續的函數調用。在可能時，将計算移到循環外。考慮有選擇地妥協程式的子產品性以獲得更大的效率。
2.消除不必要的記憶體引用。引入臨時變量來儲存中間結果。隻有在最後的值計算出來時，才将結果存放到數組或全局變量中。
3.展開循環，降低開銷，并且使得進一步的優化成為可能。