高速緩存性能

我經歷CSAPP的書，我不知道在高速性能方面以下兩個環路之間的區別：高速緩存性能

這裏緩存有2048字節，直接映射（行號爲1 ），並具有16字節的塊，並且我們定義下面的結構：

struct algae_position { 
    int x; 
    int y; 
}; 
struct algae_position grid[16][16];

代碼1：

for (i = 0; i < 16; i++) { 
    for (j = 0; j < 16; j++) { 
     total_x += grid[i][j].x; 
    } 
} 
for (i = 0; i < 16; i++) { 
    for (j = 0; j < 16; j++) { 
     total_y += grid[i][j].y; 
    } 
}

和代碼2：

for (i = 0; i < 16; i++) { 
    for (j = 0; j < 16; j++) { 
     total_x += grid[i][j].x; 
     total_y += grid[i][j].y; 
    } 
}

我的想法：我們總是有小姐，命中，小姐，命中的模式，因爲一條線只能容納兩個網格元素。所以我們總是有50％的錯過率。

然而，根據這本書，代碼2將有25％的遺漏率，因爲緩存可以容納整個網格陣列。我應該如何理解這個問題？

來源

2015-10-22 Dzung Nguyen

假設4個字節爲int s，因此每個struct algae_position的長度爲8個字節，每個高速緩存行可以包含兩個結構。同樣假設數組在緩存線邊界上對齊（從緩存線的開始處開始）。

在第一代碼，在第一循環中，所有訪問grid[i][j].x甚至j（0，2，4，...）是未命中，與接入下列它（奇數j，1，3，5，。）是命中。 第一個循環的緩存命中率爲50％。但是，由於整個陣列適合緩存，所以第二個循環中的訪問不會錯過，第二個循環的緩存命中率爲100％。因此，第一個代碼具有75％的緩存命中率。

（在實踐中，一些數據最終從高速緩存被驅逐早，至少一些的時間，所以這種代碼有50％和75％之間的真實世界的高速緩存的命中率。）

在第二個代碼中，第一個訪問grid[0][0].x是未命中。但是，這會導致整個緩存行被讀入內存，因此grid[0][0].y,grid[0][1].x和grid[0][1].y都是匹配。下一次訪問再次是未命中，所以這種四次訪問的模式，首次未命中，然後重複三次。因此，第二個代碼具有75％的緩存命中率。緩存大小在這裏不相關。

實際上，第二個代碼更好（對於更大的數組來說明顯更好）。它不僅僅僅依賴於一個緩存行（加上預測，當前的CPU很擅長），而且它還計算在該間隔期間的另外三個值，否則將等待緩存行加載。第一個代碼不僅浪費時間，而且還依賴於CPU不中斷函數，並且保留整個循環中的所有數據。因此，不僅第一代碼「廢棄」高速緩存（依賴大量高速緩存），但它在等待下一個高速緩存行被加載的同時，由於沒有做它可能做的工作而浪費CPU週期。

這些延遲問題是我希望更多程序員關注的問題。

來源

2015-10-22 18:03:44

高速緩存性能

回答

相關問題