大家好，我是TT。
在前面《如何編寫高效能的C程式》內容中，我介紹了幾個用於編寫高效能 C 程式碼的實用技巧。今天，這一篇繼續聊這個話題，來討論其他幾種常見的 C 程式碼和程式最佳化技巧，它們分別是利用迴圈展開、使用條件傳送指令、尾遞迴呼叫最佳化，以及為編譯器指定更高的編譯最佳化等級。
迴圈展開（Loop Unrolling）
為了讓你更好地理解“迴圈展開”這個最佳化技巧背後的原理，我們先從宏觀角度看看 CPU 是如何運作的。
早期的 CPU 在執行指令時，是以序列的方式進行的，也就是說，一個指令的執行開始，需要等待前一個指令的執行完全結束。這種方式在實現上很簡單，但存在的問題也十分明顯：由於指令的執行是一個涉及多個功能單元的複雜過程，而在某一時刻，CPU 也只能夠對指令進行針對當前所在階段的特定處理。
那麼，將 CPU 處理指令的流程劃分為不同階段，並讓它對多條指令同時進行多種不同處理，這樣是否可以進一步提升 CPU 的吞吐量呢？事實正是如此。
現代 CPU 為了進一步提升指令的執行效率，通常會將單一的機器指令再進行拆分，以達到指令級並行的目的。比如，對於一個基本的五級 RISC 流水線來說，CPU 會將指令的執行細分為指令提取（IF）、指令譯碼（ID）、指令執行（EX）、記憶體訪問（MEM），以及暫存器寫回（WB）共五個步驟。
在這種情況下，當第一條機器指令經過了指令提取階段的處理後，即使該條指令還沒有被完全執行完畢，CPU 也可以立即開始處理下一條機器指令。因此，從宏觀上來看，機器指令的執行由序列變為了並行，程式的執行效率得到了提升。
其中，指令提取是指從記憶體中讀取出機器指令位元組的過程。CPU 根據得到的指令位元組，在譯碼階段，從相應的暫存器中獲得指令執行所需要的引數。而在執行階段，ALU 可以選擇執行指令明確的操作，或者是計算相關記憶體引用的有效地址等操作。隨後，在訪存階段，根據指令要求，CPU 可以將資料寫回記憶體，或從記憶體中讀出所需資料。類似地，在寫回階段，CPU 可以將指令執行得到的結果存入暫存器。
而當五個階段全部執行完畢後，CPU 會更新指令指標（PC），將其指向下一個需要執行的指令。你可以透過下圖來直觀地理解這個過程：
那麼，如何將 CPU 的吞吐量最大化呢？相信你心中已經有了答案。我們需要做的，就是讓 CPU 在執行程式指令時，能夠以滿流水線的方式進行。
但現實情況並非總是這樣理想。這裡，我要介紹的程式碼最佳化技巧“迴圈展開”便與此有關。讓我們先來看一段程式碼：
在這段程式碼中，我們定義了一個名為 data 的全域性整型陣列，並在其中存放了若干個值。而函式 foo 則主要用來計算該陣列中所有數字的乘積之和。
此時，如果我們在 main 函式中呼叫函式 foo，CPU 在實際執行它的程式碼時，for 迴圈的每一輪都會產生兩個資料相關：迴圈控制變數 i 的下一個值依賴於本次迴圈變數 i 在經過自增運算後得到的結果值。同樣地，計數變數 acc 的下一個值也依賴於該變數在當前迴圈中經過乘積計算後的結果值。
而這兩個資料相關會導致 CPU 無法提前計算下一輪迴圈中各個參與變數的值。而只有在暫存器寫回，或記憶體訪問階段執行完畢，也就是變數 acc 和 i 的值被最終更新後，CPU 才會繼續執行下一輪迴圈。
那麼，應該如何最佳化這個過程呢？我們直接來看最佳化後的程式碼：
#define LEN 4096
int data［LEN］ = { 。。。 }；
int foo（void） {
int limit = LEN - 1；
int i；
int acc0 = 1；
int acc1 = 1；
for （i = 0； i < limit； i += 2） { // 2x2 loop unrolling。
acc0 = acc0 * data［i］；
acc1 = acc1 * data［i + 1］；
}
for （； i < LEN； ++i） { // Finish any remaining elements。
acc0 = acc0 * data［i］；
}
return acc0 * acc1；
}
可以直觀地看到，參與到程式執行的區域性變數變多了。而這裡的主要改動是，我們為函式 foo 中的迴圈結構應用了 2x2 迴圈展開。
迴圈展開這種程式碼最佳化技術，主要透過增加迴圈結構每次迭代時計算的元素個數，來減少迴圈次數，同時最佳化 CPU 的指令集並行與流水線排程。而所謂的 2x2 ，是指在最佳化後的程式碼中，迴圈的步長變為了 2，且迴圈累積值被分別存放在兩個獨立變數 acc0 與 acc1 中。
迴圈展開帶來的最顯著最佳化，就是減少了迴圈的迭代次數。使用多個獨立變數儲存累積值，各個累積值之間就不會存在資料相關，而這就增大了 CPU 多個執行單元可以並行執行這些指令的機會，從而在一定程度上提升了程式的執行效率。
需要注意的是，迴圈展開一方面可以帶來效能上的提升，另一方面它也會導致程式程式碼量的增加，以及程式碼可讀性的降低。並且，編譯器在高最佳化等級下，通常也會對程式碼採用隱式的迴圈展開最佳化。因此，在大多數情況下，我們並不需要手動地改變程式碼形式來為它應用迴圈展開，除非是在那些你確定編譯器沒有進行最佳化，並且手動迴圈展開可以帶來顯著效能提升的情況下。
優先使用條件傳送指令
通常來說，CPU 指令集中存在著一類指令，它們可以根據 CPU 標誌位的不同狀態，有條件地傳送資料到某個特定位置，這類指令被稱為“條件傳送指令”。舉個例子，指令 cmove 接收兩個引數 S 和 R，當 CPU 標誌暫存器中的 ZF 置位時，該指令會將 S 中的源值複製到 R 中。
與條件傳送指令類似的還有另外一類指令，它們被稱為“條件分支指令”。顧名思義，這類指令在執行時，會根據 CPU 標誌位的不同狀態，選擇執行程式不同部分的程式碼。比如指令 jz ，該指令接收一個引數 L，當 CPU 標誌暫存器中的 ZF 置位時，該指令會將下一條待執行指令修改為 L 所在記憶體位置上的指令。
對於 C 程式碼中的某些邏輯，使用條件傳送指令與條件分支指令都能夠正確完成任務。但在程式的執行效率上，這兩種方式卻可能帶來極大的差別。而這主要是由於條件分支指令可能會受到 CPU 分支預測錯誤帶來的懲罰。
現代 CPU 一般都會採用投機執行，其中的一個場景是：處理器會從它預測的，分支可能會發生跳轉的地方取出指令，並提前對這些指令進行譯碼等操作。處理器甚至會在還未確認預測是否正確之前，就提前執行這些指令。之後，如果 CPU 發現自己預測的跳轉位置發生錯誤，就會將狀態重置為發生跳轉前分支所處的狀態，並取出正確方向上的指令，開始重新處理。
由此，上述兩種指令在 CPU 的內部執行上便產生了不同。由於條件分支指令會導致 CPU 在指令實際執行前作出選擇，而當 CPU 預測錯誤時，狀態的重置及新分支的重新處理過程會浪費較多的 CPU 週期，進而使程式的執行效率下降。相對地，條件傳送指令不會修改處理器的 PC 暫存器，因此它不會導致 CPU 需要進行分支預測，也就不會產生這部分損失。
至於 CPU 是如何進行分支預測的，相關內容超出了這門課的範疇，這裡我就不詳細介紹了。但你需要知道的是，在發生類似問題時，我們可以進一步觀察程式，並嘗試使用條件傳送指令最佳化這些邏輯。為了方便你理解，我們來看個例子。你可以看看下面這段程式碼中函式 foo 的實現細節：
函式 foo 接收兩個整型陣列 x 與 y，並依次比較這兩個陣列中位於相同索引位置上的元素，最後將較大者存放到陣列 y 的對應位置上。我們可以看到，在遍歷陣列的過程中，我們在迴圈結構內使用了 if 語句，來判斷陣列 x 中的元素值是否大於陣列 y 對應位置上的元素。而在程式碼實際編譯時，if 語句通常會由對應的條件分支指令來實現。因此，在迴圈結構的“加持”下，由 CPU 分支預測錯誤引發的懲罰，在經過每一輪迭代的累積後，都可能會變得更加可觀、更加明顯。
下面，我們就來使用條件傳送指令最佳化這段程式碼。條件傳送指令一般會用於實現 C 語法中的三元運算子 ？：，因此對上述程式碼的最佳化過程也就顯而易見：
#include
#define LEN 16
void foo（int* x， int* y） {
int i；
for （i = 0； i < LEN； i++） {
int min = x［i］ < y［i］ ？ x［i］ ： y［i］；
int max = x［i］ < y［i］ ？ y［i］ ： x［i］；
x［i］ = min；
y［i］ = max； }
}
可以看到，這裡我們沒有使用 if 語句來判斷，是否應該調整兩個陣列對應位置上的數字值，而是直接使用三元運算子，來將每一次迭代時的最大值與最小值結果計算出來，並複製到陣列中的相應位置上。
透過這種方式，我們雖然解決了 CPU 分支預測失敗帶來的懲罰，但與此同時，每一次迴圈中也會多了幾次比較與賦值操作。你可能想問：這樣的一來一回真的可以提升效能嗎？我的回答是：不要小看 CPU 指令並行處理能力的高效性，但也不要小看 CPU 分支預測帶來的效能損耗。
使用更高的編譯最佳化等級
除了可以透過調整程式碼寫法來最佳化程式執行外，我們還可以為編譯器指定更高最佳化等級的選項，來讓編譯器自動為我們進行更多程式執行細節上的最佳化。
以 GCC 為例，它為我們提供了 -O0、-O1、-O2、-O3、-Os、-Ofast 等最佳化選項。我把它們各自的大致最佳化內容整理成了一張表格，你可以參考：
尾遞迴呼叫最佳化（Tail-Call Optimization）
尾遞迴呼叫最佳化也是一個重要的程式碼最佳化技巧。
總的來看，尾遞迴呼叫最佳化透過將函式的遞迴呼叫過程最佳化為迴圈結構，減少了程式執行時對 call 指令的呼叫次數，進而減少了棧幀的建立與銷燬過程，提升了程式的執行效能。並且你需要注意，尾遞迴呼叫最佳化的效果在那些函式體本身較小，且遞迴呼叫次數較多的函式上體現得會更加明顯。
我用兩篇文章的時間講述瞭如何編寫高效能C程式的技巧，這裡我給大家推薦一本書《C程式設計語言》。這本書是Kernighan和Ritchie的合成成果，兩個人都是計算機程式設計界的先驅，儘管出版到現在幾十年，據說這本書被認為是C程式設計師的”聖經”。因為它全面、系統、準確地概述了C語言的各個特性以及程式設計的基本方法。但是，在閱讀前，你需要具備基本的程式設計知識。
C程式設計語言（原書第2版·新版 典藏版） C程式設計語言
檢視
講到這裡，今天的內容也就基本結束了。最後我來給你總結一下。
這篇內容我主要介紹了四種可用於實現高效能 C 程式的技巧：
迴圈展開讓我們可以進一步利用 CPU 的指令級並行能力，讓迴圈體執行得更快；
優先使用條件傳送指令，讓我們可以在一些特定的場景中，防止使用條件分支指令帶來的 CPU 週期浪費；
使用更高的編譯最佳化等級，讓我們可以借編譯器之手，利用更多“黑科技”進一步最佳化我們的程式碼；
尾遞迴呼叫最佳化讓我們可以用迴圈代替遞迴，減少函式呼叫時的棧幀建立與銷燬過程，讓遞迴進行得更快。