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

在对不同大小的方阵进行一些实验后，出现了一个模式。总是，转置大小矩阵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上发布了两个版本：

• size 512- 平均的2.46 ms - http://ideone.com/1PV7m http://ideone.com/1PV7m
• size 513- 平均的0.75 ms - http://ideone.com/NShpo http://ideone.com/NShpo

在我的环境（MSVS 2010，全面优化）中，差异类似：

• size 512- 平均的2.19 ms
• size 513- 平均的0.57 ms

为什么会发生这种情况？

解释来自 Agner Fog 在用 C++ 优化软件 http://www.agner.org/optimize/optimizing_cpp.pdf它减少了数据在缓存中的访问和存储方式。

有关条款和详细信息，请参阅关于缓存的 wiki 条目 http://en.wikipedia.org/wiki/L2_cache，我要在这里缩小范围。

缓存的组织方式为sets and lines。一次仅使用一组，可以使用其中包含的任何行。一条线可以镜像的内存乘以线数即可得出缓存大小。

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

set = ( address / lineSize ) % numberOfsets

这种公式理想地给出了集合之间的均匀分布，因为每个内存地址都有可能被读取（我说过ideally).

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

我将尝试遵循阿格纳的例子：

假设每组有 4 行，每行保存 64 字节。我们首先尝试读取地址0x2710，进入集合28。然后我们还尝试读取地址0x2F00, 0x3700, 0x3F00 and 0x4700。所有这些都属于同一组。读之前0x4700，集合中的所有行都将被占用。读取该内存会逐出集合中的现有行，即最初保留的行0x2710。问题在于我们读取的地址是（对于本例）0x800分开。这是关键的一步（同样，对于这个例子）。

临界步幅也可以计算：

criticalStride = numberOfSets * lineSize

变量间隔criticalStride或者多个部分竞争相同的高速缓存线。

这是理论部分。接下来是解释（也是阿格纳，我正在密切关注以避免犯错误）：

假设一个 64x64 的矩阵（记住，效果根据缓存而变化），具有 8kb 缓存，每组 4 行 * 行大小为 64 字节。每行可以容纳矩阵中的 8 个元素（64 位int).

关键步幅为 2048 字节，对应于矩阵的 4 行（在内存中是连续的）。

假设我们正在处理第 28 行。我们尝试获取该行的元素并将它们与第 28 列中的元素交换。该行的前 8 个元素组成一个缓存行，但它们将进入 8 个不同的缓存行。缓存第 28 列中的行。请记住，关键步长是相隔 4 行（一列中的 4 个连续元素）。

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

大小不是关键步幅的倍数会搞乱这个完美的场景对于灾难，由于我们不再处理垂直方向上相隔很远的元素，因此缓存重新加载的次数大大减少。

另一项免责声明- 我刚刚明白了这个解释，希望我能解释清楚，但我可能是错的。无论如何，我正在等待来自的回复（或确认）神秘的 https://stackoverflow.com/users/922184/mysticial. :)