Aşağıdaki örnek kod, N
boyutunda bir matris oluşturur ve bunu SAMPLES
kez döndürür. N = 512
Transpozisyon işleminin ortalama yürütme süresi 2144 μs
(coliru link) 'dir. İlk bakmak değil mi? ... BuradaBu matris aktarımları neden bu kadar sezgiseldir?
N = 513
→1451 μs
N = 519
→600 μs
N = 530
→486 μs
N = 540
için sonuçlarEh, hiçbir özel yoktur →
492 μs
(en sonunda teori çalışmaya başlar :).
Peki neden pratikte bu basit hesaplamalar teoriden bu kadar farklı? Bu davranış, CPU önbellek tutarlılığı veya önbellek özleri ile ilgilidir? Eğer öyleyse lütfen açıklayınız.
#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)";
}
Snippet'i kaç kez çalıştırdınız? Çalışma süreleri, sisteminizin kaç tane başka şey yapabildiğine bağlı olarak, çalışmaya göre değişebilir. Bunlar yaklaşık 10 veya 20 koşunun ortalama zamanları mı, yoksa sadece tek bir koşunun zamanlamaları mı? – JGroven
Muhtemelen 512, önbelleklere çok uyan sihirli bir boyuttur, böylece çok fazla önbellek kaçırırsınız. Diğer boyutlar daha iyi uyum sağlar, böylece daha az özlüyorsunuz. – NathanOliver
Yanlış yol @NathanOliver - 512, 513'den çok * daha yavaş * –