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 회입니까? 아니면 한 번 실행 한 것입니까? – JGroven
아마도 512는 캐시에 끔찍하게 매치되는 마술 크기이므로 많은 캐시 누락이 발생합니다. 다른 크기는 더 잘 맞아서 더 적은 미스를 얻습니다. – NathanOliver
틀린 길 @NathanOliver - 512는 513보다 많이 느립니다 * –