Warum ist mein Programm langsam, wenn genau 8192 Elemente durchlaufen werden?

755

Hier ist der Auszug aus dem betreffenden Programm. Die Matrix img[][]hat die Größe GRÖSSE × GRÖSSE und wird initialisiert bei:

img[j][i] = 2 * j + i

Dann res[][]erstellen Sie eine Matrix , und jedes Feld hier ist der Durchschnitt der 9 Felder in der img-Matrix. Der Rand wird der Einfachheit halber bei 0 belassen.

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

Das ist alles, was das Programm zu bieten hat. Der Vollständigkeit halber ist hier das, was vorher kommt. Es kommt kein Code mehr. Wie Sie sehen können, handelt es sich nur um eine Initialisierung.

#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; //result of mean filter
int i,j,k,l;
for(i=0;i<SIZE;i++) 
    for(j=0;j<SIZE;j++) 
        img[j][i] = (2*j+i)%8196;

Grundsätzlich ist dieses Programm langsam, wenn SIZE ein Vielfaches von 2048 ist, z. B. die Ausführungszeiten:

SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

Der Compiler ist GCC. Soweit ich weiß, liegt dies an der Speicherverwaltung, aber ich weiß nicht wirklich viel über dieses Thema, weshalb ich hier frage.

Auch wie man das behebt, wäre schön, aber wenn jemand diese Ausführungszeiten erklären könnte, wäre ich schon glücklich genug.

Ich kenne malloc / free bereits, aber das Problem ist nicht die Menge des verwendeten Speichers, sondern lediglich die Ausführungszeit. Ich weiß also nicht, wie das helfen würde.

casperOne
quelle
67
@bokan es passiert, wenn die Größe ein Vielfaches des kritischen Schrittes des Caches ist.
Luchian Grigore
5
@Mysticial, es spielt keine Rolle, es stellt genau das gleiche Problem dar; Code kann unterschiedlich sein, aber im Grunde stellen beide Fragen ungefähr zur gleichen Zeit (und ihre Titel sind definitiv ähnlich).
Griwes
33
Sie sollten Bilder nicht mit einem zweidimensionalen Array verarbeiten, wenn Sie eine hohe Leistung wünschen. Betrachten Sie alle Pixel als Rohdaten und verarbeiten Sie sie wie ein eindimensionales Array. Machen Sie diese Unschärfe in zwei Durchgängen. Addieren Sie zuerst den Wert der umgebenden Pixel mit einer gleitenden Summe von 3 Pixeln: slideSum + = src [i + 1] -src [i-1]; dest [i] = slideSum;. Machen Sie dann dasselbe vertikal und teilen Sie gleichzeitig: dest [i] = (src [i-Breite] + src [i] + src [i + Breite]) / 9. www-personal.engin.umd.umich.edu/~jwvm/ece581/18_RankedF.pdf
Bokan
8
Hier sind tatsächlich zwei Dinge los. Es ist nicht nur Super-Alignment.
Mysticial
7
(Nur ein kleiner Trottel auf Ihrer Antwort. Für das erste Codesegment wäre es schön, wenn alle Ihre for-Schleifen geschweifte Klammern hätten.)
Trevor Boyd Smith

Antworten:

954

Der Unterschied wird durch dasselbe Super-Alignment-Problem bei den folgenden verwandten Fragen verursacht:

Das liegt aber nur daran, dass es ein weiteres Problem mit dem Code gibt.

Ausgehend von der ursprünglichen Schleife:

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

Beachten Sie zunächst, dass die beiden inneren Schleifen trivial sind. Sie können wie folgt abgewickelt werden:

for(i=1;i<SIZE-1;i++) {
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

Damit bleiben die beiden äußeren Schleifen, an denen wir interessiert sind.

Jetzt können wir sehen, dass das Problem in dieser Frage dasselbe ist: Warum wirkt sich die Reihenfolge der Schleifen auf die Leistung aus, wenn über ein 2D-Array iteriert wird?

Sie iterieren die Matrix spaltenweise statt zeilenweise.


Um dieses Problem zu lösen, sollten Sie die beiden Schleifen austauschen.

for(j=1;j<SIZE-1;j++) {
    for(i=1;i<SIZE-1;i++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

Dadurch entfällt der gesamte nicht sequentielle Zugriff vollständig, sodass Sie bei großen Zweierpotenzen keine zufälligen Verlangsamungen mehr erhalten.


Core i7 920 bei 3,5 GHz

Originalcode:

8191: 1.499 seconds
8192: 2.122 seconds
8193: 1.582 seconds

Vertauschte Außenschleifen:

8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds
Mystisch
quelle
217
Ich werde auch bemerken, dass das Abrollen der inneren Schleifen keinen Einfluss auf die Leistung hat. Der Compiler macht das wahrscheinlich automatisch. Ich habe sie nur abgewickelt, um sie loszuwerden, damit das Problem mit den äußeren Schleifen leichter erkannt werden kann.
Mysticial
29
Und Sie können diesen Code um einen weiteren Faktor drei beschleunigen, indem Sie die Summen entlang jeder Zeile zwischenspeichern. Diese und andere Optimierungen liegen jedoch außerhalb des Rahmens der ursprünglichen Frage.
Eric Postpischil
34
@ClickUpvote Dies ist tatsächlich ein Hardwareproblem (Caching). Es hat nichts mit der Sprache zu tun. Wenn Sie es in einer anderen Sprache versuchen würden, die zu nativem Code kompiliert oder JITs erstellt, würden Sie wahrscheinlich dieselben Effekte sehen.
Mysticial
19
@ClickUpvote: Du scheinst ziemlich fehlgeleitet zu sein. Diese "zweite Schleife" war nur mystisch, die inneren Schleifen von Hand abzuwickeln. Dies wird Ihr Compiler mit ziemlicher Sicherheit sowieso tun, und Mystical hat es nur getan, um das Problem mit den äußeren Schleifen offensichtlicher zu machen. Es ist keineswegs etwas, das Sie selbst tun sollten.
Lily Ballard
154
Dies ist ein perfektes Beispiel für eine gute Antwort auf SO: Verweist auf ähnliche Fragen, erklärt Schritt für Schritt, wie Sie es angegangen sind, erklärt das Problem, erklärt, wie das Problem behoben werden kann, verfügt über eine hervorragende Formatierung und sogar ein Beispiel für den ausgeführten Code auf Ihrer Maschine. Danke für Ihren Beitrag.
MattSayar
57

Die folgenden Tests wurden mit dem Visual C ++ - Compiler durchgeführt, da dieser von der Standardinstallation von Qt Creator verwendet wird (ich denke, ohne Optimierungsflag). Bei der Verwendung von GCC gibt es keinen großen Unterschied zwischen der Version von Mystical und meinem "optimierten" Code. Die Schlussfolgerung ist also, dass Compiler-Optimierungen die Mikrooptimierung besser berücksichtigen als Menschen (ich endlich). Ich lasse den Rest meiner Antwort als Referenz.


Es ist nicht effizient, Bilder auf diese Weise zu verarbeiten. Es ist besser, eindimensionale Arrays zu verwenden. Die Verarbeitung aller Pixel erfolgt in einer Schleife. Der zufällige Zugriff auf Punkte kann erfolgen über:

pointer + (x + y*width)*(sizeOfOnePixel)

In diesem speziellen Fall ist es besser, die Summe von drei Pixelgruppen horizontal zu berechnen und zwischenzuspeichern, da sie jeweils dreimal verwendet werden.

Ich habe einige Tests durchgeführt und ich denke, es lohnt sich zu teilen. Jedes Ergebnis besteht aus durchschnittlich fünf Tests.

Originalcode von user1615209:

8193: 4392 ms
8192: 9570 ms

Mystical's Version:

8193: 2393 ms
8192: 2190 ms

Zwei Durchgänge mit einem 1D-Array: erster Durchgang für horizontale Summen, zweiter Durchgang für vertikale Summe und Durchschnitt. Adressierung mit zwei Durchgängen mit drei Zeigern und nur solchen Inkrementen:

imgPointer1 = &avg1[0][0];
imgPointer2 = &avg1[0][SIZE];
imgPointer3 = &avg1[0][SIZE+SIZE];

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(*(imgPointer1++)+*(imgPointer2++)+*(imgPointer3++))/9;
}

8193: 938 ms
8192: 974 ms

Zwei Durchgänge mit einem 1D-Array und Adressierung wie folgt:

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(hsumPointer[i-SIZE]+hsumPointer[i]+hsumPointer[i+SIZE])/9;
}

8193: 932 ms
8192: 925 ms

Ein Durchgang zwischenspeichert horizontale Summen nur eine Zeile voraus, damit sie im Cache bleiben:

// Horizontal sums for the first two lines
for(i=1;i<SIZE*2;i++){
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
}
// Rest of the computation
for(;i<totalSize;i++){
    // Compute horizontal sum for next line
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
    // Final result
    resPointer[i-SIZE]=(hsumPointer[i-SIZE-SIZE]+hsumPointer[i-SIZE]+hsumPointer[i])/9;
}

8193: 599 ms
8192: 652 ms

Fazit:

  • Keine Vorteile der Verwendung mehrerer Zeiger und nur von Inkrementen (ich dachte, es wäre schneller gewesen)
  • Das Zwischenspeichern horizontaler Summen ist besser als das mehrmalige Berechnen.
  • Zwei Durchgänge sind nicht dreimal schneller, sondern nur zweimal.
  • Es ist möglich, mit einem einzigen Durchgang und dem Zwischenspeichern eines Zwischenergebnisses 3,6-mal schneller zu sein

Ich bin sicher, es ist möglich, es viel besser zu machen.

HINWEIS Bitte beachten Sie, dass ich diese Antwort eher auf allgemeine Leistungsprobleme als auf das in Mysticals hervorragender Antwort erläuterte Cache-Problem geschrieben habe. Am Anfang war es nur Pseudocode. Ich wurde gebeten, Tests in den Kommentaren durchzuführen ... Hier ist eine komplett überarbeitete Version mit Tests.

Bokan
quelle
9
"Ich denke, es ist mindestens dreimal schneller" - möchten Sie diese Behauptung mit einigen Metriken oder Zitaten untermauern?
Adam Rosenfield
8
@AdamRosenfield "Ich denke" = Vermutung! = "Es ist" = Behauptung. Ich habe keine Metrik dafür und würde gerne einen Test sehen. Aber meine erfordern 7 Inkremente, 2 Sub, 2 Add und ein Div pro Pixel. Jede Schleife verwendet weniger lokale Variablen als Register in der CPU. Die anderen erfordern 7 Inkremente, 6 Dekremente, 1 Div und zwischen 10 und 20 Mul für die Adressierung, abhängig von der Compileroptimierung. Außerdem erfordert jeder Befehl in der Schleife das Ergebnis des vorherigen Befehls, wodurch die Vorteile der superskalaren Architektur von Pentiums verworfen werden. Es muss also schneller sein.
Bokan
3
Die Antwort auf die ursprüngliche Frage dreht sich alles um Speicher- und Cache-Effekte. Der Grund dafür, dass der OP-Code so langsam ist, besteht darin, dass sein Speicherzugriffsmuster nach Spalten anstatt nach Zeilen verläuft, was eine sehr schlechte Referenzposition im Cache aufweist. Bei 8192 ist dies besonders schlimm, da aufeinanderfolgende Zeilen dieselben Cache-Zeilen in einem direkt zugeordneten Cache oder Cache mit geringer Assoziativität verwenden, sodass die Cache-Fehlerrate sogar noch höher ist. Das Vertauschen der Schleifen bietet eine enorme Leistungssteigerung, indem die Cache-Lokalität stark erhöht wird.
Adam Rosenfield
1
Gut gemacht, das sind einige beeindruckende Zahlen. Wie Sie festgestellt haben, dreht sich alles um die Speicherleistung - die Verwendung mehrerer Zeiger mit Inkrementen brachte keinen Vorteil.
Adam Rosenfield
2
@AdamRosenfield Ich war heute Morgen ziemlich besorgt, weil ich die Tests nicht reproduzieren konnte. Es scheint, dass die Leistungssteigerung nur mit dem Visual C ++ - Compiler erfolgt. Bei Verwendung von gcc gibt es nur einen kleinen Unterschied.
Bokan