Czy da się określić prędkość for loop? Oraz kilka innych pytań odnośnie natury programowania w Cpp.

Witam,
mam kilka takich pytań naprawdę u podstaw :)
założyłem wczoraj wątek na stackoverflow.
Ale nikt mi jeszcze nie odpowiedział, a ja się strasznie niecierpliwię :) więc pytam dodatkowo tutaj.

Zastanawiam się jak działają loopy. Np. czy da się jakoś obliczyć, czy to w ogóle ma sens, ile czasu zajmuje procesorowi wykonanie jednej iteracji najprostrzego loopa, np:

int a;
for (int i=0; i<100; i++)
{
     a=i;
}

I jakie to jest obciążenie dla procesora? zastanawiam się, gdyż trochę się bawię w programowanie audio. A tam loopy mają po kilkadziesiąt tysięcy iteracji. Np. 44100, a w każdej z tych iteracji mogą być inne duże loopy, a w każdej iteracji tych wewnętrznych loopów czasami dzieją się skomplikowane obliczenia, jak np. na liczbach zespolonych przy obliczaniu FFT.

Jak sprawdzić, lub zoptymalizować wydajność takich loopów?

Jakiś czas temu również gadałem z jakimś profesorem od C++ i on mi doradził aby każde zadanie w aplikacji rozbijać na oddzielne funkcje lub nawet klasy. A ja jakoś oprócz przejrzystości w kodzie, nie rozumiem takiego podejścia.

Bo np. kiedy chcę wykonać obliczenia DFT, a potem narysować wyniki na ekranie w postaci wykresu, to z tego co mówił Pan profesor powinienem zrobić przynajmniej dwie funkcje, jedną do liczenia DFT, a drugą do rysowania. Ale przecież aby narysować każdy punkt takiej transformaty fouriera to też muszę wykonać loopa. Czyli będę miał loopa w funkcji liczącej DFT, a potem drugiego loopa w funkcji rysującej. A czy dla wydajności mojego programu nie byłoby lepiej abym wykorzystał loopa DFT i w nim jednocześnie wykonał rysowanie? Wtedy przecież program ma do wykonania jednego loopa.

Nie wiem jak to wszystko ugryźć.

Albo inne pytanie, jeżeli potrzebują w loopie jakiejś zmiennej pomocniczej, to lepiej ją utworzyć poza loopem i w loopie tylko przypisywać dla tej zmiennej jakaś wartość? Np.

std::vector<int> _a;
int pomocnicza1;
int pomocnicza2;
for (int i=0; i<100; i++)
{
     pomocnicza1 = 2 i;
     pomocnicza2 = 4 i;
     _a.push_back(pomocnicza1 + pomocnicza2);
}

Czy może lepiej w każdej iteracji tworzyć liczy pomocnicze, czyli:

for (int i=0; i<100; i++)
{
     int pomocnicza1 = 2 i;
     int pomocnicza2 = 4 i;
     _a.push_back(pomocnicza1 + pomocnicza2);
}

A może jeszcze lepiej byłoby:

for (int i=0; i<100; i++)
{
     _a.push_back(2 i + 4 i);
}

Co jest najlepsze dla wydajności? I jak w przyszłości sprawdzać odpowiedzi na podobne pytania?

Z góry wielkie dzięki za wszelką pomoc.

Np. czy da się jakoś obliczyć, czy to w ogóle ma sens, ile czasu zajmuje procesorowi wykonanie jednej iteracji najprostrzego loopa, np:
da sie, wrzucasz z flaga by compiler dal Ci wygenerowany asm i wtedy zobaczysz ile konkretnych wywolan assemblera sie wykona. Pozniej specyfikacja kazdej instrukcji ile bierze cykli procesorow
Czy warto? nie. To co chcesz robic nazywa sie Premature optimialization

jakie to jest obciążenie dla procesora?
zalezy od loopa, ale pomijalne. 44100 to nie sa duze loopy ;)

Jak sprawdzić, lub zoptymalizować wydajność takich loopów?
przede wszystkim jak kompilujesz to kompiluj z flaga optymalizacji (to zalezy od tego jaki masz kompilator)

Jezeli chodzi o optymalizacje sa dwie zasady

1. optymalizuj dopiero gdy bedziesz potrzebowal i optymalizuj jedynie bottle neck
2. Gdy piszesz oprogramowanie ktore wymaga duzo wydajnosci (silnik do gier AAA) zignoruj punkt 1) oraz pomysl nad krytycznymi algrotymami wczesniej i postaraj sie je napisac jak najlepiej (nawet w asm jezeli tak bardzo potrzebujesz wydajnosci).

Profesor mial racje, przejrzystosc w kodzie jest duzo wazniejsza niz wydajnosc w wiekszosci wypadkow

Albo inne pytanie, jeżeli potrzebują w loopie jakiejś zmiennej pomocniczej, to lepiej ją utworzyć poza loopem i w loopie tylko przypisywać dla tej zmiennej jakaś wartość? Np.
przy wlaczonej optymalizacji nie ma znaczenia. Kod wynikowy bedzie taki sam

Jeszcze dodam, że często kompilator potrafi zrobić dużo dziwnych rzeczy różnym kosztem. Przykładowo pierwszej podanej przez ciebie pętli zapewne nie będzie w kodzie w cale, bo kompilator "zauważy", że jest ona zbędna. W innych przypadkach może zamienić pętlę na znany wzór, przykładowo (IIRC) LLVM potrafi rozpoznać coś takiego:

int sum(int a) {
  int ret = 0;
  for (int i = 1; i <= a; i++) ret += i;
  return ret;
}

i zamienić to na równoważny kod (lub podobny, by by zapobiec overflow):

int sum(a) {
  return a * (a + 1) / 2;
}

W innych przypadkach kompilator zamieni ciało pętli by wykorzystać instrukcje SIMD istniejące na danej architekturze.

Hasła do google: profiler, gprof, code profiling. Zasada jest taka: robisz zgodnie ze sztuką inżynierską (czysty kod, modułowość itd.). Jak Ci za wolno: profilujesz, szukasz wąskich gardeł i optymalizujesz problematyczne miejsca, np. przez rozwijanie pętli czy wyrzucenie zmiennej pomocniczej przed pętlę. Generalnie (wyjątkiem jest np. engine graficzny czy jakieś "ciasne" bare-metal embedded) takie wczesne optymalizacje są zbędne a nawet szkodliwe, bo zaciemniają obraz całości.

hauleth napisał(a):

Jeszcze dodam, że często kompilator potrafi zrobić dużo dziwnych rzeczy różnym kosztem. Przykładowo pierwszej podanej przez ciebie pętli zapewne nie będzie w kodzie w cale, bo kompilator "zauważy", że jest ona zbędna. W innych przypadkach może zamienić pętlę na znany wzór, przykładowo (IIRC) LLVM potrafi rozpoznać coś takiego:

int sum(int a) {
  int ret = 0;
  for (int i = 1; i <= a; i++) ret += i;
  return ret;
}

i zamienić to na równoważny kod (lub podobny, by by zapobiec overflow):

int sum(a) {
  return a * (a + 1) / 2;
}

W innych przypadkach kompilator zamieni ciało pętli by wykorzystać instrukcje SIMD istniejące na danej architekturze.

Bardzo cenne dla mnie uwagi, gdyż również się dużo zastanawiałem nad tym co się dzieje z kodem, który jest nieużywany. Dzięki za odpowiedź

@pajczur: polecam sobie obejrzeć

Profilowaniem bawiłem się pod JVMem i niestety, ale w przypadku krótkich funkcji profilowanie działa słabo. Najlepszym sposobem na profilowanie kodu okazywało się zwykle ręczne mierzenie czasu dla wybranych kawałków kodu. Duplikację kodu związaną z odczytywaniem czasu i wypisywaniem go na ekran (czy do logów) można załatwić za pomocą lambd (domknięć). W Javce byłoby to np:

void timed(Runnable action) {
  long startTime = System.currentTimeMillis();
  action.run();
  long totalTime = System.currentTimeMillis() - startTime();
  System.out.println("Czas: " + totalTime + "ms");
}
// potem w kodzie
long a = 0;
timed(() => {
  for (int i = 0; i < 100; i++) a += i;
});
System.out.println("Wynik: " + a);

W kodzie C++ byłoby analogicznie, ale nie znam C++ na tyle by ten kod szybko przetłumaczyć.

fasadin napisał(a):

Np. czy da się jakoś obliczyć, czy to w ogóle ma sens, ile czasu zajmuje procesorowi wykonanie jednej iteracji najprostrzego loopa, np:
da sie, wrzucasz z flaga by compiler dal Ci wygenerowany asm i wtedy zobaczysz ile konkretnych wywolan assemblera sie wykona. Pozniej specyfikacja kazdej instrukcji ile bierze cykli procesorow
Czy warto? nie. To co chcesz robic nazywa sie Premature optimialization

Dlaczego nie warto? Poniżej piszesz, że 44100 to nie jest duży loop, ale jeżeli w każdej iteracji takiego loopa jest inny loop, również 44100 i ten nadrzędny loop musi się wykonywać kilka razy na sekundę? Może to i nadal jest nie duży loop, nie wiem, nie znam się, zarobiony jestem :) ale wiem, że mam takiego loopa w swoim kodzie na liczenie DFT. No i program mi strasznie muli. Chyba właśnie z tych względów wymyślono algorytm FFT, czy nie? Dlatego zastanawiam się jakie są możliwości, czy da się to jakoś wcześniej przewidzieć, co spowoduje zamulenie, a co bez problemu będzie działało? Bardzo możliwe, że wciąż czegoś nie rozumiem, ale wydają mi się takie pytania dość istotne.

Ogólnie wielkie dzięki za odpowiedź, ale muszę jeszcze dużo się naczytać, aby ją zrozumieć, zgodnie z myślą "wiem, że nic nie wiem" :)
Grzebię właśnie w googlach, co to są Optimalization Flags, silnik AAA, asm. Ale idzie mi mozolnie, na każdy z tych tematów trzeba się naczytać w cholerę, a i tak człowiek nie jest pewien czy to zrozumiał jak należy.
Strasznie chciałbym to wszystko, wszystkie odpowiedzi, mieć podane na tacy, ale rozumiem, że się nie da :)
Ale dzięki za hinty :)

TEN POST CHYBA POWINIEN BYĆ "KOMENTARZEM", A NIE ODPOWIEDZIĄ. SORRY, POPRAWIĘ SIĘ NA PRZYSZŁOŚĆ

@pajczur: bo nie warto się interesować czy pętla zabiera dużo czasu, ale która pętla zabiera dużo czasu. Przykładowo jeśli wykonanie programu zajmuje 30s i znajdziesz supernieoptymalną pętlę, którą zoptymalizujesz do niemal niezauważalnego czasu wykonania (przyjmijmy, że przyspieszysz ją 1000x), ale odpowiadała ona za 0.0001% czasu wykonania programu, to o ile poprawi się odczucie użytkownika? A w innym miejscu znajdziesz pętlę, która wykonuje się super szybko, i poprawisz czas jej wykonywania 2x, ale była ona odpowiedzialna za 50% czasu trwania programu. Którą pętlę było lepiej optymalizować?

Jeśli chodzi o rozważania "czy pętla w pętli jest ok" warto zapoznać się ze złożonością obliczeniową. Różne algorytmy mają różną złożoność i przez to różnie zwiększa się ich czas wykonywania wraz z przyrostem ilości danych. FFT zamiast DFT używany jest właśnie dlatego, że ma mniejszą złożoność obliczeniową.

hauleth napisał(a):

@pajczur: bo nie warto się interesować czy pętla zabiera dużo czasu, ale która pętla zabiera dużo czasu. Przykładowo jeśli wykonanie programu zajmuje 30s i znajdziesz supernieoptymalną pętlę, którą zoptymalizujesz do niemal niezauważalnego czasu wykonania (przyjmijmy, że przyspieszysz ją 1000x), ale odpowiadała ona za 0.0001% czasu wykonania programu, to o ile poprawi się odczucie użytkownika? A w innym miejscu znajdziesz pętlę, która wykonuje się super szybko, i poprawisz czas jej wykonywania 2x, ale była ona odpowiedzialna za 50% czasu trwania programu. Którą pętlę było lepiej optymalizować?

No właśnie, ale jak zoptymalizować pętlę, jak się określa czy pętla jest optymalna czy nie, jak ją przyspieszyć?
Co spowalnia działanie pętli a co przyspiesza? Jakie instrukcje, w jakim stopniu obciążają pętle? Czy np. mnożenie 2 razy 2 jest bardziej obciążające dla komputera niż dodawanie 2 + 2? W tym wypadku to pewnie nie ma większej różnicy, ale jeżeli tego dodawania czy mnożenia jest bardzo dużo, to już może mieć znaczenie, a może nie? Bo własnie nie wiem.
Czy operacje na std:vectors są tak samo sprawne jak operacje na zwykłych arrayach?
Czy jeżeli potrzebuję wykonać operację na liczbach zespolonych, i tych operacji potrzebuję wykonać kilkadziesiąt tysięcy razy na sekundę, ale te operacje sprowadzają się tylko do mnożenia liczba zespolona razy liczba zespolona, czy w takim wypadku po prostu korzystać z std::complex, które przecież mają bardzo rozbudowane możliwości działań na liczbach zespolonych, czy może lepiej utworzyć własną, prostą klasę liczby zespolonej, która będzie realizowała tylko to mnożenie?

Pytam o to wszystko gdyż mam funkcję realizującą DFT. po prostu na zmiennych float, to oczywiście bardzo spowalnia pracę programu. Próbuję zatem zaimplementować własny algorytm FFT (wiem, że takie są, ale chcę poćwiczyć i zrozumieć pewne sprawy) Jednak kiedy podzieliłem loopa na pół, ale wykorzystując std::complex, wcale nie zauważyłem poprawy sprawności.

Jak zasugerował vibovit możesz "ręcznie" sprawdzać czas wykonania newralgicznych funkcji czy pętli:

#include <iostream>
#include <vector>
#include <chrono>
#include <conio.h>
using namespace std;

class Clock
{
	public:
		Clock() { start = chrono::high_resolution_clock::now(); }
		~Clock() {}
		
		float secondsElapsed()
		{
			auto stop = chrono::high_resolution_clock::now();
			return chrono::duration_cast<chrono::microseconds>(stop - start).count();
		}
		void reset() { start = chrono::high_resolution_clock::now(); }
		
	private: 
		chrono::time_point<chrono::high_resolution_clock> start;
};

int main() 
{
	int a = 1;
	int b = 1;
	int c = 1;	
	
	Clock zegar;	
	for (int i = 0; i < 1000000; i++) a *= b;
	cout << zegar.secondsElapsed() << endl;
	
	zegar.reset();
	for (int i = 0; i < 1000000; i++) a += b;
	cout << zegar.secondsElapsed() << endl;		
	
	return 0;
}

wyniki to:

• pierwsza pętla: 4000 μs
• druga pętla: 2000 μs

Trochę przesadziłem z tymi mikrosekundami bo nie ma co się aż taką dokładnością sugerować, ale jak pokazuje że wykonanie jakiejś instrukcji wynosi 0 ms (millisekundy) to chyba nie ma co optymalizować.

Edit: klasa Clock jest lekko niedopracowana ale chyba widać?