Optymalizacja kodu w C++
Wstęp
Proszę się nie łudzić że jakikolwiek kompilator wykona za nas pracę wymagającą więcej inteligencji od ślimaka. Systemy się wieszają, przeglądarki internetowe stoją w miejscu, gry się sypią i tak samo nie ma nic świętego w kompilatorach. One też są pisane przez duże grupy programistów, gdzie ponad połowa zatrudnionych częściej sięga po klawiaturę niż po rozum do głowy i książkę. Tak zwana wydajność języków niskiego poziomu (asembler, fortran) wynika raczej z niemożności pisania w tych językach rzeczy sztucznych i źle przemyślanych, bo takie programy po prostu się nie kompilują lub natychmiast padają po uruchomieniu, co automatycznie zawęża krąg potencjalnych programistów w tych językach do ludzi znających swój fach. W przypadku C++ i obecnie najpopularniejszych tzw. superskalarnych procesorów o skomplikowanych zależnościach w czasie wykonania instrukcji ocena wydajności jest niestety nauką czysto eksperymentalną jeśli nie sztuką walki.
Przepisy kucharskie
Sztukę optymalizacji chyba najprościej jest ilustrować dużą ilością przykładów, jako że konkretne reguły (chociaż teoretycznie znane) są zaskakująco zagmatwanie i przez to bezużyteczne.
* * *
Generalnie, referencja jest implementowana jako wskaźnik (dziś o rozmiarze 32 bity), stąd każda struktura o więcej niż jednej składowej powinna być przekazywana przez referencję (lub wskaźnik). Sztuką jest podawanie jak najkrótszych argumentów do wywołania funkcji, bo to kosztuje. Typowe wywołanie:
struct PUNKT {double x, y};
double funkcja(const PUNKT p)
{
//cokolwiek
};
zamieniamy na:
struct PUNKT {double x, y};
double funkcja(const PUNKT &p)
{
//cokolwiek
};
* * *
Nie opłaca się podawać referencję do np. 80 bitowego typu double, bo chociaż przesyłana jest mniejsza porcja danych, to późniejszy dostęp do tej wartości wymaga załadowania jej adresu a następnie załadowanie tego, co się pod tym adresem znajduje. Istotnie, buforowanie referencji w stałej ma sens:
void funkcja(double (&tablica)[12])
{
const double &referencja5elementu=tablica[4];
for(int i=0; i<dużo; i++)
//jakieś operacje z użyciem referencja5elementu
}
lub taki kod:
void funkcja(double (&tablica)[12])
{
const double * const wskaźnik_do_5_elementu=&tablica[4];
// lub =tablica+4;
for(int i=0; i<dużo; i++)
// Jakieś operacje z użyciem *wskaźnik_do_5_elementu
}
wypada zamienić na:
void funkcja(double (&tablica)[12])
{
const double wartość_5_elementu=tablica[4];
for(int i=0; i<dużo; i++)
// Jakieś operacje z użyciem wartość_5_elementu,
}
* * *
Nadmierne używanie "bezpieczników" w kodzie prowadzi do absurdów:
class superbezpieczna_tablica
{
int rozmiar;
double *dane;
inline double daj_wartość(int pozycja)
{
if(pozycja<0)
cerr<"Zła pozycja -\n";
if(pozycja>=rozmiar)
cerr<"Zła pozycja +\n";
return dane[pozycja];
}
};
Taka tablica będzie beznadziejnie powolna. Proponuję użyć asercji:
#include <assert.h>
class superbezpieczna_tablica
{
int rozmiar;
double *dane;
inline double daj_wartość(int pozycja)
{
assert(pozycja>=0);
assert(pozycja<rozmiar);
return dane[pozycja];
}
};
Assert oznacza "upewnij się, że...", gdy warunek jest niespełniony to w trakcie uruchamiania programu uzyskamy napis: "line 8: assertion failed in file sbtab.h: pozycja>=0" i zakończenie pracy programu. Tymczasem, w wersji finalnej podczas kompilacji zdefiniujemy makro #define NDEBUG i wszystkie asercje po prostu znikną, nie będą więcej spowalniać i zwiększać rozmiaru kodu.
* * *
Zamiana mnożenia na przesunięcia bitowe (liczby całkowite!):
int a=b*2;
int c=d*8;
int e=f*3;
int g=h*124;
To samo:
int a=b<<1;
int c=d<<3;//bo 2^3 = 8
int e=(f<<1)+f; // Nawiasowanie jest tu konieczne!
// Priorytet << i >> jest niższy niż +
// Możliwe też int e=f+f+f w tym szczególnym przypadku
int g=f+(f<<2)+(f<<3)+(f<<4)+(f<<5)+(f<<6);
// 125 to 1111101 bin czyli 1*2^0+0*2^1+1*2^2+1*2^3+1*2^4+1*2^5+1*2^6
Sztuczka działa tylko dla liczb całkowitych (char, short, int, long, long long i ich wersje unsigned)!
Przykład dla int g jest na granicy opłacalności, koszt mnożenia to ok. 22 cykle procesora, mnożenia, przesunięcia bitowe i przypisanie po jednym cyklu na operację, lecz sumowanie czeka na wynik przesunięć bitowych i obliczenia wydajności nie są oczywiste. Koszt dzielenia to ok. 40 cykli, lecz zależy to bardzo od kontekstu użycia.
* * *
Zamiana dzieleniae przez potęgę dwójki na przesunięcia bitowe (liczby całkowite!):
int a=b/2;
int c=d/8;
int e=f/256;
To samo:
int a=b>>1;
int c=d>>3;
int e=f>>8;
Nie ma prostego sposobu na dzielenie całkowite przez dowolną stałą...
* * *
Reszta z dzielenia przez potęgę dwójki jako bitowa koniunkcja:
int a=b%2;
int c=d%8;
int e=f%256;
To przecież:
int a=b&1; // Czy b jest nieparzyste?
// Czyli: czy reszta z dzielenia b przez 2 jest niezerowa,
// Czyli: czy b ma zapalony najmniej znaczący bit?
int c=d&7;
int e=f&255;
* * *
Jednoczesne / i %:
int a=b/x;
int c=b%x;
Jednoczesne dzielenie i reszta z dzielenia na tych samych argumentach to zły pomysł. Reszta z dzielenia to zawsze jedno dzielenie i jedno odejmowanie:
int a=b/x;
int c=b-a*x;
A mnożenie plus odejmowanie jest tańsze od dzielenia...
Istnieją niestandardowe funkcje, w postaci _div(&a, &b, x); które jednocześnie liczą % i /.
* * *
Zamiana dzielenia na mnożenie
class WEKTOR3D
{
double x, y, z;
operator/(const WEKTOR3D &wektor, double stała)
{
wektor.x/=stała;
wektor.y/=stała;
wektor.z/=stała;
}
};
Można zaskakująco przyśpieszyć o 50% na Pentium2:
class WEKTOR3D
{
double x, y, z;
operator/(const WEKTOR3D &wektor, double stała)
{
const double odwrotność_stałej=1.0/stała;
wektor.x*=odwrotność_stałej;
wektor.y*=odwrotność_stałej;
wektor.z*=odwrotność_stałej;
}
};
Zaskakujące jest to, że zamiast 3 dzieleń jest jedno i 3 mnożenia i i tak wynik jest szybszy... Ta technika oczywiście daje znacznie większe efekty przy większej ilości dzieleń. Przypadku dla wektora 2D jeszcze nie badałem, ale raczej poprawy nie będzie.
* * *
Prymitywne pętle liczone w dół wykonują się szybciej, jako że porównanie z zerem w pewnych przypadkach jest prostsze od porównania ze stałą:
for(int i=0; i<imax; i++)
tablica[i]=i;
Zamieniamy na:
for(int i=imax-1; i>0; i--)
tablica[i]=i;
Uwaga: ta technika bywa często źródłem błędów indeksowania gdy źle użyta, zachowuj kopie kodu... Co gorsza, dla bardziej skomplikowanych pętli rezultat może być gorszy ze stratą nawet 20%.
* * *
Redukcja wielokrotnych pętli jest wskazana:
int i;
for(i=0; i<imax; i++)
tablica_1[i]=i;
for(i=imax-1; i>0; i--)
tablica_2[i]=i;
Zamieniamy na:
int i;
for(i=0; i<imax; i++)
{
tablica_1[i]=i;
tablica_2[i]=i;
}
Nie dotyczy to sytuacji gdy w obydwu pętlach znajduje się znacząco różny tj. mający dostęp do innych tablic lub jakiś duży kod, wówczas taka zamiana spowoduje spowolnienie. Np. zazwyczaj nie opłaca się łączyć kopiowania elementów wektora niewiadomych z redukcją wsteczną podczas rozwiązywania układów liniowych.
W przygotowaniu:
- loop unrolling
- loop invariant code motion
- (a+b)*(c+d) using 3 muls
- Użycie dużych typów danych: long long, __int64
- const ułatwia pracę kompilatora i programistów, a-=b zamiast a=a-b
- Horner i metody szybsze niż Horner
- returning by const value vs direct reference filling
- fixed floating point aritmetics
- unikanie aliasing, restrict keyword
- unikanie exceptions
- unikanie virtual functions, rtti
- 2D array indexing methods
- arithmetic non-portable MSVC++ functions
Koprocesor arytmetyczny Intel a funkcje biblioteczne C++
Warto wiedzieć, które standardowe funkcje języka C++ są tylko wywołaniem swoich towarzyszy, a które mają poważną podstawę w sprzęcie. Jeśli faktycznie dane funkcje używają sprzętu, są prawdopodobnie szybsze od programowego przybliżenia funkcjami Padé. Oto lista ważnych instrukcji koprocesora arytmetycznego obecnego
w serii procesorów Pentium i kompatybilnych (lista dla koprocesorów Intel serii 8087/287/387/486):
FABS - Wartość bezwzględna
FADD - Dodaje liczby rzeczywiste
FADDP - Dodaje liczbę rzeczywistą i usuwa ją ze stosu
FBLD - Ładuje liczbę dziesiętną upakowaną
FBSTP - Zapamiętuje liczbę dziesiętną upakowaną i usuwa ze stosu
FCHS - Zmienia znak liczby
FCLEX, FNCLEX - Zeruje znacznik odstępstwa
FCOM - Porównuje liczby rzeczywiste
FCOMP - Porównuje liczby rzeczywiste i usuwa wierzchołek stosu
FCOMPP - Porównuje liczby rzeczywiste i usuwa je ze stosu
FCOS - Cosinus ST(0)
FDECSTP - Zmniejsza wskaźnik stosu
FDISI, FNIDISI - Wyłącza przerwania
FDIV - Dzieli liczby rzeczywiste
FDIVP - Dzieli liczbę rzeczywistą i usuwa ze stosu
FDIVR - Dzieli odwrotnie liczby rzeczywiste
FDIVRP - Dzieli odwrotnie liczby rzeczywiste i usuwa je ze stosu
FENI, FNEI - Zezwala na przerwania
FREE - Zwalnia rejestr
FIADD - Dodaje liczby całkowite
FICOM - Porównuje liczby całkowite
FIDIV - Dzieli liczby całkowite
FIDIVR - Dzieli odwrotnie liczby całkowite
FILD - Ładuje liczbę całkowitą
FIMUL - Mnoży liczbę całkowitą
FINCSTP - Zwiększa wskaźnik stosu
FINIT, FININIT - Inicjuje procesor
FIST - Zapamiętuje liczbę całkowitą
FISTP - Zapamiętuje liczbę całkowitą i usuwa ją ze stosu
FISUB - Odejmuje liczby całkowite
FISUBR - Odejmuje odwrotnie liczby całkowite
FLD - Ładuje liczbę rzeczywistą
FLDCW - Ładuje słowo kontrolne
FLDENV - Ładuje środowisko
FLDLG2 - Ładuje logarytm dziesiętny z 2
FLDLN2 - Ładuje logarytm naturalny z 2
FLD2E -Ładuje logarytm dwójkowy z liczby e (~2,71)
FLDL2T - Ładuje logarytm dwójkowy z 10
FLDPI - Ładuje liczbę pi (~3.14)
FLDZ - Ładuje liczbę 0.0
FLD1 - Ładuje liczbę 1.0
FMUL - Mnoży liczby rzeczywiste
FMULP - Mnoży liczby rzeczywiste i usuwa je ze stosu
FNOP - Instrukcja pusta, nic nie robi
FPATAN - Częściowy Arcustangens
FPREM - Częściowa reszta
FPREM1 - Częściowa reszta
FPTAN - Częściowy tangens
FRNDINT - Zaokrągla do liczby całkowitej
FRSTOR - Ładuje zapamiętany stan
FSAVE, FNSAVE - Zapamiętuje stan
FSCALE - Skaluje
FSETPM - Przechodzi w tryb wirtualny
FSIN - Sinus ST(0)
FSINCOS - Sinus i Cosinus ST(0)
FSQRT - Pierwiastek kwadratowy
FST - Zapamiętuje liczbę rzeczywistą
FSTCW, FNSTCW - Zapamiętuje słowo kontrolne
FSTENV, FNSTENV - Zapamiętuje środowisko
FSTP - Zapamiętuje liczbę rzeczywistą i usuwa ją ze stosu
FSTSW, FNSTSW - Zapamiętuje słowo stanu
FSTSW AX, FNSTSW AX - Zapamiętuje słowo stanu do AX
FSUB - Odejmuje liczby rzeczywiste
FSUBP - Odejmuje liczbę rzeczywistą i usuwa ją ze stosu
FSUBR - Odejmuje odwrotnie liczby rzeczywiste
FSUBRP - Odejmuje odwrotnie liczbę rzeczywistą i usuwa ją ze stosu
FTST - Sprawdza, czy wierzchołek stosu==0.0
FUCOM - Porównuje
FUCOMP - Porównuje i usuwa ze stosu
FUCOMPP - Porównuje i usuwa dwukrotnie ze stosu
FWAIT - CPU czeka, gdy 80x87 jest zajęty
FXAM - Sprawdza wierzchołek stosu
FXCH - Wymienia rejestry
FXTRACT - Rozdziela cechę i mantysę
FYL2X - Y*logarytm dwójkowy z X
FYL2XP1 - Y*logarytm z (X+1)
F2XM1 - 2X-1
Instrukcje wyróżnione wytłuszczoną czcionką są odpowiedzialne za nietrywialne operacje arytmetyczne
i w celu przyśpieszenia kodu można poszukać funkcji C++ liczących dokładnie to co owe instrukcje. Niestety, większość z nich jest zdecydowanie niestandardowa i występują głównie w kompilatorach Microsoftu. Proszę zwrócić uwagę na FSINCOS pozwalającą na jednoczesne liczenie sinusa i cosinusa danego kąta, FTST wskazuje na przyśpieszone porównywanie liczb zmiennoprzecinkowych z zerem, natomiast o odpowiednikach FXTRACT, FYL2X, FYL2XP1 i F2XM1 jako funkcjach standardowych C++ można co najwyżej pomarzyć.
Że nie zawsze funkcja standardowa ma sens przekonuje nas hypot(double x, double y), według wszelkich standardów równoważny sqrt(x*x+y*y), tymczasem na wszystkich kompilatorach jakie znam jest ona wolniejsza co najmniej dwukrotnie od sqrt(x*x+y*y). I nie należało się spodziewać cudów, bo koprocesor nie wspomaga jeszcze tego obliczenia. Szkoda tylko że ktoś tak zepsuł specyfikację tej ważnej funkcji: hypot zawiera dodatkowe sprawdzenie, czy oba argumenty są niezerowe (także w czasie najbardziej optymalizowanych kompilacji), co ma w zasadzie sens przy liczeniu długości przeciwprostokątnej, tyle że wynik i tak pozostaje bez zmian nawet przy ujemnych argumentach.
Zatem
hypot(x, y)
zamieniamy na:
sqrt(x*x+y*y)
napisał Krzysztof Bosak, www.kbosak.prv.pl, kbosak@box43.pl