12
次のコード例は、サイズがNの行列を生成し、SAMPLES回転置します。 N = 512の場合、転置操作の平均実行時間は2144 μs（coliru link）です。 一見何も特別なことは正しい、ありません？...なぜこれらのマトリックス転移時間は逆らって直感的ですか？
まあ、ここ
N = 513→1451 μsN = 519の結果である→600 μsN = 530→486 μsN = 540→492 μs（最終的に理論は働き始めます:)。
なぜ実際にこれらの単純な計算が理論と異なっているのですか？この動作は、CPUキャッシュの一貫性またはキャッシュミスに関連していますか？もしそうなら、説明してください。
#include <algorithm>
#include <iostream>
#include <chrono>
constexpr int N = 512; // Why is 512 specifically slower (as of 2016)
constexpr int SAMPLES = 1000;
using us = std::chrono::microseconds;
int A[N][N];
void transpose()
{
for (int i = 0 ; i < N ; i++)
for (int j = 0 ; j < i ; j++)
std::swap(A[i][j], A[j][i]);
}
int main()
{
// initialize matrix
for (int i = 0 ; i < N ; i++)
for (int j = 0 ; j < N ; j++)
A[i][j] = i+j;
auto t1 = std::chrono::system_clock::now();
for (int i = 0 ; i < SAMPLES ; i++)
transpose();
auto t2 = std::chrono::system_clock::now();
std::cout << "Average for size " << N << ": " << std::chrono::duration_cast<us>(t2 - t1).count()/SAMPLES << " (us)";
}
スニペットを何回実行しましたか？ランタイムは、実行中にシステムによって何が行われているかによって大きく異なることがあります。これらの平均時間は約10回または20回、または1回の実行からのタイミングだけですか？ – JGroven
おそらく512はキャッシュにぴったり合っているので、キャッシュミスが多く発生する魔法のサイズです。他のサイズはフィットしているので、ミスが少なくなります。 – NathanOliver
間違った方法@NathanOliver - 512は513よりもずっと遅い* –