Poznamka k diskuzi o rekurzi (diskuse)

[iwk]

Pokračování tady

[JS]

Napada me, a prevest to na lookup table by neumel?

[deda.jabko]

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.

[disorder]

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)

[deda.jabko]

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.

[Kvakor]

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.

[Radek Miček]

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).

[kralyk z abclinuxu]

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

[deda.jabko]

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.

[pc2005]

AMD64 ma instrukcni cache o velikosti 16B

Jako velikost jednoho cacheline?

[deda.jabko]

jasne, samozrejme, ze cacheline...

[pc2005]

Myslel jsem si to i když napoprvé jsem si to chybně dekódoval jako velikost prefetch queue u 386 .

[pc2005]

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? ).

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.

[Jiří Veselský]

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

[kralyk z abclinuxu]

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....

[deda.jabko]

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.

[kralyk z abclinuxu]

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.

[xxar3s]

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

[deda.jabko]

Pointou toho celeho blogu bylo, ze tohle tvrzeni uplne neplati a prekladace dokazou i ten prvni typ rekurze prevest na cyklus.

[xxar3s]

Niektore hej, bohuzial fsc toto zatial nepodporuje.

[Radek Miček]

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é.

[xxar3s]

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.

[Radek Miček]

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.

[pc2005]

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!)

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    

[deda.jabko]

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.

[pc2005]

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".

[deda.jabko]

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?

[pc2005]

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.