Rychlost Haskell vs. C++

Speedy

Rychlost Haskell vs. C++
« kdy: 22. 08. 2018, 14:35:49 »
Když Wadler (a to je nějaká kapacita) tvrdí, že Haskell je rychlejší než C++, čím to může být? Nějaké extra optimalizace?


optimizer

Re:Rychlost Haskell vs. C++
« Odpověď #1 kdy: 22. 08. 2018, 14:44:20 »
nějaký benchmark? Čekám další teoretickou diskuzi pseudointelektuálů.

oss

Re:Rychlost Haskell vs. C++
« Odpověď #2 kdy: 22. 08. 2018, 17:20:14 »
To cakam aj ja.

haskell


Re:Rychlost Haskell vs. C++
« Odpověď #4 kdy: 22. 08. 2018, 21:27:27 »
OMG

Ferari je prý rychlejší lakatoš.
Ale já musím jezdit po rozbitých lesních cestách a stahovat dřevo...


Hashgap

Re:Rychlost Haskell vs. C++
« Odpověď #5 kdy: 22. 08. 2018, 23:35:13 »
Nějaké extra optimalizace?
Wadler asi myslel rychlost psaní kódu. Běh záleží na použitých datových strukturách, nicméně třeba seznamy nebo hashmapy jsou ve FP v praxi stejně rychlé jako v C++.

optimizer

Re:Rychlost Haskell vs. C++
« Odpověď #6 kdy: 22. 08. 2018, 23:50:49 »
Nějaké extra optimalizace?
Wadler asi myslel rychlost psaní kódu. Běh záleží na použitých datových strukturách, nicméně třeba seznamy nebo hashmapy jsou ve FP v praxi stejně rychlé jako v C++.

seznamy jsou stejně pomalé všude, mimo FP se moc nepožívají. Mutable hashmapy v FP nejdou.

Hashgap

Re:Rychlost Haskell vs. C++
« Odpověď #7 kdy: 23. 08. 2018, 00:17:49 »
Nějaké extra optimalizace?
Wadler asi myslel rychlost psaní kódu. Běh záleží na použitých datových strukturách, nicméně třeba seznamy nebo hashmapy jsou ve FP v praxi stejně rychlé jako v C++.
Mutable hashmapy v FP nejdou.
Nikdo nemluvil o mutable. Proč reaguješ kravinama na něco, o čem nic nevíš?

JS

Re:Rychlost Haskell vs. C++
« Odpověď #8 kdy: 23. 08. 2018, 11:02:09 »
V obojim (Haskell i C++) se da psat rychly kod, pokud pouzijes dostatek usili. Je to cele jen o tom, ze C++ je jazyk nizsi urovne nez Haskell. Takze jednoduchy algoritmus, co nejak napises, bude pravdepodobne v C++ az o rad rychlejsi nez v Haskellu. Ale s tim, jak bude rust slozitost algoritmu nebo obecne toho, co delas, v Haskellu bude jednodussi dosahnout vyssiho vykonu (to neznamena, ze v C++ to nejde, jen to bude stat vetsi usili).

(Je mozne si predstavit analogickou situaci mezi assemblerem a C++, pro male programy je rucne psany assembler potencialne rychlejsi, ale tato vyhoda spatne skaluje.)

Haskell sam provadi nektere optimalizace, treba stream fusion (v podstate se da rict, ze je to slucovani smycek), ktere kompilatory nizsich jazyku obvykle nedelaji. Muzes je delat v ruce, ale to spatne skaluje s velikosti programu.

Dalsi vec je vyhodnocovani a s tim spojeny tradeoff (a to ma asi Wadler na mysli). Line vyhodnocovani je obecne pomalejsi pokud musime nejakou strukturu vyhodnotit celou, ale muze byt rychlejsi pokud ji nechceme vzdy vyhodnotit celou. V nekterych pripadech muze byt tedy program v Haskellu, co vyhodnocuje line, daleko rychlejsi nez program v C++, ktery vyhodnocuje striktne.

Kiwi

Re:Rychlost Haskell vs. C++
« Odpověď #9 kdy: 23. 08. 2018, 11:40:27 »
V obojim (Haskell i C++) se da psat rychly kod, pokud pouzijes dostatek usili. Je to cele jen o tom, ze C++ je jazyk nizsi urovne nez Haskell. Takze jednoduchy algoritmus, co nejak napises, bude pravdepodobne v C++ az o rad rychlejsi nez v Haskellu. Ale s tim, jak bude rust slozitost algoritmu nebo obecne toho, co delas, v Haskellu bude jednodussi dosahnout vyssiho vykonu (to neznamena, ze v C++ to nejde, jen to bude stat vetsi usili).

(Je mozne si predstavit analogickou situaci mezi assemblerem a C++, pro male programy je rucne psany assembler potencialne rychlejsi, ale tato vyhoda spatne skaluje.)

Haskell sam provadi nektere optimalizace, treba stream fusion (v podstate se da rict, ze je to slucovani smycek), ktere kompilatory nizsich jazyku obvykle nedelaji. Muzes je delat v ruce, ale to spatne skaluje s velikosti programu.

Dalsi vec je vyhodnocovani a s tim spojeny tradeoff (a to ma asi Wadler na mysli). Line vyhodnocovani je obecne pomalejsi pokud musime nejakou strukturu vyhodnotit celou, ale muze byt rychlejsi pokud ji nechceme vzdy vyhodnotit celou. V nekterych pripadech muze byt tedy program v Haskellu, co vyhodnocuje line, daleko rychlejsi nez program v C++, ktery vyhodnocuje striktne.
No, nevim...
https://stackoverflow.com/questions/7717691/why-is-the-minimalist-example-haskell-quicksort-not-a-true-quicksort

lopata

Re:Rychlost Haskell vs. C++
« Odpověď #10 kdy: 23. 08. 2018, 13:11:24 »
V obojim (Haskell i C++) se da psat rychly kod, pokud pouzijes dostatek usili. Je to cele jen o tom, ze C++ je jazyk nizsi urovne nez Haskell. Takze jednoduchy algoritmus, co nejak napises, bude pravdepodobne v C++ az o rad rychlejsi nez v Haskellu. Ale s tim, jak bude rust slozitost algoritmu nebo obecne toho, co delas, v Haskellu bude jednodussi dosahnout vyssiho vykonu (to neznamena, ze v C++ to nejde, jen to bude stat vetsi usili).
Jinými slovy tvrdíš, že jednoduché alogitmy Haskell překladač optimalizovat neumí a složité ano. Ne, takhle to v praxi opravdu nefunguje...

(Je mozne si predstavit analogickou situaci mezi assemblerem a C++, pro male programy je rucne psany assembler potencialne rychlejsi, ale tato vyhoda spatne skaluje.)
Doba, kdy byl ručně napsaný kód v assembleru rychlejší, než kód vygenerovaný překladačem, je dávno pryč. Dnešní CPU s dlouhou pipeline a spekulativním vyhodnocováním mají spoustu pravidel omezujících vykonávání instrukcí, které když se nedodrží, tak je kód pomalý. Člověk to rozumně nedokáže udržet v hlavě, překladač ano. V assembleru už má smysl psát jen SIMD kód, tohle překladače ještě úplně dobře nedávají.

Dalsi vec je vyhodnocovani a s tim spojeny tradeoff (a to ma asi Wadler na mysli). Line vyhodnocovani je obecne pomalejsi pokud musime nejakou strukturu vyhodnotit celou, ale muze byt rychlejsi pokud ji nechceme vzdy vyhodnotit celou. V nekterych pripadech muze byt tedy program v Haskellu, co vyhodnocuje line, daleko rychlejsi nez program v C++, ktery vyhodnocuje striktne.
Jenom v tom případě, když je kód v C++ napsaný blbě a vyhodnocuje i to, co nemusí. V runtime je jasné, co se musí vyhodnotit a co ne. Pokud se vyhodnocuje i něco navíc, je to chyba v programu. Haskell má výhodu, že to řeší automaticky, ale líne vyhodnocování má zase jiné nedostatky, např. bookkeeping overhead a horší lokalitu dat jak v instrukční, tak v datové cache, protože data se s líným vyhodnocováním nezpracovávají najednou na jednom místě, ale "po kouskách" postupně na mnoha místech.

JS

Re:Rychlost Haskell vs. C++
« Odpověď #11 kdy: 23. 08. 2018, 13:12:53 »
No, nevim...
https://stackoverflow.com/questions/7717691/why-is-the-minimalist-example-haskell-quicksort-not-a-true-quicksort

Co nevis? Vzdyt o tom presne pisu - pokud zkusis napsat (jednoduchy) algoritmus "naivne" v C++ a Haskellu, ten Haskell bude pravdepodobne pomalejsi.

JS

Re:Rychlost Haskell vs. C++
« Odpověď #12 kdy: 23. 08. 2018, 13:22:08 »
Jinými slovy tvrdíš, že jednoduché alogitmy Haskell překladač optimalizovat neumí a složité ano. Ne, takhle to v praxi opravdu nefunguje...
Netvrdim. To co tvrdim je, ze Haskell automatizuje nektere optimalizace, ktere musis v C++ delat rucne, ale ta automatizace se projevi az na vetsich programech. Neni to o tom, ze by ty jednoduche neumel.

Citace
Doba, kdy byl ručně napsaný kód v assembleru rychlejší, než kód vygenerovaný překladačem, je dávno pryč. Dnešní CPU s dlouhou pipeline a spekulativním vyhodnocováním mají spoustu pravidel omezujících vykonávání instrukcí, které když se nedodrží, tak je kód pomalý. Člověk to rozumně nedokáže udržet v hlavě, překladač ano. V assembleru už má smysl psát jen SIMD kód, tohle překladače ještě úplně dobře nedávají.
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.

Citace
Jenom v tom případě, když je kód v C++ napsaný blbě a vyhodnocuje i to, co nemusí. V runtime je jasné, co se musí vyhodnotit a co ne. Pokud se vyhodnocuje i něco navíc, je to chyba v programu. Haskell má výhodu, že to řeší automaticky, ale líne vyhodnocování má zase jiné nedostatky, např. bookkeeping overhead a horší lokalitu dat jak v instrukční, tak v datové cache, protože data se s líným vyhodnocováním nezpracovávají najednou na jednom místě, ale "po kouskách" postupně na mnoha místech.
S tim souhlasim a je to jen jinymi slovy to, co jsem napsal. To, co rikam navic je, ze napsat ten kod v C++ spravne (ve smyslu ne-blbe) je slozitejsi nez napsat ho spravne v Haskellu, protoze C++ je jazyk nizsi urovne.

lopata

Re:Rychlost Haskell vs. C++
« Odpověď #13 kdy: 23. 08. 2018, 13:47:52 »
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áš. 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. V C++ si můžu vybrat, jestli konkrétní algoritmus implementuji líně nebo žravě, v Haskellu si moc vybírat nemůžu. I v Haskellu by to asi šlo napsat tak, aby se výpočet efektivně prováděl žravě, ale je to tak trochu hack, který jde proti filozofii jazyka a stejně se bude i v takovém připadě líné vyhodnocování řešit někde na pozadí, i když není vůbec potřeba. Líného vyhodnocování se v Haskellu moc nejde zbavit a je to overhead navíc.

Kit

Re:Rychlost Haskell vs. C++
« Odpověď #14 kdy: 23. 08. 2018, 13:59:25 »
No, nevim...
https://stackoverflow.com/questions/7717691/why-is-the-minimalist-example-haskell-quicksort-not-a-true-quicksort

Otázkou zůstává, proč by někdo v Haskellu programoval quicksort, když má svůj nativní sort. Pokud budeš požadovat implementaci algoritmu, imperativní jazyky by měly být rychlejší. Pokud budeš požadovat určitou funkcionalitu, budou mít navrch funkcionální jazyky.