在前兩篇文章裡，我們討論了程序性能的兩個方面，一是算法（廣義的算法，即解決問題的方法），二是編譯器。通過這兩個方面，我想表達的意思是，一段程序的執行效率，是很難從表面現象得出結論的，至少從一些簡單的層面，如代碼的長度是幾乎難以說明任何問題——因此一定要進行Profiling才能做到有效的優化。而現在，我們假設兩段程序算法基本相同，編譯器也只是進行簡單的“翻譯”，那麼……我們能從“表面”看出性能高下嗎？
那麼就從一個最簡單的例子看起吧。假設DoSomethingA和DoSomethingB裡做的事情是固定的，那麼您認為下面兩種寫法的哪個性能更好？
for (int i = 0; i < 100; i++)
{
DoSomethingA();
DoSomethingB();
}
for (int i = 0; i < 100; i++)
DoSomethingA();
for (int i = 0; i < 100; i++)
DoSomethingB();
這兩段邏輯的算法基本上完全相同，如果編譯器只是進行直接“翻譯”而不進行優化，那麼第一種做法對於i的累加和條件跳轉比較少，因此您可能會得出結論：“很明顯”第一段代碼的執行效率比較高。只可惜事實並非那麼簡單，因為影響程序性能的另一個關鍵因素是：緩存。
“緩存”無處不在。在CPU中，性能最快的存儲設備當屬“寄存器”，不過眾所周知寄存器的數量是極其有限的。因此，CPU都會有L1 Cache和L2 Cache的多級緩存機制。其中，L2 Cache的性能比L1 Cache和寄存器都要慢，但還是比內存要快許多。當某個Core需要從內存中獲取數據的時候，便會從L1 Cache獲取數據，如果L1 Cache沒有那麼就會從多個核共用的L2 Cache拿，再沒有便會從內存拿——由於操作系統的虛擬內存機制，可能還要從磁盤的交換頁中獲取數據，此時性能自然相當差了。
雖然寄存器只使用一個字長（如4字節）的數據，但是L1 Cache從L2 Cache拿數據時總是“一塊一塊”拿的——這麼一塊往往就是連續的64個字節。換句話說，在CPU讀取的一個地址的數據之後，讀取其他一些地址上的數據便會比另一些特別快，因為它們都已經在L1 Cache中了。如果一個程序能夠利用起CPU的這個特性，那它的性能往往便可以更好一些（自然還有很多其他影響性能的因素）。
局部性（Locality），便是用來描述程序是否能利用好緩存的名詞。我們說一個程序的局部性比較好，那麼就表示它能夠較好地利用起CPU的緩存機制。局部性分“空間局部性”和“時間局部性”兩方面，前者是指“加載一個地址的數據之後，繼續加載它附近的數據”，後者表示“在加載一個地址的數據之後，短時間內重新加載這塊數據”。無論是哪一方面，目的都是希望從較快的緩存中加載“熱”的數據。為什麼冷啟動總是很慢？為什麼有人說系統從開機後會越跑越快？其實道理都差不多。
那麼現在，您還能判斷上面兩種做法的效率孰高孰低？雖然第一種做法減少了i的累加次數和條件跳轉的次數，但是它在一次循環中做了兩件事情，可能在執行DoSomethingB方法的時候，DoSomethingA方法中剛剛進入緩存的數據便冷卻了，於是在下次執行DoSomethingA時又要重新從較慢的存儲設備中加載數據。而在第二種做法中，我們“密集”地執行完100次DoSomethingA或DoSomethingB的調用，而此間大量的數據訪問都是集中在L1 Cache上，性能優勢不言而喻。
我以前的文章《計算機體系結構與程序性能》在第一部分裡也討論了局部性對程序性能的影響，講的更為具體一些，您也可以參考其中的內容。
由於程序指令不是執行效率的唯一因素，因此從代碼長短上判斷程序性能也是非常不靠譜的事情。當然，從任何獨立的角度來判斷性能可能都不合適。例如在那篇文章裡提到，出於程序性能的考慮應該使用全局變量——當然作者也認為這不是好的設計，事實上在我們剛才的例子中，在一個循環中做多件事情可能也值得重構。如果您使用全局變量，它的確省下了push，pop等指令的開銷，但是這麼一個全局變量——例如是一個靜態變量，它存儲在堆的某一個地方，訪問它並非是一個局部性方面的優秀實踐。與之相反，由於L1 Cache的作用，在調用棧上訪問“參數”或“局部變量”並不會比訪問寄存器慢多少，此時push，pop幾個指令的開銷可能就不算什麼了。更何況，如果編譯器/運行時內聯了這個方法，這樣連push，pop等指令也不會出現了。
記得前一段時間在有某些朋友在我的博客上發布一些較為“激進”的說法，例如“學底層只是對寫.NET程序沒有幫助，因為就算你知道了這些，C#也沒有辦法內嵌匯編”。我不同意這個說法，因為即便是.NET程序，它也是在符合計算機體系結構的規律下運行的，我們完全可以在一定程度上了解一段代碼在執行時的表現。
就拿目前談到的“局部性”來說，我們便可以把握很多東西。比如，我們知道每個線程的調用棧在默認情況下是1兆大小，因此兩個線程調用棧上的數據幾乎不可能出現在同一個Cache條目中。再比如，由於“時間局部性”，最近使用的數據最有可能出現在緩存中，因此在.NET 4.0的並行庫在調度“私有隊列”的任務時會傾向於執行最新創建的任務。再比如，您是使用兩個int數組來表示一系列坐標的x值和y值，還是構造一個 struct Point數組來保存它們呢？雖然使用兩個int數組更節省內存，但是從局部性考慮問題的話，您會發現同一個坐標的x值和y值存放在一起可能更為合適。
我的這幾篇文章，其實也都在強調從代碼表面判斷程序性能的“不確定性”。同樣道理，即便是把它們的匯編代碼（片斷）放在您面前，您也可能很難“看出”性能區別。這也從側面說明了Profiling的重要性：閱讀代碼是靜態的，而程序執行和Profiling都是動態的。之前有朋友對我說“你最近迷上Profiler啦？”其實我這裡的Profiling泛指“一種探索程序性能的方式”，並不是指某個特定的手段，更不是某個具體的工具——不過無論是使用VS的Profiler也好，還是自己搞一個CodeTimer，都比“讀代碼”來的可靠。
原文：http://www.cnblogs.com/JeffreyZhao/archive/2010/01/12/talk-about-code-performance-3-locality.html
