Prasime v C - ON a GOTO a, b, c

18.8.2006 14:34 | Přečteno: 1802× | Programování | | poslední úprava: 18.8.2006 14:34

Momentalne tunim jednu aplikaci na vykon a presto, ze jsem pri posledni aplikaci, co jsem psal v Basicu nadaval jak spacek. Postesklo se mne po jedne uzasne basicove konstrukci -- ON <cislo> GOTO <adresa1>, <adresa2>...

Jelikoz instrukce goto se v nekterych kruzich nesmi ani vyslovit, bude asi velke rouhani uvazovat o jeji parametrizaci.

Predstavte si, ze mate smycku typu (viz nize) a tato smycka, probiha v aplikaci miliardkrat.

while (podminka) {
   int operace = getOperace();
   switch (operace) {
      case 0: delej_neco(); break;
      case 1: delej_neco_jineho(); break;
      ...
   }
}

Vypada to docela efektivne. Problem je, ze pri kazdem pruchodu se testujji vsechny moznosti, dokud se ta spravna nenajde -- slozitost O(n) k poctu moznosti. Pri poctu milard pruchodu, uz to prestane byt zanedbatelne. Jedno reseni je usporadat hodnoty podle pravdepodobnosti. Ale to nebyva zrovna elegantni. Dalsi reseni je prasit...

Pri hledani informaci o inlinovani funkci, jsem objevil zajimave rozsireni GCC. Diky operatoru && muzete pristupovat k jednotlivym labelum jako k hodnotam.

Pozor -- toto funguje jenom v gcc, jestli je to dobre nebo spatne nevim, kazdopadne melo by se to pouzivat pouze pokud tusite co delate.

void *ptr;
if (a == 1) ptr = &&nejaky_label1;
else ptr = &&nejaky_label2;
...
goto *ptr;
...
nejaky_label1:
nejaky_label2:

Neni to sice nejlepsi priklad, ale kdyz si vezmeme ten priklad se switch, uz to muze byt uzitecnejsi

void * op_table[] = { &&case_0, &&case_1, &&case_2, ...}
while (podminka) {
   goto *op_table[getoperace];
   case_0: delej_neco(); goto complete;
   case_1: delej_neco_jineho(); goto complete;
   ...
   complete:
}

Je to sice malinko hardcore, ale obcas to dava i lepsi vysledky, jelikoz to ma konstantni slozitost vzhledem k poctu moznosti.

       

Komentáře

[Kyosuke]

Taky můžeš zaangažovat pole pointerů na funkce. Mimochodem, IBM kvůli přítomnosti v GCC přidalo tohle rozšíření do vlastního kompilátoru pro AIX.

[Michal Kubeček]

Pole funkcí by mi připadalo výrazně čistší.

[deda.jabko]

pole pointru na funkce me taky napadlo, jenomze tim se zaviraji nektera dvirka pro optimalizace v jednotlivych moznostech -- inlining, predavani, nekterych hodnot pres registry, atp.

[Kyosuke]

Inlining? Předávání parametrů? No jo, co by taky člověk mohl čekat od registrovýho procesoru...

[deda.jabko]

pekny pokus ;-] ale... inlining toho s procesorem nema moc spolecneho. jenom redukuje pocet instrukci call/ret (a tim padem i manipulace zasobnikem) nahrazenim volani telem funkce. pochybuji, ze to pujde na zasobnikovych procesorech delat lip. btw. java i c# maji hodne vychytane zpusoby inlinovani kodu a to bezi na zasobnikovych VM.

predavani parametru je jina vec... a je otazka vkusu jestli je lepsi zonglovat s registry nebo zasobniky.

[Kyosuke]

Na zásobníkových procesorech není inlining zapotřebí, to je to, co jsem měl na mysli. Respektive dopad callů na výkon je o tolik menší, že se nevyplatí, takže se ani nedělá. Větvení podle vypočítané hodnoty, respective computed call, je prakticky bez režie.

Taky mi je trošku líto, že to s těmi funkcemi neběhá tak rychle, jak by třeba mohlo. Na druhou stranu, pokud je computed goto zapotřebí k dosažení potřebného výkonu, není to ještě konec světa. Mně to nepřijde jako špatné použití skoku. Jeho smysl se je přeci poměrně jasně daný, tak proč se mu bránit?

[Michal Kubeček]

Jako kolovrátek… :-(

[Kyosuke]

Zkusil bych static SenseOfIrony i = new SenseOfIrony();

[Michal Kubeček]

error: conversion from ‘SenseOfIrony*’ to non-scalar type ‘SenseOfIrony’ requested

[Kyosuke]

Já teda kafe moc nepiju, ale myslel jsem, že v něm by to fungovalo?

[Michal Kubeček]

V kafi možná jo, ale byl jsem vyzván, abych to zkusil - bez bližšího upřesnění. A já radši čaj… :-)

[deda.jabko]

jojo, stejne tak v c-kriminal ;-] jenom v c++ to nejede

[VícNežNic]

Ovšem narozdíl od kafe se to dá spravit mávnutím kouzelné preprocesorové hůlky

[VícNežNic]

Chybu doporučuji opravit silnou ránou do hlavy, při trošce štěstí uvidíte dost hvězdiček pro nás všechny

[Michal Kubeček]

Čím víc hvězdiček, tím víc Adidas? :-)

[#Tom]

A co standardní céčkové řešení?

#include <stdio.h>
#include <stdlib.h>

void akce0() {
  printf("Akce 0\n");
}

void akce1() {
  printf("Akce 1\n");
}

void akce2() {
  printf("Akce 2\n");
}

void test(int akce) {
  void (*op_table[])() = { akce0, akce1, akce2 };
  if (akce >= 0 && akce <= 2)
    op_table[akce]();
  else
    printf("Akce mimo rozsah.\n");
}

int main(int argc, char *argv[])
{
  char *p;
  int akce; 
  if (argc < 2) { 
    printf("syntax: test číslo akce\n"); 
    return 1;
  }
  akce = strtol(argv[1], &p, 0); 
  if (p == NULL || *p != '\0') { 
    printf("Chybné zadání.\n"); 
    return 0;
  }
  printf("Volám akci...\n"); 
  test(akce); 
  return 0;
} 

[deda.jabko]

jo, to je to vyse navrhovane reseni pres pole ukazatelu na funkci... je to bezpochyby cistejsi, ale zase min efektivni, protoze jak jsem psal vys, nelze vyuzit rady optimalizaci -- predavani parametru pres registry, inlining.... taky jsem si myslel, ze to nehraje roli -- ale pokud ta smycka probiha miliardkrat s jednoduchyma operacema uz to zacina mit vliv. v me aplikaci nebyl rozdil v pouziti switch a pole funkci, ale s goto to bylo 10-20% lepsi.

[jk]

Nemelo by tu optimalizaci provest primo gcc? Vim ze kompilator Delphi to tak resi a nevidim duvod proc by gcc taky nemohlo.

[deda.jabko]

ono si to optimalizuje jen nekdy pro urcite rozsahy

[trekker.dk]

To goto complete; mi přijde jako zbytečnost - break udělá to samé.

(Hm, takže je to vlastně jedno )

[deda.jabko]

ne, neni, goto complete tam prave je misto toho break

[trekker.dk]

No a co udělá ten break? IMHO goto na_konec_switche.

[deda.jabko]

jenomze tam zadny switch neni... v tom je ta prasarna, aspon myslim ;-]

[trekker.dk]

Á, slepý jsem, nevidím. Respektive někdy vidím i to, co není

[psonek]

Goto na pointer pouzivaji napr. v projektu Portable .NET misto switchovani IL instrukci. Jinak ja prekladacum a tomu co generuji moc nerozumim, ale myslim ze switch by se mel dat optimalizovat na lepsi slozitost nez O(n).

[Kyosuke]

Pěkná stránka na podobné téma...

[msk]

Co je to GOTO? V dobe mojich zaciatkov v prasackom jazyku basic na zx spec to bola casto pouzivana instrukcia, ale bola potrebna z dovodu debility toho jazyka. Nikde inde som sa s nou zatial realne nepotreboval stretnut ( c, c++, python, perl, sh ). Co sa tyka jej vplyvu na rychlost, myslim, ze to zavisi na implementacii a k optimalizacii toho isteho kodu zvacsa vedie viac ciest. Osobne tiez patrim k ludom, ktorym sa dviha zlc ked vidia v c/c++ kode prikaz goto.

[#Tom]

Já jsem pomocí goto naprogramoval jednou průvodce v Turbo Pascalu.

[anicka]

Nekdy se to na vykonu skutecne pozna... kazdy program nejsou jen dve okynka a par funkci okolo. A clovek si za chvili zvykne Ostatne, tohle mluvi samo za sebe:

anicka@bia:/usr/src/linux> grep -r goto . | wc -l
37852

[lankvil]

jo mas pravdu clovek si zvykne:) pri prechodu z basicu sem si zase musel zvykat na funkce, kdyz moje oblibene goto bylo vsude zatracovane

p.s. http://partmaps.org/era/unix/award.html#wc

[anicka]

Dobrý pokus, ale zkusil jsi pustil grep -cr na rozvětvený adresářový strom? Na tom příkladu je podstatné, že ten grep bere vstup z pajpy...

Takhle dostaneš výstup pro každý soubor zvlášť. Ještě pořád by se to asi dalo vykousat třeba tailem a posčítat jako oneliner, ale to by už bylo skoro na kopanec od mistra Foo a zlaté wc a vůbec

[lankvil]

heh, mnj vidis to me nenapadlo :) ze ja blbec si to predtim nezkusil. no jeste se v bashi mam co ucit. samozrejme je to i efektivnejsi nez to co sem zbastlil jenom abych grep -c pouzil:

14:47:10 ganymede:/usr/src/linux$ time find . -type f| xargs cat | grep -c goto
37926

real    2m1.915s
user    0m1.612s
sys     0m5.500s
14:51:11 ganymede:/usr/src/linux$ time grep -r goto . | wc -l
grep: varování: ./debian/linux-image-2.6.17.4/lib/modules/2.6.17.4/source: smyčka pro rekurzivní průchod

grep: varování: ./debian/linux-image-2.6.17.4/lib/modules/2.6.17.4/build: smyčka pro rekurzivní průchod

37918

real    1m43.943s
user    0m1.828s
sys     0m3.848s

jen by me zajimalo proc se vysledky lisi :/

[Mikos]

Tak se podívej do zdrojáků Linuxového kernelu, tam máš goto hromadu

Dovolím si citovat Lukův příspěvek z jedné diskuze:

Že je goto hřích se říkalo v dobách, kdy se přecházelo z Basicu a kdekdo cpal goto úplně všude. goto má svůj význam, a např. v linuxovém jádru se vyskytuje celkem hustě.

Nicméně já mam velmi rád objektové programování, takže mě se goto a podobné konstrukce taky rozhodně nelíbí Ale já vubec nemusím C/C++, mám rád vyšší jazyky

[VícNežNic]

Já jsem toho názoru, že já si nejsem zcela jistý tím, co si já myslím o goto.

[Mikos]

Připadáš si vtipný?

[VícNežNic]

Ne, ty ano?

[Michal Kubeček]

Paušální odsouzení obvykle nejsou k ničemu. Vzpomínám si na člověka, který nás učil programování na gymplu. Ten mi byl schopen tvrdit, že když používám v Turbo Pascalu Exit (předčasný návrat z procedury nebo funkce, tj. obdoba céčkového return), stává se tím můj program nepřehledným a že přehlednější by bylo vnořit do sebe deset ifů…

Takže je potřeba si uvědomit, proč tam to goto je a zda přispívá k přehlednosti a srozumitelnosti kódu nebo ho naopak zatemňuje. Koneckonců vyšší jazyky běžně mají konstrukce, které jsou jen jinak pojmenované goto - v C je to třeba return, break nebo continue. A nebo třeba celý mechanismus výjimek, to je také jen maskované goto.

[VícNežNic]

Náznak goto je i ve slavné přečisté Javě

[Michal Kubeček]

Dokonce i v Pascalu (myslím teď skutečný Pascal, ne jeho komerční odvozeniny)… :-)

[VícNežNic]

No, já bych neřekl dokonce, přijde mi to celkem přirozené. Ale asi by to tam být nemuselo. V Pascalu by úplně stačilo, když jde nějak obarvit řádkový výstup a udělat jeho aspoň jednoduché stránkování, víc takový Pascalista moc nepotřebuje.

[Michal Kubeček]

Tím dokonce jsem myslel to, že Pascal je příklad jazyka, při jehož návrhu očividně praktická hlediska nehrála příliš významnou roli…

[VícNežNic]

Jistě. Nevymyslel to nakonec stejně Borland, nebo to tam opravdu bylo od začátku?

[Michal Kubeček]

Jestli úplně od začátku, to nevím, ale viděl jsem goto i v implementacích Pascalu, které neměly s Borlandem nic společného.

[deda.jabko]

bylo to tam od zacatku, mam tu knizku z roku 1988, odvolavajici se na iso7158,1982 a tam to je

[Mikos]

Tedy přirovnávat mechanismus výjimek ke goto je hodně troufalé tvrzení To se pohodlností a praktičností nedá srovnávat... možná tak kdybyste přirovna výjimky k nějakému hypergoto^2

[Michal Kubeček]

Výjimky jsou samozřejmě podstatně silnější, ale přirovnání je IMHO v pořádku, protože je to další mechanismus, který narušuje vizi ideálně čistého strukturovaného programování, které vystačí s podmíněným příkazem, cyklem a podprogramy. Výjimky jsou pak dalším krokem po konstrukcích typu return (předčasný), break nebo continue a společně ukazují, že při řešení chybových stavů může narušení toho ideálu vést naopak ke značnému zpřehlednění programu.

[Mikos]

To samozřejmě ano, myslel jsem to prostě tak, že od obyčejného gota mají výjimky hodně daleko (i když oboje narušuje onu ideu čistě strukturovaného programování). Asi jako nějaké ruční zemědělské nástroje ze středověku versus moderní počítačem řízený kombain

[Jiří (BoodOk) Kadeřávek]

Kdyby jen ke zprehledneni, ale ono se to jaksi i lepe pise (cti mysli). Lepe nez se nachazet ve stavu mysly odpovidajici sestnactemu zanoreni do serie podminek je proste komfortnejsi ty nevyhovujici stavy odpalit nekde na zacatku procedury. Nicmene jednu vyhodu nepouziti teto typicky lidske zkratkovite filosofie ma. Totiz, zrusme goto, return, break, continue a try catch a profilovat bude prochazka ruzovou zahradou.

[Michal Kubeček]

Pro mne je největším přínosem výjimek to, že mohu nezávisle na sobě řešit detekci chyby a její zpracování. Oboje tak mohu snadno umístit tam, kam se to logicky hodí, aniž bych musel řešit, jak obejít řídící struktury a jak mezi těmito dvěma místy přenést potřebná data.

[Jiří (BoodOk) Kadeřávek]

Try catch je fajn, to bezesporu. VB mel zalezitost, ktera se jmenovala error handlers. Neco jako On Error Goto ... Takovy try catch v bledemodrem. Nicmene, marne ve vyjimkach hledam On Error Resume Next (laicky receno, vykasli se na chybu a jdi dal). Samozrejme se da prislusna cast kodu uzavrit do prazdneho try catch, ale jsou to konstrukce navic. Na druhou stranu umoznuji vyjimky vicenasobne zanoreni, coz u error handleru neslo. Navic, error handler je vic goto nez vyjimka a tim padem i mene proceduralni. Takze ... at ziji vyjimky a returny.

[trekker.dk]

To měl už QBasic: ON ERROR GOTO Chyba

[deda.jabko]

to je relativni ono i system vyjimek muze zajistych okolnosti nadelat hromadu neplechy a protoze vsichni je pouzivaji, nikdo z nich nema strach jak z goto.

treba v c# se nemusi deklarovat vyjimky danych metod, v momente kdyz nejaka hluboko vnorena metoda vyvola neodchycenou vyjimku, jelikoz nejsou na povrch viditelne, malo kdo je odchytne v momente, kde by mel, takze to funguje jako jedno uzasne velke goto do neznama a muze skoncit padem aplikace, zejmana pri predavani projektu.

samozrejme vyjimky jsou sofistikovanejsi, ale muzou byt stejne nebezpecne.

[anicka]

Hlavne system vyjimek miva typicky solidni rezii... kdyz se da pouzit goto a kod zustane prehledny, urcite to pak pobezi lepe.

[Martin Beránek]

AFAIK v jave se ty vyjimky znacne vylepsily (rozdil mezi 1.3 a 1.4 byl velkej). drive neco vetsiho uzavrit do try bloku bylo na vykonosti znat, dnes temer ne...

[deda.jabko]

nojo, dijkstra ovlivnil informatiku v mnoha ohledech....

goto je prikaz pro opravdove muze, protoze jenom ti vi, kdy ho pouzit, ostatni z neho maji strach a nepouzivaji jej (toto sice neni z me hlavy, ale docela se s tim stozunuji)

zalezi fakt na tom, jestli je to vhodne pouzit nebo ne. btw. vzpominam si, jak mne jeste na gymplu ucitel nadaval za pouzivani nestrukturovaneho prikazu "break". do jiste miry mel pravdu, ale nikdo si verejne nedovoli pochybovat o spravnosti intrukce break, za to o goto toho bylo napsano spoustu nehezkeho.

[Luk]

K tomu jádru dodám, že tam má goto hluboký smysl kvůli přehlednosti kódu. V některých funkcích jsou někdy i desítky míst, kde něco může selhat. Protože se většinou musí provést nějaký úklid (něco odregistrovat, snížit počet referencí, uvolnit paměť apod.), nelze jen tak z funkce vyskočit. Proto by to jinak vedlo buď na mnoho vnořených podmínek nebo (při rozkladu na více funkcí) na celou kaskádu volání, ve kterých by se nikdo nevyznal. Proto se používá goto - při vhodně pojmenovaných návěštích je takový kód přehledný a srozumitelný.

[Kyosuke]

„Nicméně já mam velmi rád objektové programování, takže mě se goto a podobné konstrukce taky rozhodně nelíbí “

No jo, až na to, že volání metody je computed call/computed goto a ještě zkřížený se sebemodifikujícím programem...to by měli zakázat, že jo!

[Michal Kubeček]

až na to, že volání metody je computed call/computed goto

…volání virtuální metody…

[Kyosuke]

V opravdu objektových jazycích jiné metody než virtuální přeci nejsou...

[Michal Vyskočil]

Tenhle příspěvek jsem při psaní svého neviděl ... fakt

[Kyosuke]

Použil jsem "information hiding"...

[Michal Vyskočil]

Afaik smalltalkeři slovo virtuální metoda neznají, nebo ho považují za sprosté

[Mikos]

To je podpásovka Nezajímá mě jakým způsobem je volání metody realizované Zajímá mě jen jak je to přehledné a praktické a zapadá to do daného paradigmatu

[Mikos]

A vubec vždyť jsem psal že mam rád vysokoúrovňové jazyky Nezajímají mě stacky, registry, instrukce procesoru... o to ať se starají jiní

[VícNežNic]

Jinými slovy, programuješ na papíře pomocí tužky?

[Mikos]

A k tomu si přišel jak? To že se nechci zabývat nízkoúrovňovými věcmi neznamená že nemůžu programovat

Samozřejmě že třeba nějaký výkonný grafický engine (nebo podobně náročné věci) bych bohužel asi ve vysokoúrovňovém jazyku nenapsal, ale to já ani nepotřebuju...

[Michal Kubeček]

Mimochodem, 'on ... goto' není zdaleka nejúžasnější basicová vymoženost. Třeba na Spectru tahle konstrukce nebyla, ale zato argumentem goto mohl být výraz… :-)

[Kyosuke]

Třeba GOTO SIN(I) ...

[Heron]

EINE: EINE Is Not EMACS. :)
ZWEI: ZWEI Was EINE Initially. :D

Co to je proboha za patičku?

[Kyosuke]

Moje nejoblíbenější rekurzivní akronymy. Implementace EMACSu na raných lispovských počítačích v druhé polovině 70. let.

http://en.wikipedia.org/wiki/EINE

http://en.wikipedia.org/wiki/Zwei

[Kyosuke]

Hmmm, koukám, že ta druhá stránka ve Wikipedii vypadá, jako kdyby používali FAT fajlsystém a překřížily se jim klastry...

[VícNežNic]

Já bych podle výstupu na svém monitoru usuzoval, že Wikipedie šla právě do kytiček

[#Tom]

Už to zase jede.

[Jiří (BoodOk) Kadeřávek]

Dnes a vcera jsem mel neodbytny pocit, ze do kytek sel site mysql. Nezaregistroval jste to nekdo?

[LaurenDesouza]

Great post! If anyone is looking to enhance their job applications, I highly recommend checking out professional cv writing services. They offer excellent support to help you stand out in the job market.