我們寫程序的目的就是使它在任何情況下都可以穩定工作。一個運行的很快但是結果錯誤的程序并沒有任何用處。在程序開發和優化的過程中，我們必須考慮代碼使用的方式，以及影響它的關鍵因素。通常，我們必須在程序的簡潔性與它的運行速度之間做出權衡。今天我們就來聊一聊如何優化程序的性能。

1. 減小程序計算量

1.1 示例代碼

for?(i?=?0;?i?

	1.2 分析代碼

	代碼如上所示，外循環每執行一次，我們要進行一次乘法計算。i = 0，ni = 0；i = 1，ni = n；i = 2，ni = 2n。因此，我們可以把乘法換成加法，以n為步長，這樣就減小了外循環的代碼量。

	1.3 改進代碼
int?ni?=?0;
for?(i?=?0;?i?

	計算機中乘法指令要比加法指令慢得多。

	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?=?'A'?&&?s[i]?<=?'Z')
??????s[i]?-=?('A'?-?'a');
}

	3.2 分析代碼

	那么我們就測試下代碼，輸入一系列字符串。

	

	lower1代碼性能測試

	當輸入字符串長度低于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?

	以上代碼分為初始化（第3行），測試（第4行），更新（第9，10行）三部分。初始化只會執行一次。但是測試和更新每次都會執行。每進行一次循環，都會對strlen調用一次。

	下面我們看下strlen函數的源碼是如何計算字符串長度的。
size_t?strlen(const?char?*s)
{
????size_t?length?=?0;
????while?(*s?!=?'')?{
?s++;?
?length++;
????}
????return?length;
}

	strlen函數計算字符串長度的原理為：遍歷字符串，直到遇到‘’才會停止。因此，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?=?'A'?&&?s[i]?<=?'Z')
??????s[i]?-=?('A'?-?'a');
}

	將兩個函數對比下，如下圖所示。lower2函數的執行時間得到明顯提升。

	

	lower1和lower2代碼效率

	4. 消除不必要的內存引用

	4.1 示例代碼

	以下代碼作用為，計算a數組中每一行所有元素的和存在b[i]中。
void?sum_rows1(double?*a,?double?*b,?long?n)?{
????long?i,?j;
????for?(i?=?0;?i?

	4.2 分析代碼

	匯編代碼如下所示。
#?sum_rows1?inner?loop
.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 改進代碼
/*?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?

	匯編如下所示。
#?sum_rows2?inner?loop
.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;


	

	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?

	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?

	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?

	在改進后的代碼中，第一個循環每次處理數組的兩個元素。也就是每次迭代，循環索引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?

	上述代碼用了兩次循環展開，以使每次迭代合并更多的元素，也使用了兩路并行，將索引值為偶數的元素累積在變量acc0中，而索引值為奇數的元素累積在變量acc1中。因此，我們將其稱為”2×2循環展開”。運用2×2循環展開。通過維護多個累積變量，這種方法利用了多個功能單元以及它們的流水線能力

	8. 重新結合變換

	8.1 示例代碼

	我們在combine3的代碼上進行改進。

	8.2 分析代碼

	到這里其實代碼的性能已經基本接近極限了，就算做再多的循環展開性能提升已經不明顯了。我們需要換個思路，注意下combine3代碼中第12行的代碼，我們可以改變下向量元素合并的順序（浮點數不適用）。重新結合前combine3代碼的關鍵路徑如下圖所示。

	

	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;
????
????/*?Combine?2?elements?at?a?time?*/
????for?(i?=?0;?i?

	重新結合變換能夠減少計算中關鍵路徑上操作的數量，這種方法增加了可以并行執行的操作數量了，更好地利用功能單元的流水線能力得到更好的性能。重新結合后關鍵路徑如下所示。

	

	combine3重新結合后關鍵路徑

	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]?

	在原代碼的第4行中，需要對a[i]和b[i]進行比較，再進行下一步操作，這樣的后果是每次都要進行預測。改進后的代碼實現這個函數是計算每個位置i的最大值和最小值，然后將這些值分別賦給a[i]和b[i]，而不是進行分支預測。

	10. 總結

	我們介紹了幾種提高代碼效率的技巧，有些是編譯器可以自動優化的，有些是需要我們自己實現的。現總結如下。

	消除連續的函數調用。在可能時，將計算移到循環外。考慮有選擇地妥協程序的模塊性以獲得更大的效率。

	消除不必要的內存引用。引入臨時變量來保存中間結果。只有在最后的值計算出來時，才將結果存放到數組或全局變量中。

	展開循環，降低開銷，并且使得進一步的優化成為可能。

	通過使用例如多個累積變量和重新結合等技術，找到方法提高指令級并行。

	用功能性的風格重寫條件操作，使得編譯采用條件數據傳送。

	編輯：黃飛

	?