abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
14.12. 18:22 | Nová verze

Byla vydána nová verze 4.2.0 otevřeného emulátoru procesorů a virtualizačního nástroje QEMU (Wikipedie). Přispělo 198 vývojářů. Provedeno bylo více než 2 200 commitů. Přehled úprav a nových vlastností v seznamu změn.

Ladislav Hagara | Komentářů: 0
14.12. 15:33 | Pozvánky

Konference Bratislava OpenCamp 2020 proběhne v sobotu 4. dubna 2020 v Bratislavě na Fakultě informatiky a informačních technologií STU. Organizátoři vyhlásili CFP. Návrhy přednášek a workshopů lze zaslat do 31. ledna 2020.

Ladislav Hagara | Komentářů: 0
14.12. 15:11 | Nová verze

Bylo oznámeno vydání KDE Frameworks 5.65.0, tj. nové verze aktuálně 74 knihoven rozšířujících multiplatformní framework Qt a dnes využívaných nejenom KDE Plasmou a KDE Aplikacemi. Nově začleněnou knihovnou je KQuickCharts pro generování grafů.

Ladislav Hagara | Komentářů: 0
13.12. 15:44 | Nová verze

Byla vydána verze 2.4 svobodného nelineárního video editoru Flowblade (GitHub, Wikipedie). Přehled novinek v poznámkách k vydání. Zdůraznit lze přechod na Python 3.

Ladislav Hagara | Komentářů: 0
13.12. 07:00 | Nová verze

Vyšel toolkit Qt verze 5.14. Změny se týkají především Qt Quick, jeho odstínění od konkrétních nízkoúrovňových grafických API a zlepšení výkonu zvláště ve 3D. Začíná tím proces postupných příprav na Qt 6. Příští vydání (5.15) bude s dlouhodobou podporou. Aktuálně také vyšlo vývojové prostředí Qt Creator 4.11 – vedle oprav chyb a řady zjednodušení konfigurace přidává mj. experimentální podporu WebAssembly.

Fluttershy, yay! | Komentářů: 6
13.12. 06:00 | Nová verze

Byla vydána nová verze 1.41 editoru zdrojových kódů Visual Studio Code (Wikipedie). Přehled novinek i s náhledy a animovanými gify v poznámkách k vydání. Ve verzi 1.41 bylo vydáno také VSCodium, tj. komunitní sestavení Visual Studia Code bez telemetrie a licenčních podmínek Microsoftu.

Ladislav Hagara | Komentářů: 0
12.12. 23:55 | IT novinky

J2EE, nověji Java EE a nejnověji Jakarta EE, tj. Java pro vývoj a provoz podnikových aplikací a informačních systémů (Java Platform, Enterprise Edition), slaví 20 let. První verze J2EE 1.2 byla vydána 12. prosince 1999.

Ladislav Hagara | Komentářů: 0
12.12. 22:00 | Nová verze

V kancelářích společnosti NGINX, tj. společnosti stojící za stejnojmenným webovým serverem a reverzní proxy, v Moskvě proběhla policejní razie. Na NGINX si nárokuje práva společnost Rambler. Igor Sysoev, zakladatel společnosti NGINX, ve společnosti Rambler pracoval v letech 2000 až 2011. V březnu letošního roku byla společnost NGINX prodána společnosti F5 Networks za 670 milionů dolarů.

Ladislav Hagara | Komentářů: 17
12.12. 18:44 | Nová verze

Vyšel Vim 8.2. Jedná se převážně o opravnou verzi tohoto textového editoru, ale mezi několika novými funkcemi je také možnost používat vyskakovací okna v uživatelském rozhraní, což využijí zvláště vývojáři doplňků pro dialogová okna či okna s nápovědou, napovídáním atp. Ukázkou je hra killersheep.

Fluttershy, yay! | Komentářů: 1
12.12. 17:44 | Nová verze

Byla vydána nová verze 19.12.0 KDE Aplikací (KDE Applications). Přehled novinek i s náhledy v oficiálním oznámení, kompletním seznamu změn a na stránce s dalšími informacemi.

Ladislav Hagara | Komentářů: 1
Kolik jste vystřídali distribucí Linuxu? (uvažujte distribuce, které jste používali aspoň měsíc)
 (3%)
 (75%)
 (16%)
 (4%)
 (3%)
Celkem 110 hlasů
 Komentářů: 14, poslední včera 12:30
Rozcestník
Alternativně viz také můj osobní blog (RSS), kde toho hlavně v angličtině vychází mnohem víc.

Pokud se vám líbilo něco z mé produkce, můžete svou přízeň vyjádřit na Patreonu:

Ne že bych je nějak potřeboval, ale patří to k věcem, které autory obecně potěší a jasně ukazují, že jsou lidi, kteří ty hodiny času stráveného psaním umí ocenit.


Víte že můžete odebírat mé blogy pomocí RSS? (Co je to RSS?)


A kdo neumí použít RSS, tak je tu twitter: @Bystroushaak.

Od určité doby jsou všechny texty které zde publikuji verzované na Githubu.

Jestliže najdete chybu, nepište mi do diskuze a rovnou jí opravte. Github má online editor, není to skoro žádná práce a podstatně mi tím usnadníte život. Taky vás čeká věčná sláva v commit logu :)

Aktuální zápisy

www.AutoDoc.Cz

Jak se píše programovací jazyk 5: Bajtkód a literály

18.4. 01:34 | Přečteno: 2490× | Obecné IT | Výběrový blog | poslední úprava: 5.5. 23:01

Lexer rozděluje vstupní text na tokeny, které jsou parserem transformovány na abstraktní syntaktické stromy. Ty by měl vzít kompilátor a udělat z nich bytecode. Předtím je ovšem nutné si důkladně rozmyslet, jak má vlastně výsledný bajtkód vypadat, a tedy hlavně jak má vypadat virtuální stroj, kterým bude interpretován.

Jak už jsem zmiňoval, nejsem ani v nejmenším odborník na tvorbu programovacích jazyků. Když jsem se pustil do psaní specifikace VM, byly mi známé následující přístupy:

  1. Interpretace AST
  2. Interpretace imperativního bajtkódu
  3. Interpretace stack based bajtkódu

Pavel Křivánek ve své bakalářské práci Podpora beztřídního programování ve Squeak Smalltalku použil pro svůj Selfem inspirovaný jazyk Marvin stack based (na zásobníku založený) bajtkód ve stylu forthu.

Oproti tomu The Design and Implementation of the Self Compiler, an Optimizing Compiler for Object-Oriented Programming Languages (dále jen DISCOCOOPL) zmiňuje spíše imperativní bajtkód ve stylu assembleru.

V krátké výměně mailů, které jsem Pavlovi Křivánkovi poslal zmiňoval, abych zkusil zkombinovat první a druhý přístup.

Dále zde byly dva projekty Smalltalků napsaných v RPythonu:

  1. https://github.com/SOM-st/RPySOM
  2. https://github.com/hpi-swa/RSqueak (viz paper How to Build a High-Performance VM for Squeak/Smalltalk in Your Spare Time)

Oba dva sloužily jako lehká technická inpisrace při tvorbě interpretru.

Souslednost

Za zmínku pravděpodobně stojí, že tato a následující dvě kapitoly byly psány až po dokončení většiny práce na bajtkódech, interpreteru a kompilátoru. Práce na těchto komponentách však probíhala zároveň a jednalo se do jisté míry o iterativní proces. Člověk přidá jeden parametr bajtkódu, upraví kompilátor a interpreter a hned vidí, že to ovlivnilo celkový obraz tak, že nyní není třeba kousek tady a je třeba přidat kousek támhle, což vede ke změnám v kompilátoru tady a támhle, díky čemuž není třeba v interpretru tohle a támhleto může fungovat jinak..

Vytvářet něco, kde se zároveň tři a více komponent ovlivňuje, a bez samotné implementace se dopředu těžko představuje, jak konkrétně by to mělo celé vypadat, je zajímavá zkušenost. Nyní při psaní zpětně vidím, jak se to celé podepsalo na celkové podobě interpretru a hned mě napadá, že by šlo upravit spoustu komponent trochu jinak.

Vývoj, a zde a v následujících kapitolách popsaná podoba, byla ovšem diktována snahou o co nejrychlejší bootstrapping, s tím že na optimalizace a úpravy bude dost času později, pokud projekt vyhodnotím jako hodný dalšího pokračování.

Literály

Bajtkód se neskládá pouze z jednotlivých instrukcí, skládá se také z tabulky literálů. V té jsou uloženy všechny konstantní hodnoty známé v době kompilace.

Mezi ně patří:

Když pak interpreter dojde na část kde je nutné použít nějaký literál, nemusí ho v tu chvíli rekonstruovat z bajtkódu, místo toho se jednoduše podívá do tabulky literálů na patřičný index a vytvoří podle něj objekt.

Bytecodes

Pavel Křivánek navrhoval pro Marvina následující bajtkódy:

Osobně jsem se tímto setem hodně inspiroval, nakonec jsem však pro některé nenašel použití a naopak, některé které v Marvinovi nebyly mi tam přišly jako užitečné.

Nakonec jsem skončil s následujícím setem:

Přičemž některé z nich jsou parametrizované a můžou tak zabrat až tři bajty. Instrukce pracují se zásobníkem, na který vkládají, či z něj odebírají hodnoty. Zásobník je tvořen zvlášť pro každou metodu, proto například chybí instrukce pro odstranění hodnot ze zásobníku - vzhledem k tomu že instrukce hodnoty ze zásobníku odebírají implicitně, na konci se prostě celý zásobník zahodí, někdy s tím, že hodnota na vrcholu je vložená na vrchol zásobníku, ze kterého vznikl tento.

Musím říct, že mě docela překvapilo, jak málo instrukcí mi stačilo. Intuitivně jsem čekal, že jich bude minimálně dvacet. Že by mi jich stačilo šest, respektive pět bez ADD_SLOT, která je tam jen protože je to častá operace, to mě ani ve snu nenapadlo.

PUSH_LITERAL

Instrukce, kterou začíná prakticky každý set bajtkódů. Jako první vezmeme něco z tabulky literálů a vložíme to na stack.

Instrukce má dva parametry:

  1. literal_type
  2. literal_index

Druhý určuje index v tabulce, první pak typ literálů, kterým v současnosti můžou být:

  1. Nil
  2. Int
  3. String
  4. Object
  5. Block
  6. Assignment primitive

Detaily fungování budou vysvětleny v kapitole o interpretru.

Délka instrukce: 3 bajtkódy.

PUSH_SELF

Na vrchol zásobníku vlož self, tedy objekt v jehož kontextu aktuálně probíhá kód.

Délka instrukce: 1 bajtkód.

ADD_SLOT

Z vrcholu zásobníku seber jeden objekt jako hodnotu, druhý objekt jako jméno a třetí objekt jako příjemce. Do příjemce potom ulož hodnotu na dané jméno. Výsledný objekt vlož na vrchol zásobníku.

Tato instrukce by nemusela existovat, šlo by to celé implementovat pomocí mirrorů, ale vzhledem k tomu o jak často používanou záležitost se jedná, a jak strašně moc to zjednodušuje zbytek kódu, rozhodl jsem se jí takhle použít.

Délka instrukce: 1 bajtkód.

RETURN_TOP

Z vrcholu zásobníku vyber hodnotu a vrať jí.

Vrácení probíhá tak, že pokud jsou v tomto procesu předchozí zásobníky, vlož jí na vrchol předchozího zásobníku. Pokud ne, ulož jí jako návratovou hodnotu procesu.

Délka instrukce: 1 bajtkód.

RETURN_IMPLICIT

Docela dlouho jsem přemýšlel k čemu byla Pavlovi returnImplicit, a došlo mi to až když jsem implementoval bloky.

Z vrcholu zásobníku vyber hodnotu a vrať jí skrz tolik framů, dokud nebudeš ve scope ke kterému se return vztahuje.

Tohle je Selfová specialita, kde return z bloku nevrací jen z bloku, ale ze scope, kde je blok použit.

Tedy kód

(|| something ifTrue: [^ something].)

vrací nejen z bloku, ale i z method-objectu kolem něj.

Délka instrukce 1 bajtkód.

SEND

Nejkomplexnější instrukce, která objektu na zásobníku pošle zprávu.

Instrukce má dva parametry:

  1. message_type
  2. number_of_parameters

Akt poslání zprávy probíhá tak, že ze zásobníku je nejdříve vybráno number_of_parameters objektů do pole parametrů. V případě, že message_type je jeden z resend typů (UNARY_RESEND či KEYWORD_RESEND, je navíc ještě z vrcholu zásobníku sebráno jméno rodiče, kterému se má zpráva přeposlat. Dále je z vrcholu zásobníku sebráno jméno zprávy (selector) a objekt, kterému bude zpráva poslána.

Pokud jde o resend, je zpráva přeposlána parentovi - slot je vyhledán v patřičném rodičovi a je vrácen či vykonán v současném kontextu.

Pokud jde o kód, je vykonán tak, že je vytvořen nový zásobník, uložen nulový ukazatel na bajtkód (program counter) a objektu je přimapován do .scope_parent současný kontext.

Pokud jde o primitivní kód, je vykonán. Primitivní kód je voláním kompilovaných částí psaných v RPythonu.

Pokud jde o hodnotu, je vložena na vrchol zásobníku.

SEND je nejsložitější instrukcí, kterou možná časem rozdělím na víc menších.

Délka instrukce: 3 bajtkódy.

Budoucí rozvoj

Bajtkód, anglicky bytecode, je od slova byte. Samozřejmě nemusí mít přesně jeden bajt, ostatně moje instrukční sada by se mohla vejít do čtyř bitů. Do budoucna by ale mohlo interpreter zrychlit, kdybych provedl rozvoj všech často používaných instrukcí a převedl je z několika-bajtových parametrizovaných na jedno-bajtovové. Například bych mohl zavést bajtkód pro SELF_SEND, který by zkombinoval funkcionalitu PUSH_SELF a SEND. Nebo SENDKW1, který automaticky vybere jeden parametr ze zásobníku a bere ho jako keyword message. Některé instrukce by mohly obcházet PUSH_LITERAL bajtkód a rovnou si sahat na index do tabulky literálů. A tak podobně.

Taky limitace parametrů na jeden bajtkód momentálně znamená, že je možné použít pouze 256 literálů v jedné metodě, což ovšem v současné fázi vývoje bohatě stačí a nemá smysl to řešit. Časem chci přidat rozvoj na minimálně dvoubajtové definice, takže PUSH_LITERAL se prodlouží.

Zatím se však budu držet současné podoby, jelikož mám větší problémy k vyřešení a jak pravil klasik, předčasná optimalizace je kořenem všeho zla.

CodeContext

Stojí za zmínku se podívat, v čem a jak jsou vlastně bajtkódy i literály ukládány. Jedná se o třídu CodeContext, která obsahuje string s bajtkódy. Řešil jsem na #pypy v čem je nejlepší uchovávat bajtkódy, protože sám bych měl asi tendence použít bytearray, ale ten jednak po RPythonem funguje divně (měl jsem s tím nějaké problémy, už nevím přesně jaké), ale hlavně je pomalejší než zpracování stringů.

Dále obsahuje pole literals s tabulkou literálů, z nihž každý je zabalen v nějakém boxu (viz omezení RPythonu na jeden datový typ polí).

Pak jsou zde ještě dočasně uloženy různé speciální hodnoty, například se tu kešují dočasné mezi-objekty, které uchovávají parametry.

Zásobníky

Zasobníky jsem implementoval jako hierarchickou strukturu tří tříd;

MethodStack

Třída MethodStack tvoří prostý zásobník, na jehož vrchol je možné vložit instanci Objektu metodou .push(), sundat z vrcholu Objekt metodou .pop() a jako bonus implementuje .pop_or_nil(), která v případě že je zásobník prázdný vrátí singleton Objektu nil.

Třída dále uchovává nějaké obecné properties, jako .error_handler, .code_context, .bc_index a .self. Error handler je použit k řešení výjimek, code_context uchovává bajtkódy a bc_index slouží jako program counter.

Při běhu metody se sem ukládají jednotlivé literály a postupně si je z toho tahají instrukce tak jak jdou za sebou. V případě že je volána další metoda, tak na vrchol zásobníku se vloží výsledek poté co skončí. To řeší následující třída metodou .pop_frame_down().

Momentálně jsou k dispozici dvě implementace, jedna jako před-alokované pole, která je trochu rychlejší v kódu bez JITu a druhá jako linked-list, která je trochu rychlejší s JITem.

ProcessStack

Na tuto třídu navazuje ProcessStack, který je zásobníkem zásobníků a v podstatě reprezentuje jeden běžící proces. Pokaždé, když je vykonáván nějaký Object s kódem, je v ní vytvořen nový zásobník. Když kód doběhne, tak vezme poslední hodnotu z posledního zásobníku a vloží jí na vrchol zásobníku předtím. Ten co je na vrchu pak zahodí (proto nejsou potřeba samostatné POP bajtkódy).

Jak už napovídá název, taky uchovává další kontext „procesu“, jako výsledek běhu programu, informaci o tom jestli proces ještě stále běží, nebo ne.

Za zmínku stojí, že aktuální frame navrchu je vždy uchováván v proměnné .frame.

ProcessCycler

Poslední třídou je ProcessCycler, který přepíná aktuálně prováděný proces tím, že ho vždy uloží do proměnné .process. Vzhledem k tomu, že smyčka interpreteru vždy načte tuto hodnotu, provede jeden bajtkód a zavolá cyklování procesu, je tím docíleno jednoduché paralelizace.

Pokračování

V dalším díle se podíváme na implementace kompilátoru do výše uvedeného bajtkódu. Ačkoliv jsem intuitivně čekal, že půjde o něco složitého, nakonec se to ukázalo jako jedna z nejjednodušších věcí na celém projektu.

       

Hodnocení: 64 %

        špatnédobré        

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

Komentáře

Vložit další komentář

18.4. 03:01 Gilhad | skóre: 20 | blog: gilhadoviny
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Krásné :)

Drobné dloubnutí:

Bajtkód a literály: bytecode, bytekód, ...

SEND: PUSH_LITERAL: Délka instrukce: 3 batkódy.
Bystroushaak avatar 18.4. 12:28 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Díky za upozornění, to jsou artefakty dlouhého psaní článku (rozepsal jsem ho už někdy v září).
Bystroushaak avatar 18.4. 12:41 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
18.4. 07:39 petr_p | skóre: 59 | blog: pb
Rozbalit Rozbalit vše Imperativní bytekód
Stroji s „imperativním bytekódem“ se říká register-based machine. Přesně jako protiklad ke stack-based machine.
Bystroushaak avatar 18.4. 12:42 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Imperativní bytekód
Díky za doplnění, máš pravdu, teď se mi to vybavuje.
18.4. 09:02 kolcon | skóre: 15 | blog: kolcon
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
V cem jsou generovane ty obrazky?
18.4. 09:41 Bhezret
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Bystroushaak avatar 18.4. 12:52 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
V cem jsou generovane ty obrazky?
Doplnil jsem do repa přímo zdrojáky: code_context.plantuml & frames.planuml.
18.4. 12:35 Pavel Křivánek | skóre: 28 | blog: Kvičet nezávaznou konverzaci
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Pěkné, zkoušel jsi se zamyslet, jestli by nešlo reprezentovat zásobníky metod a procesů jako jakékoliv jiné objekty, pouze splňující nějaké požadavky dané VM? Otevřelo by to do budoucna řadu možností, ale chápu, že pro začátek je důležité mít co nejdříve něco, na čem lze stavět.
I'm sure it crashed in the most type-safe way possible.
Bystroushaak avatar 18.4. 12:50 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
To mě nenapadlo, částečně jsem to už řešil přes reflexi, tedy vytvoření něco jako speciálního mirroru kde je na pozadí primitivní kód co ti umožňuje s tím manipulovat. Pravděpodobně by to šlo tak jak píšeš ty, ale co jsem tak minulý týden řešil s cfbolzem z #pypy, tak tyhle věci typicky dost narušují JIT.
18.4. 18:27 Jakosek
Rozbalit Rozbalit vše Re: Jak se píše kozoprcací jazyk 5: Bajtkód a literály
Zajímavé. Ale je to asi jen akademické cvičení, že?
Bystroushaak avatar 18.4. 18:56 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše kozoprcací jazyk 5: Bajtkód a literály
Ani ne. Když si přečteš první díl, tak tam najdeš část odpovědí na téma motivace.
19.4. 12:13 Radovan
Rozbalit Rozbalit vše Re: Jak se píše kozoprcací jazyk 5: Bajtkód a literály
Tak ať máš motivaci ještě vyšší, nastupuje konkurence: https://www.root.cz/zpravicky/microsoft-predstavil-novy-programovaci-jazyk-bosque/ 8-O
Bystroushaak avatar 19.4. 12:19 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše kozoprcací jazyk 5: Bajtkód a literály
Bystroushaak avatar 19.4. 23:06 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše kozoprcací jazyk 5: Bajtkód a literály
Tady je k tomu trocha textu: Microsoft debuts Bosque – a new programming language with no loops, inspired by TypeScript

Osobně mi to přijde prostě jako funkcionální programovací jazyk.
19.4. 00:33 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
byly mi známé následující přístupy:
  1. Interpretace AST
  2. Interpretace imperativního bajtkódu
  3. Interpretace stack based bajtkódu
Vsechny tri varianty jsou ekvivalentni a navzajem prevoditelne. Hezky to jde videt na prevodu AST<-> stack-based bytecode, coz je trivialni operace. Hlavni rozdil je v tom, jak moc je ktera reprezentace vhodna pro urcity typ transformace/optimalizace nebo analyzy. AST je dobre na optimalizace vyrazu, bytecode pro registrovy virtualni stroj je zase fajn pro optimalizace postavene na toku data a CFG (obzvlast, pokud to mas formou SSA).

Stack-based bytecode je takovy kompromis mezi tim, mas tam explicitne vyjadrene rizeni vypoctu (to v tvem pripade asi neresis) a je z nej trivialni zase ziskat AST vyrazu pro dalsi transformace.

Registrove virtualni stroje maji jeste tu vyhodu, ze je snazsi jejich konverze do instrukci sady klasickych procesoru. Ale pokud delas preklad (pred provedenim) jeste pres nejaky jazyk nebo jiny bytecode, tato vyhoda pada.
Bajtkód, anglicky bytecode, je od slova byte. Samozřejmě nemusí mít přesně jeden bajt, ostatně moje instrukční sada by se mohla vejít do čtyř bitů. Do budoucna by ale mohlo interpreter zrychlit, kdybych provedl rozvoj všech často používaných instrukcí a převedl je z několika-bajtových parametrizovaných na jedno-bajtovové.

Tim moc rychlosti neziskas. Mnohem uzsi hrdlo, ktere to bude brzdit, jsou operace se zasobnikem. Pokud muzu radit, udelej si zasobniky co nejjednodussi. A pokud se mas v planu odchylit od minimalisticke instrukcni sady, pouvazuj nad tim, jak napr. skupinu casto pouzivanych instrukci pracujicich se zasobnikem prevest na jednu (byt slozitejsi) instrukci, ktera se explicitni manipulaci se zasobnikem vyhne.
Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
Bystroushaak avatar 19.4. 00:55 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
A pokud se mas v planu odchylit od minimalisticke instrukcni sady, pouvazuj nad tim, jak napr. skupinu casto pouzivanych instrukci pracujicich se zasobnikem prevest na jednu (byt slozitejsi) instrukci, ktera se explicitni manipulaci se zasobnikem vyhne.
Jo, nad tímhle uvažuji.
A pokud se mas v planu odchylit od minimalisticke instrukcni sady, pouvazuj nad tim, jak napr. skupinu casto pouzivanych instrukci pracujicich se zasobnikem prevest na jednu (byt slozitejsi) instrukci, ktera se explicitni manipulaci se zasobnikem vyhne.
Momentálně mám dvě různé implementace, jak jsem psal. Ta ve výsledku rychlejší by měla být prealokované statické pole, kde se jen updatuje index pointer, akorát že v benchmarku s JITem to momentálně vychází trochu pomaleji. Myslím že to ale chce přidat jen víc hintů ohledně toho co je statické / immutable a tak podobně. Rád bych přidal právě instrukce, které obcházejí práci se zásobníkem a konkrétní věci si berou z tabulky literálů. To by mohlo kód trochu zrychlit, ale vidím to že jen asi tak o 17% max.

Udělal jsem si takový jednoduchý benchmark na milion while cyklů, kde tělo je blok a podmínka je blok (tedy obojí je v podstatě lambda). Když jsem dopsal naivní implementaci, tak to trvalo asi dvacet vteřin. Momentálně jsem se po měsíci optimalizací dostal pod jednu vteřinu, s tím že podle cfbolze z #pypy by se mělo jít hravě dostat pod 100ms, pokud správně dodám JITové hinty.

Podle callgrindu momentálně nejvíc času žere parent lookup, a to i přesto že už jsem ho zoptimalizoval, přidal cacheování a prohledávání jen změněných částí grafu. Myslím že přepsáním na hierarchickou cache (momentálně cacheuje každý objekt sám za sebe a při lookupu prohledává jen odminule změněný graf (to pozná podle verzí objektů), ideální by bylo, kdyby se spoléhal i na cache v objektech které prohledává, což se teď neděje) se to ještě může zrychlit.

Minulý týden jsem zkoušel proof of concept dynamického rekompilátoru, který se snažil ty cache parent lookupů staticky inlinovat, ale nakonec jsem to celé vzal a zahodil, protože to bylo docela komplikované, fallback z nopovaného kódu, kde byly odstraněny PUSH_LITERAL instrukce byl docela komplikovaný a právě ta parent cache se ukázala jako vcelku dobrá sama o sobě.

V brzké době o tom vydám článek, všechny ty optimalizace jsem si poznamenával. Chci se teď zaměřit zase spíš na rozvoj funkcionality, když jsem rychlost dostal pod tu jednu vteřinu, což mi přijde pro další rozvoj jako proof of concept že to není úplně marné.
19.4. 08:01 sad
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Rekurzi můžeš nahradit nejen zásobníkem, ale i vlákny.
19.4. 11:02 Radovan
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Rekurzí můžeš nahradit nejen zásobník, ale i vlákna ;-)
Bystroushaak avatar 19.4. 12:12 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Rekurzi můžeš nahradit nejen zásobníkem, ale i vlákny.
Ok, ale jakou to má souvislost?
19.4. 13:38 sad
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Myslel jsem, že máš problém s rychlostí toho překladače.
Bystroushaak avatar 19.4. 14:00 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Nemám vůbec žádný problém s rychlostí překladače. Chybí mi doladit rychlost interpretru, kterou jsem za poslední měsíc zrychlil asi 20x, ale ani jedno vůbec nesouvisí s rekurzí. A vysloveně jsem tam psal, že mi už rychlost vyhovuje a že se chci zaměřit zase na funkcionalitu, místo rychlostních optimalizací, takže tu odpověď nechápu už vůbec.
19.4. 14:05 sad
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Aha, tak to je dobře. Zřejmě jsem si ten tvůj příspěvek špatně přečetl.
Josef Kufner avatar 19.4. 14:37 Josef Kufner | skóre: 69
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Rychlost interpretování vyřešil docela hezky Haskell. Prostě svůj zdroják přeloží do zdrojáku v C a na to pustí vyladěné překladače plné šílených optimalizací.
Hello world ! Segmentation fault (core dumped)
Bystroushaak avatar 19.4. 14:40 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
To dělá rpython taky, ale to ti samo o sobě moc nepomůže. JIT momentálně tak jak ho mám přidává docela dobrý boost (cca 130% rychlosti), a pokud se dobře vyladí, tak klidně i víc. Hezky je to vidět třeba na jednom benchmarku co jsem si dělal v pythonu, který pod cpythonem běžel 3/4 hodiny a pod pypy díky JITu 32 sekund.
Josef Kufner avatar 19.4. 23:47 Josef Kufner | skóre: 69
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Spíš jsem to myslel na případ, kdy si člověk tvoří něco svého. To pak obvykle nemá prostředky na vývoj pořádného interpretu a je lepší využít nějaký existující nástroj.
Hello world ! Segmentation fault (core dumped)
Bystroushaak avatar 20.4. 00:14 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Já myslím že dneska to úplně nedává smysl, pokud tomu nechceš věnovat roky a roky vývoje. Konkrétně co tak chodím na ty Graal talky, tak to je dneska / bude v brzké době jasná volba.
Josef Kufner avatar 20.4. 17:00 Josef Kufner | skóre: 69
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Pokud máš úlohy, kde dává smysl sestavit vlastní DSL a záleží na výkonu, tak asi nejlepším přístupem je právě překlad do jiného jazyka namísto psaní interpretu. To může být záležitost na pár dní, nikoliv pár roků, a přitom to bude velmi dobře funkční i efektivní.

Někdy ani není potřeba tvořit celý jazyk znovu, ale stačí ho trochu rozšířit. Vem si například React a jeho JSX. Prostě vzali syntaxi Javascriptu a přidali do toho HTML. Výsledkem je pohodlnější zápis HTML DOM elementů a přitom to je jen o překladu podivné syntaxe do volání pár funkcí.
Hello world ! Segmentation fault (core dumped)
Bystroushaak avatar 20.4. 23:21 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Pokud máš úlohy, kde dává smysl sestavit vlastní DSL a záleží na výkonu, tak asi nejlepším přístupem je právě překlad do jiného jazyka namísto psaní interpretu. To může být záležitost na pár dní, nikoliv pár roků, a přitom to bude velmi dobře funkční i efektivní.
Transkompilátory afaik dávají smysl jen za předpokladu, že děláš funkčně něco hodně podobného tomu podkladovému jazyku. Tedy jak píšeš, DSL. Nebo například jsem tu kdysi psal blog o brythonu, který transkompiluje za běhu python do javascriptu, což jde a má to smysluplnný výkon, protože oba jazyky jsou si alespoň přibližně podobné co do dynamičnosti a brythonu v podstatě stačí používat restriktivní javascript. Obráceně už bys to ale dělal hůř, například transkompilovat javascript do pythonu by asi chtělo pěkný kus hackování a výkon by šel do kytek. To samé se Selfem - jak jsem psal v tom druhém seriálu, kdysi vznikl Smalltalk implementovaný nad Selfem, který běžel rychleji než tehdejší smalltalky. Naopak to lidi taky zkoušeli, ale výkon byl tragický, protože právě řešení parentů musí být z principu dynamické a nemáš ho moc na co namapovat ve většině jazyků.

Co je ale killer feature toho graalu, co nikdo jiný afaik nemá, je interop. Tedy tvůj jazyk bude umět pracovat s datovými strukturami a funkcionalitou všech ostatních věcí napsaných v graalu. Tedy pythonem, ruby, C, javascriptem a kopou dalších projektů. A celé to bude mít velmi dobrý výkon. Například jsem viděl benchmark kde javascriptový kód volal generátor v ruby a celé to běželo asi 20x rychleji, než samotné ruby a jen o trochu pomaleji než optimalizované C. A teď se člověk zamyslí, že generátor v ruby je něco úplně jiného v javascriptu a oba dva používají jiné formaty intů, které to vracelo a je jasně vidět ten potenciál. Jaroslav Tulach viděl ty moje články o tinySelfu a vybral si jako semestrální projekt Self, kde killer feature bude že to narozdíl od původního Selfu bude mít k dispozici nejen Selfí stdlib, ale všechno pro python, ruby, javascript, C, ..

Přitom tam sice musíš psát interpreter, ale nemusíš jít za implementaci AST. Tedy ti stačí lexer, parser, AST strom s .eval() metodami a jsi hotový.
Bystroushaak avatar 19.4. 18:10 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
V brzké době o tom vydám článek, všechny ty optimalizace jsem si poznamenával.
Tak jo, tady: tinySelf performance gains 2019/4.
20.4. 00:42 kralyk z abclinuxu | skóre: 29 | blog:
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Ten LightWeightDict mi připomíná SmallVector / SmallString, jestli to dobře chápu, je to stejná strategie...
Bystroushaak avatar 20.4. 01:17 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Já úplně nevím co referencuješ, abych na to mohl odpovědět.
22.4. 13:23 kralyk z abclinuxu | skóre: 29 | blog:
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Sorry, už jsem jak davkol :-D Já ten koncept znám z LLVM - viz SmallVector a příp. SmallString nebo to samé v Rustu [1, 2]. Píšeš tam např., že použití linked listů pro stacky oproti běžnému pythonímu listu bylo o dost rychlejší. Možná by se stejná optimalizace jako ten LightWeightDict / SmallVector / etc. dala použít i pro stack, tj. že bys měl prealokované pole pro prvních N položek a jakékoli další by šly do toho spojáku. Otázka je, jestli by to reálně bylo rychlejší (special casing → více branchování).

Možná vůbec nejlepší, co se rychlosti týče, udělat si statistiky nejpoužívanějších sekvencí instrukcí a ty pak optzimalizovat... Ale to se blbě dělá bez reálných programů v tinySelfu.

Btw. ten `TwoPointerArray` mi připadá, že je prostě Ring buffer, jestli to dobře čtu...
Bystroushaak avatar 23.4. 09:48 Bystroushaak | skóre: 36 | blog: Bystroushaakův blog | Praha
Rozbalit Rozbalit vše Re: Jak se píše programovací jazyk 5: Bajtkód a literály
Možná by se stejná optimalizace jako ten LightWeightDict / SmallVector / etc. dala použít i pro stack, tj. že bys měl prealokované pole pro prvních N položek a jakékoli další by šly do toho spojáku. Otázka je, jestli by to reálně bylo rychlejší (special casing → více branchování).
Můžu na to mrknout.
Možná vůbec nejlepší, co se rychlosti týče, udělat si statistiky nejpoužívanějších sekvencí instrukcí a ty pak optzimalizovat... Ale to se blbě dělá bez reálných programů v tinySelfu.
Mno, ideálně chceš aby za tebe tohle řešil nějaký backend, ala ten JIT.
Btw. ten `TwoPointerArray` mi připadá, že je prostě Ring buffer, jestli to dobře čtu...
Není to úplně ring buffer, je to jednoduše prealokované pole, kde se při .pop() a .append() posouvají dva indexy zleva a zprava. Princip je podobný, ale není to cirkulární.

Založit nové vláknoNahoru

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.