最近在惡補計算機基礎(chǔ)知識，學(xué)到CSAPP第五章的內(nèi)容，在這里總結(jié)并且展開一下C++程序性能優(yōu)化相關(guān)的內(nèi)容。

衡量程序性能的方式

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

計算方式為：

#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; // 假設(shè)CPU 2.5 GHzdouble cpe = elapsed_cycles / N; // 計算 CPEstd::cout << "CPE: " << cpe << std::endl;return 0;
}

影響編譯器優(yōu)化的因素

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

gcc優(yōu)化等級

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

以下為一些妨礙編譯器優(yōu)化的因素：

內(nèi)存別名使用

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

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

很顯然，代碼段2的執(zhí)行所需耗費時間更短，其需要的內(nèi)存訪問次數(shù)更少。

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

修改全局程序狀態(tài)的函數(shù)

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

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

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

將函數(shù)定義為內(nèi)聯(lián)函數(shù)，可以直接將函數(shù)調(diào)用替換為函數(shù)體，例如，代碼段1在o1優(yōu)化下可以展開為：

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

如果使用-o2及以上優(yōu)化，可能會展開為：

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

直接優(yōu)化方法

為了舉例說明優(yōu)化方法是如何實現(xiàn)的，我們定義向量數(shù)據(jù)結(jié)構(gòu)如下：

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

data_t代表基本元素的數(shù)據(jù)類型。

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

/* 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;}
}

對于這段初始代碼，有一些方向可以進(jìn)行優(yōu)化改進(jìn)。

提高循環(huán)效率

代碼移動

代碼移動指的是將在循環(huán)里需要執(zhí)行多次但計算結(jié)果不會改變的計算移動到循環(huán)外：

#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;}
}

減少過程調(diào)用

上述函數(shù)可以繼續(xù)簡化為：

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相比，減少了索引與數(shù)組邊界的比較，但優(yōu)化效果并不明顯。

消除不必要的內(nèi)存引用

對于combine3的賦值過程：

*dest = *dest OP data[i];

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

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;
}

考慮機器特性的優(yōu)化方法

上述優(yōu)化方法都沒有依賴目標(biāo)機器的任何特性，如果要進(jìn)一步提升性能，則需要考慮利用處理器微體系結(jié)構(gòu)進(jìn)行優(yōu)化。

現(xiàn)代處理器結(jié)構(gòu)

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

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

功能單元的性能

對于功能單元進(jìn)行運算的性能，有以下幾個指標(biāo)可以用來衡量：

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

發(fā)射時間I：表示兩個連續(xù)的同類型運算之間需要的最小周期數(shù)

容量C：表示能夠執(zhí)行該運算的功能單元的數(shù)量

操作的吞吐量=C/I

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

處理器操作的抽象模型

將函數(shù)combine4的循環(huán)部分轉(zhuǎn)換為匯編代碼：

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

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

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

循環(huán)展開

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

其優(yōu)點為，可以提高緩存命中率，增加循環(huán)體內(nèi)語句并發(fā)執(zhí)行的可能性，同時減少分支預(yù)測失敗的可能性。

用循環(huán)展開繼續(xù)改進(jìn)上述代碼為：

/* 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;
}

編譯器可以很輕松地執(zhí)行循環(huán)展開，用GCC的優(yōu)化等級大于等于3時就會執(zhí)行循環(huán)展開。

提高并行性

我們知道，乘法操作和加法操作是可以并行化的，也就是說，不需要等待對方完成即可進(jìn)行下一次操作，可以在每個時鐘周期就開始一次新的操作。但目前的代碼還并不能更高速率地執(zhí)行乘法和加法，這是因為我們將累積值放在一個單獨的變量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;
}

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

除了以上并行累計的方式以外，還可以通過重新結(jié)合變換的方式對combine5進(jìn)行繼續(xù)優(yōu)化：

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的區(qū)別在于**data[i] OP data[i+1]**計算的先后順序不同，而(data[i] OP data[i+1])時可以被并行計算的，因為它不依賴于cur的計算結(jié)果，可以提前計算。（現(xiàn)代CPU的超標(biāo)量架構(gòu)，可以在一個時鐘周期內(nèi)執(zhí)行多個獨立的指令，如果兩個指令沒有數(shù)據(jù)依賴，CPU可以同時執(zhí)行它們。）

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

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

在 C++ 中，我們可以使用 條件運算符（?:）、內(nèi)聯(lián)匯編（asm）、標(biāo)準(zhǔn)庫函數(shù)（std::max） 以及 SIMD 指令 來實現(xiàn) 條件傳送。

在現(xiàn)代C++編譯器中，使用三元運算符可能被編譯器優(yōu)化為CMOV指令：

#include <iostream>//傳統(tǒng)條件分支的代碼
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;  // 編譯器可能優(yōu)化為 CMOV
}int main() {int a = 5, b = 10;std::cout << "Max: " << conditional_move(a, b) << std::endl;return 0;
}

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