Dlaczego transpozycja matrycy 512x512 jest znacznie wolniejsza niż transpozycja matrycy 513x513?

Luchian daje wyjaśnienie Dlaczego Takie zachowanie się dzieje, ale pomyślałem, że dobrym pomysłem będzie pokazanie jednego możliwego rozwiązania tego problemu, a jednocześnie pokazanie trochę o algorytmach nieświadomych pamięci podręcznej.

Twój algorytm zasadniczo robi:

for (int i = 0; i < N; i++) 
   for (int j = 0; j < N; j++) 
        A[j][i] = A[i][j];

Co jest po prostu straszne dla nowoczesnego procesora. Jednym z rozwiązań jest poznanie szczegółów dotyczących systemu pamięci podręcznej i dostosowanie algorytmu, aby uniknąć tych problemów. Działa świetnie, o ile znasz te szczegóły.. nie szczególnie przenośny.

Rozwiązanie wyglądałoby tak:

void recursiveTranspose(int i0, int i1, int j0, int j1) {
    int di = i1 - i0, dj = j1 - j0;
    const int LEAFSIZE = 32; // well ok caching still affects this one here
    if (di >= dj && di > LEAFSIZE) {
        int im = (i0 + i1) / 2;
        recursiveTranspose(i0, im, j0, j1);
        recursiveTranspose(im, i1, j0, j1);
    } else if (dj > LEAFSIZE) {
        int jm = (j0 + j1) / 2;
        recursiveTranspose(i0, i1, j0, jm);
        recursiveTranspose(i0, i1, jm, j1);
    } else {
    for (int i = i0; i < i1; i++ )
        for (int j = j0; j < j1; j++ )
            mat[j][i] = mat[i][j];
    }
}

Nieco bardziej złożony, ale krótki test pokazuje coś ciekawego na moim ancient e8400 z wydaniem VS2010 x64, kod testowy dla MATSIZE 8192

int main() {
    LARGE_INTEGER start, end, freq;
    QueryPerformanceFrequency(&freq);
    QueryPerformanceCounter(&start);
    recursiveTranspose(0, MATSIZE, 0, MATSIZE);
    QueryPerformanceCounter(&end);
    printf("recursive: %.2fms\n", (end.QuadPart - start.QuadPart) / (double(freq.QuadPart) / 1000));

    QueryPerformanceCounter(&start);
    transpose();
    QueryPerformanceCounter(&end);
    printf("iterative: %.2fms\n", (end.QuadPart - start.QuadPart) / (double(freq.QuadPart) / 1000));
    return 0;
}

results: 
recursive: 480.58ms
iterative: 3678.46ms

Edit: o wpływie wielkości: jest znacznie mniej wyraźny chociaż wciąż zauważalne w pewnym stopniu, to dlatego, że używamy rozwiązania iteracyjnego jako węzła liścia zamiast rekurencyjnego w dół do 1 (Zwykle Optymalizacja dla algorytmów rekurencyjnych). Jeśli ustawimy LEAFSIZE = 1, cache nie ma na mnie wpływu [8193: 1214.06; 8192: 1171.62ms, 8191: 1351.07ms - to jest wewnątrz marginesu błędu, wahania są w obszarze 100ms; ten "benchmark" nie jest czymś, co byłoby zbyt wygodne, gdybyśmy chcieli całkowicie dokładne wartości])

[1] źródła do tego: Cóż, jeśli nie możesz zdobądź wykład od kogoś, kto pracował nad tym z Leisersonem.. Zakładam, że ich papiery to dobry punkt wyjścia. Algorytmy te są wciąż dość rzadko opisywane - CLR ma o nich jeden przypis. Mimo to jest to świetny sposób na zaskoczenie ludzi.

Edit (uwaga: to nie ja zamieściłem tę odpowiedź; chciałem tylko dodać):
Oto pełna wersja C++ powyższego kodu:

template<class InIt, class OutIt>
void transpose(InIt const input, OutIt const output,
    size_t const rows, size_t const columns,
    size_t const r1 = 0, size_t const c1 = 0,
    size_t r2 = ~(size_t) 0, size_t c2 = ~(size_t) 0,
    size_t const leaf = 0x20)
{
    if (!~c2) { c2 = columns - c1; }
    if (!~r2) { r2 = rows - r1; }
    size_t const di = r2 - r1, dj = c2 - c1;
    if (di >= dj && di > leaf)
    {
        transpose(input, output, rows, columns, r1, c1, (r1 + r2) / 2, c2);
        transpose(input, output, rows, columns, (r1 + r2) / 2, c1, r2, c2);
    }
    else if (dj > leaf)
    {
        transpose(input, output, rows, columns, r1, c1, r2, (c1 + c2) / 2);
        transpose(input, output, rows, columns, r1, (c1 + c2) / 2, r2, c2);
    }
    else
    {
        for (ptrdiff_t i1 = (ptrdiff_t) r1, i2 = (ptrdiff_t) (i1 * columns);
            i1 < (ptrdiff_t) r2; ++i1, i2 += (ptrdiff_t) columns)
        {
            for (ptrdiff_t j1 = (ptrdiff_t) c1, j2 = (ptrdiff_t) (j1 * rows);
                j1 < (ptrdiff_t) c2; ++j1, j2 += (ptrdiff_t) rows)
            {
                output[j2 + i1] = input[i2 + j1];
            }
        }
    }
}

Jako ilustrację do wyjaśnienia w Luchian Grigore ' s answer, oto jak wygląda obecność pamięci podręcznej macierzy dla dwóch przypadków macierzy 64x64 i 65x65(zobacz link powyżej, aby uzyskać szczegóły dotyczące liczb).

Kolory w animacjach poniżej oznaczają:

• – nie w pamięci podręcznej,
• – in cache,
• – Cache hit,
• – po prostu czytaj z RAM,
• – Cache miss.

Obudowa 64x64:

Zauważ jak prawie każdy dostęp do nowego wiersza powoduje brak pamięci podręcznej. A teraz jak to wygląda w normalnym przypadku, matrycy 65x65:

Tutaj widać, że większość dostępów po początkowym rozgrzaniu to Cache hits. Tak ma działać pamięć podręczna procesora.