5

我有一个int名为 s的矩阵A，当我按列而不是行迭代它时，它的运行速度慢了大约 50 毫秒：

for(int i=0;i<n;i++)  
    for(int j=0;j<n;j++)  
        cout<<A[j][i];    //slower than of A[i][j]

有谁知道为什么会这样？我问了几个人，但他们都不知道为什么。我确信这与地址在计算机内存中的表示方式有关，但我仍然想找到一个更具体的答案。

4

5 回答 5

7

由于缓存内存，逐行遍历矩阵更快。

当您访问A[i][j]时，加载到缓存中的内存不仅仅是一个元素。请注意，矩阵的每一行都存储在连续的内存块中，因此当“周围”的内存 A[i][j]仍在缓存中时，访问同一行中的下一个元素更有可能导致它从缓存而不是主内存中读取（见缓存未命中）。

另请参阅相关问题：
为什么循环的顺序会在迭代 2D 数组时影响性能？
这两个 for 循环中哪一个在时间和缓存性能方面更有效
缓存内存是如何工作的？
矩阵乘法：矩阵大小差异小，时序差异大

于 2013-02-25T08:07:47.537 回答
3

2D 数组作为1D 数组存储在内存中，主要位于（行/列）中。这意味着具有 5 列的数组可能会一个接一个地存储为 5 列，因此根据您的访问方式与此顺序，您的访问可能会被缓存，或者它们中的每一个都可能导致缓存失败，从而导致性能上的巨大差异。

于 2013-02-25T08:07:29.133 回答
3

这是关于缓存行读取机制的。阅读空间局部性。

要验证，请尝试在运行此应用程序时禁用缓存。（我忘记了如何做到这一点，但可以做到。）

于 2013-02-25T08:08:19.887 回答
3

正如其他人所指出的，这是一个缓存问题。每次访问数组元素时，以一种方式使用它可能会导致缓存未命中。

缓存问题实际上是优化的一个非常重要的因素。这就是为什么有时做一个数组结构而不是结构数组更好的原因。比较这两个：

struct StructOfArrays {
  int values[100];
  char names[100][100];
}

struct StructOfArrays values;

struct NormalValStruct {
  int val;
  char name[100];
}

struct NormalValStruct values[100];

如果您遍历其中的值，StructOfArrays它们可能会被加载到缓存中并有效地读取。当您迭代NormalValStruct并获取 value 成员时，您将每隔一次获得一次缓存未命中。

该技巧通常用于高性能应用程序中。这通常是游戏。

于 2013-02-25T08:40:47.097 回答
2

因为第一个循环访问内存是线性的，另一个循环之间有间隙。因此第一个循环对缓存更友好。

于 2013-02-25T08:06:25.470 回答