高速缓存性能

我经历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

高速缓存性能

回答

相关问题