在简单的2D阵列中迭代的同时提高缓存性能

Question

我一直在想办法重写下面的代码，以提高数组中的缓存性能(通过减少缓存中的未命中)。

我知道数组是逐行(按顺序)存储在内存中的，所以ary[0][0]，ary[0][1]，ary[0][2]，。。。。ary[1][0]，ary[1][1]，ary[1][2]。。。ary[50][0]、ary[50][1]。。。ary[50][50]。然而，我不确定如何使用这些信息来帮助我找出如何修改循环以提高缓存性能。

for (c = 0; c < 50; c++)
for (d = 0; d < 50; d++)
ary[d][c] = ary[d][c] + 1;

Answer 1

如果你想一次访问一行的所有单元格，只需反转两个循环：

for (d = 0; d < 50; d++)
for (c = 0; c < 50; c++)
ary[d][c] = ary[d][c] + 1;

甚至

for (d = 0; d < 50; d++)
int[] array = ary[d];
for (c = 0; c < 50; c++)
array[c] = array[c] + 1;

但我怀疑它是否有任何重大影响，甚至根本没有任何影响，尤其是对这么小的阵列。使代码简单易读。不要预先优化。

Answer 2

交换循环顺序。您正在访问arr[0][0]之后的arr[1][0]。arr[1][0]在更远的地方，而arr[0][1]在下一个地址。

Answer 3

您希望最大限度地减少缓存未命中的数量以提高性能。每次缓存未命中都会导致内存访问和向缓存加载新块。这个块不仅包含您需要的值，还包含来自内存的其他相邻值。您需要利用局部性原则，即尽可能多地使用每次内存访问中的值。正如您在观察中提到的，数组是逐行存储在内存中的，因此以顺序方式遍历数组将最大限度地减少缓存未命中的数量。回到您的代码，交换循环顺序：

for (d = 0; d < 50; d++)
for (c = 0; c < 50; c++)
ary[d][c] = ary[d][c] + 1;

或者交换计算中的指数：

for (c = 0; c < 50; c++)
for (d = 0; d < 50; d++)
ary[c][d] = ary[c][d] + 1;

您甚至可以将2D阵列视为50*50大小的1D阵列，只需使用单个for循环即可从头扫描到尾。

Answer 4

除了交换循环之外，您可能不需要做任何事情，因为缓存是为了单独利用代码中引用的局部性而设计的，这意味着它将缓存数组中的第一个元素和后面的几个元素(空间局部性)，并将它们保存在缓存中一段时间(时间局部性)。

然而，有些编译器允许您控制缓存，例如gcc具有__builtin_prefetch，它允许您控制应预取哪些数据以及是否应将其保留在缓存中。

-内置函数：void __builtin_prefetch(const void*addr，rw，locality)

此函数用于在访问数据之前将数据移动到缓存中，从而最大限度地减少缓存未命中延迟。您可以插入对的呼叫__内置_prefetch到您知道内存中可能很快被访问的数据地址的代码中。如果目标支持生成数据预取指令。如果预取在访问之前尽早完成，然后数据将在缓存中当它被访问时。

手册给出了这个例子：

for (i = 0; i < n; i++)
{
a[i] = a[i] + b[i];
__builtin_prefetch (&a[i+j], 1, 1);
__builtin_prefetch (&b[i+j], 0, 1);
/* ... */
}