現代處理器與代碼性能優化
現代處理器具有相當的計算能力，但是我們可能需要按非常程序化的方式來編寫程序，以便將這些能力誘發出來。——《深入理解計算機系統》
現代處理器的一些特性
現代處理器取得了了不起的功績之一，是他們採用複雜而奇異的處理器結構，其中，多條指令可以並行的執行，同時又呈現出一種簡單的順序執行指令的表象。——《深入理解計算機系統》
在我們直觀的認識中，處理器就是那個按著編譯好的代碼指令，不斷順序重複著取指、解碼、執行操作的單調而可靠的機器。事實上，現代處理器對待代碼指令的處理方式，早已不再是表面上看起來的那麼規矩，對不同形式的代碼，它將可能呈現不同的運行策略。
關於現代處理器的特性，本文只簡單介紹與後面代碼優化技巧有關的幾個，更多更豐富的特性介紹，建議參考資料[1]，裡面有專業而詳細的描述。
1.1 超標量
可以在每個時鐘周期執行多個操作的處理器稱為「超標量處理器」。現代處理器主要從兩個方面實現超標量處理：
- 多個並行的功能單元。這些單元能同時執行相同或不同的指令，如TI的C64X+架構就配置了8個並行功能單元，分別負責乘加、邏輯、存取等操作。VLIW(Very Long Instruction Word)超長指令集被設計來給這多個功能單元進行指令分發；
- SSE(Streaming SIMD Extensions, 流SIMD指令擴展 )，SIMD即Single-In-struction,Multiple Data(單指令多數據)。通過擴展額外的矢量處理功能單元以及矢量寄存器等，可以實現單個指令控制多路相同的計算，如一次做8個Byte的數據存取 ，又或是一次做8個16x16乘法。ARM處理器中的NEON協處理器就是對ARM架構的SIMD擴展。、
1.2 高速緩存
高速緩存（cache）是一個小而快速的存儲設備，一般而言，CPU對高速緩存的訪問速度僅次於寄存器。緩存空間的大小不僅與其價格高有關，更重要的是隨著存儲能量的擴大，存儲的訪問延遲將隨之增加，因此很多處理器設計了多級的緩存結構，越靠近CPU的層級其容量越小。
現代處理器包括獨立的I-cache（指令緩存）和D-cache（數據緩存），它們由專門的硬體邏輯來管理。簡單來說，緩存管理器在CPU第一次訪問某個低層級的存儲時（緩存缺失），會連帶把該存儲地址之後的多個指令/數據與上級緩存交互，這樣當CPU接下來想訪問下一個連續的指令/數據時，就只需要訪問緩存即可（緩存命中）。
有這樣幾個重要指標來衡量高速緩存的性能：缺失率、命中率、命中時間、缺失處罰。其中從缺失 處罰這個指標中，我們來看看緩存對加快CPU的運算性能有多麼的重要。
缺失處罰是由於緩存不命中所需要的額外時間開銷。對L1高速緩存來說，命中時間的數量級是幾個時鐘周期；L1缺失需要從L2得到服務的處罰，通常是數10個周期；從L3得到服務的處罰為50個周期；從主存得到服務的處罰為200個周期！
1.3 分支預測、投機執行、條件傳送
分支代碼對於流水線處理而言是一個障礙，因為編譯器，包括硬體非常有可能無法預知下一步到底將執行哪個分支的指令，於是只好等待分支判斷結果出來後再繼續填充流水線，造成流水線中的「空泡」。
現代處理器採用了一種稱為分支預測的技術，它會猜測是否會選擇分支，同時還預測分支的目標地址。之後，使用投機執行的技術，處理器會開始取出位於它預測的分支跳轉處的指令，並對指令解碼，甚至在它確定分支是否預測正確之前就開始執行這些操作。直到確定了實際的分支路徑，如果預測正確，處理器就會「提交」投機執行的指令的結果。
當分支預測邏輯預測錯誤時，條件分支可能會招致很大的「預測錯誤懲罰」。這時，處理器必須丟掉所有投機執行的結果，在正確的位置重新開始取指令的過程，在產生有用的結果之前，必須重新填充指令流水線。
另一種處理分支的方法是使用「條件傳送指令」。編譯器能產生使用這些指令的代碼，依據條件滿足與否選擇執行或忽略指令，而不是傳統的基於控制的條件轉移。翻譯成條件傳送的基本思想是計算出一個條件表達式或語句兩個方向上的值，然後用條件傳送選擇期望的值。條件傳送指令可以被實現為普通指令流水線化處理的一部分，沒有必要猜測條件是否滿足，因此猜測錯誤也沒有處罰。
1.4 亂序執行
對於單個線程而言，如果只是順序執行指令，有時後面的指令需要依賴前面指令的執行結果，因此可能引起功能單元或流水線等待，降低了處理效率。
亂序執行是指在邏輯上在後面的指令可以先於前面的指令執行，這更提高了硬體的執行效率，達到更高的指令級並行度。處理器採用一種「寄存器重命名」的方式實現指令亂序執行的同時，保證不影響程序最終的結果。
代碼優化的必要性
現代處理器具有相當的計算能力，但是我們可能需要按非常程序化的方式來編寫程序，以便將這些能力誘發出來。——《深入理解計算機系統》
讓我們暫時拋開代碼架構以及代碼可讀性，只談論對整個程序運行性能影響最大的那些核心代碼段。大部分程序員更多關心的是實現代碼功能的演算法，而很少注意到使用對編譯器和處理器友好的代碼。例如數組排序，我們會想到底是用冒泡排序，還是插入排序，亦或是堆排序……然後樂此不疲地比較哪種演算法可以消耗最少的算力。在工程實踐中我發現，適當調整代碼實現的技巧，往往能比選擇演算法本身帶來更大的效率提升，有時這種提升是成倍甚至幾十倍的！這麼說當然不是認為演算法選擇不重要，而是想說明代碼優化同樣非常重要。
編譯器通常集成有優化器，能自動地對用戶代碼做出合適的優化。儘管有些優化器已經極盡其所能了，但人為的優化干預依然是必要的。
一方面，調整代碼結構有風險，為避免因優化造成的代碼錯誤，編譯器總是做保守估計。
另一方面，由於通常的程序本身不具有並行性，嚴重地削弱了通過超標量執行實現的指令級並行性，即使最聰明的亂序超標量處理器，同時結合聰明的和富有競爭性的編譯器，依然會受到載入延遲、cache 缺失、分支和指令之間相關等的綜合影響，使得處理器在很少的周期內充滿( 全速運行）。
鑒於上面的原因，用戶可以大致從兩個方面著手優化自己的代碼：
- 編譯器友好化。理解優化編譯器的能力和局限性，盡量通過代碼本身和預編譯偽指令「告訴」編譯器用戶的真實意圖；
- 處理器友好化。調整代碼實現方式，儘可能充分地利用處理器的硬體單元。
儘管同樣的優化策略在不同的處理器上不一定有同樣的效果，但是操作和優化的通用原則，對各種各樣的處理器都適用。
簡易卻有效的優化技巧
3.1 消除不必要的內存引用
代碼片段1
void array_sum(short *a, short *sum, length)
{
unsigned int i; for(i=0; i<length ; i++) { *sum = *sum + a[i]; }}
對於上面這段代碼，每次迭代需進行兩次讀內存操作+1次寫內存操作+1次加法。然而除了最後一次迭代時，我們需要把計算結果寫入sum所代表的存儲地址外，中間的計算過程實際上可以臨時保存在寄存器中。因此對代碼做如下改動：
代碼片段2
void array_sum(short *a, short *sum, length)
{unsigned int i;
short sum_temp = 0; for(i=0; i<length ; i++) { sum_temp = sum_temp + a[i]; } *sum = sum_temp;}
這樣便將每次迭代的內存操作從兩次讀和一次寫減少到了只需一次讀。
試想，如此明顯的優化難道編譯器不會自動完成嗎？如果我們仔細分析代碼，會發現倘若調用函數時a和sum指向了相同的地址，以上兩段代碼將可能會得到不同的兩個結果。而在無法確認是否會出現這種存儲混疊的情況下，編譯器將採取保守的態度！
3.2 多個累積變數
重新考慮代碼片段2，因為下一次sum_temp的計算依賴於上一次sum_temp的累加結果，每個周期最多只能計算一個元素的累加值 。假設處理器擁有兩個並行的加法單元，則總會有一個單元是閑置的。考慮到這一點，再把代碼改寫成如下的形式：
代碼片段3
void array_sum(short *a, short *sum, length)
{ unsigned int i; short sum_temp1 = 0; short sum_temp2 = 0; for(i=0; i<length-1 ; i+=2) { sum_temp1 = sum_temp1 + a[i];sum_temp2 = sum_temp2 + a[i+1];
} for(; i<length; i++) { sum_temp1 = sum_temp1 + a[i]; } *sum = sum_temp1 + sum_temp1;}
用兩個臨時累積變數同時累加，使得在同一個周期內處理器的兩個加法單元能同時運行，提升了指令的並行度。
3.4 書寫適合條件傳送實現的代碼
代碼片段4
for (i=0; i<CORDIC_level; i++)
{ if (y_coord < 0) { x_coord = x_coord - (y_coord >> i); y_coord = y_coord + (x_coord >> i); angle_accumulate = angle_accumulate - angleLUT[i]; } else {x_coord = x_coord + (y_coord >> i);
y_coord = y_coord - (x_coord >> i); angle_accumulate = angle_accumulate + angleLUT[i]; }}
如上代碼段4所示，循環內包含了分支判斷語句，使得編譯器難以對循環體進行流水編排。另外，由於分支預測只對有規律的模式可行，上述y_coord < 0 條件的判斷幾乎無法預測，因此分支預測將會處理得很糟糕。
如果編譯器能夠產生使用條件數據傳送而不是使用條件控制轉移的代碼，可以極大提高程序的性能。有些表達條件行為的方法能夠直接地被翻譯為條件傳送，避免了需要處理器進行分支預測的可能。
把代碼片段4改為如下的風格，並通過檢查產生的彙編代碼，確認其確實生成了使用條件傳送的代碼：
代碼片段5
int x_temp, y_temp;
for (i=0; i<CORDIC_level; i++){ x_temp = x_coord >> i; y_temp = y_coord >> i; x_coord = (y_coord < 0)? (x_coord - y_temp ) : (x_coord + y_temp); y_coord = (y_coord < 0)? (y_coord + x_temp ) : (y_coord - x_temp); angle_accumulate = (y_coord < 0)? (angle_accumulate - angleLUT[i]) : (angle_accumulate + angleLUT[i]);}
3.4 緩存友好型代碼
在本公眾號的另一篇文章《計算機系統中與存儲有關的那些事》中，已經介紹了存儲訪問的時間局部性和空間局部性，並給出了編寫局部性好的代碼示例。
這裡再討論一個容易被忽視的問題，它出現在我的實際項目調試過程中。有一個函數，不考慮存儲訪問的模擬結果顯示，該函數完整運行大概耗時100us，但實際運行卻發現該函數消耗了700us左右。因為模擬沒有考慮內存訪問的延遲，所以我們容許實際運行結果會比模擬結果稍多一些，但700us相比於100us足足大了7倍，這就有點異常了。
經過一番排查，最終發現問題出在一條變數初始化語句上。一個全局數組short a[1920*8]，在函數開頭對它進行初始化處理：
memset(a, 0, sizeof(a));
然而就這一條語句就消耗了500多個us！事後對代碼功能進行分析，發現通過一些調整是可以完全避免對該變數進行初始化的。特別是像這樣大的數組，局部性再好其緩存缺失次數也將很大，而且會造成緩存被大片刷新。
通常一些好的編程習慣，可能會導致性能的惡化，比如數據塊的初始化，在代碼中經常可以看到malloc後馬上memset，然後再對數據塊賦值，如果操作的內存塊很大，對性能影響很明顯。因此，變數初始化是一個好的編程習慣，但如果跟性能衝突儘可能避免這樣的操作或者只對關鍵的數據進行初始化，避免大塊數據的操作。
程序性能剖析
4.1 確認性能瓶頸
在處理大程序時，要明確地知道應該優化什麼地方都是很難的。此時可以藉助代碼剖析工具（code profiler），在程序執行時收集每個函數的調用次數和所花費的時間等參數，通過列印的剖析報告就能得出函數的耗時分布情況。
Amdahl定律可以用於分析程序中某部分性能的提升最終能給程序的整體性能帶來多大的影響。
Amdahl定律指出，設原程序執行時間為Told，其某部分代碼所需執行時間占該時間的比例為a，而該部分性能提升的比例為b，則整個程序的加速比為：
Told/Tnew = 1/[(1-a) + a/b]
4.2 程序的最大性能
在對代碼進行優化後，通過模擬或者實際運行，可以測試優化的效果。然而這終究只是一個相對的比較，如果能建立一種評估辦法，首先確立一個性能指數的邊界（就像參數估計中的克拉美羅界一樣），然後通過測試所寫代碼的該項性能指數，不就能得出代碼優化的絕對程度，以及預知還存在多大優化空間嗎？
《深入理解計算機系統》這本書中，作者就給我們提供了這樣的一套評估辦法。書中，作者以每元素的周期數（CPE）作為統計指數，以延遲界限和吞吐量界限兩項來描述程序的最大性能。
CPE指數只是針對循環代碼而言的（幾乎可以說代碼性能優化就是對循環的優化），它指處理數據的每個元素所消耗的周期數。之所以使用每個元素的周期數而不是每個循環的周期數來度量，是因為循環次數可能隨循環展開的程度不同而變化，而我們最終關心的是，對於給定的向量長度，程序運行的速度如何。
延遲界限描述的是，當一系列操作必須按照嚴格的順序執行時，處理每個元素所歷經的關鍵路徑（最長路徑）的周期數。當數據相關問題限制了指令級並行的能力時，延遲界限能夠限制程序性能。
吞吐量界限描述的是，處理器功能單元全力運行時的原始計算能力。比如處理器具有兩個能同時做乘法的單元，對於只有1次乘/元素的循環而言，此時的吞吐量界限就是0.5。吞吐量界限是程序性能的終極界限。
參考資料
【1】Modern Microprocessors:A 90-Minute Guide!
【2】BRYANT R E, O』HALLARON D R. Computer Systems: A Programmer』s Perspective[M]. 3 edition. Boston: Pearson, 2015.（譯名：深入理解計算機系統）
【3】CC++代碼優化的27個建議--伯樂在線.
【4】程序性能優化（一、二、三）--堅持的博客園.
歡迎來我的微信公眾號做客：信號君
專註於信號處理知識、高性能計算、現代處理器&計算機體系
幸會~
推薦閱讀：
