Rychlost Haskell vs. C++

[JSH]

To je věštení z křišťálové koule, kterou nemáš. Přitom vůbec nebereš v úvahu fundamentální odlišnosti Haskellu, které jsou dané líným vyhodnocováním. Líné vyhodnocování je největší deviza a zároveň prokletí Haskellu, protože přímo diktuje způsob zpracování dat. Žravé vyhodnocování vezme nějaký balík dat a přetransformuje je všechny najednou A -> B. Potom vezme znovu ten velký balík dat a přetransformuje je znovu B -> C. Líné vyhodnocování to bude dělat po jednotlivých prvcích A1 -> B1 -> C1, A2 -> B2 -> C2, ... Teoreticky je složitost žravého i líného vyhodnocení stejná, ale ten žravý způsob je na standardním hardware obvykle o hodně rychlejší kvůli lepšímu využití cache.

Pokud jde jen o pořadí vyhodnocování, tak samotné líné vyhodnocování je pro cache lepší. Po A1->B1 máme B1 v cache a dává smysl ho hned použít a ne ho načítat znova až projedeme všechny A->B.
Problém je v tom, že pro implementaci líného vyhodnocování v Haskellu jsou třeba boxované hodnoty. Ty jednotlivé prvky jsou rozházené po paměti a prefetcher to úplně nedává.
V C++ se právě docela často používá spojování dílčích operací do jedné veliké přes expression templates třeba v knihovnách pro matice.

[Reklama]

[lopata]

Pokud jde jen o pořadí vyhodnocování, tak samotné líné vyhodnocování je pro cache lepší. Po A1->B1 máme B1 v cache a dává smysl ho hned použít a ne ho načítat znova až projedeme všechny A->B.

Není to lepší, protože A1 načte celou cache line. B1 načte taky celou cache line, stejně jako C1, D1, E1... Snadno se stane, že při vyhodnocení A2 už není A1 cache line v cache, protože ji vytlačily další data a čte se znovu z paměti. Stejný problém se týká i instrukční cache a branch predictoru, také mají omezenou velikost, která s hloubkou zanoření velmi rychle přeteče.

A znovu opakuji, v C++ si můžu vybrat, jestli zvolím líné nebo žravé vyhodnocení podle výhodnosti pro konkrétní úlohu, v Haskellu si moc vybírat nemůžu, jsem omezený líným vyhodnocením.

[JS]

S tim souhlasim. A totez bude jednou platit pro Haskell a C++ (nebude se vyplacet psat v C++ protoze kompilator Haskellu - nebo jineho vyssiho jazyka - bude temer vzdy chytrejsi); je to jen otazka casu.

To je věštení z křišťálové koule, kterou nemáš.

Rad bych napsal, ze kristalovou kouli doma mam, ale fakt je, ze nemam. Nicmene, da se urcite koupit..

Kazdopadne, jde mi o to, ze v podobne situaci jsme uz historicky byli s tim C++ a assemblerem, nekdy v 80. az 90. letech minuleho stoleti, a taky se o tom vedly velke debaty. A skoncilo to tim, ze automatizace (kompilator) vyhral. Stejne tak myslim (bez koule), ze vyhraje i v tomto pripade. (Haskellovy kompilator uz dnes dela treba strictness analyzu, viz https://wiki.haskell.org/Performance/Strictness, takze minimalne v tomhle je napred pred C++ kompilatorem.)

Přitom vůbec nebereš v úvahu fundamentální odlišnosti Haskellu, které jsou dané líným vyhodnocováním.

Jak to, vzdyt jsem o tom v tomto vlakne zacal?

Líného vyhodnocování se v Haskellu moc nejde zbavit a je to overhead navíc.

Ja jsem si to driv taky myslel, ale dnes si myslim, ze to neni pravda a zbavit se jej lze docela pekne (a rozhodne myslim, ze je to jednodussi nez donutit C++ program chovat se line). Viz napriklad https://www.fpcomplete.com/blog/2017/09/all-about-strictness. Mam za to, ze je to proste spis o zvyku. Jinak dobra knizka k tematu, co ted ctu, je https://www.packtpub.com/application-development/haskell-high-performance-programming.

[Bacsa]

Pokud jde jen o pořadí vyhodnocování, tak samotné líné vyhodnocování je pro cache lepší. Po A1->B1 máme B1 v cache a dává smysl ho hned použít a ne ho načítat znova až projedeme všechny A->B.

A znovu opakuji, v C++ si můžu vybrat, jestli zvolím líné nebo žravé vyhodnocení podle výhodnosti pro konkrétní úlohu, v Haskellu si moc vybírat nemůžu, jsem omezený líným vyhodnocením.

Ano, Haskell je defaultně líný, ale v FP obecně si většinou můžu vybrat eager vs. lazy.

[JSH]

Pokud jde jen o pořadí vyhodnocování, tak samotné líné vyhodnocování je pro cache lepší. Po A1->B1 máme B1 v cache a dává smysl ho hned použít a ne ho načítat znova až projedeme všechny A->B.

Není to lepší, protože A1 načte celou cache line. B1 načte taky celou cache line, stejně jako C1, D1, E1... Snadno se stane, že při vyhodnocení A2 už není A1 cache line v cache, protože ji vytlačily další data a čte se znovu z paměti. Stejný problém se týká i instrukční cache a branch predictoru, také mají omezenou velikost, která s hloubkou zanoření velmi rychle přeteče.

Tady samozřejmě hrozně záleží na tom, jak velké jsou ty prvky, jak složité jsou ty operace a na spoustě dalších věcí. Já chtěl jenom vypíchnout, že to žravé vyhodnocení nemusí být vždycky pro cache lepší a naopak se v maticových knihovnách (třeba C++ Eigen) ty dílčí operace běžně spojují do větších. Obzvlášt, když díky tomu to pole Bček může úplně zmizet.

A znovu opakuji, v C++ si můžu vybrat, jestli zvolím líné nebo žravé vyhodnocení podle výhodnosti pro konkrétní úlohu, v Haskellu si moc vybírat nemůžu, jsem omezený líným vyhodnocením.

I v tom Haskellu se dá (jakž takž) vybrat. Prvky struktur se dají anotovat jako striktní nebo dokonce neboxované.

[Reklama]

[lopata]

S tim souhlasim. A totez bude jednou platit pro Haskell a C++ (nebude se vyplacet psat v C++ protoze kompilator Haskellu - nebo jineho vyssiho jazyka - bude temer vzdy chytrejsi); je to jen otazka casu.

To je věštení z křišťálové koule, kterou nemáš.

Rad bych napsal, ze kristalovou kouli doma mam, ale fakt je, ze nemam. Nicmene, da se urcite koupit..

Kazdopadne, jde mi o to, ze v podobne situaci jsme uz historicky byli s tim C++ a assemblerem, nekdy v 80. az 90. letech minuleho stoleti, a taky se o tom vedly velke debaty. A skoncilo to tim, ze automatizace (kompilator) vyhral. Stejne tak myslim (bez koule), ze vyhraje i v tomto pripade. (Haskellovy kompilator uz dnes dela treba strictness analyzu, viz https://wiki.haskell.org/Performance/Strictness, takze minimalne v tomhle je napred pred C++ kompilatorem.)

Přitom vůbec nebereš v úvahu fundamentální odlišnosti Haskellu, které jsou dané líným vyhodnocováním.

Jak to, vzdyt jsem o tom v tomto vlakne zacal?

Líného vyhodnocování se v Haskellu moc nejde zbavit a je to overhead navíc.

Ja jsem si to driv taky myslel, ale dnes si myslim, ze to neni pravda a zbavit se jej lze docela pekne (a rozhodne myslim, ze je to jednodussi nez donutit C++ program chovat se line). Viz napriklad https://www.fpcomplete.com/blog/2017/09/all-about-strictness. Mam za to, ze je to proste spis o zvyku. Jinak dobra knizka k tematu, co ted ctu, je https://www.packtpub.com/application-development/haskell-high-performance-programming.

Já nevím, mně to přijde celé ujeté. Haskell přišel s nějakým designových rozhodnotím (lazy evaluation), což má nějaké výhody a nevýhody. Během doby se přišlo na to, že lazy evaluation stojí docela dost výkonu, tak se hledalo, jak z toho ven. Transparentní optimalizace překladače beru, ty jsou v pohodě, ať si překladač klidně dělá strictness analyzu (kterou mimochodem C++ překladač na nic nepotřebuje) a vyhodí všechno, co nemusí být lazy, abych se o to nemusel starat, to je fajn. Ale proč se tím mám sakra zabývat jako uživatel a přemýšlet, jestli mám napsat foldl nebo foldl' a když náhodou na ten apostrof zapomenu, tak všechno bude zdánlivě fungovat, ale aplikace zhavaruje v nejméně vhodnou dobu v produkci, když dostane nějaká větší data? Sorry jako, takhle podle mě nevypadá mainstreamový jazyk vhodný pro produkční nasazení, ve kterém bych se odvážil psát nějakou větší aplikaci.

[JSH]

Já nevím, mně to přijde celé ujeté. Haskell přišel s nějakým designových rozhodnotím (lazy evaluation), což má nějaké výhody a nevýhody. Během doby se přišlo na to, že lazy evaluation stojí docela dost výkonu, tak se hledalo, jak z toho ven. Transparentní optimalizace překladače beru, ty jsou v pohodě, ať si překladač klidně dělá strictness analyzu (kterou mimochodem C++ překladač na nic nepotřebuje) a vyhodí všechno, co nemusí být lazy, abych se o to nemusel starat, to je fajn. Ale proč se tím mám sakra zabývat jako uživatel a přemýšlet, jestli mám napsat foldl nebo foldl' a když náhodou na ten apostrof zapomenu, tak všechno bude zdánlivě fungovat, ale aplikace zhavaruje v nejméně vhodnou dobu v produkci, když dostane nějaká větší data? Sorry jako, takhle podle mě nevypadá mainstreamový jazyk vhodný pro produkční nasazení, ve kterém bych se odvážil psát nějakou větší aplikaci.

Designových rozhodnutí, nad kterými musí programátor přemýšlet, má každý jazyk mraky. V produkci na větších datech chcípe i to C++. Stačí třeba uvolňovat větší strom smart pointerů.

[lopata]

Designových rozhodnutí, nad kterými musí programátor přemýšlet, má každý jazyk mraky. V produkci na větších datech chcípe i to C++. Stačí třeba uvolňovat větší strom smart pointerů.

Jenomže v Haskellu je to narovnávák na ohýbák. Vývoj Haskellu: uděláme lazy evaluation, to bude super! (až doteď dobrý, já proti lazy evaluation v podstatě nic nemám :-)). No jo, ale ono to nefunguje vždycky optimálně, co s tím? Nějak to uděláme, aby lazy ve skutečnosti nebylo lazy... A ten způsob, jak to do jazyka implementovali, je podlě mě nešťastný.

[Bacsa]

Já nevím, mně to přijde celé ujeté. Haskell přišel s nějakým designových rozhodnotím (lazy evaluation), což má nějaké výhody a nevýhody. Během doby se přišlo na to, že lazy evaluation stojí docela dost výkonu, tak se hledalo, jak z toho ven. Transparentní optimalizace překladače beru, ty jsou v pohodě, ať si překladač klidně dělá strictness analyzu (kterou mimochodem C++ překladač na nic nepotřebuje) a vyhodí všechno, co nemusí být lazy, abych se o to nemusel starat, to je fajn. Ale proč se tím mám sakra zabývat jako uživatel a přemýšlet, jestli mám napsat foldl nebo foldl' a když náhodou na ten apostrof zapomenu, tak všechno bude zdánlivě fungovat, ale aplikace zhavaruje v nejméně vhodnou dobu v produkci, když dostane nějaká větší data? Sorry jako, takhle podle mě nevypadá mainstreamový jazyk vhodný pro produkční nasazení, ve kterém bych se odvážil psát nějakou větší aplikaci.

Designových rozhodnutí, nad kterými musí programátor přemýšlet, má každý jazyk mraky. V produkci na větších datech chcípe i to C++. Stačí třeba uvolňovat větší strom smart pointerů.

Strom smart pointerů a normálních pointerů na tom jsou stejně.

[JSH]

Já nevím, mně to přijde celé ujeté. Haskell přišel s nějakým designových rozhodnotím (lazy evaluation), což má nějaké výhody a nevýhody. Během doby se přišlo na to, že lazy evaluation stojí docela dost výkonu, tak se hledalo, jak z toho ven. Transparentní optimalizace překladače beru, ty jsou v pohodě, ať si překladač klidně dělá strictness analyzu (kterou mimochodem C++ překladač na nic nepotřebuje) a vyhodí všechno, co nemusí být lazy, abych se o to nemusel starat, to je fajn. Ale proč se tím mám sakra zabývat jako uživatel a přemýšlet, jestli mám napsat foldl nebo foldl' a když náhodou na ten apostrof zapomenu, tak všechno bude zdánlivě fungovat, ale aplikace zhavaruje v nejméně vhodnou dobu v produkci, když dostane nějaká větší data? Sorry jako, takhle podle mě nevypadá mainstreamový jazyk vhodný pro produkční nasazení, ve kterém bych se odvážil psát nějakou větší aplikaci.

Designových rozhodnutí, nad kterými musí programátor přemýšlet, má každý jazyk mraky. V produkci na větších datech chcípe i to C++. Stačí třeba uvolňovat větší strom smart pointerů.

Strom smart pointerů a normálních pointerů na tom jsou stejně.

Já tím myslel klasický bug, kdy objekty mají smart pointery na další objekty a destruktory se volají rekurzivně až občas přeteče zásobník. U smart pointerů je to víc zákeřné, protože tam ta rekurze v destruktorech není na první pohled vidět.

[andy]

Jenomže v Haskellu je to narovnávák na ohýbák. Vývoj Haskellu: uděláme lazy evaluation, to bude super! (až doteď dobrý, já proti lazy evaluation v podstatě nic nemám :-)). No jo, ale ono to nefunguje vždycky optimálně, co s tím? Nějak to uděláme, aby lazy ve skutečnosti nebylo lazy... A ten způsob, jak to do jazyka implementovali, je podlě mě nešťastný.

Nechápu. V jazyce, který je defaultně strict musíš dělat opičárny, pokud to chceš lazy. V Haskellu holt musíš dělat opičárny, pokud to chceš strict. Mně to přijde prašť jako uhoď - a default lazy je na spoustu věcí fakt pěkná záležitost (tying the knot).

On je třeba problém, že seq není referenčně transparentní - na druhou stranu ono to je prakticky vždycky jedno.

[lopata]

Nechápu. V jazyce, který je defaultně strict musíš dělat opičárny, pokud to chceš lazy. V Haskellu holt musíš dělat opičárny, pokud to chceš strict. Mně to přijde prašť jako uhoď - a default lazy je na spoustu věcí fakt pěkná záležitost (tying the knot).

Reálně obvykle řešíš problém, jestli chceš nějaký balík dat zpracovat najednou, nebo postupně. Ve strict jazyce je to přímočaré v obou případech:

Kód: [Vybrat]

i = 0;
for (a : pole_a) {
    pole_b[i++] = foo(a);
}
i = 0;
for (b : pole_b) {
    pole_c[i++] = bar(b);
}
nebo:

Kód: [Vybrat]

i = 0;
for (a : pole_a) {
    pole_c[i++] = bar(foo(a));
}
Někdy je výhodnější první varianta, jindy druhá. Musím explicitně zvolit, jakou chci, ale obě řešení jsou jasná a přímočará. Haskell je defaultně lazy a nejde to vypnout. Ano i Haskell můžu přinutit, aby lazy nebyl, ale je to narovnávák na ohýbák, ten jazyk nebyl navržený na to, aby byl strict, je pořád lazy, i když ho přinutím spočítat něco "předčasně".

[v]

Nechápu. V jazyce, který je defaultně strict musíš dělat opičárny, pokud to chceš lazy. V Haskellu holt musíš dělat opičárny, pokud to chceš strict. Mně to přijde prašť jako uhoď - a default lazy je na spoustu věcí fakt pěkná záležitost (tying the knot).

Reálně obvykle řešíš problém, jestli chceš nějaký balík dat zpracovat najednou, nebo postupně. Ve strict jazyce je to přímočaré v obou případech:

Kód: [Vybrat]

i = 0;
for (a : pole_a) {
    pole_b[i++] = foo(a);
}
i = 0;
for (b : pole_b) {
    pole_c[i++] = bar(b);
}
nebo:

Kód: [Vybrat]

i = 0;
for (a : pole_a) {
    pole_c[i++] = bar(foo(a));
}
Někdy je výhodnější první varianta, jindy druhá. Musím explicitně zvolit, jakou chci, ale obě řešení jsou jasná a přímočará. Haskell je defaultně lazy a nejde to vypnout. Ano i Haskell můžu přinutit, aby lazy nebyl, ale je to narovnávák na ohýbák, ten jazyk nebyl navržený na to, aby byl strict, je pořád lazy, i když ho přinutím spočítat něco "předčasně".

nestačí tohle https://ghc.haskell.org/trac/ghc/wiki/StrictPragma#Strict ?

[lopata]

nestačí tohle https://ghc.haskell.org/trac/ghc/wiki/StrictPragma#Strict ?

Chápu motivaci, proč to udělali. Ale když si přečteš tohle: http://blog.johantibell.com/2015/11/the-design-of-strict-haskell-pragma.html, tak zjistíš, že je to zase jenom narovnávák na ohýbák. Jiný způsob, jak donutit jazyk, který je defaultně lazy a vždycky bude lazy, aby byl někdy strict. Což má samozřejmě některé nepříjemné vedlejší efekty, nejde to použít slepě, musí se u toho přemýšlet, protože spousta kódu závisí na tom, že se vyhodnocuje lazy a ne strict.

Přitom jediná motivace k takovým opičárnám je výkon. Lazy vyhodnocení je super, ale nepoužitelné pro high performace kód. Takže se to nějak udělá...

[v]

Takže se to nějak udělá...

no a kde je problém?