*




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 kucharskieSztukę 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. Tablica jest przekazana przez wartość, wszystkie
jej elementy są przesyłane na stos: void funkcja(const double
tablica[3][3]) { // tylko odczyt tablicy} Należy podać referencję do tej
tablicy (ale nie &tablica[3][3], co byłoby tablicą dziewięciu referencji,
niepoprawne): void funkcja(const double (&tablica)[3][3]) { //
bez zmian! } * * * Użycie bardzo małej tablicy (aż do rozmiaru 5x5) jest
niewskazane, indeksowanie wydłuża dostęp do zmiennych: void
funkcja(double (&tablica)[2][2]) { // cokolwiek, nawet zapis do
tablicy, np. tablica[1][0]=tablica[0][1]; } Należy zdefiniować prostą strukturę: struct TABLICA2X2
{e00, e01, e10, e11}; void funkcja(TABLICA2x2
&tablica) { // zmiana: tablica.e10=tablica.e01; }
* * *
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 = 8int
e=(f<<2)+f; // Nawiasowanie jest tu konieczne!



// Priorytet
<< i >> jest niższy niż + // Możliwe też int e=f+f+f w tym
szczególnym przypadkuint
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^6Sztuczka 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żenieclass 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++ functionsKoprocesor 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 rzeczywisteFADDP
- Dodaje liczbę
rzeczywistą i usuwa ją ze stosuFBLD - Ładuje liczbę dziesiętną
upakowanąFBSTP - Zapamiętuje liczbę dziesiętną upakowaną i usuwa ze
stosuFCHS - Zmienia
znak liczbyFCLEX,
FNCLEX - Zeruje znacznik odstępstwaFCOM - Porównuje liczby rzeczywisteFCOMP -
Porównuje liczby rzeczywiste i usuwa wierzchołek stosuFCOMPP - Porównuje liczby rzeczywiste i usuwa je ze
stosuFCOS - Cosinus ST(0) FDECSTP - Zmniejsza wskaźnik
stosuFDISI, FNIDISI - Wyłącza przerwaniaFDIV - Dzieli liczby rzeczywisteFDIVP - Dzieli liczbę
rzeczywistą i usuwa ze
stosuFDIVR - Dzieli odwrotnie liczby rzeczywisteFDIVRP -
Dzieli odwrotnie liczby rzeczywiste i usuwa je ze stosuFENI, FNEI -
Zezwala na przerwaniaFREE - Zwalnia rejestrFIADD - Dodaje liczby
całkowiteFICOM -
Porównuje liczby
całkowiteFIDIV - Dzieli liczby całkowiteFIDIVR - Dzieli
odwrotnie liczby całkowiteFILD - Ładuje liczbę całkowitąFIMUL
- Mnoży liczbę całkowitąFINCSTP - Zwiększa wskaźnik
stosuFINIT, FININIT -
Inicjuje procesorFIST
- Zapamiętuje liczbę całkowitąFISTP - Zapamiętuje liczbę całkowitą i
usuwa ją ze stosuFISUB - Odejmuje liczby całkowiteFISUBR - Odejmuje odwrotnie liczby
całkowiteFLD - Ładuje liczbę rzeczywistąFLDCW - Ładuje słowo kontrolne FLDENV
- Ładuje
środowiskoFLDLG2 - Ładuje logarytm dziesiętny z
2
FLDLN2 - Ładuje logarytm naturalny z 2FLD2E - Ładuje logarytm dwójkowy z liczby e
(~2,71) FLDL2T
- Ładuje logarytm
dwójkowy z 10FLDPI - Ładuje liczbę pi (~3.14) FLDZ - Ładuje liczbę
0.0FLD1 - Ładuje liczbę 1.0FMUL - Mnoży
liczby rzeczywisteFMULP - Mnoży liczby rzeczywiste i usuwa je ze
stosuFNOP - Instrukcja
pusta, nic nie robiFPATAN - Częściowy ArcustangensFPREM - Częściowa
resztaFPREM1 - Częściowa
resztaFPTAN -
Częściowy
tangensFRNDINT - Zaokrągla
do liczby całkowitejFRSTOR - Ładuje zapamiętany stanFSAVE, FNSAVE - Zapamiętuje stanFSCALE - SkalujeFSETPM -
Przechodzi w tryb wirtualnyFSIN - Sinus ST(0) FSINCOS - Sinus i
Cosinus ST(0) FSQRT - Pierwiastek kwadratowyFST - Zapamiętuje liczbę rzeczywistąFSTCW, FNSTCW
- Zapamiętuje
słowo kontrolneFSTENV,
FNSTENV - Zapamiętuje środowiskoFSTP - Zapamiętuje liczbę rzeczywistą i usuwa ją ze
stosuFSTSW,
FNSTSW - Zapamiętuje słowo stanuFSTSW AX, FNSTSW AX -
Zapamiętuje słowo stanu do AXFSUB - Odejmuje liczby rzeczywisteFSUBP
- Odejmuje liczbę
rzeczywistą i usuwa ją ze stosuFSUBR - Odejmuje odwrotnie liczby rzeczywisteFSUBRP - Odejmuje odwrotnie liczbę
rzeczywistą i usuwa ją ze stosuFTST - Sprawdza,
czy wierzchołek stosu==0.0FUCOM - PorównujeFUCOMP - Porównuje i usuwa ze
stosuFUCOMPP - Porównuje i usuwa dwukrotnie ze stosuFWAIT - CPU czeka, gdy 80x87 jest
zajętyFXAM - Sprawdza wierzchołek stosuFXCH - Wymienia rejestryFXTRACT - Rozdziela cechę i
mantysęFYL2X -
Y*logarytm dwójkowy z XFYL2XP1 - Y*logarytm z (X+1) F2XM1 -
2X-1Instrukcje 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. Zatemhypot(x, y) zamieniamy na: sqrt(x*x+y*y)
napisał Krzysztof Bosak, http://kbosak.republika.pl, [e-mail]