作者: littleshan (我要加入劍道社!) 看板: C_and_CPP
標題: Re: [問題] 記憶體使用2的倍數效能低落
時間: Thu Aug 25 12:20:54 2011
※ 引述《xxxx9659 (嘎嘎嘎嘎嘎)》之銘言：
: 當我每次位移 2 的次方倍數來存取記憶體時 效能會慢兩倍以上
: 在不同的電腦 不同的 OS 做測試 好像都有這現象
: 難道 2 的倍數很容易 cache miss ?
: 看程式碼比較好解釋 http://codepad.org/W81Vso04
: 我用直覺猜 2 的倍數應該比其他還快 解果剛好相反 整個改觀
: 這樣讓我不知道什麼地方用該用 2 的倍數 什麼地方不要用
: 有人對這種奇特現象有研究嗎＠＠
以下是我在一台 core-i3 的機器上
使用 gcc 4.6 x64 測試的結果：(有開 -O2)
func(2000, 2047); 執行時間: 0.030 sec
func(2000, 2048); 執行時間: 0.040 sec
func(2000, 2049); 執行時間: 0.030 sec
func(2000, 2050); 執行時間: 0.040 sec
--
func(2047, 2000); 執行時間: 0.030 sec
func(2048, 2000); 執行時間: 0.060 sec
func(2049, 2000); 執行時間: 0.030 sec
func(2050, 2000); 執行時間: 0.040 sec
的確當 m=2048 的時候，花了比較久的時間，而且多次測試的結果均如此。
* * *
要解釋這個現象，我目前想到的確是和 cache miss 有關。
cache 運作方式是這樣的 (以下是簡化許多的版本，實際運作更為複雜)：
1. 當 CPU 要取用記憶體時 (假設是某個位址 0xABCDFF00)，首先它去 cache 中尋找，
不過一開始當然 cache 中什麼都沒有，因此會直接從記憶體中讀取。
2. 讀取到真正的資料後，為了加速之後對同一位址的存取速度，
我們會把 0xABCDFF00 中的資料，存到 cache 中，但是要存在哪個位置呢？
我們可不能隨便找一塊空的地方就塞進去，因為尋找 cache 中的資料也需要時間。
所以比較好的做法是根據記憶體的位址，也就是 0xABDFF00，
對應到 cache 中的特定位置，之後要尋找的時候就可以很快地找到資料。
3. 最常見的做法，就是從位址中取出較低的某幾位，以我們的例子來說就是 0xFF00
來當作我們存在 cache 中的位置。至於要取幾位，就視我們的 cache 有多大。
以 64KB 的 cache 來說，取位址的低 16bit 剛剛好可以對應 cache 的大小。
4. 但這會有一個問題，那就是若有兩塊記憶體，位址剛好間隔了 64K，那麼他們的
低 16bit 會剛好相等，也就是對應到同一塊 cache 的空間。如果我們的程式同
時存取這兩塊記憶體，因為這兩塊記憶體會互相爭奪它們在 cache 中的地位，
將造成嚴重的 cache miss 而導致效能低落。
5. 因此我們使用了一種折衷的方法。當我們取出位址的低 16bit，也就是 0xFF00 時，
它對應到 cache 中的位置，並不是只有一塊空間，而是很多塊空間。當我們要在
cache 中儲存資料時，可以在這些空間中選擇一塊使用。這麼一來，就得以解決上述
「兩塊不同位址的記憶體對應到同一個 cache 位置」的問題，只要讓它們對應到
同一個 cache 位置的不同空間即可。
若一個記憶體位址可以對應到 cache 中的 N 塊空間，
我們就稱這個 cache 是 N-way set associative cache。
典型的 2-way set associative cache 的結構是長這樣的：
index way 0 way 1
┌────┬──┬────┬┬──┬────┐
│ 0 │ tag│ data ││ tag│ data │
├────┼──┼────┼┼──┼────┤
│ 1 │ tag│ data ││ tag│ data │
├────┼──┼────┼┼──┼────┤
... ... ... ... ...
其中的 index 就是由記憶體位址所算出來的 cache 編號，
一個編號可以對應到兩塊空間，也就是 way 0 和 way 1。
而 cache 中除了會存記憶體中的資料(data)以外，還會儲存「tag」，
也就是標記這塊資料原本的記憶體位址，
我們才能知道那塊資料是否確定就是我們要的。
回到你的問題。在你的 code 中，最內層的迴圈是這麼寫的：
for(j=0; j<n; ++j){
mA[j*m+i] = mB[i*n+j]; //mA[第j列, 第i行] = mB[第i列, 第j行]
}
當 m 等於 2048 的時候， mA[j*m+i] 這行每次寫入的位址
都和上一次寫入時間隔了 8K byte (假設這時int的大小為4byte)
又假設 CPU 的 L1 cache 大小為 64K
這表示 j=0, 8, 16, ... 的時候，會寫入到同一塊 cache set中，
同樣地 j=1, 9, 17, ...
以及 j=2, 10, 18, ... 這些情況都會各自寫進同一塊 cache set 中。
通常 L1 data cache 為了提高速度，associativity 不會太高 (2-way 到 8-way 之間)
因此上述的情況將導致嚴重的 write miss，
CPU 需要花時間等待 cache 中的資料寫回記憶體中，
才能繼續寫入資料。
結論：算盤本是個好物
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.15.163
推 james732:唸那本書的時候這個章節真的很頭昏...XD 08/25 12:21
推 xxxx9659:喔喔喔 原本cache的概念很模糊 看完這篇清晰許多！！！ 08/25 12:45
→ xxxx9659:所以存取時 位移不要用2的次方 但是malloc可以用2的次方 08/25 12:49
→ littleshan:malloc要看實作的方式 08/25 13:07
