C++性能優化

02-10

摘要：性能優化不管是從方法論還是從實踐上都有很多東西，本系列的文章會從C++語言本身入手，介紹一些性能優化的方法，希望能做到簡潔實用。

作者：ali4846j3o

原文：http://click.aliyun.com/m/41845/

前言

性能優化不管是從方法論還是從實踐上都有很多東西，本系列的文章會從C++語言本身入手，介紹一些性能優化的方法，希望能做到簡潔實用。

實例1

在開始本文的內容之前，讓我們看段小程序：

如果要對這段代碼進行優化，你認為瓶頸會是什麼呢？代碼-g -O2後看一眼彙編：

指令已經很少了，有多少優化空間呢？先不著急，看看下面這段代碼

寫了一個小程序，digits10_v2 比 digits10_v1快了45%, digits10_v3 比digits10_v1快了60%+。

不難看出測試結論跟數據的取值範圍相關，就本例來說數值越大，提升越明顯。是什麼原因呢？附測試程序：

Strength reduction

優化原因不是因為做了循環展開，而是由於不同指令本身的速度就是不一樣的，比較、整型的加減、位操作速度都是最快的，而除法/取余卻很慢。

下面有一個更詳細的列表，為了更直觀一些，用了clock cycle來衡量，不過這裡的clock cycle是個平均值，不同的CPU還是稍有差異：

雖然大多數場景下，數學運算都不會有太多性能問題，但相對來說，整型的除法運算還是比較昂貴的。編譯器就會利用這一特點進行優化，一般稱作Strength reduction.

對於前面的例子，核心原因是digits10_v2用比較和加法來減少除法(/=)操作，digits10_v3通過搜索的方式進一步減少了除法操作。

由於cpu並行處理技術，我們不能簡單的用後面的clock cycle來衡量性能，但不難看出處理器對類型的還是非常敏感的，以整型和浮點的處理為例：

整型

類型轉換

ints--> short/char (0~1 clock cycle)
ints --> float/double (4~16個clock cycle), signed ints 快於 unsigned ints，唯一一個場景signed比unsigned快的
short/char的計算通常使用32bit存儲，只是返回的時候做了截取，故只在要考慮內存大小的時候才使用short/char，如array
註：隱式類型轉換可能會溢出，有符號的溢出變成負數，無符號的溢出變成小的整數

運算

除法、取余運算unsigned ints 快於 signed ints
除以常量比除以變數效率高，因為可以在編譯期做優化，尤其是常量可以表示成2^n時
++i和i++本身性能一樣，但不同的語境效果不一樣，如array[i++]比arry[++i]性能好；當依賴自增結果時，++i性能更好，如a=++b,a和b可復用同一個寄存器

代碼示例

浮點

單精度、雙精度的計算性能是一樣的
常量的默認精度是雙精度
不要混淆單精度、雙精度，混合精度計算會帶來額外的精度轉換開銷，如

浮點除法比乘法慢很多，故可以利用乘法來加快速度，如

這裡介紹的大多是編譯器的擅長但又不能直接優化的場景，也是平常優化中比較容易忽視的點，其實往往我們往前多走一步，編譯器就可以工作得更好。

實例2

先看一個數字轉字元串的例子，stringstream和sprintf 自然不會是我們考慮的對象，雖然protobuf庫中的FastInt32ToBuffer很不錯，其實還能優化，下面的版本就比例子中stringstream快6倍，代碼如下：

不用細讀stringstream/sprintf的源碼，反彙編看下就能知道個大概，對於轉字元串這個場景，stringstream/sprintf就太重了，通常來說越少的指令性能也越好（如果你讀過本系列的上一篇c++性能優化（一） ---- 從簡單類型開始，不難發現，這句話也不正確，呵呵)。但本文討論的重點是內存訪問，就上面這段代碼，有什麼內存使用上的問題？如何進一步優化？

分析

優化前還是得找一下性能熱點，下面是vtune結果的截圖(雖然cpu time和彙編指令的消耗對應得不是特別好):

數組reverse的開銷跟上面生成數組元素相近，reverse有這麼耗時么？

從圖中的彙編可以看出，一次swap對應著兩次內存讀(movzxb)、兩次內存寫(movb)，因為一次寫就意味著一個讀和一個寫，描述的是內存-->cache-->內存的過程。

優化

減少內存寫操作

一個很自然的優化想法，應該盡量避免內存寫操作，於是代碼可以進一步優化，結合 Strength reduction，代碼如下：

實測發現新版本比之前版本性能提升了10%，還有優化空間么？答案是，有。方案是：通過查表，一次處理2個數字，減少數據依賴，如：

結論：

u64ToAscii_v3性能比基準版本提升了30%；
如果用到悟時的那個測試場景，性能可以提升6.5倍。

下面是完整的測試代碼和結果：

看到優化寫內存操作的威力了吧，讓我們再看一個減少寫操作的例子：

假定A、B、C都很小，且不會溢出，可以寫成

如果需要考慮溢出，也可以改為

讀取效率

對於內存的寫，最好的辦法就是減少寫的次數，那麼內存的讀取呢？

教科書的答案是：儘可能順序訪問內存。理解這句話還是得從cache line開始，因為實際的cpu比較複雜，下面的表述嘗試做些簡化，如有問題，歡迎指正：

cache line

假設L1cache大小為8K，cache line 64位元組、4way，那麼整個cache會分成32個集合，

81024/64=128=324，一個內存地址進入哪個cache line不是任意的，而是確定在某個集合中，可以通過公式(set ) = (memory

address) / ( line size) % (number of sets )來計算，如地址是10000，則(set)=10000/64%32 = 28, 即編號為28的集合內的4個cache line之一。

用16進位來描述，10000=0x2710,一次內存讀取是64bytes，那麼訪問內存地址10000即意味著地址0x2700~0x273F都進集合編號為28(0x1C)的cache line中了。

cache miss

可以看出，順序的訪問內存是能夠比較高效而且不會因為cache衝突，導致葯頻繁讀取內存。那什麼的情況會導致cache miss呢？

當某個集合內的cache line都有數據時，且該集合內有新的數據就會導致老數據的換出，進而訪問老數據就會出現cache miss。
以先後讀取0x2710, 0x2F00, 0x3700, 0x3F00, 0x4700為例, 這幾個地址都在28這個編號的集合內，當去讀0x4700時，假定CPU都是以先進先出策略，那麼0x2710就會被換出，這時候如果再訪問0x2700~0x273F的數據就cache miss，需要重新訪問內存了。
可以看出變數是否有cache 競爭，得看變數地址間的距離，distance = (number of sets ) (line size) = ( total cache size) / ( number of ways) , 即距離為3264 = 8K/4= 2K的內存訪問都可能產生競爭。
上面這些不光對變數、對象有用，對代碼cache也是如此。

建議

對於內存的訪問，可以考慮以下一些建議：

一起使用的函數存儲在一起。函數的存儲通常按照源碼中的順序來的，如果函數A,B,C是一起調用的，那盡量讓ABC的聲明也是這個順序
一起使用的變數存儲在一起。使用結構體、對象來定義變數，並通過局部變數方式來聲明，都是一些較好的選擇。例子見後文：
合理使用對齊(__attribute__((aligned(64)))、預取(prefecting data)，讓一個cacheline能獲取到更多有效的數據
動態內存分配、STL容器、string都是一些常容易cache不友好的場景，核心代碼處盡量不用

靜態變數

讓我們再回到最前面的優化，u64ToAscii_v3引入了局部靜態變數(digits)，是否合適？通常來說，要具體問題具體分析，沒有標準答案。

靜態變數和棧地址是分開的，可能會帶來cache miss的問題，通過去掉static修飾符，直接在棧上聲明變的方式可以避免，但這種做法可行有幾個前提條件：

變數大小是要限制的，不超出cache的大小(最好是L1 cache)
變數的初始化在棧上完成，故最好不要在循環內部定義，以避免不必要的初始化。

其實內存訪問和CPU運算是沒有一定的贏家，真正做優化時，需要結合具體的場景，仔細測量才能得到答案。

回顧

前面兩個實例分別從編譯器和內存使用的角度介紹了一些性能優化的方法，後面內容則會回到cpu，從指令並行的角度看看我們常見的邏輯控制有哪些可以優化的點。

流水線

通常一個CPU可以並行執行多條指令，如：4條浮點乘法，等待4個內存訪問、一個還為到來的分支比較，不同的運算單元也是可以並行計算，如for(int i = 0; i < N; ++i) a[i]=i0.2; 這裡的i < N和++i 在i0.2可以同時執行。提升指令並行能力，往往就能達到提升性能的目的。

從流水線的角度看，指令pipeline的幾個階段：fetch、decode、execute、memory-access、write-back，除了存儲器的訪問效率會影響並行度外，下一條指令的fetch/decode也很關鍵，而跳轉和分支則是又一個攔路虎，這也是本文接下去要主要分析的地方：

函數

本身開銷

函數調用使得處理器跳到另外一個代碼地址並回來，一般需要4 clock cycles，大多數情況處理器會把函數調用、返回和其他指令一起執行以節約時間。
函數參數存儲在棧上需要額外的時間( 包括棧幀的建立、saving and restoring registers、可能還有異常信息)。在64bit linux上，前6個整型參數(包括指針、引用)、前8個浮點參數會放到寄存器中；64bit windows上不管整型、浮點，會放置4個參數。
在內存中過於分散的代碼可能會導致較差的code cache

常見的優化手段

避免不必要的函數，特別在最底層的循環，應該盡量讓代碼在一個函數內。看起來與良好的編碼習慣衝突(一個函數最好不要超過80行)，其實不然，跟這個系列其他優化一樣，我們應該知道何時去使用這些優化，而不是一上來就讓代碼不可讀。
嘗試使用inline函數，讓函數調用的地方直接用函數體替換。inline對編譯器來說是個建議，而且不是inline了性能就好，一般當函數比較小或者只有一個地方調用的時候，inline效果會比較好
在函數內部使用循環(e.g., change for(i=0;i<100;i++) DoSomething(); into DoSomething()
{ for(i=0;i<100;i++) { ... } } )
減少函數的間接調用，如偏向靜態鏈接而不是動態鏈接，盡量少用或者不用多繼承、虛擬繼承
優先使用迭代而不是遞歸
使用函數來替換define，從而避免多次求值。宏的其他缺點：不能overload和限制作用域（undef除外）

分支預測

應用場景

常見的分支預測場景有if/else,for/while,switch，預測正確0~2 clock cycles，錯誤恢復12~25 clock cycles。

一般應用分支預測的正確率在90%以上，但個位數的誤判率對有較多分支的程序來說影響還是非常大的。分支預測的技術(或者說策略)非常多，這裡不會展開介紹，對寫程序來說，我們知道越簡單的場景越容易預測正確：如分支都在在一個循環內或者幾乎沒有其他分支。

關鍵因素

如果對分支預測的概念和作用還不清楚的話，可以看看後面的參考文檔。幾個影響分支預測因素：

branch target buffer (BTB)

Return Address Stack (RAS)

常見的優化手段

消除條件分支

代碼實例

優化版本1

優化版本2

優化版本3

bool類型變換

實例代碼

編譯器的行為是

優化版本

實例代碼2

反例

a && b 何時不能轉換成a & b，當a不可能為false的情況下

a | | b 何時不能轉換成a | b，當a不可能為true的情況下

循環展開

實例代碼

優化版本

優化說明

優點：減少比較次數、某些CPU上重複次數越少預測越准、去掉了if判斷
缺點：需要更多的code cache or micro-op cache、有些處理器(core 2)對於小循環性能很好(小於65bytes code)、循環的次數和展開的個數不匹配
一般編譯器會自動展開循環，程序員不需要主動去做，除非有一些明顯優點，比如減少上面的if判斷

邊界檢查

實例代碼1

實例代碼2

使用數組

實例代碼1

實例代碼2

整形的bit array語義，適用於enum、const、define

本塊小結

儘可能的減少跳轉和分支
優先使用迭代而不是遞歸
對於長的if...else，使用switch case，以減少後麵條件的判斷，把最容易出現的條件放在最前面
為小函數使用inline，減少函數調用開銷
在函數內使用循環
在跳轉之間的代碼盡量減少數據依賴
嘗試展開循環
嘗試通過計算來消除分支

參考文檔

<<深入理解計算機系統>>

http://en.wikipedia.org/wiki/Instruction_pipelining

http://web.cecs.pdx.edu/~alaa/ece587/notes/bpred-6up.pdf

http://cseweb.ucsd.edu/~j2lau/cs141/week8.html

http://en.wikipedia.org/wiki/Branch_predictor

http://en.wikipedia.org/wiki/Branch_target_predictor

http://www-ee.eng.hawaii.edu/~tep/EE461/Notes/ILP/buffer.html

http://book.51cto.com/art/200804/70903.htm

http://en.wikipedia.org/wiki/Strength_reduction

https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920

http://people.cs.clemson.edu/~dhouse/courses/405/papers/optimize.pdf

http://www.agner.org/optimize/optimizing_cpp.pdf

更多技術乾貨敬請關注云棲社區知乎機構號：阿里云云棲社區 - 知乎