c++ - 为什么转置 512x512 的矩阵比转置 513x513 的矩阵慢得多？

Question

在对不同大小的方阵进行了一些实验之后，出现了一种模式。总是，转置大小为 2^n 的矩阵比转置大小为 2^n+1 的矩阵要慢。对于 n 的小值，差别不大。

然而，在 512 的值上会出现很大的差异。(至少对我而言)

免责声明:我知道由于元素的双重交换，该函数实际上并没有转置矩阵，但它没有区别。

按照代码:

#define SAMPLES 1000
#define MATSIZE 512

#include <time.h>
#include <iostream>
int mat[MATSIZE][MATSIZE];

void transpose()
{
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
   {
       int aux = mat[i][j];
       mat[i][j] = mat[j][i];
       mat[j][i] = aux;
   }
}

int main()
{
   //initialize matrix
   for ( int i = 0 ; i < MATSIZE ; i++ )
   for ( int j = 0 ; j < MATSIZE ; j++ )
       mat[i][j] = i+j;

   int t = clock();
   for ( int i = 0 ; i < SAMPLES ; i++ )
       transpose();
   int elapsed = clock() - t;

   std::cout << "Average for a matrix of " << MATSIZE << ": " << elapsed / SAMPLES;
}

改变 MATSIZE 让我们改变大小(呃!)。我在ideone上发布了两个版本:

• 大小 512 - 平均 2.46 毫秒 - http://ideone.com/1PV7m
• 大小 513 - 平均 0.75 毫秒 - http://ideone.com/NShpo

在我的环境中(MSVS 2010，全面优化)，区别类似:

• 大小 512 - 平均 2.19 毫秒
• 大小 513 - 平均 0.57 毫秒

为什么会这样？

Answer 1

解释来自 Optimizing software in C++ 中的 Agner Fog它简化了数据在缓存中的访问和存储方式。

有关条款和详细信息，请参阅 wiki entry on caching ，我在这里缩小范围。

缓存被组织在 sets 和 lines 中。一次只使用一组，其中包含的任何行都可以使用。一行可以镜像的内存乘以行数就可以得出缓存大小。

对于一个特定的内存地址，我们可以用公式计算出哪个集合应该镜像它:

set = ( address / lineSize ) % numberOfsets

这种公式理想地给出了跨集合的均匀分布，因为每个内存地址都可能被读取(我说理想情况下)。

很明显，可能会发生重叠。在缓存未命中的情况下，将在缓存中读取内存并替换旧值。请记住，每组都有许多行，其中最近最少使用的行将被新读取的内存覆盖。

我将尝试在某种程度上遵循 Agner 的示例:

假设每组有 4 行，每行包含 64 个字节。我们首先尝试读取地址 0x2710，它位于集合 28 中。然后我们也尝试读取地址0x2F00、0x3700、0x3F00和0x4700。所有这些都属于同一个集合。在读取 0x4700 之前，集合中的所有行都将被占用。读取该内存会驱逐集合中的现有行，即最初保存 0x2710 的行。问题在于我们读取的地址(对于这个例子)0x800 分开。这是关键步幅(同样，在本例中)。

临界步幅也可以计算出来:

criticalStride = numberOfSets * lineSize

criticalStride 或多个分开的变量争夺相同的缓存行。

这是理论部分。接下来是解释(也是阿格纳，我密切关注，以免出错):

假设一个 64x64 的矩阵(请记住，效果因缓存而异)，缓存为 8kb，每组 4 行 * 行大小为 64 字节。每行可以容纳矩阵中的 8 个元素(64 位 int)。

临界步长为 2048 字节，对应于矩阵的 4 行(在内存中是连续的)。

假设我们正在处理第 28 行。我们正在尝试获取该行的元素并将它们与第 28 列中的元素交换。该行的前 8 个元素构成一个缓存行，但它们会消失进入第 28 列中的 8 个不同的缓存行。请记住，临界步长相隔 4 行(一列中的 4 个连续元素)。

当列中的元素达到 16 时(每组 4 个缓存行和相隔 4 行 = 麻烦)，前 0 元素将从缓存中逐出。当我们到达列的末尾时，所有先前的缓存行都将丢失，并且需要在访问下一个元素时重新加载(整行被覆盖)。

如果尺寸不是临界步幅的倍数，会破坏这个完美的场景灾难，因为我们不再处理在垂直方向上临界步幅分开的元素，所以缓存重新加载的次数大大减少。

另一个免责声明 - 我刚刚理解了这个解释，希望我明白了，但我可能弄错了。无论如何，我正在等待来自 Mysticial 的回复(或确认)。 . :)