2.1.1優化程式性能

性能優化有三個層次：

系統層次

算法層次

代碼層次

系統層次關注系統的控制流程和資料流程，優化主要考慮如何減少消息傳遞的個數；如何使系統的負載更加均衡；如何充分利用硬體的性能和設施；如何減少系統額外開銷（比如上下文切換等）。

算法層次關注算法的選擇（用更高效的算法替換現有算法，而不改變其接口）；現有算法的優化（時間和空間的優化）；并發和鎖的優化（增加任務的并行性，減小鎖的開銷）；資料結構的設計（比如lock-free的資料結構和算法）。

代碼層次關注代碼優化，主要是cache相關的優化（I-cache,D-cache相關的優化）；代碼執行順序的調整；編譯優化選項；語言相關的優化技巧等等。

性能優化需要相關的工具支援，這些工具包括編譯器的支援；CPU的支援；以及內建到代碼裡面的測量工具等等。這些工具主要目的是測量代碼的執行時間以及相關的cache miss, cache hit等資料，這些工具可以幫助開發者定位和分析問題。

性能優化和性能設計不同。性能設計貫穿于設計，編碼，測試的整個環節，是産品生命周期的第一個階段；而性能優化，通常是在現有系統和代碼基礎上所做的改進，屬于産品生命周期的後續幾個階段（假設産品有多個生命周期）。性能優化不是重新設計，性能優化是以現有的産品和代碼為基礎的，而不是推倒重來。性能優化的方法和技巧可以指導性能設計，但兩者的方法和技巧不能等同。兩者關注的對象不同。性能設計是從正向考慮問題：如何設計出高效，高性能的系統；而性能優化是從反向考慮問題：在出現性能問題時，如何定位和優化性能。性能設計考驗的是開發者正向建設的能力，而性能優化考驗的是開發者反向修複的能力。兩者可以互補。

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

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

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

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

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

資料跨越兩個cacheline，就意味着兩次load或者兩次store。如果資料結構是cacheline對齊的，就有可能減少一次讀寫。資料結構的首位址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 datastructure的目的是避免共享變量的鎖，使得每個CPU可以獨立通路資料而與其他CPU無關。壞處是會消耗大量的記憶體，而且并不是所有的變量都可以per-cpu化。并行是多核程式設計追求的目标，而串行化是多核程式設計裡面最大的傷害。有關并行和串行的話題，在系統層次優化裡面還會提到。

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

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顆星

把exceptionpath和critical path放到一起（代碼混合在一起），就會影響critical path的cache性能。而很多時候，exception path都是長篇大論，有點喧賓奪主的感覺。如果能把criticalpath和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顆星

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

19) Use compiler optimization options （使用編譯器的優化選項），推薦指數：4顆星

  使用編譯器選項來優化代碼，這個應該從一開始就進行。寫編譯器的人更懂CPU，是以可以放心地使用。編譯器優化有不同的目标，有優化空間的，有優化時間的，看需求使用。

20) Know your code path （了解所有的執行路徑，并優化關鍵路徑），推薦指數：5顆星

  代碼的執行路徑和靜态代碼不同，它是一個動态的執行過程，不同的輸入，走過的路徑不同。我們應該能區分出主要路徑和次要路徑，關注和優化主要路徑。要了解執行路徑的執行流程，有多少個鎖，多少個原子操作，有多少同步消息，有多少記憶體拷貝等等。這是性能優化裡面必不可少，也是唯一正确的途徑，優化的過程，也是學習，整理知識的過程，雖然有時很無聊，但有時也很有趣。

何時應該優化

如果資料表明，性能确實沒有達到名額，特别是當profiler表明，某處關鍵路徑上的代碼執行占用了大量的時間，那麼就是優化的時候了。

首先，要確定你要優化的代碼是正确的，沒有任何已知bug。因為優化後的代碼往往會變得更複雜而難以修改，是以要趁代碼還比較簡單的時候趕緊把bug都修掉吧。

　　然後，要确認性能名額，可以查specification，或者如果不清楚的話再問問客戶，或者根據其他功能性需求計算得出。用profiler收集目前的性能資料，和性能名額對比，以确定是否需要優化、哪裡需要優化。（資料要保留，因為等優化完後還要用這些資料來做對比，以檢查優化是否有效。）常見的profiler有Rational Quantify、Borland Optimizeit等等。很多UNIX下面都自帶了profiler，比如prof、gprof等，對于一般的使用已經夠了。

　　第三，進行優化。後面“常用的優化方法”一節對此進行了詳細介紹。可以照着列出的常見的優化方法一個個地套用，或者更好的辦法是進行一次團隊頭腦風暴會議，讓大家提出各種可能的優化方案。記得優化時不要删除原來的實作。可以在源檔案中以替代函數或者注釋的方式保留原來的實作。

　　第四，使用profiler，驗證優化是否如所想的那樣有效。如果有效，那是最好；如果無效甚至是幫了倒忙，那麼就趕緊取消改動，使用原來的版本，然後繼續嘗試其他的優化方案。記得優化要一步一步來，從最省事且最有效的方案到最麻煩且收益最小的方案。一旦達成性能名額就收手，不要戀戰。

　　最後，記得對優化過的代碼執行單元測試，看看有沒有為了性能犧牲了正确性。要記得在注釋或者文檔中為優化留下記錄。

常用的優化方法

　　最簡單的優化：請檢查是否使用了編譯器的最新版本，是否把優化編譯開關打開了，是否正确指定了目标處理器（以便使用MMX、SSE、3DNow!等高性能指令集以及讓編譯器自動為處理器所支援的其他進階特性做優化）。如果釋出的産品要支援多種處理器，那麼如果可能的話，請單獨為每種處理器進行編譯，分别釋出，或者使用同一個釋出包但讓安裝程式自動檢測處理器型号并安裝對應的二進制版本，或者把會在關鍵路徑上執行的代碼封裝成動态連結庫，然後讓程式啟動時自動檢測處理器型号并加載為相應型号優化過的動态連結庫版本。

　　還有，要確定使用了高性能的庫，好的算法。比如，同樣是從堆上配置設定記憶體，不同編譯器提供的malloc或者new的實作，性能差異就不小。GCC使用的DL malloc就比較高效，Borland的編譯器提供的實作使用了類似記憶體池的方式來動态管理記憶體，效率也很高，但也有些編譯器對此并沒有做什麼優化，直接進行系統調用。不僅malloc/new如此，STL的allocator也是如此。SGI STL帶的allocator為小于128位元組的記憶體塊的配置設定進行了特别優化（用記憶體池實作），是以小型字元串以及其他會用到allocator此項功能的操作都會性能比較好，但其他STL實作就沒有做這樣的優化。

　　選擇正确的算法，往往比優化地實作算法更重要。因為不同時間複雜度的算法可能會給性能帶來幾個數量級的差異，而實作上的優化則往往付出很大、所得甚少。如果有時候精度不是那麼重要，或者不需要找最佳的結果隻需要找近似最佳的結果，那麼往往可以用低時間複雜度的近似算法來代替。

　　另外，查表法也是個常用的技巧。假設，用某個公式可以把彩色圖像轉換成灰階圖象，那麼如果轉換處理量很大的話，對每個象素都用該公式計算一邊就不劃算了，完全可以事先對所有顔色都計算好，然後處理時查表即可。對三角函數也是如此。當然，為了減小表的尺寸，在精度上往往需要犧牲一些。

　　但也不要以為因為是預先計算的不需要考慮計算代價，或者記憶體比較大虛拟記憶體更大，就可以把表做得很大。記住作業系統或者作業系統進行記憶體換頁或者Cache換頁都是要時間的，兩個臨界點分别是Cache的尺寸和實體記憶體的尺寸。具體是全部計算，還是全部查表，還是部分計算部分查表，表要做得多大，這些都需要嘗試并用實際資料來支援。一個比較複雜的做法是動态地把計算出來的值緩存到稀疏表中并供以後使用時查詢，表的實體尺寸根據當時機器的Cache、記憶體狀況動态配置。

　　如果使用Java或者.NET上的程式設計語言的話，因為垃圾會占用空間，垃圾收集器的執行會占用時間，是以除了優化算法及其實作，還要注意你的代碼對垃圾收集器是否友好。比如有沒有及時把不用的引用置成null，有沒有不必要的finalizer等等。

　　要避免很大的循環體，因為它們往往會超出Cache的尺寸。盡可能避免複雜的if-else或者switch-case語句，因為現代CPU的亂序執行功能看見這些語句會覺得很無奈。即便你非要用這些語句，最好養成習慣，把最可能的分支放在最前面。還有，如果可能的話，不要在循環體中使用這些條件分支語句。

　　有一些經典著作，如ThePractice of Programming（《程式設計實踐》）、Programming Pearls（《程式設計珠玑》）、CodeComplete 2e（國内目前隻出版了第1版，叫《代碼大全》）也都提到了很多優化技術，但是，很重要的一點是，這些書都很少提到或者沒有展開講“構架設計時注意不要留下性能瓶頸或者缺陷”這個問題。這已超出了優化的範疇，而是要求在設計起始階段時就考慮到性能需求。事實上，在硬體性能極大提高、優化編譯器大行其道的今天，我們寫程式時已基本上很少需要去考慮局部的微觀實作是否優化了，因為有95%的可能編譯器會替你去操心，或者根本性能不優化也可滿足需求。甚至如果程式的内部結構比較清晰的化，算法也是可以很容易地替換的（比如用Strategy模式，或者Policy-Based Design的方式）。但也有的東西不太好在程式寫完後再改，但又可能對性能有極大影響：那就是總體的設計和構架，以及一些影響面很廣的設計決策/取舍。在今天，這些比較宏觀的内容遠比微觀的優化技巧要重要。

　　讀者可能要問了：“不是說‘不必要的優化是一切罪惡的源泉’、‘沒有資料證明就不要做優化’嗎？在設計起始階段根本還沒有代碼可以執行，怎麼獲得資料？你怎麼保證這不會是不必要的優化呢？”噢，這個問題很好回答：當設計還沒形成，代碼還沒寫時，這不叫優化，僅僅是設計。優化是一種改變，把現有的緩慢的東西變成快速的東西。而設計時“本來無一物，何來談優化”呢。

　　更何況，一些比較宏觀的構架上的決策，日後重構起來會非常困難，是以一開始就應該要考慮到。如果一開始需求尚未明确并且你也預計不到日後會有這樣的性能需求，那麼沒有考慮到也不能怪你。但若一開始客戶就提出了明确的性能要求，或者你心裡很清楚客戶一定會需要這樣的性能，而你設計時卻依然選擇了無法或者難以滿足這樣性能要求的構架，那麼這就不太好了。此外，如果兩種設計/構架，并沒有明确的實作複雜性或者優雅程度的差别，而其中一種設計/構架明顯性能擴充性更好，那麼也應該選擇後一種。這不叫“premature optimization”，而叫做“避免premature pessimization”（過早悲觀）（見C++ CodingStandards一書的Item 9）。

　　另外，還有一些很常見的和性能相關的話題。而且不少人對它們的認識還有一些誤區，比如資源（特别是記憶體）的擷取和釋放、線程間的同步（也可看作特殊資源——各種線程鎖的擷取和釋放）、字元串（或者其他緩沖區）的處理，以及這些操作的組合。這些話題很值得進一步讨論，在今後的文章中，會再和讀者進行更深層次的交流。

分支優化

局部性優化

循環展開

作者：柒月