W poprzednim poście krótko opisałem, jak używać linuxowego narzędzia profilującego gprof. Tym razem pokażę Ci, jak łatwo wykorzystać to narzędzie w praktyce!
Przykład optymalizacji na 300%
Pokażę Ci, jak przyspieszyć prosty program sortujący. Program ten wypełnia tablicę liczbami (rosnąco, od 0 do n), a następnie sortuje ją malejąco. Oto on:
// sortownica.cpp // ilość elementów do posortowania const int ELEMENT_COUNT = 100000; // zamiana wartości dwóch zmiennych void swapInts(int &a, int &b) { int a_tmp = a; a = b; b = a_tmp; } // wypełnianie tablicy (rosnąco) void fillArray(int array[], int length) { for (int i = 0; i < length; i++) array[i] = i; } // sortowanie tablicy (malejąco) void sortArray(int array[], int length) { for (int i = 0; i < length; i++) for (int j = 0; j < i; j++) if (array[i] > array[j]) swapInts(array[i], array[j]); } // main entry point int main() { int array[ELEMENT_COUNT]; fillArray(array, ELEMENT_COUNT); sortArray(array, ELEMENT_COUNT); return 0; }
Wspaniały, prawda :)
Z zegarkiem w ręku sprawdziłem, że na moim komputerze (C2D 1,83GHz) wykonuje się około 65 sekund. To trochę długo… Spróbujemy więc przyspieszyć jego działanie:
- Najpierw sprofilujemy go narzędziem gprof, żeby sprawdzić, co go spowalnia
- Następnie poprawimy kod
- Na koniec sprofilujemy program ponownie, żeby zobaczyć, czy mamy przyspieszenie
Do roboty!
1. Profilujemy program narzędziem gprof
Zeby dowiedzieć się, co w naszym programie stanowi “kulę u nogi”, musimy go sprofilować. W tym celu najpierw kompilujemy go z flagą -pg, następnie go odpalamy, a na koniec wyświetlamy wyniki profilowania narzędziem gprof. Sprowadza się to do wykonania trzech poleceń:
> g++ -O2 -pg -o sortownica sortownica.cpp > ./sortownica > gprof -b -p sortownica
A oto, co ukazuje się naszym oczom:
% cumulative self self total
time seconds seconds calls s/call s/call name
53.10 34.19 34.19 704982704 0.00 0.00 swapInts(int&, int&)
42.73 61.71 27.52 1 27.52 61.71 sortArray(int*, int)
4.57 64.65 2.94 frame_dummy
0.00 64.65 0.00 1 0.00 0.00 fillArray(int*, int)
Krótkie, konkretne podsumowanie. Już z pierwszej linijki widać, w czym tkwi problem – funkcja swapInts jest wywoływana ponad 700 milionów razy i zajmuje ponad połowę (53.10%) czasu wykonania aplikacji ! To wyraźnie prosi się o optymalizację, nie sądzisz?
2. Poprawiamy kod
Spróbujmy przyspieszyć działanie aplikacji. Ponieważ funkcja swapInts jest bardzo krótka (zaledwie 3 linijki kodu) i wywoływana bardzo wiele razy, zadeklarujemy ją jako inline:
// sortownica.cpp ... // zamiana wartości dwóch zmiennych inline void swapInts(int &a, int &b) { int a_tmp = a; a = b; b = a_tmp; } ...
A teraz zobaczmy, czy poprawiło to szybkość działania aplikacji…
3. Ponownie profilujemy program
Najpierw ponawiamy testy na naszym nowym, zoptymalizowanym kodzie:
> g++ -O2 -pg -o sortownica sortownica.cpp > ./sortownica > gprof -b -p sortownica
Następnie – porównujemy wyniki::
% cumulative self self total
time seconds seconds calls s/call s/call name
100.42 18.08 18.08 1 18.08 18.08 sortArray(int*, int)
0.00 18.08 0.00 1 0.00 0.00 global constructors keyed to _Z9fillArrayPii
0.00 18.08 0.00 1 0.00 0.00 fillArray(int*, int)
Jak widzisz, funkcja swapInts znikła z listy – kompilator wcielił ją do funkcji sortArray. Dzięki temu zeszliśmy z całkowitego czasu wykonania aplikacji równego 64 sekuny do zaledwie 18 sekund! Nawet sama funkcja sortArray zyskała na czasie – wcześniej aż 9 sekund kosztowało ją wywoływanie swapInts. Uzyskaliśmy trzykrotne przyspieszenie, a zmieniliśmy tylko jedną linijkę… Jest moc, prawda?
Podsumowanie
Profilowanie kodu pozwoliło nam bardzo szybko znaleść i poprawić funkcję winną spowolnieniu aplikacji. W rezultacie – udało się nam przyspieszyć aplikację o ponad 300%! Mam nadzieję, że ten przykład wystarczy Ci, byś docenił możliwości profilowania. Mi wystarcza w zupełności ;)
March 19th, 2011 on 08:36
chmmm. ciekawe to jest!
szkoda że jestem zmuszony do używania C.
aleee, hehe. mam timerek pracujący z rozdzielczością 1Mhz, więc mam pomiar czasu do 1us, plus 2 sprytne makra wstawiane na początku i końcu każdej funkcji dające pomiar czasu wykonania i wypisujące na terminal maksimum. pozornie może i niewiele, ale dla mnie i tak super. np. przeniesienie czcionek z pamięci wewnętrznej do zewnętrznej spowolniło wypisywanie tekstu chyba 5 razy :(
nie do zauważenia, ale… dobrze wiedzieć że taka duża zmiana czasu wykonania miała miejsce ;)
March 19th, 2011 on 08:38
BTW Borland (ja wciąż używam) ma taką opcję że program po zakończeniu tworzy plik tekstowy z listą używanych funkcji. Tylko do tej pory nie wiem gdzie dokładnie to się aktywuje w opcjach.
March 19th, 2011 on 08:40
zastanawia mnie też czy wypełnianie tablicy
for (int i = 0; i < length; i++)
array[i] = i;
nie jest wolniejsze od
for (int i = 0; i < length; i++)
*p_array++ = i;
??
March 21st, 2011 on 08:31
@mario
z ciekawości zrobiłem test.
dla g++ (GCC) 4.1.2 20071124 (Red Hat 4.1.2-42) z flagami g++ -O2 -S
dostałem odpowiednio takie dwie realizacje obu metod (tablica typu int, size = 1024):
1. notacja tablicowa
for (int i = 0; i < size; i++) array[i] = i; ASM: (eax = i, edx = size, ecx = poczatek tablicy) .L4: movl %eax, (%ecx,%eax,4) addl $1, %eax cmpl %edx, %eax jne .L4 2. notacja wskaźnikowa int* ptr = array; for (int i = 0; i < size; i++) *ptr++ = i; ASM: (eax = ptr, edx = i, ecx = size) .L11: movl %edx, (%eax) addl $1, %edx addl $4, %eax cmpl %ecx, %edx jne .L11 Czyli: notacja tablicowa, nie dość że bardziej czytelna, to wymaga jednej instrukcji mniej do realizacji.