什么是“缓存友好”代码？

Question

什么是“缓存友好”代码？“缓存不友好代码“和”缓存友好“密码？如何确保编写高效缓存代码？

Answer 1

除了@marc Claesen的答案之外，我认为缓存不友好代码的一个具有指导意义的典型示例是按列而不是逐行扫描C二维数组(例如位图图像)的代码。

行中相邻的元素在内存中也是相邻的，因此按顺序访问它们意味着按升序访问它们；这是对缓存友好的，因为缓存倾向于预取连续的内存块。

相反，按列访问这些元素是缓存不友好的，因为同一列上的元素在内存中彼此之间的距离很远(特别是，它们的距离等于行的大小)，所以当您使用这种访问模式时，您正在内存中跳转，这可能会浪费缓存在内存中检索元素的努力。

破坏演出的唯一方法就是

// Cache-friendly version - processes pixels which are adjacent in memoryfor(unsigned int y=0; y<height; ++y){
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }}

到

// Cache-unfriendly version - jumps around in memory for no good reasonfor(unsigned int x=0; x<width; ++x){
    for(unsigned int y=0; y<height; ++y)
    {
        ... image[y][x] ...
    }}

在具有小缓存和/或与大数组(例如当前机器上的10多万像素24 BPP图像)工作的系统中，这一效果可能相当显著(几个数量级的速度)；因此，如果您必须做许多垂直扫描，通常最好先旋转90度的图像，然后执行各种分析，从而限制缓存-不友好的代码仅限于旋转。