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

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 字节宽总线的机器中，我可以想象最终如果 ints 在内存中是连续的，那么 4 ints（取决于数据模型）可以发送到处理器每个时钟周期，如果它们不连续，则每个时钟周期只能发送一个 int。

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

缓存

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

Answer 1

是的，是 cache。

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

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

因此，当您访问 matrix[0][0] 时，matrix[0] 的大部分（如果不是全部）与 matrix[0][0] 处的单个元素一起被拉入缓存，而很有可能matrix[20] 中没有任何内容进入缓存。

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

原因是缓存加载了连续的块。考虑一下 matrix[0][0] 是否指代内存地址 0x12340000。访问将加载该字节，加上接下来的 127 个字节到缓存中（确切数量取决于 cpu）。所以你会有从 0x12340000 到 0x1234007F 的每个字节都在缓存中。

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

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

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

Answer 2

当 Going Column - row 时，你是这样计数的 ([C][R]) [0][0] + [0][1] + [0][2] ... 等等.所以你不是在数组的元素之间切换。

当行-列时，你是这样计数的（[C][R]）[0][0] + [1][0] + [2][0] 这样你就可以在两者之间切换每次都是数组的元素，所以在 DRAM 中需要更长的时间。

二维数组的处理方式如下：new Array{array1, array2, array3};数组内部的数组。倒数数组 (C-R) 比切换数组并计算同一行中的元素 (R-C) 更快。

数组是一块内存，所以当你有二维数组并且你计数（R-C）时，你在 DRAM 中跳来跳去，速度较慢。

DRAM里面没有机械部件不要紧，跳来跳去会比较慢。示例：SRAM 没有机械部件，但比 DRAM 慢（当然尺寸更大），因为需要移动更远的距离以增加额外的晶体管和电容器的尺寸。

edit 阅读其他答案后，我想在您迭代 (C-R) 时将整个元素加载到缓存中以便快速访问。但是当（R-C）每次将一个新的数组元素加载到缓存中时，效率不高或者可能由于效率低下而不会发生。

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

Why is iterating through the outer dimension with an outer loop faster than with an inner loop?

memory

performance

ram

caching