为什么转置一个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;
}

null

null

Answer 1

这一解释来源于Agner Fog在C++中优化软件的过程，并归结为数据是如何被访问和存储在缓存中的。

有关术语和详细信息，请参阅wiki中关于缓存的条目，我将在这里对其进行缩小。

缓存是按集合和行组织的。每次只使用一个集合，其中包含的任何行都可以使用。一行可以镜像的内存乘以行数给出了高速缓存的大小。

set = ( address / lineSize ) % numberOfsets

criticalStride = numberOfSets * lineSize

这是理论部分。接下来的解释（也是Agner，我在紧跟它以免出错）：

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

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