Dlaczego mój program jest powolny, gdy zapętla dokładnie 8192 elementy?

Poniższe testy zostały wykonane z kompilatorem 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ą Mystic a moim" zoptymalizowanym " kodem. Wniosek jest taki, że optymalizacje kompilatorów dbają o mikro optymalizację lepiej niż ludzie(w końcu ja). Resztę odpowiedzi zostawiam w celach informacyjnych.

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

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

Oryginalny kod użytkownika user1615209:

8193: 4392 ms
8192: 9570 ms

Wersja mistyczna:

8193: 2393 ms
8192: 2190 ms

Dwa przejścia przy użyciu tablicy 1D: pierwsze przejście dla Sum poziomych, drugie dla Sum pionowych i średnich. Adresowanie dwujezdniowe z trzema wskaźnikami i tylko przyrostami w ten sposób:

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 używając tablicy 1D i adresując Tak:

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

8193: 932 ms
8192: 925 ms

One pass caching horizontal sumuje tylko jeden wiersz do przodu, więc pozostają 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 przyrostów (myślałem, że będzie szybciej)
• buforowanie Sum poziomych jest lepsze niż obliczam je kilka razy.
• dwa przejścia nie są trzy razy szybsze, tylko dwa razy.
Możliwe jest osiągnięcie 3,6 razy szybciej, zarówno przy użyciu pojedynczego przejścia, jak i buforowania pośredniego wyniku.]}

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

Uwaga Proszę zauważyć, że napisałem tę odpowiedź na ogólne Problemy z wydajnością, a nie problem pamięci podręcznej wyjaśniony w doskonałej odpowiedzi Mystic. Na początku był to tylko pseudo kod. Poproszono mnie o zrób testy w komentarzach... Oto całkowicie zreformowana wersja z testami.

Uporządkowanie dostępu do elementu zostało jeszcze kilka nisko wiszących owoców. Akumulacji można dokonać w taki sposób, że podczas iteracji w prawo tylko 3 nowe wartości muszą być pobrane z pamięci i nagromadzone. Sztuczka polega na tym, aby wiedzieć, jak upuścić lewą kolumnę; podczas dodawania nowej kolumny zapamiętaj jej wartość, dopóki nie wyjdzie z okna próbkowania.

Koszt przed: 9 Czytaj, 9 dodawaj, 1 dział Koszt po: 3 read, 3 addition, 1 division

Think of the okno próbkowania jako pole 3x3, w którym śledzisz każdą kolumnę (1x3) osobno. Zbierz nową kolumnę i upuść najstarszą.

Dzielenie jest instrukcją o dużym opóźnieniu, więc może być korzystne ukrycie opóźnienia, ale przed pójściem tam wyjście kompilatora powinno być sprawdzane, czy dzielenie przez stałą jest elided i jeśli rozwijanie pętli (przez kompilator) już wykonuje pewną kompensację opóźnienia.

Ale po najbardziej dramatycznej optymalizacji poprawnego użycia pamięci podręcznej to naprawdę drobne rzeczy.