本文為CSAPP第五章學(xué)習(xí)筆記纫骑。
編寫高效的程序需要：
- 選擇合適的數(shù)據(jù)結(jié)構(gòu)和算法
- 編寫出編譯器能夠有效優(yōu)化以轉(zhuǎn)換成高效可執(zhí)行代碼的源代碼
- 對(duì)于計(jì)算量較大的任務(wù)谓厘，可以將其分解為若干小的代碼段，然后并行計(jì)算
優(yōu)化代碼：
- 減少不必要的內(nèi)容灵巧，讓代碼盡可能簡(jiǎn)單的執(zhí)行期望的工作髓需。如消除不必要的函數(shù)調(diào)用缝裤、條件測(cè)試和存儲(chǔ)器引用。
- 利用處理器提供的指令集并行能力铜靶，同時(shí)執(zhí)行多條指令叔遂。根據(jù)代碼的各項(xiàng)操作的時(shí)序特性做出合理安排，以避免不必要的等待。
在優(yōu)化代碼的時(shí)候已艰，要保證代碼的簡(jiǎn)潔和可讀性痊末，因?yàn)榇a終歸需要維護(hù)和擴(kuò)展。
1 減少存儲(chǔ)器調(diào)用
考慮如下兩個(gè)函數(shù)：
void twiddle1(int *xp, int *yp)
{
*xp += *yp;
*xp += *yp;
}
void twiddle2(int *xp, int *yp)
{
*xp += 2* *yp;
}
twiddlw1()和twiddle2()有著相似的計(jì)算行為哩掺。但是舌胶，twiddle2()只有三次寄存器調(diào)用：*xp的讀取，*yp的讀取以及*xp的寫入疮丛。twiddle1()則有六次寄存器調(diào)用幔嫂，實(shí)際計(jì)算更為麻煩。
twiddlw1()和twiddle2()也不完全相同誊薄。試考慮履恩，*xp = *yp，twiddlw1()的*xp實(shí)際等于4* *xp呢蔫，而twiddlw2()的*xp實(shí)際等于3* *xp切心。這種兩個(gè)指針指向統(tǒng)一存儲(chǔ)器的情況，也稱作存儲(chǔ)器別名使用片吊。
2 減少函數(shù)調(diào)用
考慮如下兩個(gè)函數(shù)：
void cycle1(int *xp, int *yp)
{
return f() + f() + f() + f();
}
void cycle2(int *xp, int *yp)
{
return 4*f();
}
cycle1()函數(shù)調(diào)用了f()函數(shù)四次绽昏，需要在寄存器執(zhí)行4次 建立棧幀 -> 計(jì)算f() -> 恢復(fù)棧幀 過程。而cycle2()函數(shù)只需要一次俏脊。
當(dāng)然全谤，作為特殊情況，需要考慮f()會(huì)改變?nèi)肿兞康目赡芤丁Ｈ绻_實(shí)改變认然，那么cycle1()函數(shù)就會(huì)改變?nèi)肿兞?次，而cycle2()函數(shù)只會(huì)改變1次漫萄。
3 每元素周期數(shù)CPE
考慮一個(gè)計(jì)算向量的前置和(prefix sum)的過程卷员。
向量P=(a1, a2, a3, .., ai,..., an)的前置和p(i)的計(jì)算過程可寫為:
p(1) = a1;
p(i) = p(i-1) + ai; # i > 1
代碼1
void combine(vec_pointer ptr, data_t *dest)
{
long int i;
*dest = 0;
for (i = 0; i < length(ptr); i++) { /* length(ptr)返回得是ptr所指向的向量的所含元素個(gè)數(shù) */
data_t val; /* 新建一個(gè)內(nèi)存空間 */
get_vec_element(ptr, i, &val); /* 將向量指針ptr所指的向量的第i項(xiàng)存入val */
*dest = *dest + val; /* *dest累加val，求的前置和 */
}
}
代碼1使用for循環(huán)迭代計(jì)算前置和腾务。無論ptr所指向量有多大毕骡，每次調(diào)用函數(shù)都會(huì)執(zhí)行建立棧幀和恢復(fù)棧幀，這一段代碼的耗時(shí)是一個(gè)定值S岩瘦。隨著循環(huán)次數(shù)n的變化未巫，總的耗時(shí)T＝S + nL，其中L為for循環(huán)的單位循環(huán)執(zhí)行時(shí)間担钮，在本書中又稱作每元素周期數(shù)CPE*橱赠。
4 消除循環(huán)的低效率——代碼移動(dòng)
代碼1在for循環(huán)中尤仍，每次循環(huán)都會(huì)調(diào)用length()獲取向量的所含元素個(gè)數(shù)箫津。然而這個(gè)值通常都是一個(gè)定值，如果將其存儲(chǔ)在一個(gè)局部變量中，降低調(diào)用頻率苏遥，可以有效改善代碼運(yùn)行效率饼拍。
代碼2
void combine(vec_pointer ptr, data_t *dest)
{
long int i;
*dest = 0;
long int v_length = length(ptr); /* 將length(ptr)返回值存儲(chǔ)在局部變量中 */
for (i = 0; i < v_length; i++) {
data_t val;
get_vec_element(ptr, i, &val);
*dest = *dest + val;
}
}
5 減少過程調(diào)用
代碼2的for循環(huán)中，每次都要掉用get_vec_element()來獲得第i位元素田炭，也同樣代價(jià)巨大师抄。一個(gè)合理的替代方案是：直接獲取向量，存入局部變量中教硫，然后按需調(diào)用叨吮。
代碼3
/*
* 已知vec_pointer結(jié)構(gòu)體的定義
*/
typedef struct {
long int len;
data_t *data;
} vec_rec, vec_pointer;
/*
* 新建函數(shù)
*/
data_t *get_vec_start(vec_pointer ptr)
{
return ptr->data; /* 直接獲得ptr所指向量的數(shù)據(jù)部分的頭段指針 */
}
void combine(vec_pointer ptr, data_t *dest)
{
long int i;
*dest = 0;
long int v_length = length(ptr);
data_t *data = get_vec_start(ptr); /* 將ptr數(shù)據(jù)存入數(shù)組 */
for (i = 0; i < v_length; i++) {
*dest = *dest + data[i];
}
}
6 消除不必要的存儲(chǔ)器引用
下面是代碼3中for循環(huán)的匯編代碼：
/*
* code3: data_t = float
* i 位于 %rdx, data 在 %rax, dest 在 %rbp, 越界標(biāo)志 limit 在 %r12
*/
.L498:
movss (%rbp), %xmm0 /* 取出dest，存入 %xmm0 */
mulss (%rax, %rdx, 4), %xmm0 /* 取出data[i], 并與dest相乘 */
movss %xmm0, (%rbp) /* 將結(jié)果存入dest */
addq $1, %rdx /* i加一 */
cmpq %rdx, %r12 /* 比較i是否越界 */
jg .L498 /* 如果沒有越界瞬矩，就再次循環(huán) */
可以看出代碼3的for循環(huán)中茶鉴，每次計(jì)算加法都會(huì)先引用寄存器中*dest所指向的空間，然后加和景用，最后將計(jì)算結(jié)果存入寄存器涵叮。但比較浪費(fèi)的是，每次讀取的值都是上次的計(jì)算結(jié)果伞插。
合理的解決辦法是割粮，將累加值存入局部變量中，當(dāng)計(jì)算結(jié)束后再把最終結(jié)果存入寄存器媚污。
代碼4
void combine(vec_pointer ptr, data_t *dest)
{
long int i;
long int v_length = length(ptr);
data_t *data = get_vec_start(ptr);
data_t acc = 0; /* 局部變量存儲(chǔ)累加值 */
for (i = 0; i < v_length; i++) {
acc = acc + data[i]; /* 用累加器acc累加data[i]舀瓢，求前置和 */
}
*dest = acc; /* 將結(jié)果存入寄存器 */
}
其對(duì)應(yīng)匯編代碼
/*
* code4: data_t = float
* i 位于 %rdx, data 在 %rax, 越界標(biāo)志 limit 在 %rbp, acc 在 %xmm0
*/
.L488:
mulss (%rax, %rdx, 4), %xmm0 /* 取出data[i], 并與acc相乘 */
addq $1, %rdx /* i加一 */
cmpq %rdx, %rbp /* 比較i是否越界 */
jg .L488 /* 如果沒有越界，就再次循環(huán) */
7 循環(huán)展開
至此耗美，for循環(huán)內(nèi)部代碼已經(jīng)足夠簡(jiǎn)潔氢伟。然而，循環(huán)本身也存在開銷幽歼，如果能夠在保證計(jì)算結(jié)果足夠精準(zhǔn)的情況下朵锣，減少循環(huán)次數(shù)，也能產(chǎn)生明顯的改善效果甸私。
循環(huán)展開诚些，就是一種程序變換，通過增加每次迭代計(jì)算的元素的數(shù)量皇型，來減少循環(huán)的迭代次數(shù)诬烹。循環(huán)展開從兩方面改善了程序的性能：
- 減少了不直接有助于程序結(jié)果的操作的數(shù)量，如循環(huán)索引計(jì)算弃鸦、條件分支绞吁；
- 可以進(jìn)一步變化代碼，減少整個(gè)計(jì)算的關(guān)鍵路徑上的操作數(shù)量唬格。
關(guān)鍵路徑：在循環(huán)的反復(fù)執(zhí)行過程中形成的數(shù)據(jù)相關(guān)鏈家破。
代碼5
void combine(vec_pointer ptr, data_t *dest)
{
long int i;
long int v_length = length(ptr);
long int limit = v_length - 1;
data_t *data = get_vec_start(ptr);
data_t acc = 0;
/*循環(huán)1*/
for (i = 0; i < limit; i+=2) { /* 步進(jìn)為2 */
acc = (acc + data[i]) + data[i+1]; /* acc累加下兩個(gè)data[i]颜说，求前置和 */
}
/*循環(huán)2*/
for (; i < length; i++) { /* 累加剩余元素 */
acc = acc + data[i];
}
*dest = acc;
}
觀察代碼5，有兩個(gè)for循環(huán)：
- 對(duì)于第一個(gè)循環(huán)汰聋，要保證循環(huán)不會(huì)越界(特別是
data[i+1])门粪； - 要保證當(dāng)循環(huán)索引
i滿足i<n-1實(shí)才會(huì)執(zhí)行循環(huán)，因此最大索引i+1滿足i+1<(n-1)+1=n烹困。
8 提高并行性
觀察代碼4的循環(huán)中的計(jì)算：每次計(jì)算acc之前必須等前一循環(huán)的acc計(jì)算完成后才能繼續(xù)玄妈。
同樣代碼5中循環(huán)1的計(jì)算行：每次計(jì)算acc之前先算acc + data[i]，然后計(jì)算+ data[i+1]髓梅，同樣需要等待前已循環(huán)的acc計(jì)算完畢拟蜻。
也就是說，acc的計(jì)算構(gòu)成了一個(gè)單序列的計(jì)算流程枯饿，也就是一條關(guān)鍵路徑瞭郑。如果能夠?qū)⑦@個(gè)流程拆分，就可以利用CPU的亂序特性鸭你，同時(shí)計(jì)算屈张，提高效率。
一個(gè)可行的方法就是：先分別計(jì)算奇數(shù)位元素袱巨、偶數(shù)位元素的和阁谆，然后將兩者加和。
代碼6
void combine(vec_pointer ptr, data_t *dest)
{
long int i;
long int v_length = length(ptr);
long int limit = v_length - 1;
data_t *data = get_vec_start(ptr);
data_t acc1 = 0;
data_t acc2 = 0;
/*循環(huán)1*/
for (i = 0; i < limit; i+=2) {
acc1 = acc1 + data[i]; /* 僅奇數(shù)位元素求前置和*/
acc2 = acc2 + data[i+1]; /* 僅偶數(shù)位元素求前置和 */
}
/*循環(huán)2*/
for (; i < length; i++) { /* 累加剩余元素 */
acc1 = acc1 + data[i];
}
*dest = acc1 + acc2; /* 兩個(gè)累加器求和 */
}
代碼6中有兩個(gè)關(guān)鍵路徑愉老。
9 重新結(jié)合變換
考慮對(duì)代碼5中循環(huán)1的計(jì)算行：
acc = (acc + data[i]) + data[i+1];
做出變換：
acc = acc + (data[i] + data[i+1]);
盡管只是對(duì)計(jì)算式更改了括號(hào)的位置场绿，但這對(duì)計(jì)算性能有了很大的提高。前式的第一次加法acc + data[i]前仍然需要等待前一循環(huán)acc計(jì)算完畢嫉入，而后式的第一次加法data[i] + data[i+1]則無此要求焰盗。利用CPU的亂序特性，可以在對(duì)于后式計(jì)算：可以在計(jì)算前一循環(huán)acc的同時(shí)咒林，去計(jì)算后一循環(huán)的data[i] + data[i+1]熬拒，從而提高了效率。
代碼7
void combine(vec_pointer ptr, data_t *dest)
{
long int i;
long int v_length = length(ptr);
long int limit = v_length - 1;
data_t *data = get_vec_start(ptr);
data_t acc = 0;
/*循環(huán)1*/
for (i = 0; i < limit; i+=2) {
acc = acc + (data[i] + data[i+1]); /* 重新結(jié)合變換 */
}
/*循環(huán)2*/
for (; i < length; i++) {
acc = acc + data[i];
}
*dest = acc;
}
10 一些問題
循環(huán)的并行度不能無限提高垫竞。一旦平行度超過了可用的寄存器數(shù)量澎粟，編譯器就會(huì)把多余的變量存入棧內(nèi)——從而性能巨減。
-
現(xiàn)代CPU都有預(yù)測(cè)分支并提前執(zhí)行的能力欢瞪。但是活烙，一旦CPU預(yù)測(cè)錯(cuò)誤，就會(huì)造成巨大的性能損失遣鼓。
- 首先啸盏，不要過多的關(guān)注可預(yù)測(cè)的分支(P361);
- 其次，對(duì)于難以預(yù)測(cè)的情況骑祟，盡可能使用條件數(shù)據(jù)傳送回懦，而不是條件控制轉(zhuǎn)移气笙。
v = test-expr ? then-expr : else-expr;的匯編代碼可能產(chǎn)生下面兩種結(jié)果：
/*
*條件數(shù)據(jù)傳送
*/
vt = then-expr;
v = else-expr;
t = test-expr;
if (t) v = vt;
/*
* 條件控制轉(zhuǎn)移
*/
if (!test-expr)
goto false;
v = then-expr;
goto done;
false:
v = else-expr;
done:
