abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
dnes 11:55 | Nová verze

Po půl roce vývoje od vydání verze 5.2 byla vydána nová verze 5.3 svobodného open source redakčního systému WordPress. Kódové označení Kirk bylo vybráno na počest amerického jazzového multiinstrumentalisty Rahsaana Rolanda Kirka.

Ladislav Hagara | Komentářů: 5
včera 22:44 | Nová verze

Intel dnes zveřejnil hned 18 upozornění na bezpečnostní chyby ve svých produktech. Řada z nich se týká procesorů. V upstream Linuxu se již objevují příslušné patche: TAA - TSX Asynchronous Abort (CVE-2019-11135), iTLB multihit (CVE-2018-12207), … K dispozici je také nová verze 20191112 mikrokódů.

Ladislav Hagara | Komentářů: 18
včera 19:00 | IT novinky

Příspěvek na blogu Mozilla Hacks představuje alianci s názvem Bytecode Alliance založenou společnostmi Mozilla, Fastly, Intel a Red Hat. Cílem aliance je dostat aplikace ve WebAssembly i mimo webový prohlížeč.

Ladislav Hagara | Komentářů: 2
včera 18:11 | Nová verze

Byla vydána nová major verze 1.4.0 webového poštovního klienta Roundcube (Wikipedie). Podrobný přehled novinek na GitHubu. Roundcube je nově responzivní, tj. podporuje také tablety a chytré telefony, viz náhledy.

Ladislav Hagara | Komentářů: 0
včera 17:11 | Nová verze

Byla vydána nová stabilní verze 18.06.5 linuxové distribuce primárně určené pro routery a vestavěné systémy OpenWrt (Wikipedie). Přehled změn v Changelogu. Jedná se o opravné vydání OpenWrt 18.06.0 vydaného v červenci 2018. Pro zájemce o testování je k dispozici první RC verze OpenWrt 19.07.0.

Ladislav Hagara | Komentářů: 3
včera 16:55 | Nová verze

Byla vydána verze 2.0 svobodné federalizované platformy pro sledování a sdílení videí, alternativy YouTube s podporou P2P, PeerTube (Wikipedie). Přehled novinek v příspěvku na Framablogu. Za vývojem PeerTube stojí nezisková organizace Framasoft snažící se mimo jiné nahradit svými svobodnými Frama službami služby společnosti Google (De-google-ify Internet). Bohužel ale musí některé své služby omezit.

Ladislav Hagara | Komentářů: 2
včera 10:11 | Komunita

Na přelomu října a listopadu proběhla v Lyonu GStreamer Conference 2019, tj. konference vývojářů multimediálního frameworku GStreamer. Videozáznamy přednášek byly zveřejněny na portálu UbiCast.

Ladislav Hagara | Komentářů: 0
11.11. 13:33 | Zajímavý článek

Christian Ude, bývalý dlouholetý starosta Mnichova, v rozhovoru pro německý Linux Magazin vzpomíná na projekt LiMux, kdy město přešlo na vlastní linuxovou infrastrukturu a OpenOffice.org (posléze LibreOffice), ale příští vládnoucí koalice se rozhodla vrátit se k produktům Microsoftu.

Fluttershy, yay! | Komentářů: 85
11.11. 13:22 | Komunita

Uživatelé Linuxu ve VirtualBoxu obvykle instalují Přídavky pro hosta (Guest Additions) pro lepší podporu emulovaného hardwaru. Brzy už ale nebudou přídavky potřebné. Ovladač vboxguest se dostal již do Linuxu 4.16 v dubnu loňského roku. Včera vydal Linus Torvalds Linux 5.4-rc7 (LKML). Přidán byl ovladač vboxsf (VirtualBox Shared Folder) pro sdílené složky.

Ladislav Hagara | Komentářů: 3
10.11. 23:44 | Nová verze

Byla vydána nová verze 1.40 editoru zdrojových kódů Visual Studio Code (Wikipedie). Přehled novinek i s náhledy a animovanými gify v poznámkách k vydání. Ve verzi 1.40 bylo vydáno také VSCodium, tj. komunitní sestavení Visual Studia Code bez telemetrie a licenčních podmínek Microsoftu.

Ladislav Hagara | Komentářů: 0
Jaké hodinky nosíte (nejčastěji)?
 (25%)
 (7%)
 (14%)
 (54%)
Celkem 120 hlasů
 Komentářů: 5, poslední dnes 13:28
Rozcestník

Poznamka k diskuzi o rekurzi

15.6.2013 15:56 | Přečteno: 1472× | Programování | Výběrový blog

Nedavno tu Gilhad remcal, ze pouzivani rekurze misto cyklu ve funkcionalnich jazycich je pomale, nepouzitelne, atd. Tenhle mytus je docela rozsireny, stejne jako to, ze GCC neumi poradne optimalizace. Jak to teda je...

Jako priklad si vezmeme faktorial:

int fact_rec(int n) {
        if (n == 0) return 1;
        return n * fact_rec(n - 1);
}

int fact_iter(int n) {
        int r = 1;
        for (int i = n; i >= 1; i--)
                r *= i;
        return r;
}

Pro rekurzivni faktorial generuje GCC (4.7.1) s prepinacem -O0 opravdu naivni kod.

   0:  push   rbp
   1:  mov    rbp,rsp
   4:  sub    rsp,0x10
   8:  mov    DWORD PTR [rbp-0x4],edi
   b:  cmp    DWORD PTR [rbp-0x4],0x0
   f:  jne    18 <fact_rec+0x18>
  11:  mov    eax,0x1
  16:  jmp    29 <fact_rec+0x29>
  18:  mov    eax,DWORD PTR [rbp-0x4]
  1b:  sub    eax,0x1
  1e:  mov    edi,eax
  20:  call   25 <fact_rec+0x25>
  25:  imul   eax,DWORD PTR [rbp-0x4]
  29:  leave
  2a:  ret

S prepinacem -O1 uz je to o neco lepsi, jsou odstranena zbytecna prirazeni, nevytvari se zbytecne ramec na zasobniku, jenom obsah registru ebx se uklada na zasobnik, ale porad je to kod, ktery se podoba tomu vstupnimu.

   0:  push   rbx
   1:  mov    ebx,edi
   3:  mov    eax,0x1
   8:  test   edi,edi
   a:  je     17 <fact_rec+0x17>
   c:  lea    edi,[rdi-0x1]
   f:  call   14 <fact_rec+0x14>
  14:  imul   eax,ebx
  17:  pop    rbx
  18:  ret

S prepinacem -O2 uz dostaveme neco trochu prekvapivejsiho, rekurze (vsimnte si, ze to neni bezna koncova rekurze) je prevedena na cyklus:

   0:  test   edi,edi
   2:  mov    eax,0x1
   7:  je     1a <fact_rec+0x1a>
   9:  nop    DWORD PTR [rax+0x0]
  10:  imul   eax,edi
  13:  sub    edi,0x1
  16:  jne    10 <fact_rec+0x10>
  18:  repz ret
  1a:  repz ret

Pro srovnani uvadim kod vygenerovany pro funkci fact_iter s prepinacem -O2:

   0:  test   edi,edi
   2:  mov    eax,0x1
   7:  jle    1a <fact_iter+0x1a>
   9:  nop    DWORD PTR [rax+0x0]
  10:  imul   eax,edi
  13:  sub    edi,0x1
  16:  jne    10 <fact_iter+0x10>
  18:  repz ret
  1a:  repz ret

Jak kazdy snadno nahledne, oba vystupy jsou stejne. Takze jake z toho plyne moralni ponauceni? Modre nebo zelene lentilky, stejne skonci vsechny stejnou barvou...

A jako bonus uvadim vysledek pro -O3.

   0:  test   edi,edi
   2:  je     12a <fact_rec+0x12a>
   8:  mov    edx,edi
   a:  mov    esi,edi
   c:  shr    edx,0x2
   f:  lea    ecx,[rdx*4+0x0]
  16:  test   ecx,ecx
  18:  je     130 <fact_rec+0x130>
  1e:  cmp    edi,0x6
  21:  jbe    130 <fact_rec+0x130>
  27:  lea    eax,[rdi-0x1]
  2a:  mov    DWORD PTR [rsp-0x18],edi
  2e:  movdqa xmm4,XMMWORD PTR [rip+XXXXX]
  35:
  36:  mov    DWORD PTR [rsp-0x14],eax
  3a:  lea    eax,[rdi-0x2]
  3d:  movd   xmm2,DWORD PTR [rsp-0x14]
  43:  mov    DWORD PTR [rsp-0x10],eax
  47:  lea    eax,[rdi-0x3]
  4a:  movd   xmm1,DWORD PTR [rsp-0x10]
  50:  mov    DWORD PTR [rsp-0xc],eax
  54:  xor    eax,eax
  56:  movd   xmm0,DWORD PTR [rsp-0xc]
  5c:  punpckldq xmm1,xmm0
  60:  movd   xmm0,DWORD PTR [rsp-0x18]
  66:  punpckldq xmm0,xmm2
  6a:  punpcklqdq xmm0,xmm1
  6e:  movdqa xmm1,XMMWORD PTR [rip+XXXXX]
  75:
  76:  nop    WORD PTR cs:[rax+rax*1+0x0]
  7d:
  80:  movdqa xmm3,xmm1
  84:  psrldq xmm1,0x4
  89:  add    eax,0x1
  8c:  movdqa xmm2,xmm0
  90:  cmp    edx,eax
  92:  pmuludq xmm3,xmm0
  96:  paddd  xmm0,xmm4
  9a:  psrldq xmm2,0x4
  9f:  pmuludq xmm2,xmm1
  a3:  pshufd xmm1,xmm3,0x8
  a8:  pshufd xmm2,xmm2,0x8
  ad:  punpckldq xmm1,xmm2
  b1:  ja     80 <fact_rec+0x80>
  b3:  movdqa xmm2,xmm1
  b7:  sub    edi,ecx
  b9:  cmp    esi,ecx
  bb:  psrldq xmm2,0x8
  c0:  movdqa xmm0,xmm2
  c4:  psrldq xmm2,0x4
  c9:  pmuludq xmm0,xmm1
  cd:  psrldq xmm1,0x4
  d2:  pshufd xmm0,xmm0,0x8
  d7:  pmuludq xmm1,xmm2
  db:  pshufd xmm1,xmm1,0x8
  e0:  punpckldq xmm0,xmm1
  e4:  movdqa xmm1,xmm0
  e8:  psrldq xmm1,0x4
  ed:  movdqa xmm2,xmm1
  f1:  psrldq xmm1,0x4
  f6:  pmuludq xmm2,xmm0
  fa:  psrldq xmm0,0x4
  ff:  pmuludq xmm1,xmm0
 103:  pshufd xmm0,xmm2,0x8
 108:  pshufd xmm1,xmm1,0x8
 10d:  punpckldq xmm0,xmm1
 111:  movd   DWORD PTR [rsp-0x18],xmm0
 117:  mov    eax,DWORD PTR [rsp-0x18]
 11b:  je     137 <fact_rec+0x137>
 11d:  nop    DWORD PTR [rax]
 120:  imul   eax,edi
 123:  sub    edi,0x1
 126:  jne    120 <fact_rec+0x120>
 128:  repz ret
 12a:  mov    eax,0x1
 12f:  ret
 130:  mov    eax,0x1
 135:  jmp    120 <fact_rec+0x120>
 137:  ret

Tuhle davku vogonske poezie se mi opravdu nechce rozebirat, ale vypada to, ze pro male hodnoty n (<= 6) se pouzije bezny algoritmus a na zbytek vypocet pomoci vektorovych instrukci.

       

Hodnocení: 94 %

        špatnédobré        

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

Komentáře

Vložit další komentář

15.6.2013 16:11 iwk
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
15.6.2013 17:43 JS
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Napada me, a prevest to na lookup table by neumel?
15.6.2013 18:07 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
To me napadlo jako prvni, jestli to nedela v ramci te hruzi generovane s -O3... ale vypada to, ze ne. Na druhou stranu ma predpocitany vektor cisel (radek 2e), ktery pak pouziva k dalsimu nasobeni, takze mozna by to zvladl, ale nechce se mu.
Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
15.6.2013 18:02 disorder | blog: weblog | Bratislava
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
o tomto som tiez pisal blog pred 3 rokmi, ked som sa k tomu dostal niekde cez reddit. implementovane to je v tree-tailcall.c

ale podla standardu sa na to neda spoliehat (a to prekvapivo ani v common lispe)
15.6.2013 18:30 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
o tomto som tiez pisal blog pred 3 rokmi, ked som sa k tomu dostal niekde cez reddit.

Občas se vracím k tématům, o kterých jsme už v Receptáři hovořili. Není divu, každý se nemůže dívat na všechny pořady. Tak třeba paní Emilie Bezoušková...
implementovane to je v tree-tailcall.c
Diky za info, presne tohle jsem chtel vedet. Cekal jsem, ze to bude sofistikovanejsi a vychazet primo z vnitrni SSA reprezentace.
ale podla standardu sa na to neda spoliehat (a to prekvapivo ani v common lispe)
V CommonLispu se podle standardu neda spolehat ani na ty tail cally.
Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
15.6.2013 19:50 Kvakor
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Je sice hezké, že překladač je dost chytrý na to, aby sám převáděl rekurze na cykly, ale když se objeví nějaké chybky, tak skutečnost, že neoptimalizovaný kód, který používá k ladění, se silně liší od optimalizovaného, může být za určitých okolností docela prolbematická ... Na druhou stranu, v C/C++ nejspíš nikdo takové věci stejně dělat nebude a v jiných jazycích to tolik nevadí, protože se o to postarají prostředky samotného jazyka i bez optimalizace.

PS: Ty oprefixované NOPy (obvlášť ten v poslední verzi vygenerované přes -O3) mně dostaly :-) I když pro moderní procesory je nejspíš lepší nacpat několik prefixů před jeden NOP než tam dát více "jednoduchých" NOPů, například pokud dekodér dokáže zahazovat nesmyslné prefixy.
15.6.2013 20:23 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
a v jiných jazycích to tolik nevadí, protože se o to postarají prostředky samotného jazyka i bez optimalizace.
V některých jazycích to jde vypnout – zejména kvůli ladění (např. v F#, k němuž se vztahovala původní diskuze).
16.6.2013 16:28 SkákalPřesOheňAžSiPropálilMokasíny | skóre: 29 | blog:
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Je sice hezké, že překladač je dost chytrý na to, aby sám převáděl rekurze na cykly, ale když se objeví nějaké chybky, tak skutečnost, že neoptimalizovaný kód, který používá k ladění, se silně liší od optimalizovaného, může být za určitých okolností docela prolbematická...
To ano, ovšem v GCC by mělo jít nějakým CFLAG zapnout jednu konkrétní optimalizaci, ne? Případně by mělo jít debugovat optimalizovaný kód apod...
PS: Ty oprefixované NOPy (obvlášť ten v poslední verzi vygenerované přes -O3) mně dostaly :-)
Kvůli čemu tam je? Zarovnání?

Jinak jednoduché NOPy se afaik nevidí už vlastně nikdy (na x86), pokud najdeš v binárce jednoduché NOPy, nejspíš se v ní někdo hrabal ;-)
16.6.2013 17:03 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Kvůli čemu tam je? Zarovnání?
Jo, kvuli zarovnani. AMD64 ma instrukcni cache o velikosti 16B, takze ma rado, kdyz jsou skoky zarovnane na 16B. Teoreticky by mely jit pouzit slozitejsi NOP i pro prefetch, ale na to mi prijde rozumnejsi pouzit primo instrukce prefetchX z SSE.
Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
16.6.2013 17:08 pc2005 | skóre: 38 | blog: GardenOfEdenConfiguration | liberec
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
AMD64 ma instrukcni cache o velikosti 16B
Jako velikost jednoho cacheline?
16.6.2013 19:06 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
jasne, samozrejme, ze cacheline...
Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
16.6.2013 19:27 pc2005 | skóre: 38 | blog: GardenOfEdenConfiguration | liberec
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Myslel jsem si to i když napoprvé jsem si to chybně dekódoval jako velikost prefetch queue u 386 :-D.
16.6.2013 19:24 pc2005 | skóre: 38 | blog: GardenOfEdenConfiguration | liberec
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Ty oprefixované NOPy (obvlášť ten v poslední verzi vygenerované přes -O3) mně dostaly
On je zajímavej i ten "repz ret". Tipoval bych to na ten prefetch jak psal deda.jabko. Pro ostatní co neví (;-)): "rep" je prefix cyklu a "ret" je návrat, takže tipuju, že mikrokód si při "rep" myslí, že nastane cyklus a další instrukci po "ret" nenačte, což je výhoda, protože se stejně bude skákat pryč (pro ty co ví: jak moc jsem se seknul? :-D).

Jinak ona je x86 tak šílená, že jí jednak nestačej volný hodnoty pro nový opkód a jednak se používaj různý kombinace i pro další věci. Například instrukce pause, což je vlastně jen sekvence dříve přeložitelná jako "rep nop". V Intelu to dělali už od začátku, schválně kdo bez internetu uhodne, co dělal původně na 80(1)86 opkód 0x0f (od zavedení chráněného módu jako prefix pro nové instrukce)? :-)

Jinak podobné legrácky, co používá kompilátor, jsou popsané taky tady.
16.6.2013 17:37 Jiří Veselský | skóre: 30 | blog: Jirkovo | Ostrava
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi

Jakó... To mi zní dost jako černá magie. Evidentně udělaly optimalizační metody v překladačích kus cesty kupředu od dob, kdy nás o nich nesměle učili, jak jakože umí třeba občas za vhodnej okolností vytáhnout mimo cyklus invariant... :)

Což o to, pokrok jde kupředu, ale todle mi přijde už fakt jako hodně moc. To je skoro jako kdyby ten překladač věděl, že počítáte faktoriál a prostě to celé udělal jinak, lépe a radostněji. Myslím tu poslední verzi. To mi jako někdo vysvětlete, jak todle pozná. Pochopit co dělá cizí zdroják je kolikrát problém pro člověka, ne tak pro stroj... :D

16.6.2013 17:59 SkákalPřesOheňAžSiPropálilMokasíny | skóre: 29 | blog:
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
To je skoro jako kdyby ten překladač věděl, že počítáte faktoriál a prostě to celé udělal jinak, lépe a radostněji.
A za chvíli ti řekne, aby sis s tou vázou nedělal starosti ;-)

Ne, váženě, ten překladač neví, že počítáš faktoriál, ale ví, že něco cyklicky děláš pomocí tail callu, a tak to převede to na cyklus.

Převádět rekurzi na cyklus a naopak jsme se učili někdy v druháku na střední v Packalu, takže jsem si jist, že pro moderní překladač to není problém....
16.6.2013 18:59 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Ne, váženě, ten překladač neví, že počítáš faktoriál, ale ví, že něco cyklicky děláš pomocí tail callu,
Vtip je v tom, ze v tom prikladu neni pouzity tail call, a presto to prekladac dokazal prelozit jako cyklus.
Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
16.6.2013 20:39 SkákalPřesOheňAžSiPropálilMokasíny | skóre: 29 | blog:
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Kouknul jsem na to, je to popsaný hned na začátku v komentářích v tom tree-tailcall.c.

V kostce: on pracuje s tail callem ve tvaru (obecně) return a + m * func(...);, kde a ani m nezávisí na výsledku toho tail volání. Předeve to na cyklus s akumulátory (zvlášť pro aditivní a multiplikativní proměnnou podle potřeby). Klasický tail call (tedy return func(...);) je pouze specielním případem, kdy a = 0, m = 1, tedy bez akumulátoru.

Chytrej trik.
16.6.2013 18:03 xxar3s
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Rekurzia sa prelozi na cyklus iba ked ako poslednu funkcia vola samu seba, tzn tail call.

tento map sa prelozi ako rekurzia, pri velkych zoznamoch hrozi stackoverflow:
let rec map mapper = function
| [] -> []
| x::xs -> mapper x :: (map mapper xs)
tento map sa prelozi ako cyklus:
let map mapper list =
    let rec map mapper acc = function
    | [] -> acc
    | x::xs -> xs |> map mapper (mapper x :: acc)
    list |> map mapper [] |> List.rev
16.6.2013 19:01 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Pointou toho celeho blogu bylo, ze tohle tvrzeni uplne neplati a prekladace dokazou i ten prvni typ rekurze prevest na cyklus.
Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
16.6.2013 22:00 xxar3s
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Niektore hej, bohuzial fsc toto zatial nepodporuje.
16.6.2013 20:24 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
tento map sa prelozi ako rekurzia, pri velkych zoznamoch hrozi stackoverflow:
Záleží na sémantice a implementaci. Např. v GHC Haskellu by byla preferována první verze.
tento map sa prelozi ako cyklus:
Bohužel toto řešení není příliš efektivní a ani přehledné.
16.6.2013 21:57 xxar3s
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Pridal som ešte tretí map (používa kontinuácie, takže nepotrebuje List.rev, ale pritom je tail-rekurzívny):
let rec map1 mapper = function
| [] -> []
| x::xs -> mapper x :: (map1 mapper xs)

let map2 mapper list =
    let rec map mapper acc = function
    | [] -> acc
    | x::xs -> map mapper (mapper x :: acc) xs
    List.rev (map mapper [] list)

let map3 mapper list =
    let rec map3 cnt mapper = function
    | [] -> cnt []
    | x::xs -> map3 (fun l -> cnt (mapper x :: l)) mapper xs
    map3 id mapper list
Podľa môjho testu:

map1: 3610 ms
map2: 2976 ms
map3: 3521 ms

je ten druhý map najrýchlejší (presne ako som očakával), ten prvý pri väčších zoznamoch vyhadzuje stackoverflow.
16.6.2013 23:31 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
To měříte F#, že?

Osobně bych čekal, že na krátkých seznamech bude nejrychlejší (z těch 3) ta první implementace. Pokud se vám chce, tak můžete změřit ještě knihovní List.map. Pro OCaml jsou nějaká měření v článku Optimizing List.map.
16.6.2013 19:57 pc2005 | skóre: 38 | blog: GardenOfEdenConfiguration | liberec
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Docela mě zaujalo, že tam jsou ty returny duplicitní a i v tom posledním (-O3) kódu je nepodmíněný skok (=další instrukce dosažitelná jen dalším jmp) a za ním return. Klidně by šlo imho volat nějakej již existující.

P.S. Pojďme si porovnávat (kompilátory!) :-D

gcc (GCC) 4.7.1 z aktuálního Slackware (vím, nemám 64bit OS :-( ). Kompilace přes "gcc -c zzzzzzzzzzzzz.c -O0" atd.

-O0
00000000 <fact_rec>:
   0:	55                   	push   %ebp
   1:	89 e5                	mov    %esp,%ebp
   3:	83 ec 18             	sub    $0x18,%esp
   6:	83 7d 08 00          	cmpl   $0x0,0x8(%ebp)
   a:	75 07                	jne    13 <fact_rec+0x13>
   c:	b8 01 00 00 00       	mov    $0x1,%eax
  11:	eb 10                	jmp    23 <fact_rec+0x23>
  13:	8b 45 08             	mov    0x8(%ebp),%eax
  16:	48                   	dec    %eax
  17:	89 04 24             	mov    %eax,(%esp)
  1a:	e8 fc ff ff ff       	call   1b <fact_rec+0x1b>
  1f:	0f af 45 08          	imul   0x8(%ebp),%eax
  23:	c9                   	leave  
  24:	c3                   	ret   
-O1
00000000 <fact_rec>:
   0:	53                   	push   %ebx
   1:	83 ec 18             	sub    $0x18,%esp
   4:	8b 5c 24 20          	mov    0x20(%esp),%ebx
   8:	85 db                	test   %ebx,%ebx
   a:	74 10                	je     1c <fact_rec+0x1c>
   c:	8d 43 ff             	lea    -0x1(%ebx),%eax
   f:	89 04 24             	mov    %eax,(%esp)
  12:	e8 fc ff ff ff       	call   13 <fact_rec+0x13>
  17:	0f af c3             	imul   %ebx,%eax
  1a:	eb 05                	jmp    21 <fact_rec+0x21>
  1c:	b8 01 00 00 00       	mov    $0x1,%eax
  21:	83 c4 18             	add    $0x18,%esp
  24:	5b                   	pop    %ebx
  25:	c3                   	ret    
-O2
00000000 <fact_rec>:
   0:	8b 54 24 04          	mov    0x4(%esp),%edx
   4:	b8 01 00 00 00       	mov    $0x1,%eax
   9:	85 d2                	test   %edx,%edx
   b:	74 0a                	je     17 <fact_rec+0x17>
   d:	8d 76 00             	lea    0x0(%esi),%esi
  10:	0f af c2             	imul   %edx,%eax
  13:	4a                   	dec    %edx
  14:	75 fa                	jne    10 <fact_rec+0x10>
  16:	c3                   	ret    
  17:	c3                   	ret    
-O3 == -O2

-Os
00000000 <fact_rec>:
   0:	55                   	push   %ebp
   1:	89 e5                	mov    %esp,%ebp
   3:	8b 55 08             	mov    0x8(%ebp),%edx
   6:	b8 01 00 00 00       	mov    $0x1,%eax
   b:	85 d2                	test   %edx,%edx
   d:	74 06                	je     15 <fact_rec+0x15>
   f:	0f af c2             	imul   %edx,%eax
  12:	4a                   	dec    %edx
  13:	eb f6                	jmp    b <fact_rec+0xb>
  15:	5d                   	pop    %ebp
  16:	c3                   	ret    
16.6.2013 20:23 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
vysledky zalezi jeste od nastaveni prekladace a pouziteho procesoru.

pokud dam "-O3 -m32 -march=pentium3" tak -O3 == -O2, ale s pentium4 uz to generuje kod s vektorovymi instrukcemi, pripadne to lze vynutit pouzitim -msse2.
Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
16.6.2013 20:45 pc2005 | skóre: 38 | blog: GardenOfEdenConfiguration | liberec
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Jasný, ale i tak je to rozdílný:

gcc -c zzzzzzzzzzzzz.c -O2 -march=core2
00000000 <fact_rec>:
   0:	8b 54 24 04          	mov    0x4(%esp),%edx
   4:	b8 01 00 00 00       	mov    $0x1,%eax
   9:	85 d2                	test   %edx,%edx
   b:	74 0d                	je     1a <fact_rec+0x1a>
   d:	8d 76 00             	lea    0x0(%esi),%esi
  10:	0f af c2             	imul   %edx,%eax
  13:	83 ea 01             	sub    $0x1,%edx
  16:	75 f8                	jne    10 <fact_rec+0x10>
  18:	f3 c3                	repz ret 
  1a:	f3 c3                	repz ret 
Kromě přidání těch repz (slackware default je i486) se změnil "dec" na "sub" (zajímavý, sub má delší opkód). Ještě zajímavější je ten "lea", což je jestli se nepletu taky jen "nop".
16.6.2013 21:38 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Rychlosti sub, dec a lea se docela lisi mezi jednotlivymi procesory, takze tomu se nedivim, ze to prehodil. Ta lea jako nop je zajimava, ... Nemuze to byt kvuli efektivnimu vytizeni jednotlivych pipeline?
Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
16.6.2013 23:29 pc2005 | skóre: 38 | blog: GardenOfEdenConfiguration | liberec
Rozbalit Rozbalit vše Re: Poznamka k diskuzi o rekurzi
Na 486 by měl "sub reg,imm" trvat jeden takt, navíc je to taková základní instrukce a pochybuju, že "dec" bude implementovaná v mikrokódu jinak než "sub reg,1". Navíc v rychlosti nalezené tvrzení.

Aha tak jsem to nakonec našel, "lea" je vycpávka jako "nop" s prefixama :-O.

BTW docela by mě zajímaly všechny ty vyjímky v mikrokódu, protože třeba "xchg eax,eax" je vlastně klasickej "nop" (stejnej opkód), ale obecně "xchg reg1,reg2" způsobí závislost použití registru.

Založit nové vláknoNahoru

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.