Verständnis darüber, wie man Code schreibt, der cache-freundlich ist

Question

Ich habe versucht, zu verstehen, wie man code schreibt, der cache-freundlich ist. Als ersten Schritt habe ich versucht, den Leistungsunterschied zwischen dem Zugriff auf arrays in Zeilen- und Spaltenreihenfolge zu verstehen.

Also habe ich ein int-Array der Größe 512×512 erstellt, sodass die Gesamtgröße 1MB beträgt. Mein L1-Cache ist 32KB, der L2-Cache ist 256KB und der L3-Cache ist 3MB. Also passt mein Array in den L3-Cache.

Ich habe einfach die Summe der Array-Elemente in Zeilen- und Spaltenreihenfolge berechnet und ihre Geschwindigkeit verglichen. Die Spaltenreihenfolge ist jedes Mal etwas schneller. Ich habe erwartet, dass die Zeilenreihenfolge schneller ist als die andere (vielleicht sogar mehrmals schneller).

Ich dachte, das Problem könnte auf die geringe Größe des Arrays zurückzuführen sein, also habe ich ein weiteres Array der Größe 8192×8192 (256MB) erstellt. Trotzdem das gleiche Ergebnis.

Im Folgenden ist der von mir verwendete Codeausschnitt:

#include "time.h"
#include 

#define S 512
#define M S
#define N S

int main() {
    // Summieren in der Zeilenreihenfolge
    int x = 0;
    int iter = 25000;
    int i, j;
    int k[M][N];
    int sum = 0;    
    clock_t start, end;

    start = clock();
    while(x < iter) {
        for (i = 0; i < M; i++) {
            for(j = 0; j < N; j++) {
                sum += k[i][j];
            }
        }

        x++;
    }
    end = clock();
    printf("%i\n", end-start);

    // Summieren in der Spaltenreihenfolge
    x = 0;
    sum = 0;
    int h[M][N];

    start = clock();
    while(x < iter) {
        for (j = 0; j < N; j++) {
            for(i = 0; i < M; i++){
                sum += k[i][j];
            }
        }

        x++;
    }
    end = clock();
    printf("%i\n", end-start);
}

Frage: Kann mir jemand sagen, wo mein Fehler liegt und warum ich dieses Ergebnis erhalte?

Answer 1

Ich weiß nicht wirklich, warum dieses Verhalten auftritt, aber lassen Sie mich einige Dinge klären.

Es gibt mindestens 2 Dinge zu beachten, wenn man über Cache nachdenkt: Cache-Größe und Cache-Zeilen-Größe. Zum Beispiel hat mein Intel i7 920 Prozessor einen 256KB L2 Cache mit einer Zeilengröße von 64 Bytes. Wenn Ihre Daten in den Cache passen, spielt die Reihenfolge, in der Sie darauf zugreifen, wirklich keine Rolle. Alle Probleme bei der Optimierung eines Codes für die Cache-Freundlichkeit müssen sich auf 2 Dinge konzentrieren: Wenn möglich, teilen Sie den Zugriff auf den Speicher in Blöcke auf, so dass ein Block in den Cache passt. Führen Sie alle möglichen Berechnungen mit diesem Block durch und bringen Sie dann den nächsten Block, führen Sie die Berechnungen mit ihm durch und so weiter. Das andere (was Sie versuchen) ist, auf den Speicher auf aufeinanderfolgende Weise zuzugreifen. Wenn Sie Daten aus dem Speicher anfordern (sagen wir ein int - 4 Bytes), wird eine ganze Cache-Zeile in den Cache gebracht (in meinem Fall 64 Bytes: das sind 16 benachbarte ganze Zahlen (einschließlich der angeforderten) werden in den Cache gebracht). Hier kommt die Reihenfolge der Zeilen gegen die Spalten ins Spiel. Mit der Reihenfolge der Zeilen haben Sie 1 Cache-Miss für jede 16 Speicheranforderungen, mit der Reihenfolge der Spalten erhalten Sie einen Cache-Miss für jede Anforderung (aber nur, wenn Ihre Daten nicht in den Cache passen; wenn Ihre Daten in den Cache passen, erhalten Sie das gleiche Verhältnis wie bei der Reihenfolge der Zeilen, weil Sie die Zeilen immer noch im Cache haben, von vor langer Zeit, als Sie das erste Element in der Zeile angefordert haben; natürlich kann die Assoziativität ins Spiel kommen und eine Cache-Zeile kann überschrieben werden, selbst wenn nicht der gesamte Cache mit Ihren Daten gefüllt ist).

In Bezug auf Ihr Problem, wenn die Daten in den Cache passen, wie ich sagte, spielt die Zugriffsreihenfolge nicht so eine große Rolle, aber wenn Sie die zweite Summe durchführen, sind die Daten bereits im Cache, seit Sie die erste Summe durchgeführt haben, daher ist sie schneller. Wenn Sie zuerst die Summe in Spaltenreihenfolge durchführen, sollten Sie sehen, dass die Summe in Reihenreihenfolge einfach schneller wird, weil sie danach durchgeführt wird. Wenn die Daten jedoch groß genug sind, sollten Sie nicht das gleiche Verhalten bekommen. Versuchen Sie folgendes: Führen Sie zwischen den beiden Summen eine Operation mit weiteren großen Daten durch, um den gesamten Cache ungültig zu machen.

Bearbeiten

Ich sehe einen 3-4-fachen Geschwindigkeitsgewinn für Reihe-mäßig (obwohl ich einen Geschwindigkeitsgewinn von >8x erwartet habe. Irgendeine Idee warum?). [...] es wäre großartig, wenn Sie mir sagen könnten, warum der Geschwindigkeitsgewinn nur 3x beträgt

Nicht, dass der Zugriff auf die Matrix auf die "richtige Weise" nicht viel verbessert, eher der Zugriff auf die Matrix auf die "falsche Weise" nicht so sehr schadet, wenn das einen Sinn ergibt.

Obwohl ich Ihnen keine spezifische und genaue Antwort geben kann, was ich Ihnen sagen kann ist, dass moderne Prozessoren sehr komplizierte und extrem effiziente Cache-Modelle haben. Sie sind so leistungsstark, dass sie zum Beispiel in vielen gängigen Fällen die Cache-Level verschleiern können, sodass es so aussieht, als ob Sie anstelle von 3 Ebenen Cache einen großen einstufigen Cache haben (Sie sehen keine Strafe, wenn Sie Ihre Datengröße von einer Größe, die in L2 passt, auf eine Größe erhöhen, die nur in L3 passt). Wenn Sie Ihren Code auf einem älteren Prozessor ausführen (sagen wir vor 10 Jahren), werden Sie wahrscheinlich den Geschwindigkeitsgewinn sehen, den Sie erwarten. Moderne Prozessoren haben jedoch Mechanismen, die bei Cache-Misses sehr hilfreich sind. Desktop-Prozessoren sind nach dem Prinzip entwickelt, "schlechten Code" schnell auszuführen, daher wird viel in die Verbesserung der Leistung von "schlechtem Code" investiert, da die überwiegende Mehrheit der Desktop-Anwendungen von Personen geschrieben wird, die Probleme mit Verzweigungen oder Cache-Modellen nicht verstehen. Im Gegensatz dazu machen spezialisierte Prozessoren auf dem High-Performance-Markt schlechten Code sehr schmerzhaft, weil sie schwache Mechanismen implementieren, die sich mit "schlechtem Code" befassen (oder überhaupt nicht implementieren). Diese Mechanismen verbrauchen viele Transistoren und erhöhen so den Stromverbrauch und die erzeugte Wärme, aber sie sind es wert, in einem Desktop-Prozessor implementiert zu werden, wo der Großteil des Codes "schlechter Code" ist.