Dlaczego mój program działa wolno przy zapętlaniu dokładnie 8192 elementów?

Oto fragment tego programu. Matryca img[][]ma rozmiar SIZE × SIZE i jest inicjowana o:

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

Następnie tworzysz macierz res[][], a każde pole tutaj jest średnią z 9 pól wokół niej w macierzy img. Dla uproszczenia granicę pozostawia 0.

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;
}

To wszystko, co jest w programie. Dla kompletności, oto, co nastąpi wcześniej. Po tym nie ma kodu. Jak widać, to tylko inicjalizacja.

#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;

Zasadniczo ten program jest powolny, gdy SIZE jest wielokrotnością 2048, np. Czasy wykonania:

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

Kompilatorem jest GCC. Z tego, co wiem, dzieje się tak z powodu zarządzania pamięcią, ale tak naprawdę nie wiem zbyt wiele na ten temat, dlatego tutaj pytam.

Także jak to naprawić, byłoby miło, ale jeśli ktoś mógłby wyjaśnić te czasy wykonania, byłbym już wystarczająco szczęśliwy.

Wiem już o malloc / free, ale problemem nie jest ilość pamięci, tylko czas wykonania, więc nie wiem, jak to by pomogło.

Różnica jest spowodowana tym samym problemem dotyczącym wyrównania z następujących powiązanych pytań:

• Dlaczego transponowanie macierzy 512x512 jest znacznie wolniejsze niż transponowanie macierzy 513x513?
• Mnożenie macierzy: Mała różnica w wielkości macierzy, duża różnica w czasie

Ale to tylko dlatego, że jest jeszcze jeden problem z kodem.

Począwszy od oryginalnej pętli:

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;
}

Najpierw zauważ, że dwie wewnętrzne pętle są trywialne. Można je rozwinąć w następujący sposób:

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;
    }
}

To pozostawia dwie zewnętrzne pętle, którymi jesteśmy zainteresowani.

Teraz widzimy, że problem jest taki sam w tym pytaniu: Dlaczego kolejność pętli wpływa na wydajność podczas iteracji po tablicy 2D?

Iterujesz macierz według kolumn zamiast wierszy.

Aby rozwiązać ten problem, należy zamienić dwie pętle.

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;
    }
}

Eliminuje to całkowicie niesekwencyjny dostęp, dzięki czemu nie dochodzi już do przypadkowych spowolnień przy dużych potęgach dwóch.

Core i7 920 @ 3,5 GHz

Oryginalny kod:

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

Pętle zewnętrzne zamienione:

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

Poniższe testy zostały wykonane przy użyciu kompilatora Visual C ++, ponieważ jest on używany przez domyślną instalację Qt Creator (chyba bez flagi optymalizacji). Podczas korzystania z GCC nie ma dużej różnicy między wersją Mystical a moim „zoptymalizowanym” kodem. Wniosek jest taki, że optymalizacje kompilatora lepiej zapobiegają mikrooptymalizacji niż ludzie (w końcu ja). Resztę mojej odpowiedzi zostawiam w celach informacyjnych.

Przetwarzanie obrazów w ten sposób nie jest wydajne. Lepiej jest używać tablic jednowymiarowych. Przetwarzanie wszystkich pikseli odbywa się w jednej pętli. Losowy dostęp do punktów można uzyskać za pomocą:

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

W tym konkretnym przypadku lepiej jest obliczyć i buforować sumę trzech grup pikseli w poziomie, ponieważ są one używane trzy razy.

Zrobiłem kilka testów i myślę, że warto się tym podzielić. Każdy wynik to średnio pięć testów.

Oryginalny kod użytkownika1615209:

8193: 4392 ms
8192: 9570 ms

Wersja Mystical:

8193: 2393 ms
8192: 2190 ms

Dwa przejścia przy użyciu tablicy 1D: pierwsze przejście dla sum poziomych, drugie dla sumy pionowej i średniej. Adresowanie dwuprzebiegowe z trzema wskaźnikami i tylko takie przyrosty:

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

Dwa przejścia za pomocą tablicy 1D i adresowania w ten sposób:

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

8193: 932 ms
8192: 925 ms

Jedno przejście buforuje poziome sumy tylko o jeden rząd do przodu, aby pozostały w pamięci podręcznej:

// 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

Wniosek:

• Brak korzyści z używania kilku wskaźników i tylko przyrosty (myślałem, że byłoby szybciej)
• Buforowanie sum poziomych jest lepsze niż ich wielokrotne obliczanie.
• Dwa podania nie są trzy razy szybsze, tylko dwa razy.
• Możliwe jest osiągnięcie 3,6 razy szybciej przy użyciu zarówno pojedynczego przejścia, jak i buforowania wyniku pośredniego

Jestem pewien, że można zrobić znacznie lepiej.

UWAGA Należy pamiętać, że napisałem tę odpowiedź, aby rozwiązać ogólne problemy z wydajnością, a nie problem z pamięcią podręczną wyjaśniony w doskonałej odpowiedzi Mystical. Na początku był to tylko pseudo kod. Zostałem poproszony o wykonanie testów w komentarzach ... Oto całkowicie przebudowana wersja z testami.