開篇
上一篇博文對緩存的思考——提高命中率詳細介紹了高速緩存的組織結構，并通過執行個體說詳細明了cpu從高速緩存中取資料的過程，對于緩存的工作機制應該有了清晰的認識。這篇博文就來簡單讨論以下對于緩存在實際開發中的應用，這裡将告訴你如何讓你的程式充分利用該緩存，即如何編寫高速緩存友好的代碼。
提示：如果高速緩存的運作機制還沒有清晰的認識，請參照前面文章。
注1：關于文中提到的局部性的相關知識參照：局部性原理淺析——良好代碼的基本素質
注2：這是一個系列的文章，收錄在 程式性能優化
注3：文章知識有些地方不容易了解，是以用心才能看完噢。
“用空間換時間”
在搞算法的時候經常能聽到這種說法，算法研究中通常要考慮算法的時間、空間複雜度。而這裡“用空間換時間”說的是通過犧牲一些存儲塊代碼更有效的利用緩存。進而提高程式的運作效率。可見，高效的代碼不僅依賴于良好的算法，編寫緩存有好代碼也很重要。
我們将通過下面的例子來認識這一過程
注：這裡假設高速緩存是直接映射的，即每一組隻有一行。
通過”局部性“相關的知識，我們可以看出上面的代碼有良好的空間局部性：一維向量 x[ ] 、y[ ] 都是對其元素進行步長為1的順序通路。那麼，擁有良好局部性的代碼，是否就能有效的利用高速緩存呢。不一定。
設上面代碼運作在擁有直接映射緩存的計算機上。
為了把問題描述清楚，這裡有一些假設
1、float 是4 byte，是以數組x[ ]占用空間為32byte，y[ ]也一樣
2、x[ ]存儲在記憶體中位址0-31的位置，y[ ]緊随其後在位址開始為32的連續位置。（如果覺得牽強你可了解為虛拟位址）
3、直接映射高速緩存有兩個組，每組的大小為16byte。也就是高速緩存中每組可存儲4個元素。
根據這些假設，每個x[i]、y[i]會被映射到相同的高速緩存組
元素和緩存之間的映射關系如下圖所示
圖被中間的雙線條分為左右兩欄，左邊是x[ ]的情況，右邊y[ ]的情況。
看左邊的一欄，左邊的一列代表的x 中的元素，中間的是元素在記憶體中的位址，第三列是該元素映射在緩存中的組号。
為什麼會是這樣配置設定的呢，其實在上一篇博文中就有提到。（參看前面的部落格會有更好的效果）
這裡還是簡單的說一下：
主存中的資料是根據位址被映射到緩存的不同位置的，二進制位址的不同位代表不同的資訊，一般來說從左到右分别代表：行、組、偏移。
緩存的每一行是16byte，進而可推斷緩存的位址位是4 。因為4個二進制的組合共有16種情況（也即2的4次方是16）。
下表是它們位址各個位及代表的資訊。
X[ ]:
注：這裡的位址不是元素的真實位址，指的是塊位址。x有八個元素，每個元素占四個byte，我們把這四個byte當作一個整體， 那麼x[0]就是第一塊，x[1]為第二塊，以此類推。y的情況相同。
上圖中，陰影部分的為位址的二進制表示形式。每個位址被表示成了四位的二進制數。
其中：
左邊一位标記行。因為是直接映射，每組隻有一行，是以一位就能表示。
左邊第二位标記組。我們讨論的這個緩存隻有兩個組，一位就能标記。
右邊兩表示偏移。每行中有四個資料塊，是以兩位能辨別。
可以看出，x[ ]的前四個元素屬于同一組，後四個為另一組。
下面是y[]的情況：
現在對于剛才那個圖（如下）應該有更清楚的認識了把。
x[i]和y[i]有相同的組标記、不同的行标記，這就意味着x[i]和y[i]不能同時存在于緩存中。
下面模拟一下上述代碼的執行過程。我們假設局部變量sum存于cpu寄存器中。
計算x[0]*y[0]
取x[0]
剛開始的時候緩存還沒預熱，每一行的标記為都為不可用。是以取x[0]的時候緩存不命中，緩存從下一級存儲中取出包括x[0]的整行，放入緩存第0組中，并傳回x[0]給cpu。這時緩存第一組中的元素有x[0]、x[1]、x[2]、x[3]
此時緩存的情況如下圖所示
緩存中的元素為藍色背景的部分
組序号為1的行都還沒初始化。
取y[0]
y[0]對應的塊位址是8，即1 0 00 組标記是0，行标記1，不命中。于是取出包括y[0]的行，并放入緩存中。此時的緩存情況：
取x[1]，緩存不命中，當取了x[0]本有x[1]在緩存中，當取y[0]的時候，這一行被覆寫了。是以隻能把包括x[1]行的行取出放入緩存（覆寫y行），并傳回x[1]。取了x[1]後的緩存情況和取出x[0]的情況一樣：
當取y[1]的時候，緩存不命中，又把上面x行替換為y行。
可以推理出，取出x和y 的元素總是不命中。
空間換時間
因為x[i]、y[i]映射到了相同的組，現在的這種情況稱為沖突不命中，每次對x和y 的引用都會造成沖突不命中。這一情況用“抖動”來描述。
簡單的說，即使程式有良好的時間局部性，且緩存也有足夠大小的空間來緩存，也會發生抖動。因為x[i]、y[i]被映射到了相同的緩存組。
幸運的是，可以修正這種情況，讓x[i],y[i]映射到不同的緩存組。
一個簡單的方法就是增加x的長度。給x配置設定12個float大小的空間。這樣y的其實位址就是18而不是32
如下圖所示：
這樣當引用x[0]的時候把x[0]、x[1]、x[2]、x[3]放入組0中，引用y[0]的時候把y[0],y[1],y[2],y[3]放入組1 中。
于是對引用x[1]~x[3]的引用就就能直接從緩存中擷取，同樣對y[1]~y[3]的引用也能從緩存中擷取
相比于剛開始的情況，大大增加了緩存的使利用。同時也提高了程式的性能，特别是當資料量很大的時候。
實質通過在x的後面追加元素，讓y的其實位址後移，讓y對應的組号發生改變。當然在x後面追加元素隻是占用了一部分空間，那些空間并沒有被利用，但是提高了程式的性能。
是以才說“用空間換時間”
為什麼用中間位作為組索引?
用中間位作為組索引是有原因的。
如果用最高位做索引
情況如上圖中的中間所示，連續的塊都别映射到了同一個組中（特别的，如果是直接映射高速緩存，連續的塊被映射到同一行中）這樣的确也能利用緩 存，如上圖所示，當引用第一個元素的時候，會把第1、2、3、4個拷貝到緩存的組0中，以後對2、3、4的引用就能直接在緩存中提取。引用第5個元素的時 候，把第5、6、7、8個拷貝到緩存的組1中，同樣的，對4、5、6的引用能直接在緩存中提取。後面的情況類似就不再叙述。
通過上面的叙述，你可能已經發現一個問題：當對緩存的組1進行操作的時候，緩存中的其它組是沒有被利用的，這和緩存中隻有一個組其實效果是一樣的。對緩存中的其他組沒有很好的利用，也就是說，雖然也有緩存的利用，但有最大化。
改用中間位做索引，如上圖中的右圖所示，同一組中的塊不再是連續的，這樣可以保證緩存中的所有組都能被有效的利用。
引用第1個元素的時候，将把第1、5、9、13放入緩存組1中
引用第2個元素的時候， 把第2、6、10、14放入緩存
引用第3個，把3、7、11、15放入緩存
引用第4個，把4、8、12、16放入緩存
這樣對前四個元素的引用都不會命中，而而對後面的引用都能命中。這種過程也就是所謂的緩存預熱。
高速緩存友好代碼
一維數組
上面的讨論我們假設了一種特殊的情況，下面将對如何編寫高速緩存友好代碼做更加泛化的讨論
先看下面的代碼
很容易看出，上面的代碼有良好的局部性。編譯器對代碼優化的時候 ，通常會将局部變量用寄存器儲存（因為他們在函數結束時就會被釋放）。一般來說，如果一個高速緩存塊大小為Bbyte，那麼在一個步長為k的引中，平均每 次疊代會有min (1; (wordsize k)=B )次緩存不命中。k=1時取最小值。
Example
假設v是塊對齊的，字為4個位元組，高速緩存塊為4個字，高速緩存初始化為空。那麼對v的步長為1 的引用情況如下所示
圖中的m，表示miss，即不命中；h表示hit 表示命中。
這個例子中，對v[0]的引用不命中，而接下來對v[2]~v[4]的引用命中，
對v[5]不命中，接下來對v[6]~v[7]引用命中。
上面的叙述說明了兩個問題:
1、對局部變量的反複引用是好的，因為他們存在寄存器中，通路數度很快
2、對步長為1的引用是好的，因為存儲器結構中将資料存放為連續的塊
多元數組
在對多元數組的操作中，空間局部性尤為重要。
考慮下面的例子
c語言以行序為主序的，是以上述代碼剛好是對數組a[][]的步長為1的引用，和上一種情況一樣，假設剛開始的緩存是冷緩存（剛開始的時候緩存裡沒有任何資料）。那麼對數組a[][]的通路将得到如下圖所示的命中和不命中模式：
對緩存有良好的使用。
然而，對代碼做一個微小的改動之後：
這時以步長4對數組a[][]的元素進行引用，這種情況對數組将是一列一列引用而不是一行一行引用的。他們在緩存中的命中情況如下所示
較高的不命中率對程式的運作效率有顯著影響，因為從第一層存儲中取出資料将花費比緩存中取資料多很多的時鐘周期。
小結
好的程式代碼不僅要有好的算法，對計算機硬體的充分利用也是很關鍵的一步， 前面幾篇文章主要隻是從緩存角度做了分析。
在緩存角度，要提高程式運作效率，編寫緩存友好代碼尤為關鍵，這也是區分程式員層次的一個标準，要求較高，需要你掌握緩存的工作原理，緩存内部的組 織形式，還需要編譯相關的知識，前面還有很多知識等值我們去學習，這裡隻是總結了自己的學習成果，分享給大家，希望對各位園友有用。
我覺得寫部落格不是我的目的，部落格隻是我學習過程中的副産品而已，對于某些知識，你知道它是一回事，要把它講出來卻非得把它弄透徹不可，我把寫部落格當作學習的一部分，在總結的過程中提高，還能把成果分享，我想這就是部落格最大的價值把，我們都應該享受寫部落格的這個過程。
預：下一篇博文中會從緩存角度對《程式設計之美》中的一道題目做個讨論，裡面的算法很巧妙，表面上看性能是提高了，從緩存角度卻不然。
全文完。