4

我一直在想一种方法来重写下面的代码以提高数组中的缓存性能（通过减少缓存中的未命中）。

我知道数组逐行（按顺序）存储在内存中，所以 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;
4

4 回答 4

4

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

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;

但我怀疑它会产生任何重大影响，甚至根本不会产生任何影响，尤其是在如此小的阵列上。使您的代码简单易读。不要预先优化。

于 2012-11-27T21:35:05.693 回答
3

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

于 2012-11-27T21:36:38.047 回答
1

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

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 循环从头到尾扫描它。

于 2012-11-27T21:45:10.167 回答
0

除了交换循环之外，您可能不需要做任何事情，因为缓存旨在自行利用代码中的引用局部性，这意味着它将缓存第一个元素以及随后的几个元素（空间局部性）从数组中提取并将它们保留在缓存中一段时间​​（时间局部性）。

然而，一些编译器允许你控制缓存，例如 gcc 有 __builtin_prefetch 可以让你控制哪些数据应该被预取以及是否应该留在缓存中。

— 内置函数：void __builtin_prefetch (const void *addr, rw, locality)

此功能用于通过在访问数据之前将数据移动到缓存中来最小化缓存未命中延迟。您可以将对 __builtin_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);
  /* ... */
}
于 2012-11-27T21:57:08.370 回答