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