閱讀經(jīng)典——《深入理解計算機系統(tǒng)》07
本文將介紹非常實用的程序性能優(yōu)化手段，并用一個案例來詳細(xì)說明艇纺。
- 為什么要優(yōu)化程序性能？
- 衡量性能的指標(biāo)
- 未優(yōu)化版本
- 提取重復(fù)操作
- 減少函數(shù)調(diào)用
- 避免內(nèi)存讀寫
- 還能進(jìn)一步優(yōu)化嗎？
- 循環(huán)展開
- 提高并行性
- 重結(jié)合變換
- 總結(jié)
為什么要優(yōu)化程序性能毁欣？
對于c代碼而言卒密，從源代碼到匯編代碼再到機器指令缀台，這中間是有一個編譯器在起作用的。編譯器發(fā)展到現(xiàn)在哮奇，它的功能已經(jīng)不僅僅是將源碼編譯為機器碼膛腐，更重要的是它的優(yōu)化能力睛约。編譯器需要根據(jù)指令集的特點將代碼盡可能地優(yōu)化，以得到更快的執(zhí)行速度哲身。
那么辩涝，既然有了編譯器自動做優(yōu)化，我們程序員還要手動優(yōu)化程序性能嗎勘天？
答案是肯定的怔揩。在很多情況下，編譯器無法像程序員一樣掌握足夠的信息以判斷是否可以執(zhí)行某種優(yōu)化误辑，更多的情況下沧踏，編譯器會很謹(jǐn)慎地做少量的優(yōu)化，以確保程序的正確性巾钉。而我們程序員則可以手動采用更深入的優(yōu)化策略翘狱，以獲得更高的性能。具體的案例將在下文敘述砰苍。
衡量性能的指標(biāo)
通常性能瓶頸出現(xiàn)在循環(huán)處潦匈，對于循環(huán)遍歷的元素數(shù)是固定的情況下，所用的時間正比于每個元素消耗的時間赚导。因此我們用CPE（cycles per element）來衡量程序性能茬缩。CPE是指對于一個循環(huán)操作，平均每個元素所用的周期數(shù)吼旧。
這樣說似乎不是很直觀凰锡，接下來讓案例登場吧。
未優(yōu)化版本
要想有循環(huán)圈暗，先得有個數(shù)組掂为。定義如下結(jié)構(gòu)體：
typedef int data_t;
typedef struct {
long int len;
data_t *data;
} vec_rec, *vec_ptr;
這是一個數(shù)組結(jié)構(gòu)體，包含兩個成員：len表示數(shù)組長度员串，data保存第一個數(shù)據(jù)的地址勇哗。為了通用，將data設(shè)為data_t *類型寸齐，這個類型可以任意定義為int欲诺、float、double渺鹦。
將數(shù)組所有元素乘/加的第一種實現(xiàn)扰法，也就是未優(yōu)化版本如下：
#define IDENT 0
#define OP +
/* Implementation with maximum use of data abstraction */
void combine1(vec_ptr v, data_t *dest)
{
long int i;
*dest = IDENT;
for (i = 0; i < vec_length(v); i++) {
data_t val;
get_vec_element(v, i, &val);
*dest = *dest OP val;
}
}
為了通用乘法和加法，我們用IDENT毅厚、OP的不同組合來區(qū)分兩種運算迹恐。上面代碼定義用于處理加法，如果把IDENT定義為1卧斟，并把OP定義為*就可以用來處理乘法了殴边。
這種寫法也許是我們最常用的寫法，雖然現(xiàn)在看不出有什么問題珍语，但接下來我們將分析它的性能瓶頸锤岸。
提取重復(fù)操作
這個版本最容易被指出的問題就是循環(huán)條件調(diào)用了一個函數(shù)vec_length，不管這個函數(shù)具體是如何實現(xiàn)的板乙，對于長度固定的數(shù)組來說是偷，這樣做都是一種冗余。因為其實我們可以在循環(huán)開始前定義一個局部變量length保存數(shù)組的長度值募逞，這樣就只需要調(diào)用一次vec_length蛋铆，一定會降低程序的運行時間。新的程序版本如下：
/* Move call to vec_length out of loop */
void combine2(vec_ptr v, data_t *dest)
{
long int i;
long int 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;
}
}
用實際測得的CPE來表示兩個版本間的性能差異比較有公信力放接，請看下表刺啦。
表中，每種實現(xiàn)都給出了五類數(shù)據(jù)類型的測試結(jié)果纠脾，包括整數(shù)加法玛瘸、整數(shù)乘法、浮點數(shù)加法苟蹈、單精度浮點數(shù)乘法和雙精度浮點數(shù)乘法糊渊。由于每類運算本身執(zhí)行一次需要的時間就不一樣，因此需要分開比較慧脱。
注意渺绒，combine1已經(jīng)采用了-O1級別的編譯器優(yōu)化，但combine2的用時仍然比前者短了數(shù)秒菱鸥。
編譯器為什么不自動做這個優(yōu)化呢宗兼？因為它沒那么聰明唄。它不知道vec_length這個函數(shù)的返回值是不變的采缚，因此只能謹(jǐn)慎起見针炉，不優(yōu)化。
減少函數(shù)調(diào)用
如何做進(jìn)一步的優(yōu)化就不那么容易想到了扳抽。不過想想之前《函數(shù)調(diào)用棿叟粒》中講的函數(shù)調(diào)用過程是多么的繁瑣，提示我們應(yīng)該盡量減少函數(shù)調(diào)用贸呢。新的版本如下：
/* Direct access to vector data */
void combine3(vec_ptr v, data_t *dest)
{
long int i;
long int length = vec_length(v);
data_t *data = get_vec_start(v);
*dest = IDENT;
for (i = 0; i < length; i++) {
*dest = *dest OP data[i];
}
}
現(xiàn)在镰烧，循環(huán)里不再有get_vec_element方法了，取而代之的是直接用下標(biāo)索引取數(shù)楞陷。說實話怔鳖，這是一個非常魯莽的做法，因為這樣寫的代碼不具有擴展性固蛾，而且大大破壞了原來程序的抽象和封裝结执，不是面向?qū)ο蟪绦驊?yīng)有的作風(fēng)度陆。因此，現(xiàn)在我們講的是提高程序性能的手段献幔，而不是說所有程序都應(yīng)該這樣寫懂傀。當(dāng)性能不是程序首要考慮的因素時，我們根本不需要做任何優(yōu)化蜡感。優(yōu)化之后蹬蚁，代碼會變得難以理解，通常要求附帶文檔解釋說明郑兴。
CPE測試結(jié)果如下犀斋。
雖然性能提高不多，但關(guān)鍵時候一點點的性能提升也很重要情连。
避免內(nèi)存讀寫
現(xiàn)在叽粹，讓我們關(guān)注循環(huán)中唯一的一句代碼，如何提高這句代碼的性能蒙具？
如果查看匯編代碼球榆，就很容易發(fā)現(xiàn)其中的問題（匯編碼就不再貼出來了）：每個循環(huán)都要讀寫一次內(nèi)存，這豈不是很耽誤時間禁筏。我們都知道持钉，CPU訪問內(nèi)存的速度比訪問寄存器要慢得多，因此如果把訪問內(nèi)存的操作轉(zhuǎn)變成訪問寄存器的操作就可以節(jié)約大量時間了篱昔∶壳浚看這個版本的實現(xiàn)：
/* Accumulate result in local variable */
void combine4(vec_ptr v, data_t *dest)
{
long int i;
long int length = vec_length(v);
data_t *data = get_vec_start(v);
data_t acc = IDENT;
for (i = 0; i < length; i++) {
acc = acc OP data[i];
}
*dest = acc;
}
循環(huán)中只用局部變量acc保存計算的中間值，循環(huán)結(jié)束后再賦值給*dest州刽。由于現(xiàn)代處理器都優(yōu)先使用寄存器保存局部變量的值空执，因此可以大大提高程序性能。
看看現(xiàn)在的CPE吧穗椅，簡直是飛一般的快啊辨绊。
再回頭想一下，為什么編譯器不做這樣的優(yōu)化匹表？肯定還是因為有不確定的因素门坷。假如說dest和數(shù)組v的地址有交叉，那么原始版本的程序在循環(huán)中可能會改變數(shù)組元素的值袍镀，而當(dāng)前版本的循環(huán)就不會改變數(shù)組元素的值默蚌，造成不一致的結(jié)果。因此編譯器在不確定的情況下不敢擅自做優(yōu)化苇羡。
還能進(jìn)一步優(yōu)化嗎绸吸？
我們需要知道處理器的性能極限是多少，以此判斷我們的程序還能否進(jìn)一步優(yōu)化。
上一篇文章《從零開始制作自己的指令集架構(gòu)》中詳細(xì)講述了指令集架構(gòu)的內(nèi)部結(jié)構(gòu)锦茁。但是攘轩，不得不指出，現(xiàn)代處理器架構(gòu)完全不同于Y86蜻势，雖然在某些具體的實現(xiàn)方面沿用了Y86的技術(shù)撑刺，但實際的邏輯組成卻是這樣的：
整個處理器分為兩大部分，指令控制部分和執(zhí)行部分握玛。前者負(fù)責(zé)取指以及寫回寄存器，后者又包括多個功能單元甫菠，比如FP add挠铲、load、store等等寂诱，分別負(fù)責(zé)各自獨立的計算和存取內(nèi)存操作拂苹。
上一篇文章提到了現(xiàn)代處理器用的亂序執(zhí)行技術(shù)，這個技術(shù)就依賴于這些功能單元痰洒。每個單元都是完全流水線化的瓢棒，意味著FP add單元可以每周期完成一次加法操作。而各個單元間又是完全并行執(zhí)行的丘喻，而且不必照顧指令的執(zhí)行順序脯宿。如果一條指令需要多個單元執(zhí)行，那么把每個單元需要執(zhí)行的任務(wù)排隊進(jìn)入流水線就可以了泉粉。
這里需要提出兩個名詞：
- Latency：時延连霉。一條指令從開始到完成所用的時間。
- Issue：發(fā)射時間嗡靡。兩條指令連續(xù)發(fā)射的時間間隔跺撼。完全流水線情況下應(yīng)該為1。
時延限制了順序執(zhí)行的運算的性能讨彼，而發(fā)射時間限制了流水線級別的并行運算的性能歉井。理論上在兩種限制下所能達(dá)到的最低CPE見下表（吞吐量和發(fā)射時間是同一個含義）。
可見哈误，不同類型數(shù)據(jù)和不同操作對應(yīng)的時延不同哩至，但它們在完全流水線下的CPE都可以達(dá)到1。
下一步黑滴，就要研究怎樣才能突破時延對CPE的限制憨募，最終達(dá)到吞吐量對CPE的限制。之所以combine4只接近了時延對CPE的限制袁辈，是因為代碼中每兩次運算間是順序執(zhí)行的菜谣。之所以是順序執(zhí)行的，是因為下一次的運算用到了上一次運算的結(jié)果，產(chǎn)生了數(shù)據(jù)依賴尾膊。所以媳危，接下來我們應(yīng)該考慮如何消除數(shù)據(jù)依賴。
循環(huán)展開
將本來需要n次的循環(huán)變成n/2次冈敛，每次循環(huán)內(nèi)部做兩個元素的操作待笑，這種技術(shù)就稱為循環(huán)展開∽デ矗看代碼：
/* Unroll loop by 2 */
void combine5(vec_ptr v, data_t *dest)
{
long int i;
long int length = vec_length(v);
long int 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;
}
代碼中每次循環(huán)處理兩個元素暮蹂，循環(huán)展開因數(shù)為2。
現(xiàn)在癌压，CPE為
可以發(fā)現(xiàn)仰泻，整數(shù)運算性能提升了，而且展開3次的情況下整數(shù)加法和整數(shù)乘法都達(dá)到了吞吐量界限滩届，但是浮點數(shù)運算性能卻毫無改善集侯。這是因為雖然循環(huán)展開了，但是兩次運算間仍然存在直接的數(shù)據(jù)依賴帜消，導(dǎo)致流水線的并行能力仍然沒有發(fā)揮出來棠枉。不過整數(shù)乘法卻越過了延遲界限，原因涉及到重結(jié)合變換（reassociation transformation）泡挺，我們將在后面詳細(xì)解釋辈讶。
提高并行性
現(xiàn)在，必須真正地消除數(shù)據(jù)依賴了粘衬。為了讓下次運算不再需要上次運算的結(jié)果荞估，我們可以將整個運算分為兩個并行分支，用兩個局部變量分別累加奇數(shù)項和偶數(shù)項稚新，最后再合并到一起勘伺。代碼如下：
/* Unroll loop by 2, 2-way parallelism */
void combine6(vec_ptr v, data_t *dest)
{
long int i;
long int length = vec_length(v);
long int limit = length - 1;
data_t *data = get_vec_start(v);
data_t acc0 = IDENT;
data_t acc1 = IDENT;
/* Combine 2 elements at a time */
for (i = 0; i < limit; i += 2) {
acc0 = acc0 OP data[i];
acc1 = acc1 OP data[i+1];
}
/* Finish any remaining elements */
for (; i < length; i++) {
acc0 = acc0 OP data[i];
}
*dest = acc0 OP acc1;
}
看看效果怎么樣。
果然飞醉，浮點數(shù)運算性能也提高了不少。經(jīng)過測試屯阀，如果提高到3路缅帘、4路甚至5路并行，浮點數(shù)運算也會下降到吞吐量界限难衰。
重結(jié)合變換
另一種提高并行的方式是采用重結(jié)合變換钦无。依據(jù)加法和乘法的結(jié)合律，在循環(huán)展開的基礎(chǔ)上盖袭，重新結(jié)合三個數(shù)的運算順序失暂，就可以實現(xiàn)性能提高彼宠。代碼如下：
/* Change associativity of combining operation */
void combine7(vec_ptr v, data_t *dest)
{
long int i;
long int length = vec_length(v);
long int 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;
}
原理何在呢？其實很簡單弟塞，仍然是數(shù)據(jù)依賴的問題凭峡。先計算的兩個數(shù)data[i]和data[i+1]是沒有任何數(shù)據(jù)依賴的，因此這次計算可以和下一次與acc的運算完全并行化决记，這就比之前先計算acc要好得多了摧冀。
實際效果也很明顯。
總結(jié)
最后給出一個性能優(yōu)化的完美結(jié)果。
可以看到笙瑟，當(dāng)采用了展開5次楼镐，5路并行的優(yōu)化后，無論哪一種運算都達(dá)到了吞吐量界限往枷，表明我們的優(yōu)化非常成功。
最后凄杯，有兩件事情需要提醒大家：
本文所講的這些優(yōu)化方法错洁，在大部分編譯器中都已經(jīng)實現(xiàn)了。但是它們有可能不會實行這些優(yōu)化戒突，或需要我們手動設(shè)置更高級別的優(yōu)化選項才行屯碴。所以，作為一個程序員膊存，我們應(yīng)該做的是盡量引導(dǎo)編譯器執(zhí)行這些優(yōu)化导而，或者說排除阻礙編譯器優(yōu)化的障礙。這樣可以使我們的代碼在保持簡潔的情況下獲得更高的性能隔崎。迫不得已時今艺，我們才去手動做這些優(yōu)化。
循環(huán)展開爵卒、多路并行并不是越多越好虚缎。因為寄存器的個數(shù)是有限的，x86-64最多只能有12個寄存器用于累加钓株，如果局部變量的個數(shù)多于12個实牡，就會被放進(jìn)存儲器，反倒嚴(yán)重拉低程序性能轴合。
想要親自測試的同學(xué)請移步我的GitHub倉庫optimization_demo创坞。
關(guān)注作者或文集《深入理解計算機系統(tǒng)》，第一時間獲取最新發(fā)布文章受葛。
