最近在惡補計算機基礎知識，學到CSAPP第五章的內容，在這里總結并且展開一下C++程序性能優化相關的內容。

衡量程序性能的方式

一般而言，程序的性能可以用CPE（Cycles Per Element）來衡量，其指的是處理每個元素所需的CPU時鐘周期數，計算公式為：CPE = 總執行周期數/處理的元素數量。

計算方式為：

#include <iostream>
#include <chrono>const int N = 1000000;
int arr[N];void test_function() {for (int i = 0; i < N; i++) {arr[i] = i * 2;}
}int main() {auto start = std::chrono::high_resolution_clock::now();test_function();auto end = std::chrono::high_resolution_clock::now();double elapsed_cycles = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() * 2.5; // 假設CPU 2.5 GHzdouble cpe = elapsed_cycles / N; // 計算 CPEstd::cout << "CPE: " << cpe << std::endl;return 0;
}

影響編譯器優化的因素

用gcc時，gcc -Og可以指定優化方式，但隨著優化等級升高，程序規模也可能增加。

gcc優化等級

• -O1：不會進行激進優化（如函數內聯、代碼重排序），不會影響可讀性，編譯時間仍然較短。優化包括死代碼消除、常量傳播、循環優化等。
• -O2：在基本優化的基礎上增加更高級優化：消除冗余計算、循環展開、指令調度、函數內聯、分支預測優化，仍然不會進行極端優化。
• -O3：實現更激進的循環展開、自動使用SIMD指令，使函數盡可能內聯，并消除冗余加載和存儲，對復雜的數學運算進行優化。但可能導致代碼膨脹，過度優化會導致性能下降，如緩存效率降低。
• -Os：基于-O2，但會避免增加代碼大小的優化，適合嵌入式系統。

以下為一些妨礙編譯器優化的因素：

內存別名使用

對于以下看似相同的代碼段：

//代碼段1
void twiddle1(long *xp, long *yp){*xp += *yp;*xp += *yp;
}//代碼段2
void twiddle2(long *xp, long* yp){*xp += 2* *yp;
}

很顯然，代碼段2的執行所需耗費時間更短，其需要的內存訪問次數更少。

然而，編譯器無法將代碼1優化為代碼2，因為當yp=xp時，代碼1等效于xp = 4 xp, 而代碼2等效于 *xp = 3 * *xp，編譯器不知道函數該如何被調用。這種兩個指針可能指向同一個內存位置的情況稱為內存別名使用，在只執行安全的優化中，編譯器必須假設不同的指針可能會指向內存中同一位置。

修改全局程序狀態的函數

對于以下看似相同的代碼段：

long counter = 0;
long f(){return counter++;
}
//代碼段1
long func1(){return f()+f()+f()+f();
}
//代碼段2
long func2(){return 4*f();
}

當函數f的返回值涉及到全局變量counter時，可以看出，func1的輸出為6，而func2的輸出為0。

將函數定義為內聯函數，可以直接將函數調用替換為函數體，例如，代碼段1在o1優化下可以展開為：

long funclin(){long t = counter++;t += counter++;t += counter++;t += counter++;return t;
}

如果使用-o2及以上優化，可能會展開為：

long funclin() {long tmp = counter;counter += 4;return tmp + (tmp + 1) + (tmp + 2) + (tmp + 3);
}

直接優化方法

為了舉例說明優化方法是如何實現的，我們定義向量數據結構如下：

typedef struct{long len;data_t *data;
} vec_rec, *vec_ptr;

data_t代表基本元素的數據類型。

定義初始化該向量、訪問向量元素以及獲取向量長度的方法如下：

/* Create vector of specified length */
vec_ptr new_vec(long len)
{/* Allocate header structure */vec_ptr result = (vec_ptr) malloc(sizeof(vec_rec));data_t *data = NULL;if (!result)return NULL;  /* Couldn't allocate storage */result->len = len;/* Allocate array */if (len > 0) {data = (data_t *)calloc(len, sizeof(data_t));if (!data) {free((void *) result);return NULL; /* Couldn't allocate storage */}}/* Data will either be NULL or allocated array */result->data = data;return result;
}/** Retrieve vector element and store at dest.* Return 0 (out of bounds) or 1 (successful)*/
int get_vec_element(vec_ptr v, long index, data_t *dest)
{if (index < 0 || index >= v->len)return 0;*dest = v->data[index];return 1;
}/* Return length of vector */
long vec_length(vec_ptr v)
{return v->len;
}

采用計算向量元素乘積的初始代碼如下：

#define IDENT 1
#define OP *
/* Implementation with maximum use of data abstraction */
void combine1(vec_ptr v, data_t *dest)
{long i;*dest = IDENT;for (i = 0; i < vec_length(v); i++) {data_t val;get_vec_element(v, i, &val);*dest = *dest OP val;}
}

對于這段初始代碼，有一些方向可以進行優化改進。

提高循環效率

代碼移動

代碼移動指的是將在循環里需要執行多次但計算結果不會改變的計算移動到循環外：

#define IDENT 1
#define OP *
/* Implementation with maximum use of data abstraction */
void combine2(vec_ptr v, data_t *dest)
{long i;long length = vec_length(v);*dest = IDENT;for (i = 0; i < length; i++) {data_t val;get_vec_element(v, i, &val);*dest = *dest OP val;}
}

減少過程調用

上述函數可以繼續簡化為：

data_t *get_vec_start(vec_ptr v)
{return v->data;
}/* Direct access to vector data */
void combine3(vec_ptr v, data_t *dest)
{long i;long length = vec_length(v);data_t *data = get_vec_start(v);*dest = IDENT;for (i = 0; i < length; i++) {*dest = *dest OP data[i];}
}

這種寫法和combine2相比，減少了索引與數組邊界的比較，但優化效果并不明顯。

消除不必要的內存引用

對于combine3的賦值過程：

*dest = *dest OP data[i];

需要訪問*dest指針的值，再根據這個地址從內存中取dest數組的值，并在計算完成后賦值到對應的內存上，在每次迭代過程中都要完成這樣一個從內存讀寫數據的過程，將函數繼續簡化，減少對內存的讀寫：

void combine4(vec_ptr v, data_t *dest)
{long i;long length = vec_length(v);data_t *data = get_vec_start(v);data_t cur = IDENT;for (i = 0; i < length; i++) {cur = cur OP data[i];}*data = cur;
}

考慮機器特性的優化方法

上述優化方法都沒有依賴目標機器的任何特性，如果要進一步提升性能，則需要考慮利用處理器微體系結構進行優化。

現代處理器結構

現代微處理器的簡化示意圖如下圖所示，其可以分為指令控制單元ICU和執行單元EU兩部分。

• 取指控制：ICU從指令高速緩存中讀取指令，并在譯碼后將對應的操作發送到EU。一般來說，會在當前執行的指令很早之前就進行取指。然而當程序遇到分支時，處理器采用分支預測技術，會猜測是否選擇該分支并預測其目標地址。使用投機執行技術，處理器會在確定分支預測是否正確前就跳到分支對應的指令，甚至開始執行這些對應的操作。如果分支預測錯誤，則將狀態重新設為分支點的狀態。
• 指令譯碼：接收實際的程序指令并將其轉換為一組基本操作。
• 加載和存儲單元：內置加法器，用于讀寫內存。
• 分支單元：向ICU返回分支預測是否正確的結果。
• 算術運算單元：執行整數和浮點數操作的不同組合。
• 退役單元：記錄正在進行的處理，并確保其遵守機器級程序的語義。退役單元包含了多種寄存器，并控制這些寄存器的更新。指令譯碼時，其信息被放置在一個隊列中，直到分支點預測結果出現，若預測正確，則程序寄存器的更新將被實際執行。任何對程序寄存器的更新都只會在指令退役的時候才會發生。

功能單元的性能

對于功能單元進行運算的性能，有以下幾個指標可以用來衡量：

延遲L：表示完成運算所需要的總時間

發射時間I：表示兩個連續的同類型運算之間需要的最小周期數

容量C：表示能夠執行該運算的功能單元的數量

操作的吞吐量=C/I

對于一個執行n個乘法的函數，若其需要L*n+K個周期，其中K為調用函數和初始化等開銷，此時CPE=L，對于單個按照順序執行的功能單元組成的函數，延遲L表明了CPE的最小值，而對于多個功能單元組成的函數，還需要考慮其吞吐量。

處理器操作的抽象模型

將函數combine4的循環部分轉換為匯編代碼：

Inner loop of combine44. data_t = double, OP = *
acc in %xmm0, data+i in %rdx, data+length in %rax
1 .L25:
2 vmulsd (%rdx), %xmm0, %xmm0    loop: Multiply acc by data[i]
3 addq $8, %rdx                  Increment data+i
4 cmpq %rax, %rdx                Compare to data+length
5 jne .L25                       If !=, goto loop

將其抽象為數據流圖，并去除不影響數據流的指令：

可以看出，乘法和加法運算是制約循環性能的兩個因素，而浮點乘法的延遲約為整數加法的5倍，其成為了最關鍵的制約原因，程序的CPE為5。循環中的其他操作與乘法器并行地執行。

循環展開

循環展開是一種程序變換，通過增加每次迭代計算元素的數量來減少循環的迭代次數。

其優點為，可以提高緩存命中率，增加循環體內語句并發執行的可能性，同時減少分支預測失敗的可能性。

用循環展開繼續改進上述代碼為：

/* 2 x 1 loop unrolling */
void combine5(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 cur= IDENT;/* Combine 2 elements at a time */for (i = 0; i < limit; i += 2) {cur= (cur OP data[i]) OP data[i + 1];}/* Finish any remaining elements */for (; i < length; i++) {cur =  cur OP data[i];}*dest = cur;
}

編譯器可以很輕松地執行循環展開，用GCC的優化等級大于等于3時就會執行循環展開。

提高并行性

我們知道，乘法操作和加法操作是可以并行化的，也就是說，不需要等待對方完成即可進行下一次操作，可以在每個時鐘周期就開始一次新的操作。但目前的代碼還并不能更高速率地執行乘法和加法，這是因為我們將累積值放在一個單獨的變量cur中，在前面計算完成之前都不能計算cur的新值。

為了提高并行性，我們可以用多個累積變量分別計算：

void combine6(vec_ptr v, data_t *dest){long i;long length = vec_length(v);long limit = length - 1;data_t cur0 = IDNET;data_t cur1 = IDNET;for(i = 0; i <limit; i+=2){cur0 = cur0 OP data[i];cur1 = cur1 OP data[i+1];}for(; i < length; i++)cur0 = cur0 OP data[i];*dest = cur0 OP cur1;
}

我們可以將多個累積變量變換歸納為將循環展開k次，以及并行累積k個值，得到k×k的循環展開，當k足夠大時，程序在所有情況下幾乎都能達到吞吐量界限。通常，只有保持能執行該操作的所有功能單元的流水線都是滿的，程序才能達到這個操作的吞吐量界限，對延遲為L，容量為C的操作而言，要求循環展開因子k ≥ L*C即可達到最大吞吐量。

除了以上并行累計的方式以外，還可以通過重新結合變換的方式對combine5進行繼續優化：

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 cur = IDENT;for(i = 0; i < limit; i+=2){cur = cur OP (data[i] OP data{i+1]);}for(; i < length; i++)cur = cur OP data[i];*dest = cur;
}

combine7和combine5的區別在于**data[i] OP data[i+1]**計算的先后順序不同，而(data[i] OP data[i+1])時可以被并行計算的，因為它不依賴于cur的計算結果，可以提前計算。（現代CPU的超標量架構，可以在一個時鐘周期內執行多個獨立的指令，如果兩個指令沒有數據依賴，CPU可以同時執行它們。）

書寫適用于條件傳送的代碼

條件傳送（Conditional Move, CMOV） 是一種 CPU 指令優化技術，它允許根據條件決定是否執行數據傳送，而不使用傳統的條件跳轉（branching）。
在 x86 架構中，CMOV 指令集（如 CMOVZ, CMOVNZ, CMOVL 等）可以在滿足某些條件時，將值從一個寄存器傳送到另一個寄存器，而不會觸發分支預測失敗的問題。

在 C++ 中，我們可以使用 條件運算符（?:）、內聯匯編（asm）、標準庫函數（std::max） 以及 SIMD 指令 來實現 條件傳送。

在現代C++編譯器中，使用三元運算符可能被編譯器優化為CMOV指令：

#include <iostream>//傳統條件分支的代碼
int branching(int x, int y){if (x > y)return x;elsereturn y;}
//使用條件傳送的代碼
int conditional_move(int x, int y) {return (x > y) ? x : y;  // 編譯器可能優化為 CMOV
}int main() {int a = 5, b = 10;std::cout << "Max: " << conditional_move(a, b) << std::endl;return 0;
}

除此之外，gcc在 -O2 或更高級別優化下，std::max(a, b) 可能會被優化為 CMOV 指令