在前兩篇文章里，我們討論了程序性能的兩個方面，一是算法（廣義的算法，即解決問題的方法），二是編譯器。通過這兩個方面，我想表達的意思是，一段程序的執(zhí)行效率，是很難從表面現(xiàn)象得出結(jié)論的，至少從一些簡單的層面，如代碼的長度是幾乎難以說明任何問題——因此一定要進行Profiling才能做到有效的優(yōu)化。而現(xiàn)在，我們假設(shè)兩段程序算法基本相同，編譯器也只是進行簡單的“翻譯”，那么……我們能從“表面”看出性能高下嗎？

　　那么就從一個最簡單的例子看起吧。假設(shè)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();

　　這兩段邏輯的算法基本上完全相同，如果編譯器只是進行直接“翻譯”而不進行優(yōu)化，那么第一種做法對于i的累加和條件跳轉(zhuǎn)比較少，因此您可能會得出結(jié)論：“很明顯”第一段代碼的執(zhí)行效率比較高。只可惜事實并非那么簡單，因為影響程序性能的另一個關(guān)鍵因素是：緩存。

　　“緩存”無處不在。在CPU中，性能最快的存儲設(shè)備當屬“寄存器”，不過眾所周知寄存器的數(shù)量是極其有限的。因此，CPU都會有L1 Cache和L2 Cache的多級緩存機制。其中，L2 Cache的性能比L1 Cache和寄存器都要慢，但還是比內(nèi)存要快許多。當某個Core需要從內(nèi)存中獲取數(shù)據(jù)的時候，便會從L1 Cache獲取數(shù)據(jù)，如果L1 Cache沒有那么就會從多個核共用的L2 Cache拿，再沒有便會從內(nèi)存拿——由于操作系統(tǒng)的虛擬內(nèi)存機制，可能還要從磁盤的交換頁中獲取數(shù)據(jù)，此時性能自然相當差了。

　　雖然寄存器只使用一個字長（如4字節(jié)）的數(shù)據(jù)，但是L1 Cache從L2 Cache拿數(shù)據(jù)時總是“一塊一塊”拿的——這么一塊往往就是連續(xù)的64個字節(jié)。換句話說，在CPU讀取的一個地址的數(shù)據(jù)之后，讀取其他一些地址上的數(shù)據(jù)便會比另一些特別快，因為它們都已經(jīng)在L1 Cache中了。如果一個程序能夠利用起CPU的這個特性，那它的性能往往便可以更好一些（自然還有很多其他影響性能的因素）。

　　局部性（Locality），便是用來描述程序是否能利用好緩存的名詞。我們說一個程序的局部性比較好，那么就表示它能夠較好地利用起CPU的緩存機制。局部性分“空間局部性”和“時間局部性”兩方面，前者是指“加載一個地址的數(shù)據(jù)之后，繼續(xù)加載它附近的數(shù)據(jù)”，后者表示“在加載一個地址的數(shù)據(jù)之后，短時間內(nèi)重新加載這塊數(shù)據(jù)”。無論是哪一方面，目的都是希望從較快的緩存中加載“熱”的數(shù)據(jù)。為什么冷啟動總是很慢？為什么有人說系統(tǒng)從開機后會越跑越快？其實道理都差不多。

　　那么現(xiàn)在，您還能判斷上面兩種做法的效率孰高孰低？雖然第一種做法減少了i的累加次數(shù)和條件跳轉(zhuǎn)的次數(shù)，但是它在一次循環(huán)中做了兩件事情，可能在執(zhí)行DoSomethingB方法的時候，DoSomethingA方法中剛剛進入緩存的數(shù)據(jù)便冷卻了，于是在下次執(zhí)行DoSomethingA時又要重新從較慢的存儲設(shè)備中加載數(shù)據(jù)。而在第二種做法中，我們“密集”地執(zhí)行完100次DoSomethingA或DoSomethingB的調(diào)用，而此間大量的數(shù)據(jù)訪問都是集中在L1 Cache上，性能優(yōu)勢不言而喻。

　　我以前的文章《計算機體系結(jié)構(gòu)與程序性能》在第一部分里也討論了局部性對程序性能的影響，講的更為具體一些，您也可以參考其中的內(nèi)容。

　　由于程序指令不是執(zhí)行效率的唯一因素，因此從代碼長短上判斷程序性能也是非常不靠譜的事情。當然，從任何獨立的角度來判斷性能可能都不合適。例如在那篇文章里提到，出于程序性能的考慮應(yīng)該使用全局變量——當然作者也認為這不是好的設(shè)計，事實上在我們剛才的例子中，在一個循環(huán)中做多件事情可能也值得重構(gòu)。如果您使用全局變量，它的確省下了push，pop等指令的開銷，但是這么一個全局變量——例如是一個靜態(tài)變量，它存儲在堆的某一個地方，訪問它并非是一個局部性方面的優(yōu)秀實踐。與之相反，由于L1 Cache的作用，在調(diào)用棧上訪問“參數(shù)”或“局部變量”并不會比訪問寄存器慢多少，此時push，pop幾個指令的開銷可能就不算什么了。更何況，如果編譯器/運行時內(nèi)聯(lián)了這個方法，這樣連push，pop等指令也不會出現(xiàn)了。

　　記得前一段時間在有某些朋友在我的博客上發(fā)布一些較為“激進”的說法，例如“學底層只是對寫.NET程序沒有幫助，因為就算你知道了這些，C#也沒有辦法內(nèi)嵌匯編”。我不同意這個說法，因為即便是.NET程序，它也是在符合計算機體系結(jié)構(gòu)的規(guī)律下運行的，我們完全可以在一定程度上了解一段代碼在執(zhí)行時的表現(xiàn)。

　　就拿目前談到的“局部性”來說，我們便可以把握很多東西。比如，我們知道每個線程的調(diào)用棧在默認情況下是1兆大小，因此兩個線程調(diào)用棧上的數(shù)據(jù)幾乎不可能出現(xiàn)在同一個Cache條目中。再比如，由于“時間局部性”，最近使用的數(shù)據(jù)最有可能出現(xiàn)在緩存中，因此在.NET 4.0的并行庫在調(diào)度“私有隊列”的任務(wù)時會傾向于執(zhí)行最新創(chuàng)建的任務(wù)。再比如，您是使用兩個int數(shù)組來表示一系列坐標的x值和y值，還是構(gòu)造一個struct Point數(shù)組來保存它們呢？雖然使用兩個int數(shù)組更節(jié)省內(nèi)存，但是從局部性考慮問題的話，您會發(fā)現(xiàn)同一個坐標的x值和y值存放在一起可能更為合適。

　　我的這幾篇文章，其實也都在強調(diào)從代碼表面判斷程序性能的“不確定性”。同樣道理，即便是把它們的匯編代碼（片斷）放在您面前，您也可能很難“看出”性能區(qū)別。這也從側(cè)面說明了Profiling的重要性：閱讀代碼是靜態(tài)的，而程序執(zhí)行和Profiling都是動態(tài)的。之前有朋友對我說“你最近迷上Profiler啦？”其實我這里的Profiling泛指“一種探索程序性能的方式”，并不是指某個特定的手段，更不是某個具體的工具——不過無論是使用VS的Profiler也好，還是自己搞一個CodeTimer，都比“讀代碼”來的可靠。

it知識庫：淺談代碼的執(zhí)行效率（3）：緩存與局部性，轉(zhuǎn)載需保留來源！

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯(lián)系我們修改或刪除，多謝。