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

Question

我有一个 2D 数组

a1[10000][100]

，有 10000 行和 100 列，还有一个 2D 数组

a2[100][10000]

，它是

a1

的转置矩阵。

现在我需要按

a1

、

a1[0][20]

、

a1[0][70]

、

a1[1][20]

、...、

a1[1][70]

的顺序访问

a1[9999][20]

的2列（例如第21列和第71列），

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行）（通过使用额外的数组来存储要访问的列/行索引），它也得到相同的结果，后者比后者更快前者。

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

Answer 1

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

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

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

Answer 2

这是因为 C++ 有行优先顺序 (https://en.wikipedia.org/wiki/Row-_and_column-major_order)。您应该避免在 C/C++ 中进行列主访问 (https://www.appentra.com/knowledge/checks/pwr010/)。

原因是元素按行存储，按行访问可以更好地利用缓存行、矢量化和其他硬件功能/技术。

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 字节。