05-優化程序性能

寫程序最主要的目標就是使它在所有可能的情況下都正確工作。一個運行得很快但是給出錯誤結果的程序沒有任何用處。程序員必須寫出清晰簡潔的代碼，這樣做不僅是為了自己能夠看懂代碼，也是為了在檢査代碼和今后需要修改代碼時，其他人能夠讀懂和理解代碼。另一方面，在很多情況下，讓程序運行得快也是一個重要的考慮因素。本章主要介紹了循環展開，減小過程調用，消除不必要的內存引用等優化代碼的方法，有助于我們寫出高效的代碼，提高代碼的性能。

編寫高效程序需做到以下幾點：

我們必須選擇一組適當的算法和數據結構
我們必須編寫出編譯器能夠有效優化以轉換成高效可執行代碼的源代碼
針對處理運算量特別大的計算，將一個任務分為多個部分，這些部分可在多核、多處理器的某種組合上并行計算

優化編譯器的能力和局限性

編譯器必須很小心地對程序只使用安全的優化，也就是說對于程序可能遇到的所有可能的情況，在C語言標準提供的保證之下，優化后得到的程序和未優化的版本有一樣的行為。限制編譯器只進行安全的優化，消除造成不希望的運行時行為的可能原因，但這也意味著程序員需花費更大力氣寫出編譯器能夠將之轉換成有效機器代碼的程序。為了理解決定一種程序轉換是否安全的程度，讓我們看看如下兩個過程：
-w963

上述代碼都是將存儲在由指針yp指示的位置處的值加到指針xp指示的位置處的值。但是函數twiddle2的效率更高，因為它只要求3次內存引用（讀*xp，讀*yp，寫*xp），而twiddle1需要6次（2次讀*xp，2次讀*yp，2次寫*xp）。不過，如果xp = yp，那么函數twiddle1實際的操作是將xp的值增加4倍。而函數twiddle2則是將xp的值增加了3倍。由于編譯器不知道xp與yp是否可能相等，因此twiddle2不能作為twiddle1的優化版本。

如果編譯器無法確定兩個指針是否指向同一位置，那么編譯器就會假設所有情況都有可能發生，這就限制了可能的優化策略。

對于下面的代碼：
-w1053

單純觀察上面代碼發現，函數func1需要調用四次f，但是func2僅需調用一次f，那么是不是這就意味著func2的效率高呢？其實未必，如果f的功能如下所示：
-w1051

顯然對于上面的f，func1返回6，func2返回0。這種情況編譯器也無法判斷，因此編譯器不會對這種情況作出優化。可以看到編譯器的優化其實是非常“保守的”。

GCC優化指令

-Og:默認配置，不優化。
-O1:編譯器試圖優化代碼大小和執行時間，它主要對代碼的分支，常量以及表達式等進行優化，但不執行任何會占用大量編譯時間的優化。
-O2:GCC執行幾乎所有不包含時間和空間權衡的優化（比如，嘗試更多的寄存器級的優化以及指令級的優化）。與-O1相比，此選項增加了編譯時間，但提高了代碼的效率。
-O3:比-O2更優化，對于-O3編譯選項，在-O2的基礎上，打開了更多的優化項（比如，使用偽寄存器網絡，普通函數的內聯，以及針對循環的更多優化）。不過可能導致編譯出來的二級制程序不能debug。
-Os:主要是對代碼大小的優化，我們基本不用做更多的關心。通常各種優化都會打亂程序的結構，讓調試工作變得無從著手。并且會打亂執行順序，依賴內存操作順序的程序需要做相關處理才能確保程序的正確性。

程序性能表示

我們引入度量標準每元素的周期數（Cycles Per Element, CPE），作為一種表示程序性能并指導我們改進代碼的方法。CPE這種度量標準幫助我們在更細節的級別上理解迭代程序的循環性能。這種度量標準對執行重復計算的程序來說是很適當的，例如處理圖像中的像素，或是計算矩陣乘積重的元素。處理器活動的順序是由時鐘控制的，時鐘提供了某個頻率的規律信號，通常用千兆赫茲（GHz），即十億周期每秒來表示，如當一個系統有“4GHz”處理器字樣，這表示處理器時鐘運行頻率為每秒$4\times 10^9$個周期。每個時鐘周期的時間是時鐘頻率的倒數。從程序員的角度來看，用時鐘周期表示度量標準要比用納秒或者皮秒來表示有幫助的多。用時鐘周期來表示，度量值表示的是執行了多少條指令，而不是時鐘運行的有多快。

-w983

程序實例

消除循環的低效率（Code Motion）

舉個例子如下代碼所示：

void lower1(char *s) {
    size_t i;
    for (i = 0; i < strlen(s); i++)
    if (s[i] >= 'A' && s[i] <= 'Z')
        s[i] -= ('A' - 'a');
}

程序看起來沒什么問題，一個很平常的大小寫轉換的代碼，但是為什么隨著字符串輸入長度的變長，代碼的執行時間會呈指數式增長呢？我們把程序轉換成GOTO形式看下：

void lower1(char *s) {
    size_t i = 0;
    if (i >= strlen(s))
        goto done;
loop:
    if (s[i] >= 'A' && s[i] <= 'Z')
        s[i] -= ('A' - 'a');
    i++;
    if (i < strlen(s))
        goto loop;
done:
}

我們可以看到，在C語言中調用strlen一次，這個函數實際上會執行兩次。還有一個重要的原因是：字符串的長度并不會隨著循環的進行而改變，因此，我們可以把strlen放在循環外，避免每次都調用strlen進行計算。

因為C語言中的字符串是以null結尾的字符序列，strlen必須一步一步地檢查這個序列，直到遇到null字符。對于一個長度為n的字符串，strlen所用的時間與n成正比。因為對lower1的n次迭代的每一次都會調用strlen，所以lower1的整體運行時間是字符串長度的二次項，正比于$n^2$。

優化后的代碼如下所示：

void lower2(char *s) {
    size_t i;
    size_t len = strlen(s); /*放在函數體外*/
    for (i = 0; i < len; i++)
        if (s[i] >= 'A' && s[i] <= 'Z')
            s[i] -= ('A' - 'a');
}

二者的執行效率比較如下所示：

這種優化是常見的一類優化的方法，稱為代碼移動（Code motion）。這類優化包括識別要執行多次（例如在循環里）但是計算結果不會改變的計算。因而可以將計算移動到代碼前面不會被多次求值的部分。

減少過程調用

/* Move call to vec_length out of loop */
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;
    }
}

從combine2的代碼中我們可以看出，每次循環迭代都會調用get_vec_element來獲取下一個向量元素。對每個向量引用，這個函數要把向量索引i與循環邊界做比較，很明顯會造成低效率。在處理任意的數組訪問時，邊界檢查可能是個很有用的特性，但是對combine2代碼的簡單分析表明所有的引用都是合法的。

data_t *get_vec_start(vec_ptr v) {
    return v - data;
}
/* Move call to vec_length out of loop */
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];
}

作為替代，假設為我們的抽象數據類型增加一個函數get_vec_start。這個函數返回數組的起始地址，然后就能寫出此combine3所示的過程，其內循環里沒有函數調用。它沒有用函數調用來獲取每個向量元素，而是直接訪問數組。事實上，經過這一步后，并沒有使得性能有較大提升，在整數求和的情況下還會造成性能下降。這是因為內循環中還有其他的操作形成了瓶頸。后面會詳細講到。這只是我們優化路上的一步。

消除不必要的內存引用

先看看combine3的x86-64匯編代碼：

#Inner loop of combines. data_t double, OP =
#dest in %rbx, data+i in %rdx, data+length in %rax 
.L17:
vmovsd (%rbx), %xmm()               # Read product from dest 
vmulsd (%rdx), %xmm0, %xmm0         # Multiply product by data[i]
vmovsd %xmm, (%rbx)                 # Store product at dest
addq $8, %rdx                       # Increment data+i
cmp %rax, %rdx                      # Compare to data+length 
jne .L17

在這段循環代碼中，我們看到，指針dest的地址存放在寄存器%rbx中，它還改變了代碼，將第i個數據元素的指針保存在寄存器%rdx中，注釋中顯示為data+i。每次迭代，這個指針都加8。循環終止操作通過比較這個指針與保存在寄存器各ax中的數值來判斷。我們可以看到每次迭代時，累積變量的數值都要從內存讀出再寫入到內存。這樣的讀寫很浪費，因為每次迭代開始時從dest讀出的值就是上次迭代最后寫入的值。

我們能夠消除這種不必要的內存讀寫，combine4所示的方式如下。引入一個臨時變量acc，它在循環中用來累積計算出來的值。只有在循環完成之后結果才存放在dest中。正如下面的匯編代碼所示，編譯器現在可以用寄存器%xmm0來保存累積值。

#Inner loop of combines. data_t double, OP =
#dest in %rbx, data+i in %rdx, data+length in %rax 
.L25:
vmulsd (%rdx),%xmm0,%xmm0       # Multiply product by data[i]
addq $8,%rdx                    # Increment data+i
cmp %rax,%rdx                   # Compare to data+length 
jne .L25

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

把結果累積在臨時變量中。將累積值存放在局部變量acc（累積器（accumulator）的簡寫）中，消除了每次循環迭代中從內存中讀出并將更新值寫回的需要。程序性能如下（以int整數為例），單位為CPE。

-w1074

理解現代處理器

超標量（superscalar）：在每個時鐘周期執行多個操作
亂序（out-of-order）：指令執行的順序不一定要與它們在機器級程序中的順序一致

如上圖所示，為一個亂序處理器的框圖。整個設計有兩個主要部分：指令控制單元（Instruction Control Unit,ICU）和執行單元（Execution Unit,EU）。前者負責從內存中讀出指令序列，并根據這些指令序列生成一組針對程序數據的基本操作；而后者執行這些操作。
指令高速緩存（Instruction cache）：一個特殊的高速存儲器，它包含最近訪問的指令。
分支預測（branch prediction）：處理器會猜測是否會選擇分支，同時還預測分支的目標地址。使用投機執行（ speculative execution）的技術，處理器會開始取出位于它預測的分支，會跳到的地方的指令，并對指令譯碼，甚至在它確定分支預測是否正確之前就開始執行這些操作。如果過后確定分支預測錯誤，會將狀態重新設置到分支點的狀態，并開始取出和執行另一個方向上的指令。標記為取指控制的塊包括分支預測，以完成確定取哪些指令的任務。
指令譯碼邏輯：一條指令會被譯碼成多個操作。例如，addq %rax,8(%rdx)。這條指令會被譯碼成為三個操作：一個操作從內存中加載一個值到處理器中，一個操作將加載進來的值加上寄存器%rax中的值,而一個操作將結果存回到內存。
讀寫內存是由加載和存儲單元實現的。加載單元處理從內存讀數據到處理器的操作。這個單元有一個加法器來完成地址計算。類似，存儲單元處理從處理器寫數據到內存的操作。它也有一個加法器來完成地址計算。如圖中所示，加載和存儲單元通過數據高速緩存（ data cache）來訪問內存。數據高速緩存是一個高速存儲器，存放著最近訪問的數據值。
退役單元（retirement unit）:記錄正在進行的處理，并確保它遵守機器級程序的順序語義。退役單元控制這些寄存器的更新。指令譯碼時，關于指令的信息被放置在一個先進先出的隊列中。這個信息會一直保持在隊列中，直到發生以下兩個結果中的一個。首先，一旦一條指令的操作完成了，而且所有引起這條指令的分支點也都被確認為預測正確，那么這條指令就可以退役（retired）了，所有對程序寄存器的更新都可以被實際執行了。另一方面，如果引起該指令的某個分支點預測錯誤，這條指令會被清空（flushed），丟棄所有計算出來的結果。通過這種方法，預測錯誤就不會改變程序的狀態了。(任何對程序寄存器的更新都只會在指令退役時才會發生)
寄存器重命名（register renaming）：當一條更新寄存器r的指令譯碼時，產生標記t，得到一個指向該操作結果的唯一的標識符。條目（r,t）被加入到一張表中，該表維護著每個程序寄存器r與會更新該寄存器的操作的標記t之間的關聯。當隨后以寄存器r作為操作數的指令譯碼時，發送到執行單元的操作會包含t作為操作數源的值。當某個執行單元完成第一個操作時，會生成一個結果（v,t），指明標記為t的操作產生值v。所有等待t作為源的操作都能使用v作為源值，這就是一種形式的數據轉發。通過這種機制，值可以從一個操作直接轉發到另一個操作，而不是寫到寄存器文件再讀出來，使得第二個操作能夠在第一個操作完成后盡快開始。重命名表只包含關于有未進行寫操作的寄存器條目。當一條被譯碼的指令需要寄存器r，而又沒有標記與這個寄存器相關聯，那么可以直接從寄存器文件中獲取這個操作數。有了寄存器重命名，即使只有在處理器確定了分支結果之后才能更新寄存器，也可以預測著執行操作的整個序列。
延遲（latency）：它表示完成運算所需要的總時間。
發射時間（Issue time）：它表示兩個連續的同類型的運算之間需要的最小時鐘周期數。

浮點數加法器流水線化分為三個階段：一個階段處理指數值，一個階段將小數相加，而另一個階段對結果進行舍入。

容量（capacity）：它表示能夠執行該運算的功能單元的數量。
延遲界限：完成合并運算的函數所需要的最小CPE值。
最大吞吐量：發射時間的倒數。給出了CPE的最小界限。

循環展開

循環展開是一種程序變換，通過增加每次迭代計算的元素的數量，減少循環的迭代次數。循環展開能夠從兩個方面改進程序的性能。首先，它減少了不直接有助于程序結果的操作的數量，例如循環索引計算和條件分支。第二，它提供了一些方法，可以進一步變化代碼，減少整個計算中關鍵路徑上的操作數量。

/*2 * 1 loop unrolling*/
/*使用2×1循環展開。這種變換能減小循環開銷的影響*/
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 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;
}

上述代碼是使用的“2 * 1循環展開“的版本。第一個循環每次處理數組的兩個元素。也就是每次迭代，循環索引i加2，在一次迭代中，對數組元素i和i+1使用合并運算。（注意訪問不要越界，正確設置limit，n個元素，一般設置界限n-1）。$K \times 1$循環展開次數和性能提升并不是正比關系，一般來講，最多循環展開一次后，性能提升就不會很大了（主要原因是關鍵路徑中n個mul操作，迭代次數減半，但是每次迭代中還是有兩個順序的乘法操作。具體參考csapp P367）。

提高并行性

多個累積變量
$P_n$表示$a_0, a_1, ..., a_n$乘積：${P_n} = \sum\limits_{i = 0}^{n - 1} {{a_i}} $。假設$n$為偶數，我們還可以把它寫成${P_n} = P{E_n} \times P{O_n}$，這里$P{E_n}$是索引為偶數的元素的乘積，而$P{O_n}$是索引值為奇數的元素的乘積。

代碼如下：

/*2 * 2 loop unrolling*/
/*運用2×2循環展開。通過維護多個累積變量，這種方法利用了多個功能單元以及它們的流水線能力*/
void combine6(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 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;
}

上述代碼用了兩次循環展開，以使每次迭代合并更多的元素，也使用了兩路并行，將索引值為偶數的元素累積在變量acc0中，而索引值為奇數的元素累積在變量acc1中。因此，我們將其稱為”2×2循環展開”。同前面一樣，我們還包括了第二個循環，對于向量長度不為2的倍數時，這個循環要累積所有剩下的數組元素。然后，我們對acc0和acc1應用合并運算，計算最終的結果。事實上，combine6比combine5性能提升近2倍左右。

重新結合變換

/*2 * 1a loop unrolling*/
/*運用2×1a循環展開，重新結合合并操作。這種方法增加了可以并行執行的操作數量*/
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 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;
}

我們可以看到關鍵路徑上只有n/2個操作。每次迭代內的第一個乘法都不需要等待前一次迭代的累積值就可以執行。因此，最小可能的CPE減少了2倍。這種改進方式幾乎達到了吞吐量的極限。在執行重新結合變換時，我們又一次改變向量元素合并的順序。對于整數加法和乘法，這些運算是可結合的，這表示這種重新變換順序對結果沒有影響。對于浮點數情況，必須再次評估這種重新結合是否有可能嚴重影響結果。我們會說對大多數應用來說，這種差別不重要。總的來說，重新結合變換能夠減少計算中關鍵路徑上操作的數量，通過更好地利用功能單元的流水線能力得到更好的性能。大多數編譯器不會嘗試對浮點運算做重新結合，因為這些運算不保證是可結合的。當前的GCC版本會對整數運算執行重新結合，但不是總有好的效果。通常，我們發現循環展開和并行地累積在多個值中，是提高程序性能的更可靠的方法。

寄存器溢出

我們可以看到對這種循環展開程度的增加沒有改善CPE，有些甚至還變差了。現代x86-64處理器有16個寄存器，并可以使用16個YMM寄存器來保存浮點數。一旦循環變量的數量超過了可用寄存器的數量，程序就必須在棧上分配一些變量。例如，下面的代碼片段展示了在10×10循環展開的內循環中，累積變量acc0是如何更新的：

# Updating of accumulator acco in 10 x 10 unrolling 
vmulsd (%rdx),%xmm,%xmm0       #acc0 *=data[i]

我們看到該累積變量被保存在寄存器%xmm0中，因此程序可以簡單地從內存中讀取data[i],并與這個寄存器相乘。與之相比，20×20循環展開的相應部分非常不同：

# Updating of accumulator acco in 20 x 20 unrolling 
vmovsd 40(%rsp),%xmm0
vmulsd (%rdx),%xmm0,%xmm0
vmovsd %xmmO,40(%rsp)

累積變量保存為棧上的一個局部變量，其位置距離棧指針偏移量為40。程序必須從內存中讀取兩個數值：累積變量的值和data[i]的值，將兩者相乘后，將結果保存回內存。一旦編譯器必須要訴諸寄存器溢出，那么維護多個累積變量的優勢就很可能消失。幸運的是，x86-64有足夠多的寄存器，大多數循環在出現寄存器溢出之前就將達到吞吐量限制。

-w1183

分支預測何預測錯誤懲罰
現代處理器的工作遠遠超前于當前正在執行的指令。

不要過分關心可預測的分支
我們已經看到錯誤的分支預測的影響可能非常大，但是這并不意味著所有的程序分支都會減緩程序的執行。實際上，現代處理器中的分支預測邏輯非常善于辨別不同的分支指令的有規律的模式和長期的趨勢。例如，在合并函數中結束循環的分支通常會被預測為選擇分支，因此只在最后一次會導致預測錯誤處罰。
書寫適合用條件傳送實現的代碼
程序中的許多測試是完全不可預測的，依賴于數據的任意特性，例如一個數是負數還是正數。對于這些測試，分支預測邏輯會處理得很糟糕。對于本質上無法預測的情況，如果編譯器能夠產生使用條件數據傳送而不是使用條件控制轉移的代碼，可以極大地提高程序的性能。我們發現GCC能夠為以一種更“功能性的”風格書寫的代碼產生條件傳送，在這種風格的代碼中，我們用條件操作來計算值，然后用這些值來更新程序狀態，這種風格對立于一種更“命令式的”風格，這種風格中，我們用條件語句來有選擇地更新程序狀態。

posted @ 2023-07-13 19:45 miseryjerry 閱讀(170) 評論(0) 收藏舉報

刷新頁面返回頂部

Perfect1zsh1t