12
Poniższy przykład kodu generuje macierz o rozmiarze N i przenosi ją SAMPLES liczbę razy. Kiedy N = 512 średni czas wykonania operacji transpozycji to 2144 μs (coliru link). Na pierwszy rzut oka nie ma nic specjalnego, prawda? ...Dlaczego te czasy transpozycji macierzy są tak intuicyjne?
Cóż, tutaj znajdują się wyniki dla
N = 513→1451 μsN = 519→600 μsN = 530→486 μsN = 540→492 μs(wreszcie! Teoria zacznie działać :).
Dlaczego więc w praktyce te proste obliczenia różnią się od teorii? Czy to zachowanie wiąże się ze spójnością pamięci podręcznej procesora lub brakami w pamięci podręcznej? Jeśli tak, proszę wyjaśnij.
#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)";
}
Ile razy uruchomiłeś ten fragment? Środowiska wykonawcze mogą znacznie różnić się w zależności od uruchomienia, w zależności od tego, ile innych rzeczy może wykonać twój system. Czy są to przeciętne czasy około 10 lub 20 przebiegów, czy tylko czasy od jednego przebiegu? – JGroven
Prawdopodobnie 512 to magiczny rozmiar, który strasznie pasuje do pamięci podręcznej, więc dostajesz dużo braków w pamięci podręcznej. Inne rozmiary pasują lepiej, więc dostajesz mniej braków. – NathanOliver
Zła droga @NathanOliver - 512 to dużo * wolniej * niż 513. –