性能優化技巧之代碼層次優化
編者按：在上一篇《性能優化技巧之三個層次》中主要介紹了性能優化的三個層次。本文是性能優化系列文章的第二篇，主要講解性能優化在代碼層次方面的優化：I-cache相關的優化和D-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 (把相關代碼放在一起)
推薦指數：☆☆☆☆☆
把相關代碼放在一起有兩個涵義，一是相關的源文件要放在一起;二是相關的函數在object文件 里面，也應該是相鄰的。這樣，在可執行文件被加載到內存里面的時候，函數的位置也是相鄰的。 相鄰的函數，沖突的幾率比較小。而且相關的函數放在一起，也符合模塊化編程的要求：那就是 高內聚，低耦合。
如果能夠把一個code path上的函數編譯到一起(需要編譯器支持，把相關函數編譯到一起)， 很顯然會提高I-cache的命中率，減少沖突。但是一個系統有很多個code path，所以不可能面 面俱到。不同的性能指標，在優化的時候可能是沖突的。所以盡量做對所以case都有效的優化， 雖然做到這一點比較難。
2) Cache line alignment (cache對齊)
推薦指數：☆☆☆☆
數據跨越兩個cache line，就意味著兩次load或者兩次store。如果數據結構是cache line對齊的， 就有可能減少一次讀寫。數據結構的首地址cache line對齊，意味著可能有內存浪費(特別是 數組這樣連續分配的數據結構)，所以需要在空間和時間兩方面權衡。
3) Branch prediction (分支預測)
推薦指數：☆☆☆
代碼在內存里面是順序排列的。對于分支程序來說，如果分支語句之后的代碼有更大的執行幾率， 那么就可以減少跳轉，一般CPU都有指令預取功能，這樣可以提高指令預取命中的幾率。分支預測 用的就是likely/unlikely這樣的宏，一般需要編譯器的支持，這樣做是靜態的分支預測。現在也有 很多CPU支持在CPU內部保存執行過的分支指令的結果(分支指令的cache)，所以靜態的分支預測 就沒有太多的意義。如果分支是有意義的，那么說明任何分支都會執行到，所以在特定情況下，靜態 分支預測的結果并沒有多好，而且likely/unlikely對代碼有很大的侵害(影響可讀性)，所以一般不 推薦使用這個方法。
4) Data prefetch (數據預取)
推薦指數：☆☆☆☆
指令預取是CPU自動完成的，但是數據預取就是一個有技術含量的工作。數據預取的依據是預取的數據 馬上會用到，這個應該符合空間局部性(spatial locality)，但是如何知道預取的數據會被用到，這個 要看上下文的關系。一般來說，數據預取在循環里面用的比較多，因為循環是最符合空間局部性的代碼。
但是數據預取的代碼本身對程序是有侵害的(影響美觀和可讀性)，而且優化效果不一定很明顯(命中 的概率)。數據預取可以填充流水線，避免訪問內存的等待，還是有一定的好處的。
5) Memory coloring (內存著色)
推薦指數：不推薦
內存著色屬于系統層次的優化，在代碼優化階段去考慮內存著色，有點太晚了。所以這個話題可以放到 系統層次優化里面去討論。
6)Register parameters (寄存器參數)
推薦指數：☆☆☆☆
寄存器做為速度最快的內存單元，不好好利用實在是浪費。但是，怎么用?一般來說，函數調用的參數 少于某個數，比如3，參數是通過寄存器傳遞的(這個要看ABI的約定)。所以，寫函數的時候，不要 帶那么多參數。c語言里還有一個register關鍵詞，不過通常都沒什么用處(沒試過，不知道效果，不過 可以反匯編看看具體的指令，估計是和編譯器相關)。嘗試從寄存器里面讀取數據，而不是內存。
7) Lazy computation (延遲計算)
推薦指數：☆☆☆☆☆
延遲計算的意思是最近用不上的變量，就不要去初始化。通常來說，在函數開始就會初始化很多數據，但是 這些數據在函數執行過程中并沒有用到(比如一個分支判斷，就退出了函數)，那么這些動作就是浪費了。
變量初始化是一個好的編程習慣，但是在性能優化的時候，有可能就是一個多余的動作，需要綜合考慮函數 的各個分支，做出決定。
延遲計算也可以是系統層次的優化，比如COW(copy-on-write)就是在fork子進程的時候，并沒有復制父 進程所有的頁表，而是只復制指令部分。當有寫發生的時候，再復制數據部分，這樣可以避免不必要的復制， 提供進程創建的速度。
8） Early computation (提前計算)
推薦指數：☆☆☆☆☆
有些變量，需要計算一次，多次使用的時候。最好是提前計算一下，保存結果，以后再引用，避免每次都 重新計算一次。函數多了，有時就會忽略這個函數都做了些什么，寫程序的人可以不了解，但是優化的時候 不能不了解。能使用常數的地方，盡量使用常數，加減乘除都會消耗CPU的指令，不可不查。#p#
9)Inline or not inline (inline函數)
推薦指數：☆☆☆☆☆
Inline or not inline，這是個問題。Inline可以減少函數調用的開銷(入棧，出棧的操作)，但是inline也 有可能造成大量的重復代碼，使得代碼的體積變大。Inline對debug也有壞處(匯編和語言對不上)。所以 用這個的時候要謹慎。小的函數(小于10行)，可以嘗試用inline;調用次數多的或者很長的函數，盡量不 要用inline。
10) Macro or not macro (宏定義或者宏函數)
推薦指數：☆☆☆☆☆
Macro和inline帶來的好處，壞處是一樣的。但我的感覺是，可以用宏定義，不要用宏函數。用宏寫函數， 會有很多潛在的危險。宏要簡單，精煉，最好是不要用。中看不中用。
11) Allocation on stack (局部變量)
推薦指數：☆☆☆☆☆
如果每次都要在棧上分配一個1K大小的變量，這個代價是不是太大了哪?如果這個變量還需要初始化(因 為值是隨機的)，那是不是更浪費了。全局變量好的一點是不需要反復的重建，銷毀;而局部變量就有這個 壞處。所以避免在棧上使用數組等變量。
12) Multiple conditions (多個條件的判斷語句)
推薦指數：☆☆☆
多個條件判斷時，是一個逐步縮小范圍的過程。條件的先后，決定了前面的判斷是否多余的。根據code path 的情況和條件分支的幾率，調整條件的順序，可以在一定程度上減少code path的開銷。但是這個工作做 起來有點難度，所以通常不推薦使用。
13) Per-cpu data structure (非共享的數據結構)
推薦指數：☆☆☆☆☆
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)
推薦指數：☆☆☆☆☆
32位環境里面用64位counter很顯然會影響性能，所以除非必要，最好別用。有關counter的優化可以多 說幾句。counter是必須的，但是還需要慎重的選擇，避免重復的計數。關鍵路徑上的counter可以使用 per-cpu counter，非關鍵路徑(exception path)就可以省一點內存。
15) Reduce call path or call trace (減少函數調用的層次)
推薦指數：☆☆☆☆
函數越多，有用的事情做的就越少(函數的入棧，出棧等)。所以要減少函數的調用層次。但是不應該 破壞程序的美觀和可讀性。個人認為好程序的首要標準就是美觀和可讀性。不好看的程序讀起來影響心 情。所以需要權衡利弊，不能一個程序就一個函數。
16) Move exception path out (把exception處理放到另一個函數里面)
推薦指數：☆☆☆☆☆
把exception path和critical path放到一起(代碼混合在一起)，就會影響critical path的cache性能。 而很多時候，exception path都是長篇大論，有點喧賓奪主的感覺。如果能把critical path和 exception path完全分離開，這樣對i-cache有很大幫助。
17) Read, write split (讀寫分離)
推薦指數：☆☆☆☆☆
在cache.pdf里面提到了偽共享(false sharing)，就是說兩個無關的變量，一個讀，一個寫，而這 兩個變量在一個cache line里面。那么寫會導致cache line失效(通常是在多核編程里面，兩個變量 在不同的core上引用)。讀寫分離是一個很難運用的技巧，特別是在code很復雜的情況下。需要 不斷地調試，是個力氣活(如果有工具幫助會好一點，比如cache miss時觸發cpu的execption處理 之類的)。
18) Reduce duplicated code(減少冗余代碼)
推薦指數：☆☆☆☆☆
代碼里面的冗余代碼和死代碼(dead code)很多。減少冗余代碼就是減小浪費。但冗余代碼有時 又是必不可少(copy-paste太多，尾大不掉，不好改了)，但是對critical path，花一些功夫還 是必要的。
19) Use compiler optimization options (使用編譯器的優化選項)
推薦指數：☆☆☆☆
使用編譯器選項來優化代碼，這個應該從一開始就進行。寫編譯器的人更懂CPU，所以可以放心 地使用。編譯器優化有不同的目標，有優化空間的，有優化時間的，看需求使用。
20) Know your code path (了解所有的執行路徑，并優化關鍵路徑)
推薦指數：☆☆☆☆☆
代碼的執行路徑和靜態代碼不同，它是一個動態的執行過程，不同的輸入，走過的路徑不同。 我們應該能區分出主要路徑和次要路徑，關注和優化主要路徑。要了解執行路徑的執行流程， 有多少個鎖，多少個原子操作，有多少同步消息，有多少內存拷貝等等。這是性能優化里面 必不可少，也是唯一正確的途徑，優化的過程，也是學習，整理知識的過程，雖然有時很無聊， 但有時也很有趣。
代碼優化有時與編程規則是沖突的，比如直接訪問成員變量，還是通過接口來訪問。編程規則上肯定是說要通過接口來訪問，但直接訪問效率更高。還有就是許多ASSERT之類的代碼，加的多了，也影響性能，但是不加又會給debug帶來麻煩。所以需要權衡。代碼層次的優化是基本功課，但是指望代碼層次的優化來解決所有問題，無疑是緣木求魚。從系統層次和算法層次考慮問題，可能效果會更好。
代碼層次的優化需要相關工具的配合，沒有工具，將會事倍功半。所以在優化之前，先把工具準備好。有關工具的話題，會在另一篇文章里面講。
還有什么，需要好好想想。這些優化技巧都是與c語言相關的。對于其他語言不一定適用。每個語言都有一些與性能相關的編碼規范和約定俗成，遵守就可以了。有很多Effective, Exceptional 系列的書籍，可以看看。
代碼相關的優化，著力點還是在代碼上，多看，多想，就會有收獲。
【編輯推薦】
