Skocz do zawartości

[TuT] Optymalizacja kodu

Polecane posty

Autor tematu Napisano (edytowany)

Czesc, chcialbym wam dzis udzielic paru rad, odnosnie przyspieszania dzialania naszego programu, pokaze wam, jak mozna zejsc z okolo 20 sekund do 0.1 na programie liczacym ta sama rzecz, a wiec zaczynamy

  • Algorytmem, ktorym bede sie zajmowal bedzie algorytm liczacy sume liczb w ciagu od 1 do n, takie proste, zeby wszyscy zrozumieli. Aby wynik byl bardziej miarodajny, program 'obciazylem' dodatkowo wypisywaniem paru rzeczy, a wiec, oto kod poczatkujacego programisty:

 


#include <iostream>
using namespace std;
int main()
{
unsigned long long liczba = 40000, suma = 0;
while(liczba>0)
{
suma += liczba;
liczba --;
cout<<"Dodalem liczbe "<<liczba<<" do sumy, ktora wynosi "<<suma<<"."<<endl;
}
cout<<suma;
return 0;
}

 



Kod wykonuje sie okolo 30s (33, 31, 31.5), zoptymalizujmy go! Hmm, co by mozna bylo w nim zmienic ... wywalamy endla, zamiast niego piszemy \n, wylaczamy synchronizacje IO, i uruchamiamy nasz program kolejny raz


#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0); // wylaczanie synchr IO
unsigned long long liczba = 40000, suma = 0;
while(liczba>0)
{
suma += liczba;
liczba --;
cout<<"Dodalem liczbe "<<liczba<<" do sumy, ktora wynosi "<<suma<<".\n"; // \n przechodzi jak endl do nowej linii, ale dziala szybciej
}
cout<<suma;
return 0;
}

 

 

  • Zgadnijcie ile sie wykonywal ten kod ... 4 sekundy,czyli okolo 8 razy szybciej! D: Jest szybciej, zajebiscie, no ale nadal za wolno ... Pomyslmy, co mozna by zmienic w nim... Zamiast duzej zlozonosci, czyli po prostu im wieksze bedzie wejscie, tym dluzej bedzie dzialal program, pomyslmy, czy nie dalo by sie czegos zrobic w stalym czasie, czyli podamy mu input 1, program bedzie dzialal sekunde, podamy input 30000, program bedzie dzialal 1 sekunde. A wiec myslimy ... hmm, jesli nie macie pomyslu, czesto odpowiedz jest w googlach, lub na forach.

 

 

 

  • Zamienmy wiec petle na wzor na sume liczb w ciagu od 1 do n, jest to (n*(n+1))/2.

 


#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
unsigned long long liczba = 40000;
cout<<(liczba*(liczba+1))/2;
return 0;
}

 



Tym sposobem pozbylismy sie coutow,petli, niepotrzebnej zmiennej. Ten algorytm wykonuje sie w ~0.074s, wiec jest to mozna powiedziec czas zerowy, ten przyklad pokazuje, jak mozna przejsc z ponad 30 sekund, do 0.074s, wiecie ile razy szybciej nasz program wykonuje sie teraz? Zakladajac, ze poczatkowy czas to 30 sekund, a koncowy to 0.0074, to nasz algorytm dziala 405 razy szybciej!


zalozmy jednak, ze nie mozemy wyprowadzic jakiegos wzoru, nasz program musi opierac sie na petli.. zalozmy tez, ze wiemy ile razy musi ta petla przejsc, lub wiemy przynajmniej, ze musi ona przejsc n*2 / n*3 / n*5 razy, wtedy mozemy zastosowac ten trick, zamiast czegos w stylu:

 


for(int i = 1; i < 100; i++){cout<<"bla bla bla";}

 



piszemy:






for(int i = 1; i<20; i+=5)
{
cout<<"bla bla bla";
cout<<"bla bla bla";
cout<<"bla bla bla";
cout<<"bla bla bla";
cout<<"bla bla bla";
}

 



technika ta nazywa sie loop unrolling (odwijanie petli), pozwala ona zmniejszyc ilosc iteracji petli, wiec pozwala dzialac szybciej naszemu programowi nie wiem dokladnie jaki przyrost efektywnosci daje ta metoda, ale przy duzej ilosci iteracji na pewno sie sprawdzi.

  • zmienne - uzywajcie mozliwie jak najmniejszych zmiennych, po co uzywac inta, w zadaniu w ktorym pisze, ze wejscie jest w zakresie np 1<n<200, uzywamy wtedy shorta; staramy sie szacowac wynik, aby uniknac bledow, im mniej zmiennych tym szybciej w teorii dziala program, w praktyce - czasami to widac, czasami nie.

Widzialem ostatnio kilka kodow typu:



//bla bla bla
for(int i = 1; i<100; i++)
{
a = b;
b +=4;
//wiem ze to nie ma sensu, chodzi o sam przyklad
}




jesli chcemy cos zrobic, typu a = b, zrobmy to przed petla, nie w niej, bo gdy napiszemy to w niej, to bedzie to powtarzane co kazde przejscie petli, po co marnowac zasoby ...


W c++ mozemy wypisywac dane na wiele sposobow, cout, printf, puts, etc, cout z wlaczona synchronizacja I/O jest wolniejszy od printfa i putsa, lecz po wylaczeniu jest juz szybszy














Mam nadzieje, ze pomoglem Wam przynajmniej w jakims stopniu, bede staral sie aktualizowac temat, i dodawac nowe rzeczy, postaram sie takze go jutro jakos sformatowac
~0.0.1

Edytowano przez encoreeFTW

Udostępnij ten post


Link to postu
Udostępnij na innych stronach
Pani Kasia

loop unrolling działa dzięki zmiejszeniu liczb skoków które resetują cache procesora, ale sądze że na nowszych procesorach to nie ma znaczenia ;>


Pisze boty do gier WWW na zlecenie.

Udostępnij ten post


Link to postu
Udostępnij na innych stronach
Pani Kasia

Całkiem przydatne. Można przyspieszyć działanie aplikacji bez większego wysiłku.

Małe pytanie: Dlaczego dostał warna?

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

@Top: Możesz zmienić for(int i = 1; i<100; i+=5) na for(int i = 1; i<20; i++)

Udostępnij ten post


Link to postu
Udostępnij na innych stronach
Pani Kasia

Nie zgodze się z wpływem wielkości zmiennych na szybkość... spotkałem się nawet z opinią kogoś kto zna się na rzeczy że używanie inta (przyjmując, że int ma rozmiar słowa* procesora) będzie szybsze niż shorta.

Niestety nie potrafię Ci teraz tego udowodnić, po prostu tak słyszałem z bardzo wiarygodnego źródła, prawdopodobnie można by znaleźć powód w manualach intela.

Oczywiście to wszystko tyczy się starszych procesorów, na nowszych to whatever :D

---------------------------------------

im mniej zmiennych tym szybciej? Wydaje mi się że zazwyczaj jest inaczej - jest tutaj dylemat, szybkość wykonywania kodu czy ilość zajmowanej pamięci ram. Mówie tutaj o algorytmach które mogą chodzić szybciej jeżeli stworzymy je nie martwiąc się o pamięć. Sama w sobie ilość zmiennych nie ma kompletnie żadnego wpływu na program afaik.

 

*przyjeło się nazwyać słowo procesora podwójnym słowem, ale to tak naprawdę jedno słowo.


Pisze boty do gier WWW na zlecenie.

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

co do wielkosci zmiennych - szczerze nie wiem xD

 

co do ilosci - wiecej zmiennych == wiecej operacji na nich

 

nie mowimy tu o 1 czy 2, tylko niektorzy robia sobie np 30 zmiennych, i nwm po co, skoro to sa jakies liczniki czy cus, kod jest czytelniejszy, i powinno szybciej dzialac, bo zajmujesz mniej miejsca w pamieci, przyklady bralem z tego co widzialem jakie rzeczy u mnie w klasie oddaja ... jedna dziewczyna zachodzila w glowe czemu cout nie dziala jak sie napisze

 

cout<<zmienna,zmienna2,123,467
xD

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

moim zdaniem

Nie zgodze się z wpływem wielkości zmiennych na szybkość... spotkałem
się nawet z opinią kogoś kto zna się na rzeczy że używanie inta
(przyjmując, że int ma rozmiar słowa* procesora) będzie szybsze niż
shorta.

Niestety nie potrafię Ci teraz tego udowodnić, po prostu tak
słyszałem z bardzo wiarygodnego źródła, prawdopodobnie można by znaleźć
powód w manualach intela.


Oczywiście to wszystko tyczy się starszych procesorów, na nowszych to whatever :Da

to zależy od implementacji.

Na przykład vector<bool> jest wolniejszy od vector<int> bo używa bitset, żeby lepiej upakować dane.

im mniej zmiennych tym szybciej?

Ilość zmiennych nie ma znaczenia. Ważna jest ilość wykonywanych operacji na nich. Niekoniecznie ilosc zmiennych ~ ilość operacji

spotkałem się nawet z opinią kogoś kto zna się na rzeczy że używanie
inta (przyjmując, że int ma rozmiar słowa* procesora) będzie szybsze niż
shorta.

Do maksymalnie wielkości rejestru procesora.

Z
wyjątkiem przypadków, kiedy na 'skrawku' danych o wielkości jednego
rejestru znajduje się więcej niż jedna 'zmienna', wtedy trzeba ją
wyłuskać.

Lub kiedy 'zmienna' nie mieści się w rejestrze. (tzn. ma rozmiar większy od rozmiaru rejestru)

 

@btw. znalazłem ten temat

https://stackoverflow.com/questions/4763455/c-data-type-size-impact-on-performance

https://stackoverflow.com/questions/2550281/floating-point-vs-integer-calculations-on-modern-hardware

https://stackoverflow.com/questions/506237/why-is-float-division-slow

Udostępnij ten post


Link to postu
Udostępnij na innych stronach
Pani Kasia

a gdybysmy mieli np tablice 1kkk elementowe, 1 z nich jest char, 2

unsigned long long, a 3 int, no to ta long long bedzie wiecej zajmowala,

o ile sie nie myle xD

Ale co w związku z tym? Zajmiesz więcej pamięci i tyle.

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

no a na zadaniach masz limity dostepnej pamieci, no i im mniej zajmiesz tym masz wiecej na cos innego

Ale my tu mówimy chyba o wpływie zajętej pamięci na szybkość działania programu ;d. A to ma się z tym nijak (poza tym jak działa cache).

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

moim zdaniem

to zależy od implementacji.

Na przykład vector<bool> jest wolniejszy od vector<int> bo używa bitset, żeby lepiej upakować dane.

 

Ilość zmiennych nie ma znaczenia. Ważna jest ilość wykonywanych operacji na nich. Niekoniecznie ilosc zmiennych ~ ilość operacji

 

Do maksymalnie wielkości rejestru procesora.

Z

wyjątkiem przypadków, kiedy na 'skrawku' danych o wielkości jednego

rejestru znajduje się więcej niż jedna 'zmienna', wtedy trzeba ją

wyłuskać.

Lub kiedy 'zmienna' nie mieści się w rejestrze. (tzn. ma rozmiar większy od rozmiaru rejestru)

 

@btw. znalazłem ten temat

https://stackoverflow.com/questions/4763455/c-data-type-size-impact-on-performance

https://stackoverflow.com/questions/2550281/floating-point-vs-integer-calculations-on-modern-hardware

https://stackoverflow.com/questions/506237/why-is-float-division-slow

 

oo dokładnie o to mi chodziło

EDIT: One more thing - if you choose an awkward type (like a 16-bit

integer on a 32-bit or 64-bit platform), you may end up with worse

performance because the CPU will have to surgically extract the 16-bit

value and turn it into something it can work with. But typically, ints

are a good choice.

 

 

słowa procesora to właśnie maksymalny rozmiar rejestru ogólnego przeznaczenia.


Pisze boty do gier WWW na zlecenie.

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

Przepraszam za odkop, ale czy czas kompilacji zajmuje właśnie 30s, ponieważ "obciążyłeś" program std::cout, a w finalnej wersji już nie? Dla przykładu skorzystałem z pierwszej wersji, wywaliłem scout'a, i wychodzi mi dokładnie ten sam czas co w twojej ostatecznej formie.

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

Przepraszam za odkop, ale czy czas kompilacji zajmuje właśnie 30s, ponieważ "obciążyłeś" program std::cout, a w finalnej wersji już nie? Dla przykładu skorzystałem z pierwszej wersji, wywaliłem scout'a, i wychodzi mi dokładnie ten sam czas co w twojej ostatecznej formie.

 

 

Pierwszy program wykonuje się jakiś tam czas.

 

Drugi z kolei jest szybszy od pierwszego - jak niby wywaliłeś cout? Tam zamiast endl jest /n.

 

Ostatni program wykonuje się natychmiastowo, bo wypisuje tylko wynik.


pyhvh7E.png


 


Udostępnij ten post


Link to postu
Udostępnij na innych stronach

To są 2 całkiem różne programy

w 1 wersji wypisałeś 40000 razy coś tam w konsoli

w ostatecznej wypisałeś raz...

Co nie zmienia faktu, że wszystko się zgadza. :)

Tytuł tutka brzmi: "Optymalizacja kodu". Zamierzeniem ulepszanych kodów programu jest zsumowanie liczb z ciągu od 1 do n.

 

W wersji pierwszej mamy pętlę "while", w której 40 000 razy dodajemy do siebie kolejne liczby ze zbioru od 1 do 40 000 i wyświetlamy za pomocą "cout" przeprowadzoną operację.

 

W wersji drugiej robimy dokładnie to samo, ale z wyłączoną synchronizacją I/O oraz z "\n" zamiast "endl".

 

W wersji trzeciej zamiast pętli "while" używamy wzoru na sumę liczb ze zbioru od 1 do n, czyli (n*(n+1))/2, i jedyny myk polega na tym, że z automatu musimy darować sobie ów linijkę:

cout<<"Dodalem liczbe "<<liczba<<" do sumy, ktora wynosi "<<suma<<".\n"; // \n przechodzi jak endl do nowej linii, ale dziala szybciej
Zakładamy jednak, że miała ona jedynie funkcję estetyczną i nie jest potrzebna jakkolwiek w zadaniu. Początkujący programiści mają tendencję do tego typu "upiększeń", nawet jeżeli nie jest to w żaden sposób wymagane. Właśnie dlatego autor zapewne uznał, że może ją sobie wyrzucić "od tak". :)

 

Lekkie przekłamanie jednak występuje, bo linijka mimo wszystko swoje musiała na ekran wyrzucić. Leci plus za spostrzegawczość. ;)

 

­

Edytowano przez VisCouTT

KIbanner.jpg

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

Co nie zmienia faktu, że wszystko się zgadza. :)

Tytuł tutka brzmi: "Optymalizacja kodu". Zamierzeniem ulepszanych kodów programu jest zsumowanie liczb z ciągu od 1 do n.

 

W wersji pierwszej mamy pętlę "while", w której 40 000 razy dodajemy do siebie kolejne liczby ze zbioru od 1 do 40 000 i wyświetlamy za pomocą "cout" przeprowadzoną operację.

 

W wersji drugiej robimy dokładnie to samo, ale z wyłączoną synchronizacją I/O oraz z "\n" zamiast "endl".

 

W wersji trzeciej zamiast pętli "while" używamy wzoru na sumę liczb ze zbioru od 1 do n, czyli (n*(n+1))/2, i jedyny myk polega na tym, że z automatu musimy darować sobie ów linijkę:

cout<<"Dodalem liczbe "<<liczba<<" do sumy, ktora wynosi "<<suma<<".\n"; // \n przechodzi jak endl do nowej linii, ale dziala szybciej
Zakładamy jednak, że miała ona jedynie funkcję estetyczną i nie jest potrzebna jakkolwiek w zadaniu. Początkujący programiści mają tendencję do tego typu "upiększeń", nawet jeżeli nie jest to w żaden sposób wymagane. Właśnie dlatego autor zapewne uznał, że może ją sobie wyrzucić "od tak". :)

 

Lekkie przekłamanie jednak występuje, bo linijka mimo wszystko swoje musiała na ekran wyrzucić. Leci plus za spostrzegawczość. ;)

 

­

 

 

 

Nic się nie zgadza i sam to napisałeś.

 

Jest różnica między pokazaniem wyniku, a pokazywaniem działań na danym wyniku.


pyhvh7E.png


 


Udostępnij ten post


Link to postu
Udostępnij na innych stronach

po przeczytaniu tego tuta ciesze się ze nie pisze w c++ :)


Linux pozwoli wycisnąć ostatnią łzę z twojego procesora.

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

po przeczytaniu tego tuta ciesze się ze nie pisze w c++ :)

 

Hmm... wywnioskowałeś to po?

 

Co to za manie się tworzą z tym C++. A to Java lepsza, bo da się na niej zarabiać, a to C++ zły, bo wolny i lepiej programować w C#.

 

Zamiast pisać takie komentarze może łaskawie wróćcie do pisania programów.

 

Zastanówcie się czasami czemu dany język istnieje, a tym bardziej jest w czołówce (no, bo o C++ słychać bardzo często, nie tylko w grach).


pyhvh7E.png


 


Udostępnij ten post


Link to postu
Udostępnij na innych stronach

  • Kto przegląda   0 użytkowników

    Brak zalogowanych użytkowników przeglądających tę stronę.

×
Okienko zamknie się za 5 sekund...