[推薦]性能優化的方法和技巧：代碼

本文是彎曲大牛KernelChina所寫，非常不錯，在這裡和大家分享一下。

代碼層次的優化是最直接，也是最簡單的，但前提是要對代碼很熟悉，對系統很熟悉。很多事情做到後來，都是一句話：無他，但手熟爾^-^。

在展開這個話題之前，有必要先簡單介紹一下Cache相關的内容，如果對這部分内容不熟悉，建議先補補課，做性能優化對Cache不了解，基本上就是盲人騎瞎馬。

Cache的關注點

Cache一般來說，需要關心以下幾個方面

1）Cache hierarchy

Cache的層次，一般有L1, L2, L3 （L是level的意思）的cache。通常來說L1，L2是內建  在CPU裡面的（可以稱之為On-chip cache），而L3是放在CPU外面（可以稱之為Off-chip  cache）。當然這個不是絕對的，不同CPU的做法可能會不太一樣。這裡面應該還需要加上  register，雖然register不是cache，但是把資料放到register裡面是能夠提高性能的。

2）Cache size

Cache的容量決定了有多少代碼和資料可以放到Cache裡面，有了Cache才有了競争，才有   了替換，才有了優化的空間。如果一個程式的熱點(hotspot)已經完全填充了整個Cache，那   麼再從Cache角度考慮優化就是白費力氣了，巧婦難為無米之炊。我們優化程式的目标是把   程式盡可能放到Cache裡面，但是把程式寫到能夠占滿整個Cache還是有一定難度的，這麼大   的一個Code path，相應的代碼得有多少，代碼邏輯肯定是相當的複雜（基本上是不可能，至少   我沒有見過）。

3）Cache line size

CPU從記憶體load資料是一次一個cache line；往記憶體裡面寫也是一次一個cache line，是以一個   cache line裡面的資料最好是讀寫分開，否則就會互相影響。

4）Cache associative

Cache的關聯。有全關聯(full associative)，記憶體可以映射到任意一個Cache line；也有N-way   關聯，這個就是一個哈希表的結構，N就是沖突鍊的長度，超過了N，就需要替換。

5）Cache type

有I-cache（指令cache），D-cache（資料cache），TLB（MMU的cache），每一種又有L1,   L2等等，有區分指令和資料的cache，也有不區分指令和資料的cache。

更多與cache相關的知識，可以參考這個連結：

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

或者是附件裡面的cache.pdf，裡面有一個簡單的總結。

代碼層次的優化

主要是從以下兩個角度考慮問題：

1）I-cache相關的優化

例如精簡code path，簡化調用關系，減少備援代碼等等。盡量減少不必要的調用。但是有用還是無用，是和應用相關的，是以代碼層次的優化很多是針對某個應用或者性能名額的優化。有針對性的優化，更容易得到可觀的結果。

2）D-cache相關的優化

減少D-cache miss的數量，增加有效的資料通路的數量。這個要比I-cache優化難一些。

下面是一個代碼優化技巧清單，需要不斷地補充，優化和篩選。

1) Code adjacency （把相關代碼放在一起），推薦指數：5顆星

把相關代碼放在一起有兩個涵義，一是相關的源檔案要放在一起；二是相關的函數在object檔案  裡面，也應該是相鄰的。這樣，在可執行檔案被加載到記憶體裡面的時候，函數的位置也是相鄰的。  相鄰的函數，沖突的幾率比較小。而且相關的函數放在一起，也符合子產品化程式設計的要求：那就是  高内聚，低耦合。

如果能夠把一個code path上的函數編譯到一起（需要編譯器支援，把相關函數編譯到一起），  很顯然會提高I-cache的命中率，減少沖突。但是一個系統有很多個code path，是以不可能面  面俱到。不同的性能名額，在優化的時候可能是沖突的。是以盡量做對是以case都有效的優化，  雖然做到這一點比較難。

2) Cache line alignment （cache對齊），推薦指數：4顆星

資料跨越兩個cache line，就意味着兩次load或者兩次store。如果資料結構是cache line對齊的，  就有可能減少一次讀寫。資料結構的首位址cache line對齊，意味着可能有記憶體浪費（特别是  數組這樣連續配置設定的資料結構），是以需要在空間和時間兩方面權衡。

3) Branch prediction （分支預測），推薦指數：3顆星

代碼在記憶體裡面是順序排列的。對于分支程式來說，如果分支語句之後的代碼有更大的執行幾率，  那麼就可以減少跳轉，一般CPU都有指令預取功能，這樣可以提高指令預取命中的幾率。分支預測  用的就是likely/unlikely這樣的宏，一般需要編譯器的支援，這樣做是靜态的分支預測。現在也有  很多CPU支援在CPU内部儲存執行過的分支指令的結果（分支指令的cache），是以靜态的分支預測  就沒有太多的意義。如果分支是有意義的，那麼說明任何分支都會執行到，是以在特定情況下，靜态 分支預測的結果并沒有多好，而且likely/unlikely對代碼有很大的侵害（影響可讀性），是以一般不  推薦使用這個方法。

4) Data prefetch (資料預取），推薦指數：4顆星

指令預取是CPU自動完成的，但是資料預取就是一個有技術含量的工作。資料預取的依據是預取的資料  馬上會用到，這個應該符合空間局部性（spatial locality），但是如何知道預取的資料會被用到，這個  要看上下文的關系。一般來說，資料預取在循環裡面用的比較多，因為循環是最符合空間局部性的代碼。

但是資料預取的代碼本身對程式是有侵害的（影響美觀和可讀性），而且優化效果不一定很明顯（命中  的機率）。資料預取可以填充流水線，避免通路記憶體的等待，還是有一定的好處的。

5) Memory coloring （記憶體着色），推薦指數：不推薦

記憶體着色屬于系統層次的優化，在代碼優化階段去考慮記憶體着色，有點太晚了。是以這個話題可以放到  系統層次優化裡面去讨論。

6）Register parameters （寄存器參數），推薦指數：4顆星

寄存器做為速度最快的記憶體單元，不好好利用實在是浪費。但是，怎麼用？一般來說，函數調用的參數  少于某個數，比如3，參數是通過寄存器傳遞的（這個要看ABI的約定）。是以，寫函數的時候，不要  帶那麼多參數。c語言裡還有一個register關鍵詞，不過通常都沒什麼用處（沒試過，不知道效果，不過  可以反彙編看看具體的指令，估計是和編譯器相關）。嘗試從寄存器裡面讀取資料，而不是記憶體。

7) Lazy computation （延遲計算），推薦指數：5顆星

延遲計算的意思是最近用不上的變量，就不要去初始化。通常來說，在函數開始就會初始化很多資料，但是  這些資料在函數執行過程中并沒有用到（比如一個分支判斷，就退出了函數），那麼這些動作就是浪費了。

變量初始化是一個好的程式設計習慣，但是在性能優化的時候，有可能就是一個多餘的動作，需要綜合考慮函數  的各個分支，做出決定。

延遲計算也可以是系統層次的優化，比如COW(copy-on-write)就是在fork子程序的時候，并沒有複制父  程序所有的頁表，而是隻複制指令部分。當有寫發生的時候，再複制資料部分，這樣可以避免不必要的複制，  提供程序建立的速度。

8] Early computation （提前計算），推薦指數：5顆星

有些變量，需要計算一次，多次使用的時候。最好是提前計算一下，儲存結果，以後再引用，避免每次都  重新計算一次。函數多了，有時就會忽略這個函數都做了些什麼，寫程式的人可以不了解，但是優化的時候  不能不了解。能使用常數的地方，盡量使用常數，加減乘除都會消耗CPU的指令，不可不查。

9）Inline or not inline （inline函數），推薦指數：5顆星

Inline or not inline，這是個問題。Inline可以減少函數調用的開銷（入棧，出棧的操作），但是inline也  有可能造成大量的重複代碼，使得代碼的體積變大。Inline對debug也有壞處（彙編和語言對不上）。是以  用這個的時候要謹慎。小的函數（小于10行），可以嘗試用inline；調用次數多的或者很長的函數，盡量不  要用inline。

10) Macro or not macro (宏定義或者宏函數），推薦指數：5顆星

Macro和inline帶來的好處，壞處是一樣的。但我的感覺是，可以用宏定義，不要用宏函數。用宏寫函數，  會有很多潛在的危險。宏要簡單，精煉，最好是不要用。中看不中用。

11) Allocation on stack （局部變量），推薦指數：5顆星

如果每次都要在棧上配置設定一個1K大小的變量，這個代價是不是太大了哪？如果這個變量還需要初始化（因  為值是随機的），那是不是更浪費了。全局變量好的一點是不需要反複的重建，銷毀；而局部變量就有這個  壞處。是以避免在棧上使用數組等變量。

12) Multiple conditions （多個條件的判斷語句），推薦指數：3顆星

多個條件判斷時，是一個逐漸縮小範圍的過程。條件的先後，決定了前面的判斷是否多餘的。根據code path  的情況和條件分支的幾率，調整條件的順序，可以在一定程度上減少code path的開銷。但是這個工作做  起來有點難度，是以通常不推薦使用。

13) Per-cpu data structure (非共享的資料結構），推薦指數：5顆星

Per-cpu data structure 在多核，多CPU或者多線程程式設計裡面一個通用的技巧。使用Per-cpu data  structure的目的是避免共享變量的鎖，使得每個CPU可以獨立通路資料而與其他CPU無關。壞處是會  消耗大量的記憶體，而且并不是所有的變量都可以per-cpu化。并行是多核程式設計追求的目标，而串行化  是多核程式設計裡面最大的傷害。有關并行和串行的話題，在系統層次優化裡面還會提到。

局部變量肯定是thread local的，是以在多核程式設計裡面，局部變量反而更有好處。

14) 64 bits counter in 32 bits environment （32位環境裡的64位counter），推薦指數：5顆星

32位環境裡面用64位counter很顯然會影響性能，是以除非必要，最好别用。有關counter的優化可以多  說幾句。counter是必須的，但是還需要慎重的選擇，避免重複的計數。關鍵路徑上的counter可以使用  per-cpu counter，非關鍵路徑(exception path）就可以省一點記憶體。

15) Reduce call path or call trace （減少函數調用的層次），推薦指數：4顆星

函數越多，有用的事情做的就越少（函數的入棧，出棧等）。是以要減少函數的調用層次。但是不應該  破壞程式的美觀和可讀性。個人認為好程式的首要标準就是美觀和可讀性。不好看的程式讀起來影響心  情。是以需要權衡利弊，不能一個程式就一個函數。

16) Move exception path out （把exception處理放到另一個函數裡面），推薦指數：5顆星

把exception path和critical path放到一起（代碼混合在一起），就會影響critical path的cache性能。  而很多時候，exception path都是長篇大論，有點喧賓奪主的感覺。如果能把critical path和  exception path完全分離開，這樣對i-cache有很大幫助。

17) Read, write split （讀寫分離），推薦指數：5顆星

在cache.pdf裡面提到了僞共享(false sharing)，就是說兩個無關的變量，一個讀，一個寫，而這  兩個變量在一個cache line裡面。那麼寫會導緻cache line失效（通常是在多核程式設計裡面，兩個變量  在不同的core上引用）。讀寫分離是一個很難運用的技巧，特别是在code很複雜的情況下。需要  不斷地調試，是個力氣活（如果有工具幫助會好一點，比如cache miss時觸發cpu的execption處理  之類的）。

18) Reduce duplicated code（減少備援代碼），推薦指數：5顆星

代碼裡面的備援代碼和死代碼(dead code)很多。減少備援代碼就是減小浪費。但備援代碼有時  又是必不可少（copy-paste太多，尾大不掉，不好改了），但是對critical path，花一些功夫還  是必要的。

代碼優化有時與程式設計規則是沖突的，比如直接通路成員變量，還是通過接口來通路。程式設計規則上肯定是說要通過接口來通路，但直接通路效率更高。還有就是許多ASSERT之類的代碼，加的多了，也影響性能，但是不加又會給debug帶來麻煩。是以需要權衡。代碼層次的優化是基本功課，但是指望代碼層次的優化來解決所有問題，無疑是緣木求魚。從系統層次和算法層次考慮問題，可能效果會更好。

代碼層次的優化需要相關工具的配合，沒有工具，将會事倍功半。是以在優化之前，先把工具準備好。有關工具的話題，會在另一篇文章裡面講。

還有什麼，需要好好想想。這些優化技巧都是與c語言相關的。對于其他語言不一定适用。每個語言都有一些與性能相關的編碼規範和約定俗成，遵守就可以了。有很多Effective, Exceptional 系列的書籍，可以看看。

代碼相關的優化，着力點還是在代碼上，多看，多想，就會有收獲。

參考資料：

1）http://en.wikipedia.org/wiki/CPU_cache

2)  Effective C++: 55 Specific Ways to Improve Your Programs and Designs (3rd Edition)

3)  More Effective C++: 35 New Ways to Improve Your Programs and Designs

4) Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library

5) Effective Java (2nd Edition)

6) Effective C# (Covers C# 4.0): 50 Specific Ways to Improve Your C# (2nd Edition) (Effective Software Development Series)