O pythone a rýchlosti

10.8.2014 20:20 | Přečteno: 6726× | Programovanie | | poslední úprava: 10.8.2014 20:45

To že autor referenčnej implementácie pythonu si z výkonu ťažkú hlavu nerobí je vo všeobecnosti známe. Benchmarky referenčnej implementácie sú pomerne jednoznačné (škoda, že medzi benchmarky nechcú zaradiť PyPy). V dnešnom blogu sa pozrieme tak trochu na črevá PyPy, RPython (python ktorý je schopný bežať približene rovnako ako C program) a benchmarky s V8.

Python

Python patrí medzi moje celkom obľúbené jazyky. Je známy tým, že vie všetko možné ale nič poriadne (presne ako ja). Má akési objekty, ale plnohodnotné OOP ako smalltalk to nie je. Má akési funkcie vyššieho rádu ale tail rekurziu nemá (druhý haskell to tiež nebude ). Referenčná implementácia je napísaná v C. Okrem referenčnej implementácie sa na internete povaľuje množstvo ďalších alternatívnych (jython, ironpython …).

Python patrí medzi interpretované jazyky. Zdrojové kódy majú príponu .py. Pri prvom spustení sa zvyčajne prekladajú do bytekódu (.pyc) vďaka čomu je štart programov v pythone pomerne rýchly (odpadáva fáza parsovania pri každom spustení).

PyPy

V nie tak moc dávnych dobách zopár nadšencov napísalo interpret pythonu v pythone. Vďaka réžii pythonu boli programy bežiace v ňom asi 1000x pomalšie než programy bežiace v C-Pythone. Zatiaľ čo v začiatkoch bola táto implementácia absolútne najpomalšia dnes je zo skutočne kompatibilných implementácií najrýchlejšia (v benchmarkoch má v priemere 6,45-násobné zrýchlenie oproti CPythonu).

V súčasnosti sa PyPy skladá z dvoch hlavných komponentov - Python interpret napísaný v RPythone (čo je obyčajný python s pár obmedzeniami) a RPython prekladač (preklad na screenshote, do terminálu vykresľuje mandelbrotovú množinu), ktorý prekladá python do nízkoúrovňového jazyka. Dokáže zároveň automaticky generovať VM s JIT-om.

Pomocou PyPy toolchainu je možné veľmi jednoducho napísať vlastný interpretovaný jazyk a vygenerovať k nemu JIT kompilátor.

RPython

Obmedzenia, ktoré musí spĺňať RPython program vyplývajú zo spôsobu prekladu. Jedným z dôvodov prečo je python pomerne pomalý je jeho dynamickosť. V pythone je možné zapísať napr. a = 1; a = "text"; a bude to plne validný python kód. V RPythone sú typy statické a automaticky dedukované z kontextu (haskellisti s radosťou vysvetlia). V prípade nesprávneho použitia typov jednoducho program nepôjde skompilovať. Vďaka týmto vlastnostiam je možné generovať nízkoúrovňový kód s minimálnou réžiou písaný vo vysokoúrovňovom jazyku.

Benchmarkový predkrm

Na začiatok nudný neefektívny príklad:

Python

def fib(n):
    if n <= 1: return n
    else: return fib(n-2) + fib(n-1)


def main(argv):
    n = int(argv[1])
    print "fib of", n, "is", fib(n)
    return 0

Javascript

function fib(n) {
    if (n <= 1) {
        return n;
    }
    else {
        return fib(n-2) + fib(n-1);
    }
}

console.log(fib(36));

C++

#include <iostream>

using namespace std;

ulong fib(ulong n) {
    if (n <= 1) {
        return n;
    }
    else {
        return fib(n-2) + fib(n-1);
    }
}

int main(int argc, char *argv[])
{
    ulong n = atoi(argv[1]);
    cout << "fib of " << n << " is " << fib(n);
    return 0;
}

Kód pre python a rpython je identický, líši sa len v inicializačnom kóde:

if __name__ == "__main__":
    import sys
    main(sys.argv)

v štandardnom pythone vs. rpython:

def target(driver,args):
    return main,None

Výsledky

	CPython	PyPy	V8	RPython	C++
Čas	16,817 s	2,785 s	0,830 s	0,326 s	0,172 s
Rozdiel oproti C++	98 x	16 x	4.8 x	1.9 x	1.0 x

Na jednoduchom príklade je vidieť, že peniaze naliaté do V8 za niečo stáli No dosť bolo hrania sa, poďme sa pozrieť na tieto benchmarky (je tam odkaz na zdrojáky). Zopár benchmarkov som upravil tak, aby fungovali aj pod rpythonom, zvyšok sa mi už nechcelo prepisovať, takže výsledky nie sú kompletné

Problém	CPython	PyPy	V8	RPython
1	383,9 us	95,4 us	352,5 us	5,8 us
2	36,6 us	9,8 us	20,9 us	0,805 us
3	1 227,2 us	236,9 us	167,3 us	143,9 us
4	546 650 us	149 140 us	598 210 us	76 941 us
5	32,90 us	25,75 us	5,15 us	2,13 us
6	2,2 us	0,8 us	0,1 us	0,005 us
7	205 070 us	23 680 us	58 020 us	3 175 us
8	2 882,10 us	563,65 us	1 570,90 us	134,11 us
9	116 120 us	1 680 us	1 130 us	734 us
10	1 314 900 us	269 800 us	571 540 us	43 838 us
13	270,8 us	135,4 us	1 678,6 us
15	9,7 us	4,9 us	3,6 us
16	392,6 us	196,3 us	86,9 us
18	432,1 us	216,1 us	275,3 us
19	503,5 us	251,8 us	63,8 us
20	229,7 us	114,9 us	1 804,7 us
24	39,8 us	19,9 us	13,1 us
28	1 948,2 us	974,1 us	19,7 us
40	84,3 us	42,2 us	12,9 us
45	4,1 us	2,1 us	0,1 us

Mierne upravené zdrojáky tak aby išli pod rpythonom sú dostupné v mojom klone.

Záver

Z výsledkov je vidieť, že JIT v PyPy funguje diametrálne odlišne od V8. Nedá sa jednoznačne povedať, že niektorý z nich je rýchlejší / pomalší. Ak by mimochodom niekoho zaujímalo ako funguje V8 a prečo je delete príšerné pomalý tak tento blog je pre vás.

Samozrejme v priamom porovnaní medzi jazykmi so statickými typmi a dynamickými typmi je rozdiel vo výkone jednoznačný. Statické typy je však možné s určitými obmedzeniami dostať aj do jazyka ako je python a to bez akéhokoľvek písania hintov. Na podobnom princípe funguje aj typový systém haskellu.

       

Obrázky

Komentáře

[Šangala]

Pokud je doba trvání testu nějaké jednotky až stovky µs, tak tomu moc nevěřím, bo to ovlivňuje i silnější prdnutí tchyně ve vaně a každé spuštění vygeneruje jiné výsledky (jak v testu, tak ve vaně)…

[mirec]

Je to čas prerátaný na iteráciu, všetky testy bežali min 100 iterácií u najdlhšie trvajúcich po 100000 po najkratšie trvajúce.

[Šangala]

Furt nic moc (nejkratší celkem jen 0.01 sec), ale už je to trochu lepší .

[mirec]

Pardon ušla mi jedna 0, najkratší bežal 1000000.

[Šangala]

Tak to máme .... celkem .... 0.1 sec / nejkratší test…

[frdrx]

Hlavně se lidi nenechte navábit k předčasným optimalizacím.

[Šangala]

Pomalu přestávám na chybu předčasné optimalizace věřit, bo spousta věcí už je tak pomalá a náročná, že by se styl vývoje měl přehodnotit a neměli by se některé jazyky používat na některé věcí (zrovna u Pythonu jsem si už říkal, kurňa zahoďte to a použijte už radši Javu, a teď jak to vidím, tak to přehodnocuji a říkám, kurňa přeložte to a pořádně ).

[frdrx]

No nevím, ale na úrovni na které mi předčasná optimalizace přijde jako jedno nejškodlivějších chyb, kterých se dokážu dopustit.

[frdrx]

Mělo být:

No nevím, ale na úrovni na níž jsem, mi předčasná optimalizace přijde jako jedna z nejškodlivějších chyb, kterých se dokážu dopustit.

[pavlix]

+1

[Šangala]

S ohledem na kód nebo uživatele? :)

[frdrx]

Na kód, samozřejmě, což přináší výhodu i uživateli.

[Šangala]

Jo-jo - jen než si toho uživatel všimne, chvilku trvá

[frdrx]

Většinou si toho ani nevšimne.

[Šangala]

No právě, ale zas určitě všimne toho, jak „dlouho to trvá“.

[frdrx]

Jenom do chvíle dojde na již nikoli předčasné optimalizace.

[Ilfirin]

Pěkné pěkné. Jinak pro zajímavost, existuje nový py_to_c kompilátor nuitka. Už jsem s ním něco zkompiloval, ale běželo to stejně jako v cpythonu, tak jsem to zase zahodil. A pokud už bych chtěl opravdu brutal výkon, tak se nejslibněji jeví numba. Pokus je pravda alespoň desetina, co se o ní píše, tak zrovna právě na to matematické blbnutí je ideální.

[mirec]

Na také bežné matematické blbnutie je python celkom rýchly. Numpy je pekne optimalizované, používa vektorové operácie a s pomerne rýchlym backendom je fakt super tam, kde sa python používa len ako lepidlo medzi knižnicami. Nedávno so sa tak dokonca hral s OpenCV a spracovaním videa, ale nakoniec som to aj tak prepísal do C++ (nie kvôli výkonu, ale ako príprava na jeden menší článok).

[Ilfirin]

Tak pokud vím, tak ani numpy není záchrana, pokud člověk dělá algoritmy s velkým množstvím kroků. Což byl ukázkový případ ten fibonacci a proto tak krutý čas cpythonu.

[mirec]

To áno, záleží od typu problému. Ja sa väčšinou hrajem s obrazom (fotky / video) a tam je to takmer vždy o vektorových operáciách zliepaných trochou interpretovaného kódu.

[Seraph]

To s tou type inferenci bude zase přehnané, Haskell ji má kompletní. Taková scala se taky chlubí type inferenci, přičemž ji dokáže použít pouze u deklarace proměnné. RPython na tom nebude líp, pouze odhaduji. Jo, a tail call rekurze je v Haskellu škůdce. Způsobuje thunk leak a musí proběhnout celá, což díky call by need rekurze v Haskellu nemusí.

[mirec]

Ten thunk leak je jedna z vecí ktoré sa mi dosť na haskelli nepáčia (prekvapilo ma to u funkcií ako fold), ale vlastne to celkom vyplýva z lenivosti vykonávania.

Čo sa týka typov ... rpython (aspoň čo som si všimol) všetko kompletne prekladal na natívne typy, žiadne obaľovanie. Typ majú nie len premenné, ale aj polia (homogénne), tuple (pevná veľkosť, nemôže sa na jednom mieste vo funkcii vrátiť ("a", 1) a (1, "a"), položky musia mať rovnaký typ) ...

[Seraph]

Thunk leak vznikne když je použita tail call rekurze a nevynutí se pomocí funkce seq či bang patterns striktní vyhodnocení operací. Pak thunk leak nehrozí. Nejlepší je tail call rekurzy nepoužívat vůbec (pokud se v tom člověk moc neorientuje). A když by nám hrozil stack oveflow, tak si prostě zvětšíme limit pro stack. Samozřejmě například u funkce length (a podobných) je výhodnější použít tail call rekurzi se striktním vytuněním. Částečné výsledky funkce length jsou k ničemu, takže správně napsaná tail call rekurze nenese nevýhody.

[Seraph]

Kouknul jsem se do zdrojáků Prelude na funkce z rodiny fold. Jsou tail call rekurzivní a spoléhají na GHC strictness analizer. Který ne vždy detekuje místo kde se hodí vynutit striktní vyhodnocení. Takže z toho důvodu jste měl thunk leak při použití fold{l|r}. Řešení je napsat si vlastní verzi funkce fold{l|r}, jedná se o 3 řádky, takže to ani nezdrží.

[lmbot]

foldr negeneruje thunky, takze smysl ma psat jen striktni verzi foldl, pokud je potreba vyhodnocovat z leva.

Zavrhovat (TC) rekurzi je nesmysl, jen je potreba si uvedomit jaka struktura rekurzivnim volanim vznika a podle toho se zaridit - aplikaci striktniho vyhodnoceni na parametr(y) a/nebo v kombinaci s guard rekurzi.

[lmbot]

Zvysovat limit zasobniku je cesta do pekel, pokud neni jednoznacne znama velikost mnoziny nad kterou se funkce vykonava. Staci pak vetsi objem vstupnich dat a k preteceni stejne dojde.

Pokud k tomu neni hodne dobry duvod, tak je lepsi na vhodnych mistech vynutit predcasne vyhodnoceni nebo upravit algoritmus a vystacit si s vychozim stackem. Velkou cast optimalizace zvladne i prekladac GHC, ale nelze se spolehat ze vyresi veskery nevhodne napsany kod.

[pavlix]

Má akési objekty, ale plnohodnotné OOP ako smalltalk to nie je.

Konkrétně?

[mirec]

Zapuzdrenie

[pavlix]

Zapouzdření je věcí návrhu aplikace a lze v Pythonu implementovat a dokonce k tomu existují zavedené zvyklosti. Jediné, co Python neumí, je vynucení dodržování toho zapouzdření, ale umělá omezení není něco, o čem bych se chtěl u jazyka typu Python bavit.

[mirec]

Nič to nemení na tom, že skutočné vynútené zapuzdrenie nemá. Mne to samozrejme nevadí, dokonca sa mi páči, že nie je striktne OOP / striktne funkcionálny ... jednoducho podľa mňa celkom dobre vybraný mix kadečoho.

[pavlix]

Nič to nemení na tom, že skutočné vynútené zapuzdrenie nemá.

To ovšem tvůrce pythoních programů nijak neomezuje, naopak jim to umožňuje dělat věci, které by jinak dělat nemohli a nejspíše ani neměli. Ale to je obecná vlastnost pythonu, že součástí jeho návrhnu není ochrana proti nekompetentním programátorům.

Nicméně tato vlastnost (volný přístup k privátním datům) lze podle mě implementovat i pro libovolný jiný jazyk a i se to tak pro účely debuggerů dělá. Stejnětak není problém přidat kompilátoru volbu, aby zapouzdření nevynucoval.

Řešení, které používá python, vede k tomu, že se stírají technické rozdíly mezi standardním během, testováním a debugováním. Samozřejmě každá sranda něco stojí a toto rozhodnutí má i své nevýhody, jen podle mě nespočívají v tom, že by byl programátor jazykem nějak omezován.

[JS1]

Pokud bys tak stal o to vynucene zapouzdreni (nechapu proc, ale dejme tomu), muzes si tusim celkem bez problemu napsat metatridu, ktera ho vynuti.

[Seraph]

Díky GC není predikovatelný okamžik zavolání destruktoru objektu. Tím pádem není možné použít RAII, což je unikátní vlastnost daná objektovému paradigmatu. On vlastně ani ten destruktor není třeba v OO jazyce s GC...

[pavlix]

To je pravda a vcelku očividně se toto pythoní API snaží dohnat podporou with. Na druhou stranu tvrzení, že je RAII vlastností objektového paradigmatu podle mě narazí na to, že různí lidé chápou objektové paradigma různě a to nejčastěji s ohledem na svůj oblíbený programovací jazyk.

[pavlix]

Mimochodem, používá smalltalk RAII, když už jsme u toho?

[x]

Na druhou stranu tvrzení, že je RAII vlastností objektového paradigmatu podle mě narazí na to, že různí lidé chápou objektové paradigma různě

Příkladně Alan Kay: OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things. Kde se v tom skrývá RAII fakt netuším.

[rADOn]

Mě python dovedl ke stejnému pohledu. Když chci poškádlit céčkaře nebo Javisty tak jim říkám že v těch jazycích nejsou objekty ale jen tečky ve jménech

[Seraph]

Tak jako funkcionalni paradigma ma unikátní vlastnost teoreticky implicitního paralelismu bez synchronizace. Tak OOP ma takřka zdarma management zdrojů.

[Michal]

A co cython? Osobně vždy vytvořím většinu kódu v cpython a pak těch pak řádku kódu co mají běžet rychle přepisu do cython a s trochou snahy dostanu výsledky na úrovni C++. I když rpython vypadá taky zajímavě

[mirec]

RPython nie je moc známy pretože je to interný projekt PyPy určený na implementáciu interpretovaného jazyka. Ja som ho zneužil na trochu iné veci hlavne zo zvedavosti a chcel som ľuďom tak trochu predstaviť práve tento projekt lebo moc sa o ňom nepíše a pritom je to najrýchlejšia implementácia pythonu kde nie je potrebné zadávať hinty.

Samozrejme cython je vďaka kompilácii kritických častí rýchlejší len ... treba dopísať hinty a odekorovať.

[Ilfirin]

A v tom je právě (opakuji se) kouzlo numba, která dovede být rychlejší jak cython bez toho, aniž by se kod jakkoli optimalizoval na C. Takže si osobně myslím, že Cythonu zvoní hrana (ve smyslu rychlostní optimalizace, jako nástroj na tvorbu rozšíření samozřejmě nemá chybu).

[pavlix]

bez toho, aniž by

Ale fuj.

[lmbot]

S Cythonem jsem si kdysi hral, ale vidim ze podobne jako Numba to je zakryvane zoufalstvi (jako predzahradky ). Dokaze optimalizovat jen podmnozinu pythonu, u cisel vetsich nez uint64 se stejne pouzije pythonni kod (ktery vola gmp) a pomale volani funkci a omezeni behu jen na jedno vlakno zustava. Ma smysl jen u omezenych pripadu pri vypoctech, ktere se pokud mozno provadi jen v ramci jedne fce/metody.

To uz je rozumnejsi misto CPythonu pouzit Jython nebo PyPy, ale co jsem mel moznost testovat, zatim o moc lepsi vysledky nedavaji, nekdy dokonce i horsi nez CPython. Dynamicke typovani ma proste svou dan, kterou nelze nezaplatit.

[henkye]

máš špatně název článku - je tam protimluv

[Bystroushaak]

Nigga please.