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


755

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.


67
@ Bokan dzieje się tak, gdy rozmiar jest wielokrotnością krytycznego kroku pamięci podręcznej.
Luchian Grigore

5
@ Mistyczne, to nie ma znaczenia, ujawnia ten sam dokładny problem; kod może być inny, ale w zasadzie oba pytania zadają o tym samym czasie (a ich tytuły są zdecydowanie podobne).
Griwes,

33
Nie należy przetwarzać obrazu przy użyciu tablicy 2 wymiarów, jeśli chcesz uzyskać wysoką wydajność. Weź pod uwagę, że wszystkie piksele są nieprzetworzone i przetwarzaj je jak tablicę jednowymiarową. Zrób to rozmycie w dwóch krokach. Najpierw dodaj wartość otaczających pikseli za pomocą przesuwnej sumy 3 pikseli: slideSum + = src [i + 1] -src [i-1]; dest [i] = slideSum ;. Następnie zrób to samo w pionie i podziel w tym samym czasie: dest [i] = (src [i-width] + src [i] + src [i + width]) / 9. www-personal.engin.umd.umich.edu/~jwvm/ece581/18_RankedF.pdf
bokan

8
Tak naprawdę dzieje się tutaj dwie rzeczy. To nie tylko superrównanie.
Mysticial

7
(Drobny drobiazg w odpowiedzi. W pierwszym segmencie kodu byłoby miło, gdyby wszystkie twoje pętle for miały nawiasy klamrowe.)
Trevor Boyd Smith

Odpowiedzi:


954

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

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

217
Zauważę również, że rozwinięcie wewnętrznych pętli nie ma wpływu na wydajność. Kompilator prawdopodobnie robi to automatycznie. Rozwinąłem je wyłącznie w celu pozbycia się ich, aby ułatwić wykrycie problemu z zewnętrznymi pętlami.
Mysticial

29
Możesz przyspieszyć ten kod trzykrotnie, buforując sumy wzdłuż każdego wiersza. Ale ta i inne optymalizacje są poza zakresem pierwotnego pytania.
Eric Postpischil

33
@ClickUpvote W rzeczywistości jest to problem sprzętowy (buforowanie). Nie ma to nic wspólnego z językiem. Jeśli wypróbujesz to w innym języku, który kompiluje lub JIT do kodu natywnego, prawdopodobnie zobaczysz te same efekty.
Mysticial

19
@ClickUpvote: Wydaje się, że jesteś raczej wprowadzony w błąd. Ta „druga pętla” była po prostu mistycznym ręcznym rozwijaniem wewnętrznych pętli. Jest to coś, co twój kompilator prawie na pewno zrobi, a Mystical zrobił to tylko po to, aby problem z zewnętrznymi pętlami stał się bardziej oczywisty. W żadnym wypadku nie należy się tym zajmować.
Lily Ballard,

154
TO jest doskonały przykład dobrej odpowiedzi na SO: odwołuje się do podobnych pytań, wyjaśnia krok po kroku, w jaki sposób do niego podchodzisz, wyjaśnia problem, wyjaśnia, jak NAPRAWIĆ problem, ma świetne formatowanie, a nawet przykład uruchomionego kodu na twojej maszynie. Dziękuję za twój wkład.
MattSayar

57

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.


9
„Myślę, że jest co najmniej 3 razy szybszy” - czy chcesz poprzeć to roszczenie przy pomocy niektórych danych lub cytatów?
Adam Rosenfield,

8
@AdamRosenfield „Myślę, że” = przypuszczenie! = „Jest” = roszczenie. Nie mam na to żadnych danych i chciałbym zobaczyć test. Ale moje wymagają 7 przyrostów, 2 sub, 2 dodawania i jednego div na piksel. Każda pętla używa mniej lokalnych zmiennych niż rejestr w CPU. Inne wymagają 7 przyrostów, 6 spadków, 1 div i od 10 do 20 mul do adresowania w zależności od optymalizacji kompilatora. Również każda instrukcja w pętli wymaga wyniku poprzedniej instrukcji, co odrzuca zalety super-skalarnej architektury Pentium. Więc musi być szybciej.
bokan

3
Odpowiedź na pierwotne pytanie dotyczy przede wszystkim efektów pamięci i pamięci podręcznej. Powodem, dla którego kod OP jest tak wolny, jest to, że wzorzec dostępu do pamięci przebiega według kolumn zamiast wierszy, które mają bardzo słabą lokalizację pamięci podręcznej. Jest to szczególnie złe w przypadku 8192, ponieważ wtedy kolejne wiersze kończą się przy użyciu tych samych linii pamięci podręcznej w pamięci podręcznej z mapowaniem bezpośrednim lub pamięci podręcznej o niskiej asocjacji, więc wskaźnik pominięcia pamięci podręcznej jest jeszcze wyższy. Wymiana pętli zapewnia ogromny wzrost wydajności poprzez znaczne zwiększenie lokalizacji pamięci podręcznej.
Adam Rosenfield,

1
Dobra robota, to imponujące liczby. Jak zauważyłeś, chodzi przede wszystkim o wydajność pamięci - użycie kilku wskaźników z przyrostami nie przyniosło żadnych korzyści.
Adam Rosenfield

2
@AdamRosenfield Martwiłem się dziś rano, ponieważ nie mogłem odtworzyć testów. Wygląda na to, że wzrost wydajności jest możliwy tylko dzięki kompilatorowi Visual C ++. Używając gcc, jest tylko niewielka różnica.
bokan
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.