Temat wykladu:
C/C : Optymalizacja w C/C (by Gynvael Coldwind, 2007-05-08) @ wyklady.net
Komentarze: http://forum.wyklady.net/index.php?topic=107
18:04GynvaelWitam wszystkich na moim pierwszym wykladzie w nowym sezonie ;>
GynvaelWyklad bedzie dotyczyc zagadnien optymalizacji (glownie pod katem szybkosci dzialania) oprogramowania pisanego w C/C++
18:06GynvaelJeszcze 3 slowa o mnie, tak w ramach przedstawienia sie... jestem Gynvael Coldwind, pracuje jako reverse engineer i programista w hiszpanskiej firmie zajmujacej sie bezpieczenstwem klientow roznych bankow ;>
GynvaelObecnie skonczylem studia na politechnice wroclawskiej (informatyka) i czekam na obrone pracy inzynierskiej ;>
Gynvaelok tyle ;>
Gynvaelteraz kwestia organizacyjna...
Gynvaelpytania na privie, co ciekawsze bede tu przeklejac i odpowiadac
18:07Gynvaelna reszte postaram sie odpowiedziec na privie ;>
GynvaelZaczne od definicji, co to jest optymalizacja... nie bede oryginalny i posluze sie wiki
18:08GynvaelOptymalizacja to metoda wyznaczania najlepszego rozwišzania (poszukiwanie ekstremum funkcji) z punktu widzenia okreslonego kryterium (wskaznik) jakosci (np. kosztu, drogi, wydajnosci).
Gynvael(będzie głównie o optymalce pod wzgledem predkosci)
Gynvaelw stosunku do oprogramowania mowimy tak na prawde o trzech wariantach optymalizacji:
Gynvael
18:09Gynvael- optymalizacja pod wzgledem predkosci dzialania, czyli stanowczo najpopularniejsza ;>
Gynvael- optymalizacja pod wzgledem zuzycia pamieci, tzn tak zeby oprogramowanie zuzywalo jej jak najmniej
Gynvael- oraz optymalizacja pod wzgledem wielkosci kodu (i/lub danych)
18:10GynvaelTrojkat na powyzszym obrazku nalezy interpretowac w nastepujacy sposob:
GynvaelCzym bardziej zblizamy sie do ktoregos z rogow trojkata, tym bardziej oddalamy sie od reszty
18:11GynvaelPrzykladowo, jesli chcemy uzyskac duza predkosc dzialania, to prawdopodobnie bedziemy musieli naduzyc kodu (patrz loop unrolling o ktorym bedzie troszke pozniej), lub np pamieci (patrz lookup tables o ktorych tez bedzie pozniej)
18:12GynvaelIdac w druga strone, jesli chcemy miec maly kod wynikowy, to prawdopodobnie bedziemy musieli skorzystac np. z kompresji, a dekompresja szybka nigdy nie byla, po za tym zuzywa troche pamieci
18:13GynvaelTeraz takie odpowiedz na takie male pytanie.. po co w zasadzie optymalizowac
GynvaelPo co optymalizowac wielkosc kodu ?
GynvaelAlbo inaczej, kiedy warto/trzeba ?
18:14Afro_PLkiedy kod jest zbyt duzy i wydluza czas pracy
Gynvael- jesli piszemy pod bardzo specyficzna platforme na ktorej jest bardzo malo miejsca na kod
MeMeKdawno sie zaczelo?
Gynvaelnp chcemy napisac nowy BIOS z super mega ficzerami na stary komp ktory ma kostki po 4kb... auc
18:15GynvaelMeMeK 10 minut temu
Gynvaelalbo piszemy shellcode do wysploitowania jakiegos progsa a bufor (z roznych przyczyn) ma dokladnie 256 bajtow...
Gynvael- for fun...
18:16Gynvaelprzykladem for fun moze byc demoscena na ktorej bardzo popularne sa produkcje typu intro4k czy intro64k
Gynvaelwarto rzucic okiem np na http://awards.scene.org/
18:17Gynvaelinnym przykladem moze byc gra .kkrieger, zajmujaca ponizej 100kb, a grafika doroownujaca takim produkcja jak Unreal czy nawet Unreal 2
Gynvaelhttp://www.theprodukkt.com/
18:18Gynvaelpo za tym czasem na ircu zbierze sie grupa ludzi i mysli jak cos napisac tak zeby dostac jak najmniejsza ilosc kodu wynikowego
Gynvaelprzykladowo w przeciagu ostatniego roku bralem udzial w dwoch takich konstruktywnych -zabawach- ;>
Gynvaelpierwsza polegala na napisaniu procedury zmiany wartosci (int) na string'a zapisanego w HEX'a
Gynvaelczyli np 123 na 7B
18:19Gynvaelz tego co pamietam to udalo nam sie zejsc ponizej 20 bajtow
Gynvaelostatnio za sprawa fr3m3na tworzylismy kompilatory jezyka Brainfuck, tak zeby byly jak najmniejsze
Gynvaeladam_i uzyskal wynik 126 bajtow
18:20Gynvaelok dalej
GynvaelPo co optymalizowac pod wzgledem wielkosci uzywanej pamieci
Gynvael- pamiec nawet teraz jest ograniczona... caszem piszemy jakies wieeelkie obliczenia ktore najchetniej by zjadly 20gb ramu.. jako ze nie kazdy tyle ma, to trzeba optymalizowac
18:21Gynvael- na niektorych systemach wbudowanych (embedded) pamieci nie ma za duzo, przykladem moga byc na przyklad komoorki ktore dopiero ostatnio maja wiecej niz 1mb pamieci
Gynvaelskala optymalizacji tutaj jest tak na prawde rozna
18:22Gynvaelmozemy czasem walczyc o 1gb
Gynvaela innym razem o 5 bajtow
GynvaelA po co optymalizowac jesli chodzi o szybkosc ?
Gynvaelto chyba kazdy wie ;> jednak lepiej miec 100 fps w Quake 3 niz 15 ;>
18:23Gynvaelniektorzy nieslusznie uwazaja ze skoro mamy super sprzety to nie trzeba optymalizowac
Gynvaelnie jest to do konca prawda ;>
Gynvaelsprzet jest szybki, ale jeszcze nie na tyle by mozna kompletnie zaniedbac optymalizacje
Gynvaelprzykladem moze byc raytracing i rendering np w takim 3D Max
18:24Gynvaelszybszy sprzet co najwyzej liniowo poprawi czas renderowania
Gynvaelzamiast 1h bedziemy czekac 30 minut
Gynvaelale jesli ktos z programistow wpadnie na jakis pomysl co mozna dobrze zoptymalizowac
Gynvaelto to 1h moze zejsc i do 2 minut
18:25GynvaelTeraz takie dwie wazne rzeczy jesli chodzi o optymalizacje
Gynvaelnajpierw cytat (by Donald Knuth): "przedwczesna optymalizacja jest zrodlem wszelkiego zla"
Gynvaelchodzi glownie o to ze optymalizacja na pewno nie poprawia czytelnosci kodu, ani dla nas, ani dla kompilatora
Gynvael(mowie o tej recznej)
18:26Gynvaelciekawostka od darkjames'a
Gynvael<darkjames> http://www.catb.org/~esr/writings/taoup/html/ch12s01.html
Gynvael<darkjames> [113] The eighteen-month doubling time usually quoted for Moore's Law implies that you can collect a 26% performance gain just by buying new hardware in six months.
Gynvael;>
Gynvaelona dotyczy w sumie drugiej rzeczy
Gynvaelmianowicie czasem po prostu nie warto optymalizowac
18:27Gynvaeljesli koszt wynajecia programisty ktory przeprowadzi optymalizacje jest wiekszy niz spodziewany zysk
Gynvaelto po prostu nie warto tego robic
18:28GynvaelCo do samej optymalizacji
Gynvaelto optymalizowac mozemy na roznych poziomach
Gynvaelna samej gorze jest optymalizacja ktora wykonujemy juz na poziomie projektowania oprogramowania
Gynvaelw momencie kiedy decydujemy np ze uzyjemy C++ bo jest szybszy niz Java
18:29Gynvaelczy Java bo ma mniejsze binarki niz VB
Gynvaelniz JPG bo zajmuje mniej miejsca niz BMP
Gynvaelpozniej, w momencie planowania implementacji
Gynvael(lub pozniej w ramach procesu optymalizacji)
18:30Gynvaelprzychodzi moment wyboru algorytmu
18:31Gynvaelmusimy byc swiadomi w tym momencie tego ze np sortowanie babelkowe sie pisze szybko milo i przyjemnie
Gynvaelale jest duzo wolniejsze niz np quick sort
Gynvaelmusimy byc rowniez swiadomi ze radix sort moze byc szybszy niz quick sort ;>
18:32Gynvaelna koncu mamy optymalizacje na poziomie implementacji
Gynvaela w zasadzie dwa rodzaje
Gynvaelpierwszy polega na stosowaniu znanych sztuczek dzialajacych w danym jezyku (language-specific)
18:33-!-Netsplit krakow.ircnet.pl <-> katowice.ircnet.pl quits: _m, d0b0c0p, Requel
Gynvaela drugi na zblizenie sie do platformy na ktora piszemy, wykorzystanie jej mozliwosci poprzez sformuowanie kodu w najbardziej optymalny dla niej sposob (np wykorzystanie pipeliningu, SSE)
18:34Gynvaelmusimy jednak pamietac ze zbytnie zblizenie sie do platformy bardzo utrudnia przenoszenie programow pozniej
18:36GynvaelSSE <=- chodzilo mi o Streaming SIMD Extension, czyli rozszerzenie procesora wspomagajace powtarzajace sie operacje na duzych partiach danych (technicznie wyglada to tak ze naraz sie robi np dodawania na 4rech floatach zamiast na jednym)
GynvaelSSE, MMX, etc to temat na oddzielnny wyklad wiec sie zaglebial nie bede
Gynvaelok koniec teorii ;>
18:37GynvaelReszta wykladu bedzie poswiecona optymalizowaniu pod wzgledem szybkosci dzialania
-!-Netsplit torun.ircnet.pl <-> katowice.ircnet.pl quits: _m, d0b0c0p, Requel
GynvaelWiec tak, po pierwsze istnieja programy ulatwiajace lokalizowanie miejsc ktore trzeba zoptymalizowac
18:38GynvaelSa to tzw profilery... do pakietu gcc jest dostepny profiler gprof
Gynvaelpo za tym Intel wydal swoj VTune (niestety platny, ale mozna eval. version sciagnac)
Gynvaeldodatkowo pod *nixy zostal stworzony profiler Valgrind
18:39Gynvaeltaki profiler zazwyczaj umie wskazac ktora funkcja jest najwiecej razy wywolywana, ktora na najdluzszy okres czasu "zjada" procesor etc
18:40Gynvaeloprocz profilerow warto miec swoje jakies procedurki ktore mierza czas / ilosc cykli procesora
Gynvaelna potrzeby tego wykladu bede stosowal http://vexillium.org/~gynvael/opt/rtdsc.c oraz http://vexillium.org/~gynvael/opt/speed.h
18:41Gynvaelrtdsc.c zawiera wrapper na polecenie RTDSC ktora zwraca ilosc wykonanych do tej pory cykli procesora
18:42Gynvaelspeed.h zawiera funkcje tcount()... w momencie drugiego wywolania funkcji na STDERR pojawia sie informacje ile czasu minelo od poprzedniego wywolania tcount()
Gynvaelrtdsc() bede uzywal do obliczenia roznicy przed i po rozpoczeciu kodu
Gynvaelobie te metody NIE SA obiektywne, a tym bardziej precyzyjne
Gynvaelnatomiast wystarczaja zeby odpowiedziec na pytanie "czy kod dziala szybciej"
18:44Gynvaelbart^xt zauwazyl ze rtdsc moze klamac na wieloprocesorowych stacjach
Gynvael;>
18:45Gynvaelniemniej jednak na kompie na ktorym teraz -siedze- mam jeden core, wiec wyniki ktore bede podawac beda wmiare ok ;>
Gynvaelrtdsc ofc jest platform-specyfic... tzn x86
Gynvael;>
Gynvaeldobra
18:46Gynvaela teraz bedzie krotka lista wmiare standardowych trikow na zoptymalizowanie kodu, wraz z przykladami i pomiarami
18:47Gynvael1. Lookup table
Gynvaelhttp://vexillium.org/~gynvael/opt/opts4.c
Gynvaelsytuacja wyglada tak
18:48Gynvaelmamy jakies 'j' ktore jest zmienne i przyjmuje wartosci od 0 do 25
18:49Gynvaelw zaleznosci od tego co przyjmie 'j', do zmiennej 'g' dodajemy jakas wartosc
18:50Gynvaelmusimy sprawdzic co 'j' przyjelo i odpowiednio zareagowac
Gynvaelw kodzie jest switch/case
Gynvaelkod jest wykonywany 100mln razy, tak zeby bylo co mierzyc
GynvaelTICKS: 000001578 TIME: 1.57800 sec
GynvaelRDTSC DIFF: 2360008915
Gynvaelu mnie kod wykonuje sie 'tyle'
Gynvaelpytanie brzmi 'jak mozna to zoptymalizowac'
18:51Gynvaelniektorzy ucza zeby zamiast 'switch/case' dac else/if, ale to jest zly pomysl;> o tym za chwile
Gynvaelmozna jednak stworzyc tablice z wartosciami
Gynvaeli zrobic tablica[j % 26]
Gynvaela dokladniej g += tablica[j % 26];
Gynvaelzaoszczedzi to paru porownan i paru skokow
18:52Gynvaelhttp://vexillium.org/~gynvael/opt/opts5.c
Gynvaeltak wyglada zoptymalizowany kod
GynvaelTICKS: 000001468 TIME: 1.46800 sec
GynvaelRDTSC DIFF: 2191607761
Gynvaeli faktycznie wykonuje sie odrobine szybciej
Gynvaelpowstaja dwa pytania
18:53Gynvael1) czemu tylko tyle
Gynvael2) czemu nie if/else
Gynvael1) <=- nowoczesne kompilatory w przypadku switch i wartosci kolejnych tworza tak zwane jump tables, czyli tablice z pointerami adresow
Gynvaeli w domysle wykonywane jest goto adres_skoku[j % 16]
18:54Gynvaela to jest po prostu szybkie, jako ze jedyne porownanie jakie kompilator tam wrzuci to czy j nie jest czasem mniejszy od 0 lub wiekszy od 26
Gynvael% 26 tam
Gynvael* 25
18:55Gynvael2) a zapiszmy to za pomoca if/else i zobaczmy
Gynvaelhttp://vexillium.org/~gynvael/opt/opts6.c
GynvaelTICKS: 000003953 TIME: 3.95300 sec
GynvaelRDTSC DIFF: 1621625649
Gynvaelauc, ponad 2 razy gorzej
Gynvaelkompilator domyslnie przerobi to na serie sprawdzen i skokow
Gynvaela to szybkie nie jest
18:56Gynvaelczasem jednak trafimy na kompilator ktory jest przyglupawy i nie umie w przypadku switcha zrobic jump table
Gynvaelwtedy mozemy sprobowac zrobic if/elseif, ale w sposob przypominajacy drzewo
Gynvaelna poczatek, podzielmy te wszystkie ify na czesc mniejsza od 13 i reszte
18:57Gynvaelhttp://vexillium.org/~gynvael/opt/opts7.c
GynvaelTICKS: 000003187 TIME: 3.18700 sec
GynvaelRDTSC DIFF: 495542677
Gynvaeljak widac jest lepiej
Gynvaelidzmy o krok dalej i zromy kolejne podzialy
18:58Gynvaelhttp://vexillium.org/~gynvael/opt/opts8.c
Gynvaeljak widac teraz dodatkowo dzielone jest na galaz mniejsza od 6 i reszte
Gynvaeloraz mniejsza od 19 i reszte
Gynvaelpodzial na <13 nadal zostal
GynvaelTICKS: 000002765 TIME: 2.76500 sec
GynvaelRDTSC DIFF: 4130054772
18:59Gynvael2.765sec jest lepsze niz 3.953
Gynvaelmozna isc z tym podzialem dalej
Gynvaelale niestety nie zblizymy sie ani do switch/case opartego na jump table
Gynvaelani do lookup table
19:00Gynvaelniemniej jednak warto o tym pamietac
Gynvaelok dalej ;>
19:01Gynvael3. (2 byla optymalizacja ifow) "aliasy" na parametry przekazywane pointerem
Gynvaelhttp://vexillium.org/~gynvael/opt/opts9.c
Gynvaelmamy taka sytuacje
19:02Gynvaelmamy funkcje func() ktora dostaje inta, przekazywanego pointerem
Gynvaelnastepnie 100mln razy przekazyje tego wartosc wskazywana przez ten pointer do funkcji dodaj
GynvaelTICKS: 000000937 TIME: 0.93700 sec
GynvaelRDTSC DIFF: 1420670838
Gynvaelproblemem tutaj tak na prawde jest to ze "*sth" wykonuje sie 100mln razy
19:03Gynvaelczyli 100mln razy procesor musi sprawdzic jaka wartosc ma pointer sth (tj odczytac ja z pamieci) a nastepnie odczytac z pamieci inta wskazyywanego przez sth
Gynvaelrozwiazaniem problemu jest stworzenie zmiennej lokalnej ktora raz na poczatku funkcji dostanie wartosc *sth
Gynvaela potem bedziemy uzywac tejze zmiennej zamiast *sth
19:04Gynvaelhttp://vexillium.org/~gynvael/opt/opts10.c
GynvaelTICKS: 000000875 TIME: 0.87500 sec
GynvaelRDTSC DIFF: 1317263034
Gynvael0.06 sec szybciej, nieduzo, ale zawsze cos
19:05Gynvaelnalepszy pameitac ze czasami liczymy czas obliczeniowy w godzinach, i to by moglo byc np 87 zamiast 93 godzin ;>
Gynvael6 godzin juz robi roznice ;>
Gynvael4. Natywne slowo maszyny
19:06Gynvaeljakos tak sie przyjelo ze WORD to 16 bitow, ale jest to w sumie niezgodne z prawda
GynvaelWORD jest typem natywnym dla danej platformy
Gynvaelpod dosem bylo to 16 bitow
Gynvaelpod winda slowo ma juz 32 lub nawet 64 bity
Gynvaeloperujac na natywnej wielkosci zmiennej (czyli na natywnym WORD) program dziala szybciej niz na wielkosciach mniejszych
19:08Gynvaelwezmy za przyklad jakas petle i wrzucmy w nia troche obliczen arytmetycznych
Gynvaelsiedze na maszynie 32 bitowej wiec jako odnosnik uzyje int'a
Gynvaelhttp://vexillium.org/~gynvael/opt/opts12.c
19:09GynvaelTICKS: 000002797 TIME: 2.79700 sec
GynvaelRDTSC DIFF: 4188994405
Gynvaelok, to teraz wrzuce zamiast int np short "bo jest mniejszy wiec szybciej bedzie sie liczyc" (wniosek nieprawdziwy, ale czesto wysnuwany)
Gynvaelhttp://vexillium.org/~gynvael/opt/opts11.c
GynvaelTICKS: 000003171 TIME: 3.17100 sec
GynvaelRDTSC DIFF: 461919159
Gynvaelhuh, wolniej
Gynvaelno to "char"
19:10Gynvaelhttp://vexillium.org/~gynvael/opt/opts13.c
GynvaelTICKS: 000003109 TIME: 3.10900 sec
GynvaelRDTSC DIFF: 361602909
Gynvaelszybciej, ale nadal wolno...
Gynvaelwniosek: int jest na prawde natywny dla maszyny, wiec jest szybszy
19:11GynvaelDeeTahPanLtah: Bita ? ;> nieee my nie bedziemy Bili intow zeby je przyspieszyc ;>
Gynvaelok dalej
Gynvael5. ALU > FPU
19:12GynvaelALU, czyli jednostka arytmetyczna od operacji na liczbach naturalnych/calkowitych jest szybszy niz FPU (czyli jednotska od floatow i double)
Gynvaeltest ?
Gynvaelzmienmy w powyzszych przykladach int na float
Gynvaelhttp://vexillium.org/~gynvael/opt/opts14.c
19:13Gynvaelchcecie to odpalcie ;>
Gynvaelprzed wykladem i sie 92 sekundy to wykonywalo
Gynvaelhehe
19:14Gynvaeljesli chodzi o precyzje obliczen
Gynvaelto float jest oczywiscie szybszy niz double
Gynvaela double niz long double
19:15GynvaelZdecydowanie najgorsza sytuacja jest gdy nie ma normalnego koprocesora FPU, i wszystkie floatingi sa emulowane
Gynvaelwtedy mozemy zapomniec wogoole o uzywaniu floatow
19:16Gynvaelzreszta, jesli mamy mozliwosc i nie potrzebujemy mega precyzji, to mozna sie przerzucic z floatow na inty
Gynvaeli powiedzmy dedykowac jeden bajt dla "liczby po przecinku"
Gynvaela pozostale 3 na czesc "przed przecinkiem" ;>
19:17Gynvael6. Loop jamming
Gynvaelloop jamming to po prostu laczenie petli
Gynvaelhttp://vexillium.org/~gynvael/opt/opts15.c
GynvaelTICKS: 000000984 TIME: 0.98400 sec
GynvaelRDTSC DIFF: 1466389555
Gynvaelpolaczenie petli w jedna
Gynvaeldaje lepszy rezultat
Gynvaelhttp://vexillium.org/~gynvael/opt/opts16.c
GynvaelTICKS: 000000562 TIME: 0.56200 sec
GynvaelRDTSC DIFF: 823512458
19:18Gynvaeljest to w sumie logiczne i oczywiste
Gynvaelnatomiast jest przypadek
Gynvaelkiedy dwie petle sa jednak szybsze niz jedna
Gynvaelmianowiscie jesli kodu w petli jest duuuzo
Gynvaelwtedy rozbicie na dwie petle moze dac lepszy efekt (ma to zwiazek z cachowaniem procka etc)
19:19Gynvael7. Loop unroling
Gynvaelto w sumie jest najstarsza technika pod sloncem ;>
Gynvaelhttp://vexillium.org/~gynvael/opt/opts1.c
Gynvaelmamy sobie duza tablie (20mln intow)
Gynvaeli chcemy ja zsumowac
19:20Gynvaelnajprostsze rozwiazanie to dodanie kazdego elementu w petli, jeden po drugim
GynvaelTICKS: 000000203 TIME: 0.20300 sec
GynvaelRDTSC DIFF: 307088127
Gynvaelloop unrolling polega na "rozwinieciu" petli w ten sposob zeby zamiast jednego dodawania w ciele byly np 4, i zeby zamiast i++ bylo i+=4
Gynvaelhttp://vexillium.org/~gynvael/opt/opts2.c
19:21GynvaelTICKS: 000000171 TIME: 0.17100 sec
GynvaelRDTSC DIFF: 255730705
19:22Gynvaeldlaczego tak jest ? zamiast 4rech i++ mamy jedno i+=4, i zamiast 4rech i < WIELKSOC mamy jedno
Gynvael8. Pipelining
Gynvaelto jest juz typowe platform-spec
Gynvaelmianowicie CPU ktore wiekszosc z nas ma w swoich kompach moze wykonac kilka operacji naraz
19:23Gynvaelpod warunkiem ze te operacje nie wymagaja nawzajem swoich wartosci
Gynvaelhttp://vexillium.org/~gynvael/opt/opts3.c
Gynvaelwezmy pod uwage taki kod
Gynvaelpetla nadal rozwinieta
Gynvaelale sumujemy do 4rech roznych zmeinnych
Gynvaela na koncu po petli je dodajemy do siebie
19:24Gynvaeldzieki temu sa to 4ry oddzielne operacje
Gynvaelktore moga byc wykonane jednoczesnie
GynvaelTICKS: 000000156 TIME: 0.15600 sec
GynvaelRDTSC DIFF: 214483353
19:25Gynvael9. Pointery
Gynvael<reqamst> dlaczego cpu automatycznie opts2 nie zrobi takiego triku w opts3?
19:26Gynvaelponiewaz w opts2 mamy 4ry razy uzyte sum +=.. wiec druga linia z sum += wymaga wyniku z pierwszej
Gynvaelw przypadku opts3 sum2 nie wymaga wyniku sum1
Gynvaelwiec nie musi na niego 'czekac'
19:27Gynvaelok
Gynvaeldalej
Gynvaelto w sumie blad robiony przez poczatkujacych
19:28Gynvaelhttp://vexillium.org/~gynvael/opt/opts17.c
Gynvaelmamy funkcje
Gynvaelktora potrzebuje pointer
Gynvael*ktora potrzebuje strukture
Gynvaelblad polega na tym ze przekazujemy strukture cala
Gynvaeli jest ona caaala kopiowana
Gynvaelmimo iz nie korzystamy z niej calej
19:29GynvaelTICKS: 000001375 TIME: 1.37500 sec
GynvaelRDTSC DIFF: 2070562285
Gynvaelgdybysmy skorzystali z pointera do przekazania structa
Gynvaelhttp://vexillium.org/~gynvael/opt/opts18.c
19:30GynvaelTICKS: 000000985 TIME: 0.98500 sec
GynvaelRDTSC DIFF: 1487939201
Gynvaelrezultat byl by lepszy
Gynvaelwracajac do loop unrolling
Gynvael<mik01aj> mam pytanko... czy to, ze rozwinelismy dokladnie 4 cykle petli ma znaczenie? czy dla 5 wynik bylby podobny?
19:31Gynvaelto kwestia poeksperymentowania
Gynvaelslyszalem rozne wersje, niektorzy polecali zeby do 4rech rozwijac
Gynvaelinni do 8
Gynvaelwarto sie tym pobawic i samemu okreslic ;>
19:32Gynvael10. Prekalkulacja wynikow / cache'owanie wynikow
Gynvaelco do cacheowania wynikow, @ przykald z sumowaniem (Ten w loop unroll uzyty)
19:33Gynvaelzalozmy ze takie sumowanie bylo by robione bardzo czesto
Gynvaelwtedy warto by zrobic to tylko raz, a potem pamietac wynik
Gynvaeli w miare zmian, aktualizowac ta sume
Gynvaelwtedy nie trzeba by jej znowu przeliczac
Gynvael;>
Gynvaela co do reszty
19:34Gynvaelwezmy jakas wolna operacja matematyczna...
Gynvaelhmm
Gynvaelhmm
Gynvaelsinus ;>
Gynvaelsinus, realizowany przez instrukcje FPU FSIN jest wolny
Gynvaelhttp://vexillium.org/~gynvael/opt/opts19.c
Gynvaelzalozmy ze musimy duuuzo razy jakas wartosc sinusa policzyc
GynvaelTICKS: 000001796 TIME: 1.79600 sec
GynvaelRDTSC DIFF: 2679071545
19:35Gynvaelzalozmy rowniez ze nie potrzebujemy wszystkich mozliwych katow
Gynvaelsin(0.00), sin(0.01), sin(0.02) etc co 0.01 nam wystarczy
Gynvaelmozna stworzyc tablice z wartosciami sin dla wszystkich tych wartosci
19:36Gynvaeltaka gdzie beda zapisane juz wczesniej wyliczone wyniki
Gynvaeltablica nie bedzie bardzo duza
Gynvaelhttp://vexillium.org/~gynvael/opt/opts20.c
Gynvaelwtedy zamiast f = sin(kat) bedziemy robic
Gynvaelf = sintab[314]; //sinf(3.14f);
Gynvaelczyli f = sintab[(int)(kat * 100)];
GynvaelTICKS: 000000093 TIME: 0.09300 sec
GynvaelRDTSC DIFF: 139743015
19:37Gynvael1.796 vs 0.093
Gynvaelroznica niemala
Gynvaelta metoda jest czesto w grach wykorzystywana
19:38Gynvaelhmm
Gynvaelczas sie powoli konczy
19:39Gynvaelale jeszcze o kilku metodach chcial bym powiedzeic
Gynvael11. wielowymiarowe tablice
Gynvaeljesli chcemy policzyc sume z wielowymiarowej tablicy
Gynvaelnp
Gynvaelint dane[2000][1000];
Gynvaelto NIE robimy tak:
19:40Gynvaelhttp://vexillium.org/~gynvael/opt/opts21.c
GynvaelTICKS: 000002750 TIME: 2.75000 sec
GynvaelRDTSC DIFF: 4094346580
Gynvaelbledem tutaj jest iteracja po kolumnach zamiast po wierszach
Gynvaelbaaardzo to psuje cache'owanie procesorowi
Gynvaelpoprawna wersja, czyli najpierw wiersze
Gynvaelto
Gynvaelhttp://vexillium.org/~gynvael/opt/opts22.c
GynvaelTICKS: 000001312 TIME: 1.31200 sec
GynvaelRDTSC DIFF: 1981093587
19:41Gynvaelpewne zrodla twierdza ze dobrze jest aby wiersz mial dlugosc potegi 2jki, nawet jesli to bedzie sie wiazalo z nadmiarowoscia
Gynvaelhttp://vexillium.org/~gynvael/opt/opts23.c
GynvaelTICKS: 000001312 TIME: 1.31200 sec
GynvaelRDTSC DIFF: 1959388872
Gynvaelw moim przypadku nie robi to jednak duzej roznicy
Gynvaelnatomiast mozemy splaszczyc ta tablice
Gynvaeltak zeby zamiast [2000][1000] otrzymac [2000*1000]
19:42Gynvaelhttp://vexillium.org/~gynvael/opt/opts24.c
GynvaelTICKS: 000001171 TIME: 1.17100 sec
GynvaelRDTSC DIFF: 1742240367
19:44Gynvaelok
Gynvaeljeszcze teraz kilka porad, juz bez przykladow
Gynvael- rekusja jest zla, nie uzywac, za duzo czasu sie traci na wywolanie funkcji
19:45Gynvael- jesli musimy czesto dzielic floata przez okreslona stala wartosc, lepiej wyliczyc wyrazenie 1.0f / wartosc wczesniej, i mnozyc przez nie
Gynvael- puts jest szybsze od printf, ale oczywiscie mniej elastyczne ;>
19:46Gynvael- jesli mamy plik z danymi, pliki binarne wymagaja mniej przetwarzania niz pliki tekstowe
Gynvael- inline czasami nie dziala, #define zawsze
Gynvael- w niektorych systemach jest funkcja mallopt gdzie mozemy ustawic opcje MAXFAST, wtedy alokacja pamieci via malloc dziala szybko
19:47Gynvaelad rekursja .. tak chodzi o rekurncje ;>
Gynvael- jesli mamy petla { funkcja() }, to warto to zmeinic na funkcja() { petla { } }
19:48Gynvael- cache w CPU jest podzielony na male bloczki... jesli trzymamy zmienne z ktorych czesto korzystamy "blisko siebie" w pameici, wtedy jest wieksza szansa ze CPU ma ten bloczek z obydwoma (wieksza liczba) tymi zmiennymi scachowany.. struct sie klania ;>
19:49Gynvael- jesli mamy kilka warunkow w if... if(a && b && c).. to pierwszy powinien byc ten ktory NAJCZESCIEJ jest FALSZYWY, w przypadku if(a || b || c) pierwszy powinien byc ten ktory jest najczesciej PRAWDZIWY
Gynvael(wtedy pozostale nie sa sprawdzane)
Gynvael- jesli sie ma klika prockow / rdzeni, warto pomyslec o multi threadingu ;>
19:50Gynvael- warto znac swoj kompilator, i jego opcje.. -O3... etc.. kompilator bardzo duzo rzeczy zoptymalizuje sam.. ale nie wszystko
19:51Gynvael- kompilator lepiej optymalizuje jeden duzy plik niz ten sam kod rozbity na kilka malych plikow (glownie o wielkosc kodu tu chodzi)... np w projekcie ReactOS przed kompilacja lacza wszystkie zrodla danego modulu w jeden
19:52Gynvael- optymalizacja na poziomie assemblera i tak zawsze bedzie lepsza, mimo iz kompilatory sa coraz lepsze... jesli chce sie cos zrobic dobrze, trzeba to zrobic samemu.. jesli duzo operujemy na grafice, warto zainteresowac sie SSE, SSE2, SSE3, SSSE3 czy SSE4 ktory ma wyjsc niedlugo, oraz MMX, i obydwoma 3DNow!
19:53Gynvael- rozgalezienia sa zle:
Gynvaelif(b > 10) a += 5; else c +=2; jest WOLNIEJSZE niz a += 5; if(b <= 10) { a -= 5; c += 2; }
19:54Gynvael- inicjalizacja wartosci (int a = 5) jest szybsza niz nadawanie wartosci (int a; a = 5;) (chociaz kompilator powinien o to dbac)
19:55Gynvael- kopiowanie kilku bajtow na raz (np poprzez cast tablicy char[] na int*) jest szybsze niz pojedynczych bajtow.. to samo jesli chodzi o porownywanie
19:56Gynvael- i inne ;>
Gynvaeltemat optymalizacji jest baardzo szeroki, polecam w sumie google jako dobry zbior porad.. ale nie wierzcie we wszystkie ;> warto samemu sprawdzic
19:57GynvaelOK ;> na koniec zrodla
Gynvaelhttp://www.abarnett.demon.co.uk/tutorial.html
Gynvaelhttp://www.tantalon.com/pete/cppopt/main.htm
Gynvaelhttp://www.prism.uvsq.fr/~cedb/local_copies/lee.html
Gynvaelhttp://www.eventhelix.com/RealtimeMantra/Basics/OptimizingCAndCPPCode.htm
Gynvaelhttp://www.rddvs.com/FasterC/
Gynvaelhttp://www.azillionmonkeys.com/qed/optimize.html
Gynvaelhttp://www.codeproject.com/cpp/C
GynvaelNie ze wszystkim niestety zdazylem, moze bedzie druga czesc jesli wyrazicie taka potrzebe
Gynvaelhttp://forum.wyklady.net/index.php?topic=107.0 <=- tutaj mozna komentowac i oceniac wyklad
19:58Gynvaeljesli ktos by chcial poprowadzic o czyms wyklad to msg defc0n ;>
Gynvaelok tyle ;> dziekuje za wspolnie spedzony czas i zapraszam na kolejne wyklady ;>