wydajność virtual vs wskaźnik do metody

0

Cześć, chcę zrobić klasę, gdzie będzie kilka rodzajów funkcji, które będą operować na tych samych zmiennych. Każdy obiekt tej klasy może używać tylko jednej wybranej funkcji.
Zastanawiam się teraz co będzie bardziej wydajne:

  1. zrobienie kilku funkcji (metod) i zrobienie do niej wskaźnika, który w danym obiekcie będzie ustawiony na wybraną metodę (i wywoływany będzie wskaźnik),
  2. zrobienie funkcji virtualnej i zrobienie kilku rodzajów obiektów (różniących się tylko tą funkcją - ilość zmiennych w obiekcie etc. będzie taka sama).
    Czy w tym wypadku (chodzi o wydajność) będzie miało znaczenie czy funkcja jest (może być) statyczna?

Z góry dziękuję za rozwianie moich wątpliwości.

2

Na jedno wychodzi.
W praktyce może wyjść jakaś ledwo mierzalna różnica zależna od wielu czynników (konkretny kompilator, konkretny procesor...)

Wątpliwe jest raczej, by ci aż tak zależało na wydajności, żeby miało to znaczenie.

0

Jeżeli tych funkcji wirtualnych masz mnóstwo, niektóre z nich wywoływane miliony razy zaś są bardzo krótkie to może wyjść istotna różnica.
W pozostałych przypadkach (czyli 99.99%) tak jak napisał @Azarien wyżej.

3

Nie przejmuj sie wydajnoscia dopoki na prawde Twoj program nie bedzie mial z nia problemow. Jak zacznie miec to prawdopodobnie skopales algorytm. Jak wszystko inne zawiedzie to dopiero optymalizuj takie pierdoły.

0
_13th_Dragon napisał(a):

Jeżeli tych funkcji wirtualnych masz mnóstwo, niektóre z nich wywoływane miliony razy zaś są bardzo krótkie to może wyjść istotna różnica.

No właśnie w tym rzeczy, że tak właśnie będzie ;-( Rozumiem, że różnica będzie na niekorzyść funkcji virtualnych?

2

jak wyżej + zanim cokolwiek się zacznie optymalizować to najpierw trzeba wiedzieć CO, a to należy ustalić za pomocą profilera.

Większość początkujących optymalizuje jakieś głupie rzeczy (jak wywołania wirtualne), gdy tymczasem 99% czasu program traci na inne pierdoły, których naprawienie nie wymagają przechytrzania kompilatora.

0

Jak napisał @MarekR22, użyj profilera.

Jest jednak pewien haczyk - samo profilowanie dodaje pewien narzut na wywołania funkcji. Ten narzut jest proporcjonalnie tym większy im mniej rzeczy się dzieje w funkcji. W przypadku masy małych funkcji profiler może pokazywać głupoty.

Wydajność wywołań funkcji wirtualnych zależeć będzie z grubsza od stopnia skomplikowania hierarchii wirtualnego dziedziczenia. Jeżeli głębokość jest minimalna, tzn jeden bazowy interfejs + klasy dziedziczące wprost po tym interfejsie to narzut powinien być porównywalny z wywoływaniem funkcji ze wskaźników.

Najlepiej gdybyś podał kod, być może da się to zrobić inaczej.

0

Dopóki nie piszesz low levelowych bebechów krytycznych ze względu na wydajność używaj virtual bez obawy.
Z drugiej strony nie jest prawdą że virtual call-e kosztują tyle samo co zwykłe call-e.
Metody wirtualne rzeczywiście są nieco wolniejsze głównie przez unimożliwienie zinlinowania
(jedna z najważniejszych optymalizacji wykonywanych przez kompilator) i przez narzut związany z obsługą vtable.
Kompilatory starają się zamieniać virtual call-e na zwykłe call-e tam gdzie to tylko możliwe.

Tutaj jest sporo ciekawych informacji na ten temat:
http://assemblyrequired.crashworks.org/2009/01/19/how-slow-are-virtual-functions-really/

0
Kofcio napisał(a):
  1. zrobienie kilku funkcji (metod) i zrobienie do niej wskaźnika, który w danym obiekcie będzie ustawiony na wybraną metodę (i wywoływany będzie wskaźnik),
  2. zrobienie funkcji virtualnej i zrobienie kilku rodzajów obiektów (różniących się tylko tą funkcją - ilość zmiennych w obiekcie etc. będzie taka sama).
    Czy w tym wypadku (chodzi o wydajność) będzie miało znaczenie czy funkcja jest (może być) statyczna?

To jest to samo z poziomu finalnego kodu- virtuale to wskaźniki, formalnie tablica wskaźników.

0

Najwydajniejsze będzie użycie klasy szablonowej, gdyż umożliwi wstawianie kodu funkcji w miejscu wywołania.
Zamiast tworzyć wskaźnik do funkcji utwórz klasę szablonową, dziedziczącą po klasie z funkcjami, parametryzowaną funkcją do wywołania.

struct foo
{
  void f1(){}
  void f2(){}
  void f3(){}
};

template<void (foo::*F)()>
struct bar : private foo
{
  void f() 
  {
    (this->*F)();
  }
};

bar<&foo::f2> b;
b.f();
0
Wibowit napisał(a):

Najlepiej gdybyś podał kod, być może da się to zrobić inaczej.

Ogólnie to jest tak, że kiedyś napisałem sobie sieć neuronową typu MLP, w której klasa Neuron wyglądała mniej więcej tak: (okrojona wersja - to co najważniejsze):

class Neuron
	{
	private:
		//...
		vector<Weight> weights;
		Weight bias;
		ActFunType act_fun_type;

		double(*act_fun)(double&);		//wskaźnik do wybranej funkcji aktywacji
		double(*deriv_fun)(double&);	//wskaźnik do wybranej pochodnej funkcji aktywacji

		//funkcje aktywacji
		static double sigmoid_act_fun(double&);
		static double bipolar_act_fun(double&);
		//...

		//pochodne funkcji
		static double sigmoid_deriv_fun(double&);
		static double bipolar_deriv_fun(double&);
		//...

	public:
		double& get_output(vector<double>& inputs);
		inline void set_delta(double& error);
		void set_act_fun(int act_fun_type);
		//...
	};

inline double& Neuron::get_output(vector<double>& inputs)
	{
	output = bias;
	for(unsigned i = 0; i < weights.size(); i++)
		output += weights[i] * inputs[i];
	output = act_fun(output);   //wywołanie wskaźnika do funkcji

	return output;
	}
//...

Teraz jednak rozważam trochę ją zmodyfikować i zrobić funkcje virtualne i zastanawiam się jak to wpłynie (czy w ogóle) na wydajność. Oczywiście funkcja będzie wykonywana miliony razy (w trakcie nauki). Fakt, że to jest proces jednorazowy, ale...

0

Moze sie myle bo pokazałeś tlyko fragment kodu, ale jak wygląda u ciebie liczenie odpowiedzi sieci przy wielu warstwach? Nie jest czasem tak ze liczysz odpowiedź każdego neuronu wielokrotnie? Bo nie widzę tu żadnego cache na getOutput neuronu, a to jest kluczowa sprawa jeśli to ma działać szybko...

0

Na upartego można obecną konstrukcję nazwać kompozycją na delegatach :P Obiektowe dziedziczenie nie zawsze jest odpowiedzią na wszystko.

Jeśli zarówno act_fun jak i deriv_fun nie korzystają z metod i pól instancji z klasy Neuron to nie widzę powodu by na siłę robić obiektówkę, skoro obecny kod jest mniej więcej idiomatycznym C++em. Ewentualnie, jeśli te funkcje mają przyjmować jakieś ekstra parametry to możesz stworzyć strukturę zawierającą zarówno wskaźnik jak i część parametrów i wtedy na niej zbudować kompozycję.

PS:
Nie zastanawiałem się długo nad odpowiedzią :P

0
Shalom napisał(a):

Nie jest czasem tak ze liczysz odpowiedź każdego neuronu wielokrotnie?

Ohh, nie! ;-) Wyniki każdego neuronu zapisywane są w tablicy, która jest w klasie Layer przechowującej N neuronów, a która to jest później przekazywana do neuronów w kolejnej warstwie.

W klasie Network wygląda to tak:

inline void Network::send_inputs(vector<double>& new_inputs)
	{
	layers[0].send_inputs(inputs);
	for(unsigned i = 1; i < layers.size(); i++)
		layers[i].send_inputs(layers[i - 1].get_outputs());
	}

a w klasie Layer tak:

inline void Layer::send_inputs(vector<double>& inputs)
	{
	for(unsigned int i = 0; i < neurons.size(); i++)
		outputs[i] = neurons[i].get_output(inputs);
	}

inline vector<double>& Layer::get_outputs()
	{
	return outputs;
	}
1

"... tablica dla każdej klasy, dla rodzica osobna tablica, przeszukiwane rekord po rekordzie przy każdym wywołaniu". - _13th_Dragon

Głupoty opowiadasz.
Dla każdej klasy jest jedna finalna tablica, w której są umieszczane wskazy na funkcje rodziców, jeśli dana klasa nie redefiniuje danej funkcji.

Metody dynamiczne są wyszukiwane w osobnych tablicach - znaczy te messagesy, zwykle do komunikatów windows.
To jest wyszukiwane po numerach lub nawet po nazwach, co jest już wielokrotnie wolniejsze,
ale jest tu niekiedy stosowany specjalny cacheing tych komunikatów... ale w VCL chyba nie.

A te tamplety są szybkie, ale do programowania, a nie w działaniu - kupa zwielokrotnionego kodu, więc rozmiar programów jak i wydajność ostatecznie gówniana.

0

A te tamplety są szybkie, ale do programowania, a nie w działaniu - kupa zwielokrotnionego kodu, więc rozmiar programów jak i wydajność ostatecznie gówniana.

Zależy ile kodu się z nich generuje. Rozwijanie kodu generalnie zwiększa wydajność dopóki intensywnie mielony kod mieści się w cache. Gdy kolejne poziomy cache nie są w stanie pomieścić mielonego kodu to wydajność coraz szybciej spada.

0
Wibowit napisał(a):

Jeśli zarówno act_fun jak i deriv_fun nie korzystają z metod i pól instancji z klasy Neuron to nie widzę powodu by na siłę robić obiektówkę, skoro obecny kod jest mniej więcej idiomatycznym C++em.

No właśnie jeśli różnica w wydajności nie byłaby duża to planowałem to troszkę inaczej zorganizować i wykorzystać już pola klasy.

0
Wibowit napisał(a):

A te tamplety są szybkie, ale do programowania, a nie w działaniu - kupa zwielokrotnionego kodu, więc rozmiar programów jak i wydajność ostatecznie gówniana.

Zależy ile kodu się z nich generuje. Rozwijanie kodu generalnie zwiększa wydajność dopóki intensywnie mielony kod mieści się w cache. Gdy kolejne poziomy cache nie są w stanie pomieścić mielonego kodu to wydajność coraz szybciej spada.

Dla prostych spraw jest OK, bo tam głównie inline pójdą, więc rozmiar jak i szybkość optymalne.

Ale dla złożonych klasy masakra wychodzi - wolne i wielkie, z 90% redundancji;
np. powstanie programik z 10 MB, a faktycznie tam jest góra 100-200KB kodu zaledwie, to znaczy gdyby to zaprogramować poprawnie.

0
Kofcio napisał(a):
Wibowit napisał(a):

Jeśli zarówno act_fun jak i deriv_fun nie korzystają z metod i pól instancji z klasy Neuron to nie widzę powodu by na siłę robić obiektówkę, skoro obecny kod jest mniej więcej idiomatycznym C++em.

No właśnie jeśli różnica w wydajności nie byłaby duża to planowałem to troszkę inaczej zorganizować i wykorzystać już pola klasy.

Lepiej rób to obiektowo, bo to są bardzo prymitywne klaski.

Jawnych wskaźników do funkcji używało się powszechnie w c, i tylko z powodu braku obiektowości.

0

Jeśli zależy Ci na wydajności metod wirtualnych, to dobrze to napisać to w Javie. JVM potrafi sprowadzić 99% wywołań wirtualnych do wywołań statycznych z zerowym narzutem lub wywołań przez inline cache (statycznych z dodatkowym testem, również podlegających optymalizacjom inline).

0
Krolik napisał(a):

Jeśli zależy Ci na wydajności metod wirtualnych, to dobrze to napisać to w Javie. JVM potrafi sprowadzić 99% wywołań wirtualnych do wywołań statycznych z zerowym narzutem lub wywołań przez inline cache (statycznych z dodatkowym testem, również podlegających optymalizacjom inline).

Zdurniałeś, chłopie.
Jawy i inne postskrypciarskie języki nadają się do robienia obrazków, np. stron w sieci.

0

http://www.azulsystems.com/blog/cliff/2010-04-08-inline-caches-and-call-site-optimization

jakieś brednie...

virtualne są momentalnie wywoływane - z tablicy, zatem jakikolwiek dodatkowy cache tylko to spowolni.

być może w tej javie metody dynamiczne nazywają virtualnymi.

0

Z tego co ja rozumiem to w Javie dynamiczna dewirtualizacja działa w dużym uproszczeniu tak:

  1. Najpierw mamy metodę przyjmującą listę:
TypA metoda(List<TypB> lista) { 
 ciało metody
}

Wywołania metod na obiekcie lista są zawsze przez wykonywanie skoku do metody przez wskaźnik z vtable.
2. W czasie wykonywania JVM ogarnia, że za parametr lista zwykle jest podstawiany obiekt klasy WeirdList, która pochodzi z np świeżo dołączonej do classpatha biblioteki nieznanej w czasie kompilacji programu.
3. JVM zamienia metodę mniej więcej na coś takiego:

TypA metoda(List<TypB> lista) {
 if (lista instanceof WeirdList) {
  ciało metody zoptymalizowane, tzn z wklejonymi funkcjami gdzie to jest opłacalne, a gdzie nie jest to są wywołania i tak bezpośrednie, bez używania wskaźników z vtable
 } else {
  ciało metody takie jak wcześniej, czyli wszystko leci przez wskaźniki z vtable, nie ma inlineningu
 }
}

Krótki test dewirtualizacji w JVMce: Dlaczego foreach jest gorsze od for (beta) - wszystkie pętle miały podobny czas co oznacza, że JVM wyciął nie tylko wywołania z vtable, ale dokonał inlineingu. Wyciął też alokowanie obiektu na stercie (Escape Analysis).

0

Znowu jakieś głupoty.

Nie ma kilku vtable w obiekcie - jest jedna na klasę.

A to inlinowanie virtuali ma niewielki sens, bo tylko dla malutkich funkcji, które zwykle i tak nie są virtual.

inline int TRura::numer() { return fi; }

0

Znowu jakieś głupoty.

Nie ma kilku vtable w obiekcie - jest jedna na klasę.

No i co z tego. Wywołanie wirtualne zawsze musi iść przez wskaźnik do funkcji, nawet gdyby siedział już w rejestrze procesora (a w x86-32 rejestry są bardzo cenne).

A to inlinowanie virtuali ma niewielki sens, bo tylko dla malutkich funkcji, które zwykle i tak nie są virtual.

inline int TRura::numer() { return fi; }

To co ma sens zależy od algorytmu i konkretnego podejścia.

W Javie praktycznie wszystkie nieprywatne metody są wirtualne, więc inlining jest wszędzie potrzebny.

0
Wibowit napisał(a):

Wywołanie wirtualne zawsze musi iść przez wskaźnik do funkcji, nawet gdyby siedział już w rejestrze procesora (a w x86-32 rejestry są bardzo cenne).

Każde wywołanie idzie przez jakiś wskaźnik - adres, nie ma różnicy.

call 0x6565776
czy takie coś:
call reg/mem

to żadna różnica.

Wibowit napisał(a):

W Javie praktycznie wszystkie nieprywatne metody są wirtualne, więc inlining jest wszędzie potrzebny.

No i dlatego tam teraz ćwiczą te śmieszne skecze - niby optymalizacja, a faktyczne taka prowizoryczna próba naprawy kolosalnego buga.

0

kolosalnego buga, jakiego buga?

0

Każde wywołanie idzie przez jakiś wskaźnik - adres, nie ma różnicy.

call 0x6565776
czy takie coś:
call reg/mem

to żadna różnica.

Różnica jest przy nowoczesnych CPU. W kodzie typu call 0xABCD nie trzeba nawet odpalać predykcji skoków, natomiast w kodzie typu call reg/mem trzeba już to odpalić, a błędna predykcja to wyczyszczenie potoku, czyli kilkanaście/ kilkadziesiąt zmarnowanych cykli.

Do tego wywołania wirtualne to brak możliwości inlineowania, jak już wspomniał Krolik.

No i dlatego tam teraz ćwiczą te śmieszne skecze - niby optymalizacja, a faktyczne taka prowizoryczna próba naprawy kolosalnego buga.

Nie każdy ma ciśnienie na to, by ręcznie optymalizować kod, skoro JVMka sobie spokojnie radzi z niskopoziomowymi optymalizacjami. Zamiast zastanawiać się kiedy użyć metody wirtualnej, wskaźnika do metody, szablonu czy czego tam jeszcze albo np którego smart pointera użyć lub w jaki sposób alokować pamięć, Javowcy zastanawiają się jak zamodelować potrzeby biznesowe. I tak zresztą gdy projekt jest na tyle długowieczny, że programiści przy nim zmieniają się średnio co parę lat to w przypadku uber-mastah optymalizacji kolejni programiści nie wiedzieli by o co biegało poprzedniemu autorowi z jego fikuśnymi optymalizacjami.
Czas programisty jest cenny, a Java jest na tyle szybka, że klepanie aplikacji biznesowych w C++ zupełnie nie ma sensu. Zysk wydajnościowy z przepisania z Javy na C++ i tak byłby pomijalny przy większości aplikacji biznesowych, bo wąskim gardłem jest zwykle I/O (dysk lub sieć).

Między Javą, a C/ C++em jest jeszcze jedna różnica - w Javie wszystkie odwołania do tablic powodują sprawdzenie czy indeks nie wychodzi poza tablicę. Różnic jest dużo więcej, ale nawet z nimi wszystkimi JVM sobie w miarę dobrze radzi.

Swego czasu popełniłem kilka implementacji mojego autorskiego algorytmu kompresji: https://github.com/tarsa/TarsaLZP
Java vs C/ C++ (bez intrinsicsów) na enwik9:
189s vs 114s
PyPy to aż 1089s przy czym PyPy i tak jest generalnie eksperymentalne (tzn takie mam wrażenie, że nie jest wykorzystywane szeroko w produkcji).

0
Wibowit napisał(a):

Różnica jest przy nowoczesnych CPU. W kodzie typu call 0xABCD nie trzeba nawet odpalać predykcji skoków, natomiast w kodzie typu call reg/mem trzeba już to odpalić, a błędna predykcja to wyczyszczenie potoku, czyli kilkanaście/ kilkadziesiąt zmarnowanych cykli.

Rewelacja.
Policz jeszcze ile marnujesz cykli z powodu przełączania pomiędzy tymi wątkami, np. w win 7 stoi ciągle z 600 wątków przynajmniej.

Wibowit napisał(a):

Nie każdy ma ciśnienie na to, by ręcznie optymalizować kod, skoro JVMka sobie spokojnie radzi z niskopoziomowymi optymalizacjami. Zamiast zastanawiać się kiedy użyć metody wirtualnej, wskaźnika do metody, szablonu czy czego tam jeszcze albo np którego smart pointera użyć lub w jaki sposób alokować pamięć, Javowcy zastanawiają się jak zamodelować potrzeby biznesowe. I tak zresztą gdy projekt jest na tyle długowieczny, że programiści przy nim zmieniają się średnio co parę lat to w przypadku uber-mastah optymalizacji kolejni programiści nie wiedzieli by o co biegało poprzedniemu autorowi z jego fikuśnymi optymalizacjami.

Jakoś odwrotnie wychodzi: gdy odpalę niekiedy przypadkiem program z tej javy, to aż płakać się chce jak coś może tak mulić, chlapie to jak... ZX spectrum 40 lat temu. :)

Wibowit napisał(a):

Swego czasu popełniłem kilka implementacji mojego autorskiego algorytmu kompresji: https://github.com/tarsa/TarsaLZP
Java vs C/ C++ (bez intrinsicsów) na enwik9:
189s vs 114s

Ja mogę zrobić nawet i 1000s... a podejrzewam że i więcej dałbym radę. :))

0

Rewelacja.
Policz jeszcze ile marnujesz cykli z powodu przełączania pomiędzy tymi wątkami, np. w win 7 stoi ciągle z 600 wątków przynajmniej.

Scheduler w Windowsie pracuje z częstotliwością 1000 Hz, a przez większość wywołań schedulera nie ma przełączania zadań, więc cykli zmarnowanych na przełączanie zadań jest mało.

Natomiast jeśli kod jest źle skonstruowany i potok procesora jest w kółko czyszczony to spadek wydajności może być bardzo duży.

Jakoś odwrotnie wychodzi: gdy odpalę niekiedy przypadkiem program z tej javy, to aż płakać się chce jak coś może tak mulić, chlapie to jak... ZX spectrum 40 lat temu.

Trzeba wziąć poprawkę na to, że przy startowaniu Javy jest ładowany cały runtime, a ten zwykle nie leży ani w cache ani nie jest przeparsowany i sprawdzony pod kątem poprawności, więc trzeba go załadować i sprawdzić. Dodatkowo kod jest na początku interpretowany, a potem kompilowany w locie - dlatego, by porównanie C++ kontra JVM było fair trzeba doliczyć czas kompilacji do czasu uruchomienia. Jeśli ktoś nie uruchamia programów Javowych w kółko to problemu z czasem uruchamiania nie ma - a aplikacje biznesowe są rzadko odpalane, ale długo stoją odpalone. Kod Javowy można skompilować do EXEka jak ktoś ma na to ciśnienie - wystarczą narzędzia typu http://www.excelsiorjet.com/ (ale to narzędzie jest dość drogie).

1 użytkowników online, w tym zalogowanych: 0, gości: 1