Seznamte se: pypy

24.3.2007 19:10 | Přečteno: 1857× | Dev/Tech/Gnu |

V programování a programovacích jazycích se vrtám roky rokoucí a proto se málokdy stane, že mě něco překvapí. Ale přesně to se před pár týdny stalo. Narazil jsem totiž na pypy a připomněl si, co znamená hackerství ve svém nejlepším významu.

Co je vlastně pypy? Pypy je implementace jazyka Python v Pythonu samotném. Na první pohled je to pěkná divočina, vlastně až nesmysl. Standardní interpreter Pythonu je napsán v jazyce C (říkejme mu CPython), pypy je do jisté míry prostá reimplementace CPythonu, akorát napsaná v Pythonu.

Pypy ve své základní podobě samozřejmě není schopen přímo běžet v operačním systému, pro svůj běh potřebuje interpreter Pythonu a tedy CPython. Program spuštěný nad pypy je tedy interpretován dvojitě. Je to pomalé? Nu, je to véélmi pomalé - zhruba dvoutisíckrát pomalejší oproti "nativní" implementaci. Nesmysl? Keep on reading!

V této základní podobě je pypy pouze skvělý nástroj na experimentování s jazykem jako takovým. Je jednodušší přidat nějakou experimentální konstrukci do pypy než do CPythonu - prostě proto, že je použit mnohem vyšší jazyk.

Nativní pypy

Co mi ale vyrazilo dech, je možnost přeložit celý pypy z Pythonu do C. Obecně samozřejmě není možné jen tak přeložit pythoňácký zdroják do céčka. Pypy je ale implementován ve speciální podmnožině Pythonu, která je osekána o některé divočejší konstrukce (jako třeba eval()). Tuto podmnožinu nazývají RPython (restricted). Pypy přeložené do céčka je už jenom 2x až 4x pomalejší než originální CPython.

Aby toho nebylo dost, tak ono překládací udělátko je dostatečně obecné (pythoňácký bajtkód převede do grafové reprezentace a tam dělá zvěrstva jako typovou inferenci) a schopné generovat v podstatě jakýkoliv kód. Kromě C funguje překlad do dotnetího CIL spustitelného na Monu, kód pro experimentální LLVM (low level virtual machine), počítá se s Java bajtkódem.

Pypy je taky framework pro tvorbu interpreterů - v RPythonu lze napsat "specifikaci" jiného jazyka než Pythonu a z této "specifikace" vygenerovat interpreter pro libovolnou platformu. Tuším jsem na stránkách viděl něco o Prologu a uvažuje se o Scheme.

Ještě se vám to nedá dost? Stay connected!

Flexibilita

Když se při implementaci CPythonu van Rossum rozhodl pro nějaký přístup a tento byl zadrátován do céčka, často už s tím nejde hnout. Například GC - CPython používá ke správě paměti počítání referencí. Předělat tento GC na mark and sweep je zhola nemožné, protože inkrementováním a dekrementováním počítadla referencí je céčkový zdroják prošpikován na mnoha místech. Pypy umí céčkový zdroják vygenerovat, takže aspekt správy paměti stačí změnit na jednom místě. Přepínačem je možno volit mezi Boehm GC a počítáním referencí.

Pypy má ještě několik zajímavých možností. Asi nejdůležitější je stackless Python. Originální stackless Python je sada invazivních patchů do CPythonu, která umožňuje oprostit se od limitů systémového zásobníku. Originální patche jsou dost těžko udržovatelné, stackless aspekt pypy je jeden přepínač ovlivňující generování céčkového kódu.

Další chuťovka je modifikace umožňující lazy vyhodnocování.

Jak na věc

Aktuální verze 0.99 běží jenom na Pythonu 2.4 (patche pro 2.5 budou brzy v svn), přičemž je potřeba také dávat pozor na verze některých knihoven jako třeba ctypes. V Dapperovi mi interpretovaný pypy běžel, ale překlad padal na podivných výjimkách. Nejjistější je tedy vybildit si to podle následujícího rychlonávodu, ke kterému jsem došel po četných experimentech:

• stáhnout python 2.4 (v Dapperovy jsou zastaralé ctypes, ve 2.5 to stejně nejde)
• vybildit python 2.4
• stáhnout ctypes (0.9.9 nebo novější), Numeric a nahodit do Pythona
• nahodit SDL (libsdl-ttf1.2-dev libsdl-mixer1.2-dev libsdl-image1.2-dev) (nepovinně, hodí se pro vizualizaci takového call grafu)
• stáhnout pygame a nahodit do pythona (opět jen pro vizualizaci)
• nahodit libgc-dev (Boehm GC)

No a teď stačí zadat magický příkaz a vygenerovat vlastní interpreter přímo na tělo:

cd pypy/translator/goal
/usr/local/bin/python translate.py --text --batch targetpypystandalone.py

Pozor, proces překladu trvá i na Core2 dvacet minut a sežere to tak půl giga paměti. Nicméně to vypisuje hezké hlášky, tak se můžete dívat, co to asi dělá. Osobně nechápu, jak může na stroji s vyšším výkonem než celé DoD za studené války něco "užitečného" trvat dvacet minut. Předpokládám, že grafy popisující kód, které to konstruuje, jsou dost velké a je tam nějaká sviňa s O(N^2). Ale pokud to vydržíte, zjeví se vám nová binárka pypy-c, kterou můžete bez ostychu spustit.

Parodii na IronPython vygenerujete asi takto:

translate.py --text --batch --backend=cli targetpypystandalone.py

Srovnání výkonu

Uvádím tabulku srovnávající výkon v pystone (Intel Core Duo 1.66 GHz).

from test import pystone
pystone.main()

Interpreter	pystone
CPython 2.4	39062
pypy-c	11236
pypy-cli	957
pypy	18

Schválně, kolik dáte v pystone vy?-)

Závěr

No je to hezká hračka a třeba z toho nakonec vyleze lepší interpreter, než je ten Rossumův. Projekt je aktivní, mailinglist živý, sponzoruje mj. EU.

       

Komentáře

[unknown_]

[Vallhala]~>python a.py
Pystone(1.1) time for 50000 passes = 1.25
This machine benchmarks at 40000 pystones/second
[Vallhala]~>

Pentium M 1.7 GHz, FreeBSD 7.0-CURRENT

[paskma]

Pystone(1.1) time for 50000 passes = 0.87 This machine benchmarks at 57471.3 pystones/second

Core2 @1.86 GHz. Nejrychlejší komp, ke kterému mám přístup.

[xxx]

nema tam ke konci byt spis omega(n^2). (Teda ne z by to O(n^2) vylucovalo, ze je to i ta omega :)

[Marek Bernát]

Podľa mňa chcel autor povedať len toľko, že je to asymptoticky horšie ako lineárne. Tá big-O notation sa niekedy zneužíva na strašné veci

[paskma]

Jop, něco takového jsem chtěl říct . S tím, že "horší než lineární" není dost výstižné, protože O(n log(n)) je na "obyčejná" data vždy v pohodě. O(n^2) už umí udělat pěknou paseku. Kdo nevěří, ať si nechá seřadit bubble-sortem trapný milion integerů.

[Marek Bernát]

Hm, ale to už nemá s asymtotickosťou v nekonečne takmer nič spoločné. Ty sa snažíš namerať reálnu záťaž pre konečné n. A tam už zavážia aj konštanty apod. Konkrétne, ak máš časovú zložitosť T_n = 10^6 n log(n), tak platí T_n ∈ O(n log n), ale pre n = 10^6 to bude stále pomalšie ako nejaké S_n = n^2. Na druhej strane sa dá namietať, že v praxi tie riadiace konštanty nebývajú také zbesilé

Skrátka, aby som to zhrnul, tak o tom, akú zložitosť majú algoritmy v pypy, sa nedá povedať prakticky nič. Ale aspoň som si zopakoval asymptoty

[paskma]

Ale jasné. Ty jsi určitě tak ve třeťáku na výšce (MFF?), jsi aktuálně nasáklý tou teorií a vidíš, že moje povídání z pohledu téhle teorie není tak úplně košer.

Ale já jsem to psal z čistě inženýrského pohledu. Já si prostě myslím že je tam něco nelineárního, protože si nedovedu představit, že by tam byl milionkrát lineární průchod (jak jsi ostatně poznamenal).

Dneska pokračuju ve čtení dokumentace. Mají tam nějaký graf (uzly bloky kódu, hrany skoky) a ty uzly se snaží poskládat aby byl co nejmenší počet skoků. Teorii grafů jsem sice už skoro zapomněl, ale nějakým tím polynomem mi to smrdí.

[Marek Bernát]

Odhalil si ma, som na MFF Ale je to komplikovanejšie, lebo informatika ma prestala baviť, tak som prešiel na fyziku. Takže teóriou nasiaknutý nie som; O-notáciu som používal naposledy keď som riešil informatické súťaže na strednej. A to bolo už dáávno

To je dobre, že si sa dal na dokumentáciu. Ak sa dá niekde zistiť, akú to má zložitosť, tak asi tam. A idem sa na to pozrieť aj ja, znie to zaujímavo.

[Marek Bernát]

Aha, sorry, neviem prečo som si tú tvoju omega asocioval s Theta

Btw, O(n^2) a omega(n^2) sa vylučujú. Nevylučovalo by sa to s Omega(n^2). Potom by sme dostali tú Theta ako prienik. Dúfam, že zasa neblúznim