C++二维数组的访问效率

Question

我有一个二维数组 a1[10000][100]，有 10000 行和 100 列，还有一个二维数组 a2[100][10000]，它是 a1.

的转置矩阵

现在我需要按 a1[0][20]、a1[0][70]、a1[1][20] 的顺序访问 a1 的 2 列（例如第 21 列和第 71 列）， a1[1][70]、...、a1[9999][20]、a1[9999][70]。或者我也可以访问 a2 来实现相同的目标（顺序：a2[20][0]、a2[70][0]、a2[20][1]、a2[70][1]、...、a2[20][9999], a2[70][9999]).但后者比前者快得多。相关代码简化如下(size1 = 10000):

1  sum1 = 0;
2  for (i = 0; i < size1; ++i) {
3      x = a1[i][20];
4      y = a1[i][70];
5      sum1 = x + y;
6  } // this loop is slower
7  a_sum1[i] = sum1;
8
9  sum2 = 0;
10 for (i = 0; i < size1; ++i) {
11     x = a2[20][i];
12     y = a2[70][i];
14     sum2 = x + y;
15 } // this loop is faster
16 a_sum2[i] = sum2;

访问 a2 的更多行（我也尝试过 3、4 行而不是上面示例中的 2 行）也比访问相同数量的 a1 的列更快。当然我也可以把第3-5行（或第11-14行）换成一个循环（通过使用一个额外的数组来存储要访问的column/row索引），也得到与后者相同的结果比前者快。

为什么后者比前者快很多？我对高速缓存行有所了解，但我不知道这种情况的原因。谢谢。

Answer 1

这是因为 C++ 具有行优先顺序 (https://en.wikipedia.org/wiki/Row-_and_column-major_order). You should avoid column-major access in C/C++ (https://www.appentra.com/knowledge/checks/pwr010/)。

原因是元素按行存储，按行访问可以更好地使用缓存行、矢量化和其他硬件features/techniques。

Answer 2

如果您在短时间内访问同一缓存行中的地址，则可以从内存缓存中受益。下面的解释假定您的数组包含 4 字节整数。

在你的第一个循环中，你在循环中的两次内存访问相隔50*4字节，下一次迭代向前跳转400字节。这里的每个内存访问都是缓存未命中。

在第二个循环中，您仍然有两次相隔 50*400 字节的内存访问，但在下一个循环迭代中，您访问的地址紧邻先前获取的值。假设常见的 64 字节缓存行大小，每 16 次循环迭代只有两次缓存未命中，其余的可以从这样一个循环开始时加载的两个缓存行中提供。

Answer 3

原因是缓存局部性。

a2[20][0], a2[20][1], a2[20][2] ... 在内存中并排存储。而 a1[0][20]、a1[1][20]、a1[2][20] ... 不是（同样适用于 a2[70][0]、a2[70][1]、a2[70][2] ...） .

这意味着访问 a1[0][20]、a1[1][20]、a1[2][20] 会浪费 DRAM 带宽，因为它只会使用从 DRAM 加载的每个 64 字节缓存行中的 4 或 8 个字节.

C++二维数组的访问效率

Access efficiency of C++ 2D array

c++

performance

caching