SquirrelFish: regulární výrazy, vlastnosti objektů a budoucnost

V dnešní části seriálu dokončíme povídání o interpretu SquirrelFish. Podíváme se na to, jakým způsobem urychluje práci s regulárními výrazy a jak optimalizuje přístup k vlastnostem objektů. Článek zakončíme popisem některých optimalizací, které jeho vývojáři chtějí implementovat v blízké budoucnosti.

Seriál: Do hlubin implementací JavaScriptu (14 dílů)

  1. Do hlubin implementací JavaScriptu: 1. díl – úvod 30.10.2008
  2. Do hlubin implementací JavaScriptu: 2. díl – dynamičnost a výkon 6.11.2008
  3. Do hlubin implementací JavaScriptu: 3. díl – výkonnostně nepříjemné konstrukce 13.11.2008
  4. Do hlubin implementací JavaScriptu: 4. díl – implementace v prohlížečích 20.11.2008
  5. Do hlubin implementací JavaScriptu: 5. díl – implementace mimo prohlížeče 27.11.2008
  6. SquirrelFish: reprezentace hodnot JavaScriptu a virtuální stroj 4.12.2008
  7. SquirrelFish: optimalizace vykonávání instrukcí a nativní kód 11.12.2008
  8. SquirrelFish: regulární výrazy, vlastnosti objektů a budoucnost 18.12.2008
  9. SpiderMonkey: zpracování JavaScriptu ve Firefoxu 8.1.2009
  10. SpiderMonkey: rychlá kompilace JavaScriptu do nativního kódu 15.1.2009
  11. V8: JavaScript uvnitř Google Chrome 22.1.2009
  12. Rhino: na rozhraní JavaScriptu a Javy 29.1.2009
  13. Velký test rychlosti JavaScriptu v prohlížečích 5.2.2009
  14. Javascriptové novinky: souboj o nejrychlejší engine pokračuje 19.3.2009

Regulární výrazy

minulém dílu našeho seriálu jsme si povídali o kompilaci JavaScriptu do nativního kódu. Vývojáři se rozhodli kód, který ji zajišťuje, použít ještě na jednom místě – ke kompilaci regulárních výrazů.

Implementace regulárních výrazů

Ke zpracování regulárních výrazů SquirrelFish standardně používá modifikovanou knihovnu PCRE. Ta sama o sobě není nijak pomalá a regulární výrazy umí předkompilovat do mezikódu, který urychluje opakované testování s mnoha řetězci. Odpadá tak opakované parsování a situace je v podstatě analogická kompilaci do bajtkódu v běžných programovacích jazycích.

Na platformě x86 se ale nyní místo PCRE využívá nový nástroj WREC (WebKit Regular Expression Compiler). Ten z regulárního výrazu vygeneruje kus nativního kódu, který pracuje podstatně rychleji než zpracování pomocí PCRE – vývojáři uvádí až pětinásobné zrychlení. Daní za zrychlení je zesložitění kódu, který teď obsahuje dva kompletní enginy na zpracování regulárních výrazů (WREC totiž obsahuje i samostatný parser a na PCRE je prakticky nezávislý).

Podrobné informace o kompilaci regulárních výrazů najdete ve zdrojovém kódu WebKitu v adresáři JavaScriptCore/wrec, případně vyhledáním všech výskytů řetězce #if ENABLE(WREC).

Proč optimalizovat regulární výrazy

Dobrá otázka je, proč vlastně regulární výrazy až takto optimalizovat? Zdánlivě se totiž na webu používají maximálně tak při validaci formulářů.

Pravdou je, že ač regulární výrazy nejsou příliš důležité v běžných skriptech, mají své využití v různých knihovnách a frameworcích. Neobejdou se bez nich například selektorové enginy většiny běžných frameworků, parsování JSON, grafická knihovna Processing.js (kde překládají speciální jazyk do JavaScriptu) nebo framework Capuccino (kde podobně pomáhají při překladu jazyka Objective-J). Zde všude je důležité, aby byly regulární výrazy co možná nejrychlejší. Regulární výrazy též hojně testuje javascriptový benchmark SunSpider, jehož zrychlení jistě bylo významnou motivací pro vývojáře.

Přístup k vlastnostem objektů

Ve 2. dílu jsme si povídali o tom, jaké výkonnostní problémy způsobuje dynamičnost JavaScriptu – především to, že předem nemůžeme s jistotou určit typy objektů (dynamické typování) a že za běhu programu lze předefinovat prakticky libovolné vlastnosti objektů.

Implementace JavaScriptu (SquirrelFish nevyjímaje) u každého objektu obvykle udržují hash tabulku, která mapuje názvy vlastností na jejich hodnoty. Při přístupu k vlastnosti (tj. při zjišťování hodnoty či volání metody) se pak tato hash tabulka prohledává. Pokud v ní vlastnost není nalezena, prohledávají se rekurzivně tabulky prototypů. Hledání končí ve chvíli, kdy se hodnota vlastnosti najde, nebo prohledávaný objekt už nemá prototyp.

Příklad přístupu k vlastnosti objektu

Příklad přístupu k vlastnosti objektu.

Urychlení přístupu

Je zřejmé, že přístup k vlastnostem je kvůli (často mnohonásobnému) prohledávání hash tabulek pomalý. Jedním ze způsobů, jak ho lze urychlit, je použít inline keš. Její implementace ve SquirrelFish je založena na dvou pozorováních:

  1. Objekty ve skriptu se obvykle rozpadají do několika tříd, přičemž objekty ze stejné třídy mají stejnou množinu vlastností. Obvykle (ale ne nutně) je to dáno tím, že jsou vytvořeny stejným konstruktorem. Třídy v našem pojetí jsou analogií tříd ve statických jazycích, ale nejsou dány svými deklaracemi, nýbrž strukturou objektů (dva nezávisle vytvořené objekty s vlastnostmi x a y budou mít tedy stejnou třídu).
  2. U přístupu k vlastnosti na konkrétním místě v programu (tedy např. „volání metody obj.f() na řádku 137“) je typické, že objekt, k jehož vlastnosti přistupujeme, bude mít při opakovaných průchodech kódem stále stejnou třídu.

SquirrelFish se za běhu programu snaží evidovat třídy vznikajících objektů a přiřazuje jim jednoznačné identifikátory. Udržuje si také informace o vnitřní struktuře objektů z každé třídy – ví, na jakém místě v paměti jsou uloženy jejich jednotlivé vlastnosti. Interpret má tedy k dispozici v podstatě stejné informace, jako kompilátor statického jazyka, jen mu je nesděluje uživatel typovými deklaracemi, ale musí si je zjistit sám za běhu programu.

Jak tedy SquirrelFish urychluje jednotlivé přístupy k vlastnostem objektů? U každého se při prvním spuštění poznamená, jaké třídy je objekt, k jehož vlastnosti přistupujeme. Obecný kód, který používá prohledávání hash tabulek, je pak přímo v bajtkódu nebo nativním kódu (odtud slovo inline v názvu) nahrazen kódem, který využije informací o struktuře třídy a hodnotu vlastnosti hledá přímo na známé pozici v jejích datech. Místo prohledávání se tedy vykoná jen instrukce typu „načti hodnotu z adresy o 8 bajtů větší, než je adresa objektu“, což je podstatně rychlejší. Rozdíl na celkové době běhu programu může být i desítky procent.

Čtenáře možná napadne, co se stane, když takto upravený kód narazí na objekt jiné třídy, než na kterou byl specializován. Na to je samozřejmě třeba myslet a na začátek přidat test ověřující, zda je objekt té třídy, kterou kód očekává. Pokud ne, vyhledávání se provede klasickým postupem. Tento případ se nazývá cache miss.

Další možnosti

Právě popsaná varianta se nazývá monomorfní inline keš. Má tu nevýhodu, že je specializována jen na jednu třídu objektů. Pokud bychom kód specializovali na více tříd, získáme polymorfní inline keš. Zde je třeba dát pozor na to, že tato varianta bude mít o něco složitější logiku testování, což ji zpomalí v případech, kdy bude jedna třída výrazně převažovat.

Polymorfní keš je možné za běhu programu dále optimalizovat, například občas kód překompilovat tak, aby se v testech nejdříve zkoušely nejpravděpodobnější třídy apod. Podobná rozhodnutí a optimalizace jsou závislé na profilování a sbírání statistik o běhu programu za jeho běhu. Je to jeden z příkladu adaptivní kompilace, což je velmi zajímavá oblast světa interpretů a kompilátorů, kterou interprety JavaScriptu teprve začínají zkoumat.

Okénko do budoucnosti

Vývojáři SquirrelFish věří, že – byť je SquirrelFish již dnes poměrně rychlý – jde jeho výkon ještě podstatně vylepšit. Základem je přitom reprezentace programů bajtkódem, která otvírá cestu k mnohým optimalizacím, z nichž některé si představíme. Nutno říct, že tyto optimalizace jsou ve světě kompilátorů většinou velmi dobře známé, a tedy nijak převratné.

Constant folding

Jedna ze základních optimalizací je constant folding, tedy vypočítávání hodnot konstantních výrazů již při kompilaci. Místo výrazu 5 + 2 * 3 se například do bajtkódu vloží přímo hodnota 11. V dynamických jazycích je tato optimalizace malinko zesložitěna dynamickým typováním a v JavaScriptu navíc není možné optimalizovat vestavěné funkce (místo výrazu Math.sin(Math.PI) nemůže kompilátor vložit 0, protože se v předchozím kódu mohla změnit definice sinPI).

Osobně mě překvapilo, že tuto optimalizaci SquirrelFish neprovádí už dávno, protože jde bez problémů provést už při reprezentaci programu pomocí AST – nepotřebuje bajtkód.

Type inference

Type inference znamená, že se kompilátor snaží dělat úsudky o typech proměnných a na jejich základě může zjednodušit některé operace. Pro vysvětlení použijeme náš již poněkud ohraný příklad s operátorem „+“, který může znamenat buď numerický součet, nebo spojení textových řetězců. Pokud kompilátor díky struktuře programu ještě před spuštěním programu dokáže, že oba operandy jsou například čísla, může vygenerovat kód, který nebude typy operandů kontrolovat, ale rovnou použije variantu s numerickým součtem a bude tedy rychlejší.

Zmiňované dokazování není v JavaScriptu kvůli jeho dynamickému charakteru vůbec jednoduché. Některé problémy, které v podobným úsudkům často brání, jsme si popisovali ve 3. dílu.

Escape analysis

Při běhu jedné javascriptové funkce často vzniknou hodnoty, které jsou lokální v tom smyslu, že odkaz na ně nikdy neopustí funkci. Okamžikem návratu z funkce zanikají. Takové hodnoty je možné detekovat a místo alokace na heapu a následné garbage collection je možné je umístit na zásobník a zrušit je při opuštění funkce, což je podstatně rychlejší. Technika escape analysis se zabývá právě detekcí takovýchto objektů.

Další optimalizace

Další optimalizace, na které se chtějí vývojáři SquirrelFish zaměřit, jsou například copy propagation, specializace kódu podle kontextu nebo peephole optimization. Virtuální stroj SquirrelFish pak chtějí rozšířit mj. o constant pool a instrukce s implicitními registrovými operandy. Také by rádi rozběhali direct threading na Windows. Další optimalizace jsou nastíněny na vývojářském wiki (odkazovaná stránka je ale v době psaní článku 6 měsíců stará). Principy uvedených optimalizací si zde popisovat nebudeme, případní zájemci si jistě podrobnosti dohledají.

Zda budou všechny zde uvedené optimalizace opravdu implementovány, není jisté. Při vývoji se totiž například může ukázat, že místo očekávaného zrychlení nová vlastnost kompilátor zpomalí, nebo že zrychlení není dost velké na to, aby ospravedlnilo zesložitění kódu. Nemluvě o tom, že vývoj a testování některých optimalizací trvá dlouho a nemusí se tak vyplatit ekonomicky. Každopádně prostor pro další zrychlování interpretu není malý a osobně se domnívám, že zrychlení o několik desítek procent, ne-li větší, je jen otázkou času a vynaloženého úsilí.

Co nás čeká příště

Vzhledem k nadcházejícím svátkům bude tento seriál pokračovat až po Novém roce. V nejbližších dílech se budeme zabývat interpretem SpiderMonkey, který je používán ve Firefoxu a v dalších prohlížečích založených na jádru Gecko a jehož původním autorem je sám tvůrce JavaScriptu Brendan Eich. Centrem naší pozornosti přitom bude zejména jeho vývojová verze TraceMonkey.

Zdroje

Autor je vývojář se zájmem o programovací jazyky, webové aplikace a problémy programování jako takového. Vystudoval informatiku na MFF UK a během studií zde i trochu učil. Aktuálně pracuje v SUSE.

Věděli jste, že nám můžete zasílat zprávičky? (Jen pro přihlášené.)

Komentáře: 5

Přehled komentářů

alblaho Děkuji
Jan R. Re: Děkuji
David Majda Re: Děkuji
Anonym RE: SquirrelFish: regulární výrazy, vlastnosti objektů a budoucnost
Anonym skvely
Zdroj: https://www.zdrojak.cz/?p=2897