webentwicklung-frage-antwort-db.com.de

Warum ist mein Programm langsam, wenn es genau 8192 Elemente durchläuft?

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

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

Dann erstellen Sie eine Matrix res[][], und jedes Feld hier wird als Durchschnitt der 9 Felder in der img-Matrix verwendet. 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 es zum Programm gibt. Der Vollständigkeit halber kommt hier was vor. Es folgt kein Code. Wie Sie sehen, 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. 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 nett, 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, dass nicht viel Speicher verwendet wird, sondern lediglich die Ausführungszeit. Ich weiß also nicht, wie das helfen würde.

736
anon

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

Das liegt aber nur daran, dass es noch 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 vertauschen.

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 Verzögerungen mehr erhalten.


Core i7 920 bei 3,5 GHz

Originalcode:

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

Vertauschte Outer-Loops:

8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds
929
Mysticial

Die folgenden Tests wurden mit dem Visual C++ - Compiler durchgeführt, da er von der Standardinstallation von Qt Creator verwendet wird (vermutlich 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 besser für die Mikrooptimierung sorgen 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. Zufälliger Zugriff auf Punkte kann erfolgen mit:

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

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

Ich habe einige Tests gemacht und denke, es lohnt sich, sie zu teilen. Jedes Ergebnis ist ein Durchschnitt von fünf Tests.

Originalcode von user1615209:

8193: 4392 ms
8192: 9570 ms

Version von Mystical:

8193: 2393 ms
8192: 2190 ms

Zwei Durchgänge mit einem 1D-Array: Erster Durchgang für horizontale Summen, zweiter für vertikale Summe und Durchschnitt. Zwei-Pass-Adressierung mit drei Zeigern und nur Inkrementen wie folgt:

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 folgender Adressierung:

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, bei dem horizontale Summen nur eine Zeile vor ihnen zwischengespeichert werden, 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 Inkremente (ich dachte, es wäre schneller gewesen)
  • Das Zwischenspeichern horizontaler Summen ist besser, als sie mehrere Male zu berechnen.
  • Zwei Durchgänge sind nicht dreimal schneller, sondern nur zweimal.
  • Es ist möglich, 3,6-mal schneller mit einem einzigen Durchgang und dem Zwischenspeichern eines Zwischenergebnisses zu arbeiten

Ich bin mir sicher, dass es viel besser geht.

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

55
bokan