performance - 为什么使用外部循环比使用内部循环更快地迭代外部维度？

Question

让我们考虑一个矩阵

std::vector<std::vector<int>> matrix;

每行的长度相同。我会调用每个std::vector<int>一列。

为什么使用外部循环迭代外部维度比使用内部循环更快？

第一个程序:首先遍历列

int sum = 0;
for (int col = 0 ; col < matrix.size() ; col++)
{
   for (int row = 0 ; row < matrix[0].size() ; row++)
   {
      sum += matrix[col][row];
   }
}

第二个程序:首先遍历行

int sum = 0;
for (int row = 0 ; row < matrix[0].size() ; row++) // Assuming there is at least one element in matrix
{
   for (int col = 0 ; col < matrix.size() ; col++)
   {
      sum += matrix[col][row];
   }
}

这是我的猜测

在内存中跳跃

我可能有一个模糊的直觉，即在内存中跳来跳去比读取连续的内存需要更多的时间，但我认为 RAM 的内存访问需要恒定的时间。另外，DRAM 中没有移动部件，我不明白为什么读取两个 int 会更快如果它们是连续的？

总线宽度

安int取 2 个字节(尽管它可能因数据模型而异)。在具有 8 字节宽总线的机器中，我可以想象最终如果 int s 在内存中是连续的，那么 4 int s(取决于数据模型)可以在每个时钟周期发送到处理器，而只有一个 int如果它们不连续，可以按时钟周期发送。

如果是这种情况，那么如果 matrix将包含 long long int这是 8 字节长，我们不会再看到这两个程序之间有任何区别(我还没有测试过)。

缓存

我不确定为什么，但我觉得缓存可能是第二个程序变慢的原因。缓存的影响可能与我在上面谈到的总线大小参数有关。有可能只有 DRAM 中连续的内存才能加载到缓存中，但我不知道为什么会这样。

Answer 1

是的，是 cache .

有一个奇怪的巧合¹，当程序访问内存中的数据时，它们经常会立即或稍后访问附近的数据。

CPU 设计者意识到了这一点，因此将缓存设计为一次加载整个内存块。

因此，当您访问 matrix[0][0] 时，matrix[0] 的其余部分(即使不是全部)也会与单个数据一起被拉入缓存matrix[0][0] 中的元素，而很有可能 matrix[20] 中没有任何内容进入缓存。

请注意，这取决于由连续数组组成的矩阵，至少在最后一个维度是这样。如果您使用的是链表，那么您可能² 看不出太大差异，而是无论访问顺序如何都会体验到较慢的性能。

原因是缓存加载了连续的 block 。考虑 matrix[0][0] 是否引用内存地址 0x12340000。访问将加载该字节，加上接下来的 127 个字节到缓存中(确切数量取决于 cpu)。因此，从 0x12340000 到 0x1234007F 的每个字节都在缓存中。

在连续数组中，0x12340004 处的下一个元素已在缓存中。但是链表不是连续的，下一个元素几乎可以在任何地方。如果它在 0x12340000 到 0x1234007F 范围之外，您将一无所获。

---

¹ 仔细想想，这真的不是什么奇怪的巧合。使用本地堆栈变量？访问相同的内存区域。遍历一维数组？对同一内存区域的多次访问。遍历二维数组，外部循环中的外部维度和内部嵌套循环中的内部数组？基本上迭代一堆一维数组。

² 您可能运气好，链表的节点彼此相邻，但这似乎不太可能发生。而且您仍然无法在缓存中容纳那么多元素，因为指向下一个元素的指针会占用空间，而且间接寻址会对性能造成额外的小影响。