Pekelná konstrukce

27.5.2007 17:47 | Přečteno: 1857× | Ani zbla | poslední úprava: 27.5.2007 17:51

Kdysi dávno jsem byl v konferencích cecko@pandora.cz a os@pandora.cz. Už nevím, do které z nich kdosi poslal kus kódu v céčku, který řadu přítomných udivil. Jednalo se o Duff's device, které by se ale mělo jmenovat spíš Hell device. Po letech jsem na tuto konstrukci znovu narazil, tak se s vámi chci podělit

O co jde? Je to kus kódu, kde je konstrukce switch promíchána s jinou konstrukcí - v tomto případě do/while. A je to validní céčkový zdroják.

 
switch (count % 8)  /* count > 0 assumed */
 {
   case 0:        do {  *to++ = *from++;
   case 7:              *to++ = *from++;
   case 6:              *to++ = *from++;
   case 5:              *to++ = *from++;
   case 4:              *to++ = *from++;
   case 3:              *to++ = *from++;
   case 2:              *to++ = *from++;
   case 1:              *to++ = *from++;
                     } while ((count -= 8) > 0);
 }

K čemu je to dobré? Dnes k ničemu. Ale v 80. letech se dělaly optimalizace na zmenšení počtu větvení programu, takže výše uvedený kód byl rychlejší než:

 do {                          /* count > 0 assumed */
   *to++ = *from++;            
 } while (--count > 0);

Dneska už jsou procesory někde jinde, zrychlení to nepřinese. A programátoři takhle už optimalizovat neumí - za vše mluví, že když jsem si psal na tohle benchmark, vyrobil jsem Segmentation Fault. Jdu zase Pythonit.

       

Komentáře

[Ondřej Čečák]

"A programátoři takhle už optimalizovat neumí -- za vse mluvi ..."

Nebo to, ze tvrdi, ze Java je pomala.

[Michal Kubeček]

1. Pokud by taková optimalizace skutečně pomohla, měl by ji dělat překladač, ne programátor. Takhle zprasit a znečitelnit zdroják kvůli drobnému zrychlení, to nejsem při nejlepší vůli ochoten považovat za chvályhodné.

2. Současné verze GCC (a nejspíš i jiných překladačů) mají funkce typu memcpy() implementované jako builtin, který už je optimalizován pro danou platformu.

3. Až někdy nebudu mít do čeho dloubnout, docela rád se podívám, jestli je to syntakticky opravdu v pořádku nebo jestli je to jen nepozornost překladače.

[b42]

Dnes uz asi takova optimalizace nema opodstatneni, nicmene v teto podobe vznikla pred temer 25 lety a v te dobe asi byly veci trochu jine nez jsou dnes:) viz wikipedia

[b42]

Divam se ze link je i v clanku. Omlouvam se a prosim vsechny, aby se tvarili jako ze jsem nic nenapsal.

[alblaho]

Ty jsi ten post snad vůbec nečetl. Jasně říkám, že dnes už je to pasé. Navíc to ani není hezké, ale spíš je to kuriozita.

Syntakticky to v pořádku opravdu je. Dokonce i v C++, pač Stroustrup to má údajně v knížce

[Michal Kubeček]

Na platnosti věty "Takhle zprasit a znečitelnit zdroják kvůli drobnému zrychlení, to nejsem při nejlepší vůli ochoten považovat za chvályhodné." trvám bez ohledu na rok vzniku takové hrůzy.

[Kyosuke]

Takže ekvivalent v assembleru by byla "nepřenositlelná hrůza", když tohle je přenositelná hrůza?

[Michal Kubeček]

Od toho, kdo programuje v assembleru, se takové hrůzy víceméně očekávají. Ve vyšším programovacím jazyce (šetřte klávesnici, céčko je vyšší programovací jazyk) by se mělo myslet i na srozumitelnost kódu.

[Kyosuke]

Ehm, já vím, že Cčko je vyšší jazyk - kdyby nebylo, nebylo by přece (z definice vyššího jazyka) přenositelné.

[Michal Vyskočil]

Když slyším vyšší jazyk, tak mě vždy napadne změřit výšku jejich specifikace

[deda.jabko]

v tom pripade nejvyssim programovacim jazykem je bezesporu Open XML

[Kyosuke]

1) Kompilátory Cčka v roce 1983 na strojích s omezeným množstvím paměti neměly zrovna mistrovské optimalizátory. A to zrychlení v danou chvíli asi nebylo "drobné", myslím, že bylo dvojnásobné nebo tak nějak. Teoreticky bych ho (na modernějším VAXu) mohl zkusit změřit, luštit latenci VAXích instrukcí ze specifikace se mi nechce, je příliš tlustá a jednoduchá tabulka v ní není.

2) Tohle ale nebyl memcpy(). Nebo aspoň ne původně: Alblaho měl vložit původní verzi, jejíž smysl je poněkud čitelnější (viz Wikipedia).

[alblaho]

No, ta původní verze dělá tohle:

 do {                          /* count > 0 assumed */
   *to = *from++;              /* Note that the to pointer is NOT incremented */
 } while (--count > 0);

Tedy neinkrementuje pointer to. Čuměl jsem na to jak puk, a myslel jsem, že ostatní čtenáři by čuměli taky. Pak jsem si přečetl, že na adrese to je namapován I/O port a rozsvítilo se mi. Takže původní verze sice nelze smést ze stolu tvrzením "použij memcpy", ale zato je dnes zcela dokonale pasé. I když jednou jsem v nějaké embedded krabičce na port takhle přistupoval...

[jekub]

ad 3, syntakticky je to v pořádku, dokonce to uvádí Bjarne Stroustrup jako cvičení po některé kapitole v "C++ Programovací jazyk"

[Ladicek]

Kdysi dávno jsem byl v konferencích cecko@pandora.cz a os@pandora.cz.

A proč už nečteš OS? Nedávno jsme tam probírali, jestli by náhodou kluci od Flexu nechtěli to svoje dítko opensourcovat

Tedy ve skutečnosti o tom padly dvě věty a zas to šlo hodně rychle do kytek. Ale co, Aleš Procháska byl celkem pro

[alblaho]

Jsem myslel, že už se zajímá jen o potápění.

Jak je znám, tak by si stejně vymysleli licenci nekompatibilní s čímkoliv. "Můžete linkovat s tím a tím, jen když si budete hvízdat Most přes řeku Kwai"

[Andrej]

Tento hustý kousek kódu mě zaujal natolik, že jsem udělal malý benchmark.