[bcb]decyzje bez if i switch (kontrolowane skoki)

witam

Robię program, który zajmuje się liczeniem. Istotna jest więc efektywność. Próbuję rozwiązać problem bardzo szybkiego podejmowania decyzji (wykonania odpowiedniej funkcji).

Program podejmie działania zależne od wartości pewnej zmiennej całkowitej. Powiedzmy, że w przypadku jeśli x == 1 wykona funkcje Fu1, a jesli x == 2 to wtedy funkcję Fu2. Załóżmy też, że tych funkcji i możliwych wartości jest trochę więcej, a decyzja będzie podejmowana miliony razy na sekundę.

Tworzenie ciągów typu:

       if (x==1) Fu1();
else if (x==2) Fu2();
else if (x==3) Fu3();

to kompletna pomyłka. Za podobną pomyłkę uważam także switch - case, bo one również będą sprawdzać kolejne wartości. Jeśli możliwych wartości będzie 50, to czasem będzie potrzebne 50 porównań co jedno okrążenie pętli - wtedy czas wykonania programu zaczyna po prostu zależeć od czasu podjęcia decyzji

Pomyślałem, że skoro tak ważna jest wydajność, możnaby zastosować zupełnie nieczysty i niestrukturalny chwyt, który świetnie działał w BASIC-u (z użyciem GOTO)i w ASSEMBLERZE (z użyciem skoku relatywnego):

Szczególnie łatwo zobrazować to w BASICU, bo nie trzeba liczyć zajętości pamięci przez poszczególne rozkazy ...aha, wyjaśniam, że to jest "kopalniany" BASIC, bo ostatnio używłem go na ZX Spectrum ileś tam lat temu :)

998 REM szybka decyzja: wykonanie ktorejś z funkcji Fu1, Fu2, Fu3, Fu4...  
999 REM w zależności od zmiennej x (kopalniany BASIC)
1000 GOTO (x+1000)
1001 GOTO Fu1
1002 GOTO Fu2
1003 GOTO Fu3
1004 GOTO Fu4
...
...

Jak widać program się rozgałęzia w zależności od zmiennej, ale nie ma porównań - po prostu sama zmienna steruje skokiem. Jeśli zmienna x wynosi 2, to wykona się GOTO 1002, a tam jest wywołanie funkcji Fu2. Dodatkowym plusem jest to, że każde takie podjęcie decyzji trwa tyle samo.

Wiem, że to jest rozwiązanie zupełnie parszywe, ale mój program jest już bardzo zaawansowany, a wcale nie rozrósł się nadmiernie, więc nie zaszkodzi mu taki "chwyt" w jednym kluczowym miejscu, a wręcz niezwykle pomoże.

Czy ktoś wie, jak można coś takiego powtórzyć w C++?? A jak wie, to czy podzieli się tą wiedzą na forum? :)

Zrób sobie tablicę z adresami funkcji i wywołuj funkcję o podanym indeksie z tej tablicy.

Jeżeli funkcje, które masz zamiar wywoływać mają taką samą liczbę i typy argumentów, to możesz użyć tablicy wskaźników na funkcje.
Na przykład masz 7 funkcji wywoływanych z dwoma argumentami int:

void (*(tablica_wskaznikow[7]))(int x, int y);//definicja wskaźnika

I jeśli znasz numer funkcji która chcesz wywołać to po prostu:

int numer=3;
(*tablica_wskaznikow[numer])(7,8);

qdoj napisał(a)

Pomyślałem, że skoro tak ważna jest wydajność, możnaby zastosować zupełnie nieczysty i niestrukturalny chwyt, który świetnie działał w BASIC-u (z użyciem GOTO)i w ASSEMBLERZE (z użyciem skoku relatywnego):

Problem w tym, że to co wpływa na wydajność (niekorzystnie) to właśnie skoki, a nie same porównania ;)

Wiem, że to jest rozwiązanie zupełnie parszywe, ale mój program jest już bardzo zaawansowany[...]

Instrukcja goto jest częścią języka, więc nie jest czymś nielegalnym, nieprawidłowym itd.

Szczawik napisał(a)

Zrób sobie tablicę z adresami funkcji i wywołuj funkcję o podanym indeksie z tej tablicy

To jest sposób z którego sam często korzystam ;)

Odpowiedzi, jakich udzielili szczawik i -=mAkAbrAs=- satysfakcjonują mnie całkowicie.

Wielkie dzięki. Jakoś nie mogłem sam wpaść na tablicę adresów :(

Mam jeszcze pytanie do 0x666, który jak zwykle zabija mi ćwieka :)

Problem w tym, że to co wpływa na wydajność (niekorzystnie) to właśnie skoki, a nie same porównania

Dlaczego? Nie rozumiem tego.

Pytam raczej z pozycji laika. Zdawało mi się, że skok to jedna z najkrótszych możliwych operacji, bo wymaga tylko podmiany zawartości rejestru IP (Instruction Pointer) procesora - po prostu wpisuje się tam nowy adres następnego rozkazu. Porównania natomiast są połączeniem operacji arytmetycznej (odejmowania) ze skokiem warunkowym typu JNZ (mój assembler też jest kopalniany, więc może obecnie nie ma już takiego rozkazu. W każdym razie dla mnie ten mnemonik oznaczał zawsze Jump if Not Zero).

Nie wiem, czy mam rację, ale w taki właśnie sposób, jak powyżej, zawsze o tym myślałem. Dlatego pytam, bo może coś przeoczyłem.

0x666 napisał:

Instrukcja goto jest częścią języka, więc nie jest czymś nielegalnym, nieprawidłowym itd.

:) tak, ale mi chodziło nawet nie tyle o użycie GOTO, ile o ilość jego kolejnych wystąpień.
Pisząc posta uprościłem problem do maksimum, żeby ludziom nie mieszać niepotrzebnie, ale w moim faktycznym programie zmienna x będzie przyjmować dość pokaźne rozmiary :(. Po prostu mając do wyboru: wykonać sto porównań, czy stracić sto "integerów" (400 bajtów) wybieram w tym akurat przypadku to drugie.

Jeszcze raz dzięki za wszystkie uwagi.

DODANO:
O nie...
właśnie coś sobie uświadomiłem. Stosując wskaźniki do funkcji tracę możliwość korzystania z dobrodziejstw inline. To trochę porażka. Chyba muszę się trochę zatrzymać i pomyśleć nad tym programem :)

to o czym mówisz ma sens w przypadku prostych procesorów, nie używających żadnych zaawansowanych metod przyspieszania wykonywania kodu (np. 8051).
w przypadku nowszych procesorów intela, które mają bardzo rozbudowane potokowe (piped) dekodowanie/wykonywanie rozkazów, instrukcja skoku powoduje, że trzeba wyczyścić cały potok i rozpocząć dekodowanie od początku, przez co kilka wcześniejszych, częściowo zdekodowanych, musi być wyczyszczonych, na ich miejsce muszą trafić nowe instrukcje, które muszą przejść przez kolejne stopnie dekodowania. dlatego tak naprawdę koszt skoku to nie jeden cykl procesora, ale w przybliżeniu tyle cykli, ile wynosi długość potoku dekodowania (nie jestem na bieżąco, ale ostatnio było to ponad 7).
na szczęście AMD rozwiązał dekodowanie w zupełnie inny sposób :-)

Za podobną pomyłkę uważam także switch - case, bo one również będą sprawdzać kolejne wartości. Jeśli możliwych wartości będzie 50, to czasem będzie potrzebne 50 porównań co jedno okrążenie pętli

Instrukcja switch nie sprawdza kolejno wszystkich wartości, ale tworzy tablicę przesunięć i wykonuje jeden skok.
Zatem wygląda to tak samo jak z tym goto. :D

qdoj napisał(a)

O nie...
właśnie coś sobie uświadomiłem. Stosując wskaźniki do funkcji tracę możliwość korzystania z dobrodziejstw inline. To trochę porażka. Chyba muszę się trochę zatrzymać i pomyśleć nad tym programem

Proponuję najpierw napisać program/moduł tak żeby działał. Później z pomocą jakiegoś profilera szukasz tzw. wąskich gardeł (termin rodem z produkcji XXX ;P ) aplikacji i wtedy zastanasz się nad sposobem optymalizacji najwolniejszych procedur.

qdoj: Hmmm. Po pierwsze założenia nie są prawidłowe. Nie traktuj języka C/C++ jako opisu tego co zostanie (dokładnie) umieszczone w programie wynikowym. Nie bierzesz pod uwagę metod optymalizacji (kod źródłowy można przedstawić na wiele sposobów w kodzie wynikowym). Obecne kompilatory potrafią same o wiele lepiej optymalizować, z uwzględnieniem np. szybkości albo rozmiaru kodu wynikowego. Dodatkowy argument: one naprawdę wiedzą jak generować kod na odpowiedni procesor (to zostało poruszone).

Jako mały przykład (switch-case):

#include <stdio.h>
int s;
int main()
{
    int a = 0;
    scanf("%d", &a);
    switch (a)
    {
        case 0:
            printf("aa");
            s++;
            break;
        case 1:
            printf("bb");
            s+=2;
            break;
        case 2:
            printf("foo");
            break;
        case 8:
        case 9:
        case 10:
            printf("bar");
            break;
    }
}

MinGW-GCC 3.4.2 -O3 -march=pentium daje:

	pushl	%ecx
	pushl	%ecx
	pushl	%eax
	pushl	$LC0
	call	_scanf

; DECYZJA case'ów
; widzisz tu kompilator stworzył tablicę skoków
; zauważ jak jest rozwiązany zakres 3...7, po prostu skok do L2 :)

	movl	-4(%ebp), %eax
	addl	$16, %esp
	cmpl	$10, %eax
	ja	L2
	jmp	*L9(,%eax,4)

L9:
	.long	L3
	.long	L4
	.long	L5

	.long	L2
	.long	L2
	.long	L2
	.long	L2
	.long	L2

	.long	L8
	.long	L8
	.long	L8

L3:
	subl	$12, %esp
	pushl	$LC1
	call	_printf
	movl	_s, %edx
	addl	$16, %esp
	incl	%edx
	movl	%edx, _s

L2:
	xorl	%eax, %eax
	leave
	ret
L8:
	subl	$12, %esp
	pushl	$LC4
	call	_printf
L13:
	addl	$16, %esp
	jmp	L2
L4:
	subl	$12, %esp
	pushl	$LC2
	call	_printf
	movl	_s, %ecx
	addl	$16, %esp
	addl	$2, %ecx
	movl	%ecx, _s
	jmp	L2
L5:
	subl	$12, %esp
	pushl	$LC3
	call	_printf
	jmp	L13

Podsumowując: weź sobie do serca radę 0x666, no i ucz się C... :)

aha, no tak... potoki [sciana]
Nie wpadłbym na to. Jeszcze dużo chleba...

marcinEc napisał(a)

qdoj: Hmmm. Po pierwsze założenia nie są prawidłowe. Nie traktuj języka C/C++ jako opisu tego co zostanie (dokładnie) umieszczone w programie wynikowym. Nie bierzesz pod uwagę metod optymalizacji (kod źródłowy można przedstawić na wiele sposobów w kodzie wynikowym). Obecne kompilatory potrafią same o wiele lepiej optymalizować, z uwzględnieniem np. szybkości albo rozmiaru kodu wynikowego. Dodatkowy argument: one naprawdę wiedzą jak generować kod na odpowiedni procesor (to zostało poruszone).

[...] weź sobie do serca radę 0x666, no i ucz się C... :)

Spoko, dzięki wielkie za wyjaśnienia. Otworzyliście mi oczy na coś, nad czym w ogóle się nie zastanawiałem. Pomyślę nad tym wszystkim.
Tylko ostatnio już nie wiem, co mam czytać. Atakuję kilka książek jednocześnie, a przy tym zastanawiam się, czy chcąc myśleć poważnie o pracy w zawodzie programisty, koniecznie trzeba się przesiąść z Borlanda-Inprise'a (jakkolwiek wykupionego) na oficjalne produkty Microsoftu???

Mam stare złe przyzwyczajenia z czasów, gdy jeśli chciałeś mieć kod zoptymalizowany, musiałeś to zrobić samemu. Prawdę mówiąc nazwa profiler (ad 0x666) nie jest mi obca, ale nigdy nie widziałem takiego narzędzia w akcji. Jednak ponieważ nie lubię zadawać na forach idiotycznych pytań, więc raczej wrócę do tematu, jak się dowiem, co to dokładnie jest.

Tymczasem muszę znaleźć jakąś książkę o kodzie maszynowym widzianym z punktu widzenia programisty w C++ i nauczyć się ufać kompilatorowi trochę bardziej oraz popracować nad algorytmiką.

Dzięki wszystkim za zabranie głosu.

Mam stare złe przyzwyczajenia z czasów, gdy jeśli chciałeś mieć kod zoptymalizowany, musiałeś to zrobić samemu.

I dalej tak jest tyle, że teraz optymalizujesz te najbardziej krytyczne fragmenty kodu, a nie całą bibliotekę/program.

Prawdę mówiąc nazwa profiler (ad 0x666) nie jest mi obca, ale nigdy nie widziałem takiego narzędzia w akcji. Jednak ponieważ nie lubię zadawać na forach idiotycznych pytań, więc raczej wrócę do tematu, jak się dowiem, co to dokładnie jest.

W skrócie polega to na tym, że mierzysz czasy, ilość wywołań poszczególnych funkcji, partii kodu itd. Na podstawie tychże pomiarów wiesz m.in które częsci kodu są najwolniejsze (bottleneck) i wymagają optymalizacji (o ile to konieczne).

Nigdy nie stosowałem profilerów a szybkość działania moich algorytmów przeczy teorii względności - chodzi o nieprzekraczalność prędkości c. :D

W BCB ryzykowne jest używanie wszystkich tworów pochodzących z Delphi - stringi, i ich pochodne (StringList, TStrings a nawet TList - marnotrawią jedynie pamięć i ogólnie nadają się do śmietnika.

Ostatnio, z moich obserwacji wynika, że potężnym błędem jest nadużywanie rekurencji.

W każdej książce o algorytmach jest przykład takiego skrajnego nadużycia - obliczanie silni.
Mimo to wszędzie widać nieszczęśników, którzy otrzymali zadanie obliczenia: silni,
trójkąt paskala albo liczby fibbonaciego przy pomocy rekurencji. [rotfl]
Czyżby idiotyzm, z tzw. elit, przeciekł już do szkół? 8-O