本文為CSAPP第五章學習筆記。

編寫高效的程序需要：

1. 選擇合適的數(shù)據(jù)結(jié)構(gòu)和算法
2. 編寫出編譯器能夠有效優(yōu)化以轉(zhuǎn)換成高效可執(zhí)行代碼的源代碼
3. 對于計算量較大的任務(wù)，可以將其分解為若干小的代碼段，然后并行計算

優(yōu)化代碼：

1. 減少不必要的內(nèi)容，讓代碼盡可能簡單的執(zhí)行期望的工作。如消除不必要的函數(shù)調(diào)用、條件測試和存儲器引用。
2. 利用處理器提供的指令集并行能力，同時執(zhí)行多條指令。根據(jù)代碼的各項操作的時序特性做出合理安排，以避免不必要的等待。

在優(yōu)化代碼的時候，要保證代碼的簡潔和可讀性，因為代碼終歸需要維護和擴展。

1 減少存儲器調(diào)用

考慮如下兩個函數(shù)：

void twiddle1(int *xp, int *yp)
{
    *xp += *yp;
    *xp += *yp; 
}

void twiddle2(int *xp, int *yp)
{
    *xp += 2* *yp;
}

twiddlw1()和twiddle2()有著相似的計算行為。但是，twiddle2()只有三次寄存器調(diào)用：*xp的讀取，*yp的讀取以及*xp的寫入。twiddle1()則有六次寄存器調(diào)用，實際計算更為麻煩。

twiddlw1()和twiddle2()也不完全相同。試考慮，*xp = *yp，twiddlw1()的*xp實際等于4* *xp，而twiddlw2()的*xp實際等于3* *xp。這種兩個指針指向統(tǒng)一存儲器的情況，也稱作存儲器別名使用。

2 減少函數(shù)調(diào)用

考慮如下兩個函數(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次 建立棧幀 -> 計算f() -> 恢復棧幀 過程。而cycle2()函數(shù)只需要一次。

當然，作為特殊情況，需要考慮f()會改變?nèi)肿兞康目赡堋Ｈ绻_實改變，那么cycle1()函數(shù)就會改變?nèi)肿兞?次，而cycle2()函數(shù)只會改變1次。

3 每元素周期數(shù)CPE

考慮一個計算向量的前置和(prefix sum)的過程。

向量P=(a1, a2, a3, .., ai,..., an)的前置和p(i)的計算過程可寫為:

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所指向的向量的所含元素個數(shù)  */
        data_t val;                     /* 新建一個內(nèi)存空間 */
        get_vec_element(ptr, i, &val);  /* 將向量指針ptr所指的向量的第i項存入val */
        *dest = *dest + val;            /* *dest累加val，求的前置和 */
    }
}

代碼1使用for循環(huán)迭代計算前置和。無論ptr所指向量有多大，每次調(diào)用函數(shù)都會執(zhí)行建立棧幀和恢復棧幀，這一段代碼的耗時是一個定值S。隨著循環(huán)次數(shù)n的變化，總的耗時T＝S + nL，其中L為for循環(huán)的單位循環(huán)執(zhí)行時間，在本書中又稱作每元素周期數(shù)CPE*。

4 消除循環(huán)的低效率——代碼移動

代碼1在for循環(huán)中，每次循環(huán)都會調(diào)用length()獲取向量的所含元素個數(shù)。然而這個值通常都是一個定值，如果將其存儲在一個局部變量中，降低調(diào)用頻率，可以有效改善代碼運行效率。

代碼2

void combine(vec_pointer ptr, data_t *dest)
{
    long int i;                     
    *dest = 0;
    long int v_length = length(ptr);   /* 將length(ptr)返回值存儲在局部變量中 */
    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位元素，也同樣代價巨大。一個合理的替代方案是：直接獲取向量，存入局部變量中，然后按需調(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 消除不必要的存儲器引用

下面是代碼3中for循環(huán)的匯編代碼：

/*
 * code3: data_t = float
 * i 位于 %rdx, data 在 %rax, dest 在 %rbp, 越界標志 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)中，每次計算加法都會先引用寄存器中*dest所指向的空間，然后加和，最后將計算結(jié)果存入寄存器。但比較浪費的是，每次讀取的值都是上次的計算結(jié)果。

合理的解決辦法是，將累加值存入局部變量中，當計算結(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;                     /* 局部變量存儲累加值 */
    for (i = 0; i < v_length; i++) { 
        acc = acc + data[i];            /* 用累加器acc累加data[i]，求前置和 */
    }
    *dest = acc;                        /* 將結(jié)果存入寄存器 */
}

其對應(yīng)匯編代碼

/*
 * code4: data_t = float
 * i 位于 %rdx, data 在 %rax, 越界標志 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)足夠簡潔。然而，循環(huán)本身也存在開銷，如果能夠在保證計算結(jié)果足夠精準的情況下，減少循環(huán)次數(shù)，也能產(chǎn)生明顯的改善效果。

循環(huán)展開，就是一種程序變換，通過增加每次迭代計算的元素的數(shù)量，來減少循環(huán)的迭代次數(shù)。循環(huán)展開從兩方面改善了程序的性能：

1. 減少了不直接有助于程序結(jié)果的操作的數(shù)量，如循環(huán)索引計算、條件分支；
2. 可以進一步變化代碼，減少整個計算的關(guān)鍵路徑上的操作數(shù)量。

關(guān)鍵路徑：在循環(huán)的反復執(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) {           /* 步進為2 */
        acc = (acc + data[i]) + data[i+1];   /* acc累加下兩個data[i]，求前置和 */
    }
    
    /*循環(huán)2*/
    for (; i < length; i++) {                /* 累加剩余元素 */
        acc = acc + data[i];
    }
    *dest = acc;                             
}

觀察代碼5，有兩個for循環(huán)：

1. 對于第一個循環(huán)，要保證循環(huán)不會越界(特別是data[i+1])；
2. 要保證當循環(huán)索引i滿足i<n-1實才會執(zhí)行循環(huán)，因此最大索引i+1滿足i+1<(n-1)+1=n。

8 提高并行性

觀察代碼4的循環(huán)中的計算：每次計算acc之前必須等前一循環(huán)的acc計算完成后才能繼續(xù)。

同樣代碼5中循環(huán)1的計算行：每次計算acc之前先算acc + data[i]，然后計算+ data[i+1]，同樣需要等待前已循環(huán)的acc計算完畢。

也就是說，acc的計算構(gòu)成了一個單序列的計算流程，也就是一條關(guān)鍵路徑。如果能夠?qū)⑦@個流程拆分，就可以利用CPU的亂序特性，同時計算，提高效率。

一個可行的方法就是：先分別計算奇數(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;           /* 兩個累加器求和 */                            
}

代碼6中有兩個關(guān)鍵路徑。

9 重新結(jié)合變換

考慮對代碼5中循環(huán)1的計算行：

acc = (acc + data[i]) + data[i+1];

做出變換：

acc = acc + (data[i] + data[i+1]);

盡管只是對計算式更改了括號的位置，但這對計算性能有了很大的提高。前式的第一次加法acc + data[i]前仍然需要等待前一循環(huán)acc計算完畢，而后式的第一次加法data[i] + data[i+1]則無此要求。利用CPU的亂序特性，可以在對于后式計算：可以在計算前一循環(huán)acc的同時，去計算后一循環(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 一些問題

1. 循環(huán)的并行度不能無限提高。一旦平行度超過了可用的寄存器數(shù)量，編譯器就會把多余的變量存入棧內(nèi)——從而性能巨減。

2. 現(xiàn)代CPU都有預測分支并提前執(zhí)行的能力。但是，一旦CPU預測錯誤，就會造成巨大的性能損失。

   • 首先，不要過多的關(guān)注可預測的分支(P361);
   • 其次，對于難以預測的情況，盡可能使用條件數(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: