Почему транспонирование матрицы 512x512 происходит намного медленнее, чем транспонирование матрицы 513x513?

После проведения некоторых экспериментов с квадратными матрицами разных размеров возникла закономерность. Как правило, транспонирование матрицы размера 2^nпроисходит медленнее, чем транспонирование матрицы размера2^n+1. При малых значениях nразница невелика.

Однако большие различия возникают при значении 512 (, по крайней мере, для меня )

. Отказ от ответственности :Я знаю, что функция на самом деле не транспонирует матрицу из-за двойной замены элементов, но это не имеет значения.

Соответствует коду:

#define SAMPLES 1000
#define MATSIZE 512

#include 
#include 
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 мс

Почему это происходит?