Witam

Jest sobie taki kod:

http://pastebin.org/94340

Dwie wersje procedury, obie robia to samo. Jedna ma spory gaszcz
if-ow i jest brzydka, druga ma ladne wywolanie przez wskaznik.
Z pomiaru czasu na moim laptopie (atom N270) wynika ze ta z
gaszczem if-ow wypada o 20% szybciej. Dlaczego wywolanie
metody jest takie kosztowne? Przeciez po if-ach tez musi skakac,
aby wybrac wlasciwy kod.

Pozdrawiam

do góry

Mariusz Marszałkowski pisze:
> Witam
>
> Jest sobie taki kod:
>
> http://pastebin.org/94340
>
> Dwie wersje procedury, obie robia to samo. Jedna ma spory gaszcz
> if-ow i jest brzydka, druga ma ladne wywolanie przez wskaznik.
> Z pomiaru czasu na moim laptopie (atom N270) wynika ze ta z
> gaszczem if-ow wypada o 20% szybciej. Dlaczego wywolanie
> metody jest takie kosztowne? Przeciez po if-ach tez musi skakac,
> aby wybrac wlasciwy kod.

Obstawiam, że bardzo dobrze działa branch prediction. I już.

JD

do góry

>> Dwie wersje procedury, obie robia to samo. Jedna ma spory gaszcz
>> if-ow i jest brzydka, druga ma ladne wywolanie przez wskaznik.
>> Z pomiaru czasu na moim laptopie (atom N270) wynika ze ta z
>> gaszczem if-ow wypada o 20% szybciej. Dlaczego wywolanie
>> metody jest takie kosztowne? Przeciez po if-ach tez musi skakac,
>> aby wybrac wlasciwy kod.
>
> Obstawiam, że bardzo dobrze działa branch prediction. I już.

W pewnym programie dla konkretnych danych wejściowych osiągałem 10-krotne
przyspieszenie, gdyż algorytm wpadał w długi, ale bardzo powtarzalny cykl.
Przyspieszenie było prawdopodobnie zasługą cache'u i predykcji skoków.

--
Azarien

do góry

On 20 Lut, 14:40, "Wiktor S." <wswiktor&poczta,f...@no.spam> wrote:
> >> Dwie wersje procedury, obie robia to samo. Jedna ma spory gaszcz
> >> if-ow i jest brzydka, druga ma ladne wywolanie przez wskaznik.
> >> Z pomiaru czasu na moim laptopie (atom N270) wynika ze ta z
> >> gaszczem if-ow wypada o 20% szybciej. Dlaczego wywolanie
> >> metody jest takie kosztowne? Przeciez po if-ach tez musi skakac,
> >> aby wybrac wlasciwy kod.
>
> > Obstawiam, że bardzo dobrze działa branch prediction. I już.
>
> W pewnym programie dla konkretnych danych wejściowych osiągałem 10-krotne
> przyspieszenie, gdyż algorytm wpadał w długi, ale bardzo powtarzalny cykl.
> Przyspieszenie było prawdopodobnie zasługą cache'u i predykcji skoków.

Dlaczego predykcja nie zadziala w przypadku call ?
Jak sadzicie, gdy taki gaszcz if-ow pojawi sie w duzym programie to
tez
dojdzie do dobrej predykcji?

Pozdrawiam

do góry

On 20 Lut, 10:01, Jędrzej Dudkiewicz <j...@g...com>
wrote:

> Obstawiam, że bardzo dobrze działa branch prediction. I już.

> > const int r = rand()%8;

Rozklad bedzie raczej rownomierny.
Watpie, aby kompilator byl tak sprytny, aby widzial, ze zawsze jest
srand(123);

Do Mariusza, nie lepiej time_t T=time(NULL);
i dwa razy srand(T); ?

pozdrawiam
bartekltg

do góry

On 20 Lut, 05:50, Mariusz Marszałkowski <m...@g...com> wrote:
> Witam
>
> Jest sobie taki kod:
>
> http://pastebin.org/94340
>
> Dwie wersje procedury, obie robia to samo. Jedna ma spory gaszcz
> if-ow i jest brzydka, druga ma ladne wywolanie przez wskaznik.
> Z pomiaru czasu na moim laptopie (atom N270) wynika ze ta z
> gaszczem if-ow wypada o 20% szybciej. Dlaczego wywolanie
> metody jest takie kosztowne? Przeciez po if-ach tez musi skakac,
> aby wybrac wlasciwy kod.

Drugie spojrzenie na kod.
Nie jest to wynikiem po prostu tego, ze w proc1 funkcje są inline,
a w proc 2 nie mogą? Zerknij do wypluwanego asm.

A jak kompilator dobry będą tylko 3 ify.
BTW, dlaczego nie swith-case? kompilator miałby
ułatwione zadanie.

pozdrawiam
bartekltg

do góry

On 20 Lut, 17:59, bartekltg <b...@g...com> wrote:
> On 20 Lut, 05:50, Mariusz Marszałkowski <m...@g...com> wrote:
>
> > Witam
>
> > Jest sobie taki kod:
>
> >http://pastebin.org/94340
>
> > Dwie wersje procedury, obie robia to samo. Jedna ma spory gaszcz
> > if-ow i jest brzydka, druga ma ladne wywolanie przez wskaznik.
> > Z pomiaru czasu na moim laptopie (atom N270) wynika ze ta z
> > gaszczem if-ow wypada o 20% szybciej. Dlaczego wywolanie
> > metody jest takie kosztowne? Przeciez po if-ach tez musi skakac,
> > aby wybrac wlasciwy kod.
>
> Drugie spojrzenie na kod.
> Nie jest to wynikiem po prostu tego, ze w proc1 funkcje są inline,
> a w proc 2 nie mogą? Zerknij do wypluwanego asm.
Raz mamy inlinie i procesor musi przedrzec sie przez gaszcz
skokow warunkowych aby dotrzec do wlasciwego kodu.

Drugi raz procesor musi odlozyc parametry na stosie, wyszukac
adres w tablicy i zrobic call(adres) .

I w jednym i w drugim przypadku procesor ma do wykonania
pewna prace aby dotrzec do wlasciwego kodu, u mnie wyszlo
ze kod z gaszczem ifow jest wyraznie szybszy.

Bardzo lubie kod z wskaznikami (albo wirtualami), co zrobic
aby bylo rownie wydajnie?

> A jak kompilator dobry będą tylko 3 ify.
> BTW, dlaczego nie swith-case? kompilator miałby
> ułatwione zadanie.
Ze swich-case w duzym kodzie dziala jeszcze wolniej, a
w malym szybciej. Przynajmniej w moich testach tak bylo.

Pozdrawiam

do góry

On 20 Lut, 21:24, Mariusz Marszałkowski <m...@g...com> wrote:

> Raz mamy inlinie i procesor musi przedrzec sie przez gaszcz
> skokow warunkowych aby dotrzec do wlasciwego kodu.
>
> Drugi raz procesor musi odlozyc parametry na stosie, wyszukac
> adres w tablicy i zrobic call(adres) .
>
> I w jednym i w drugim przypadku procesor ma do wykonania
> pewna prace aby dotrzec do wlasciwego kodu, u mnie wyszlo
> ze kod z gaszczem ifow jest wyraznie szybszy.

Widac korzysci z inline sa wystarczajaco duze ze niweluja
'gaszcz' 3 ifów.
W przypadku ze wskaznikami zapewne tez wszytkie zmienne,
sztuk 3, laduja na stosie. Przy inline moze byc to robione inaczej.

> Bardzo lubie kod z wskaznikami (albo wirtualami), co zrobic
> aby bylo rownie wydajnie?

Lepszy kompilator:)
Trudno cos wymyslic nie wiedzac, jak wyglada generowany kod.
[chwilowo zajety, nie chec mi sie samemu tewstowac].

Jesli nie potrzebujesz tych funkcji ogolniej, wpakuj funkcje w klase
ktora bedzie znala adres int t[4] a przekazywac funkcjom bedziesz
tylko x. I nic nie bedziesz odbierac, bo modyfikacja odbedzie sie
wewnatrz funkcji. W wersji lzejszej, przekazujesz tylko t i x,
tez nic nie zwracasz.

Strzal na slepo, ale moze zadzialac.

> > A jak kompilator dobry będą tylko 3 ify.
> > BTW, dlaczego nie swith-case? kompilator miałby
> > ułatwione zadanie.
>
> Ze swich-case w duzym kodzie dziala jeszcze wolniej, a
> w malym szybciej. Przynajmniej w moich testach tak bylo.

Dziwne:)

Duzym/malym?
Do obu proc1/proc2 dodaleś swith/case? Do proc2, jak?

pozdrawiam
bartekltg

do góry

On 20 Lut, 21:42, bartekltg <b...@g...com> wrote:
> Strzal na slepo, ale moze zadzialac.
Juz sprawdziłem z przekazywaniem parametrow przez zmienna
golobalną, działa szybciej, ale nadal wolniej niż gąszcz if-ów.

> > Ze swich-case w duzym kodzie dziala jeszcze wolniej, a
> > w malym szybciej. Przynajmniej w moich testach tak bylo.
>
> Dziwne:)
Niezle zj...by dostalem za to, bo bylem przekonany ze
switch case dziala ogolnie szybciej, a na duzych projektach
okazalo sie ze nagle dziala wolniej. Moze procesor ma
jakis zasob pamieci na statystyki do predykcji i na duzym
programie ona sie wyczerpuja?

> Duzym/malym?
> Do obu proc1/proc2 dodaleś swith/case? Do proc2, jak?
Ten duzy program to cos zupelnie innego, ale tez mial
taki gaszcz if-ow do wyboru procedury. Zaproponowalem ze
zadziala szybciej na swich case, a tam dupa...

> pozdrawiam
Rowniez pozdrawiam

do góry

On 20 Lut, 21:42, bartekltg <b...@g...com> wrote:

> > Ze swich-case w duzym kodzie dziala jeszcze wolniej, a
> > w malym szybciej. Przynajmniej w moich testach tak bylo.
>
> Dziwne:)
Zlamalem sie i zrobilem testy.
kontrola wyniku mod 100, maksymalny piorytet

kod lekko przerobiony, aby 1233 nie bylo stala:
--scanf("%d",&s);
--.....
--srand(s);

40000000 powtorzen
start:123
if = 22 czas = 3562 wsk = 22 czas = 3359 case = 22 czas = 3391
if = 22 czas = 3484 wsk = 22 czas = 3344 case = 22 czas = 3391
if = 22 czas = 3484 wsk = 22 czas = 3360 case = 22 czas = 3406
if = 22 czas = 3500 wsk = 22 czas = 3360 case = 22 czas = 3406
if = 22 czas = 3484 wsk = 22 czas = 3438 case = 22 czas = 3421
if = 22 czas = 3516 wsk = 22 czas = 3328 case = 22 czas = 3390


Wyniki najlepisze:
wsk 333 100%
case 339 101.8%
if 348 104.5%

100000000 powtorzen
start 10
if = -39 czas = 8704 wsk = -39 czas = 8265 case = -39 czas = 8438
if = -39 czas = 8734 wsk = -39 czas = 8359 case = -39 czas = 8469
if = -39 czas = 8734 wsk = -39 czas = 8375 case = -39 czas = 8469
if = -39 czas = 8797 wsk = -39 czas = 8313 case = -39 czas = 8468
if = -39 czas = 8625 wsk = -39 czas = 8250 case = -39 czas = 8484
if = -39 czas = 8750 wsk = -39 czas = 8266 case = -39 czas = 8375
if = -39 czas = 8609 wsk = -39 czas = 8297 case = -39 czas = 8390
if = -39 czas = 8609 wsk = -39 czas = 8250 case = -39 czas = 8703
if = -39 czas = 8641 wsk = -39 czas = 8343 case = -39 czas = 8422

Wyniki najlepisze:
wsk 825 100%
case 839 101.7%
if 861 104.4%

Wskazniki okazaly sie najszybsze, if najwolniejsze,
'case' w polowie drogi. Roznice minimalne.

Niewlaczenie maksymalnego piorytetu oznaczalo, ze
machanie myszka i drapanie sie po plecach calkowicie
zaburza wyniki (w dowolnym kierunku).

Kompilator - tradycyjnie VC.

pozdrawiam
bartekltg

do góry