SquirrelFish: optimalizace vykonávání instrukcí a nativní kód

Dnes se budeme věnovat tomu, jak urychlit vykonávání instrukcí bajtkódu JavaScriptu ve virtuálním stroji SquirrelFish. Představíme si přitom techniku direct threading, která zrychluje dispatching instrukcí, a další optimalizace. Na závěr článku se podíváme, jak je na tom SquirrelFish s generováním nativního kódu.

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

minulém dílu jsme si říkali, že jedním z problémů interpretů je pomalý dispatching instrukcí – tj. nalezení kódu, který vykonává právě zpracovávanou instrukci bajtkódu. Pojďme se nyní podívat, jak přesně dispatching probíhá, proč je to pomalá operace a jak ho lze urychlit.

Smyčka interpretu a dispatching

Každý interpret má v sobě „nekonečnou“ smyčku, ve které vykonává instrukce bajtkódu. V každém jejím kroku musí provést několik operací:

  • načíst opkód instrukce z paměti (fetch)
  • nalézt kód, který instrukci vykonává (dispatch)
  • vykonat instrukci (execute), včetně načtení jejích operandů a uložení výsledků
  • přejít na další instrukci
Fáze zpracování instrukcí bajtkódu interpretem

Fáze zpracování instrukcí bajtkódu interpretem.

Instrukce jsou obvykle uloženy v souvislém bloku v paměti, načtení opkódu tedy není složité – pokud je opkód instrukce stejně dlouhý jako slovo na dané platformě (což u SquirrelFish je), pak na něj stačí obvykle jen jedna instrukce.

Problémem ovšem je nalezení kódu implementujícího instrukci. Interpret má v sobě obvykle jeden velký příkaz switch, který se větví podle opkódu a v tělech jednotlivých větví obsahuje kód vykonávající instrukce.

Příkaz switch se (v ideálním případě) zkompiluje do tabulky, kde na místech indexovaných opkódy budou adresy kódu v jednotlivých větvích příkazu switch. To znamená, že při vykonávání bajtkódu se bude muset u každé instrukce provést vyhledání v tabulce (což zabere několik instrukcí) a poté nepřímý skok závislý na opkódu instrukce.

Nepřímé skoky v podobě používané interprety jsou na dnešních procesorových architekturách prakticky nepredikovatelné – procesor u takového skoku musí ve většině případů zastavit své předzpracovávání následujících instrukcí, protože neví, kde se bude ve vykonávání kódu pokračovat. To spolu s vyhledáváním v tabulce způsobuje relativní pomalost interpretu.

Zpomalení zde může být opravdu značné. Například podle měření provedeného na několika interpretech tvoří nepřímé skoky přibližně 3–13 % z instrukcí reálného stroje při běhu interpretu a především zaberou víc než polovinu času běhu interpretu. Vyplatí se tedy dispatching zoptimalizovat, na což se podíváme za chvilku.

Další části vykonávání instrukce již pro nás nejsou zajímavé. Průběh vykonání je pro každou z nich jiný a těžko lze zde uplatnit nějakou obecnou optimalizaci. Posun k další instrukci je ve většině případů jen inkrementace ukazatele na aktuální instrukci, případně jeho přepsání novou hodnotou (u instrukcí způsobujících skok, jako je třeba volání metody či vyvolání výjimky).

Urychlení dispatchingu

Technika, která se v interpretech (včetně SquirrelFish) používá pro urychlení dispatchingu instrukcí, se nazývá direct threading a nemá nic společného s vlákny, jak by se snad z názvu mohlo zdát. Její myšlenka je jednoduchá: nahradit opkódy instrukcí přímo ukazateli na kód, který vykonává danou instrukci. Zbavíme se tak celého příkazu switch a prohledávání tabulky. Skok na kód sice stále zůstane nepřímý, ale je obvykle o něco lépe predikovatelný, a tedy i rychlejší. Celkové dosažené zrychlení může být až dvojnásobné (samozřejmě velmi závisí na architektuře procesoru, použitém kompilátoru a dalších faktorech).

Technika není implementačně vůbec náročná – stačí předem projít vygenerovaný kód a opkódy instrukcí nahradit příslušnými adresami. Opkódy virtuálního stroje SquirrelFish jsou na to dokonce přímo stavěné (mají stejnou velikost jako ukazatel, který přijde na jejich místo).

Menším problémem je, že musíme znát adresu kódu, který vykonává jednotlivé instrukce. To znamená, že potřebujeme určit adresu návěští v jazyce C a pracovat s ní (odborně řečeno, návěští musí být first-class value). V ANSI C to není možné, ale některé překladače to dovedou. Mezi ně patří například gcc, nikoliv už ale Microsoft Visual C++.

Pro SquirrelFish, který je potřeba kompilovat oběma zmíněnými překladači, to znamená, že musí podporovat obě metody dispatchingu (příkaz switch i direct threading). Použitá metoda se vybere pomocí podmíněné kompilace při sestavení interpretu.

Další optimalizace

SquirrelFish se kromě optimalizace dispatchingu instrukcí snaží urychlit i jejich samotné vykonávání. Mnoho instrukcí se například díky dynamickému typování rozpadá na několik různých případů podle typů operandů, např. operátor „+“ může představovat buď numerický součet, nebo spojení textových řetězců. V takových případech se SquirrelFish snaží nejdříve testovat a řešit nejběžnější případy, a až poté zkoumá varianty okrajové. Správné seřazení podmínek znamená, že se stráví méně času zkoumáním slepých větví.

U zmiňovaného operátoru „+“ je například podle vývojářů SquirrelFish nejčastější případ, kdy jsou oba operandy čísla, případně řetězce, a relativně častá je ještě varianta, kdy je nalevo řetězec a napravo číslo. Všechny ostatní kombinace operandů se vyskytují vzácně.

Vývojáři také zkoumali frekvence vykonávání jednotlivých instrukcí a jejich kombinací. Pro často se opakující vzory po sobě jdoucích jednoduchých instrukcí vytvořili nové tzv. combo instrukce. Ty mají stejnou funkcionalitu jako série instrukcí jednoduchých, ale ušetří se u nich na dispatchingu.

Kompilace do nativního kódu

Jak již bylo řečeno v předchozích dílech, SquirrelFish podporuje just-in-time (JIT) kompilaci do nativního kódu. Spojení just-in-time znamená, že kompilace neprobíhá předem jako u klasických kompilátorů, ale program se kompiluje po částech za jeho běhu.

V současné době je kompilace podporována pouze na platformě x86. Přidání dalších architektur je v principu možné, ale dle vývojářů i mého pohledu do zdrojového kódu interpretu to bude vyžadovat poměrně velkou refaktorizaci celého kompilátoru.

Kdy a co se kompiluje?

Nativní kód je generován z bajtkódu, přičemž jsou vždy kompilovány najednou celé funkce. Kompilace je líná, tzn. funkce se kompiluje až ve chvíli, kdy má být spuštěna – do té doby je její kód reprezentován bajtkódem. Šetří se tak čas, který by se strávil kompilací nikdy nevolaných funkcí.

Při zkoumání kompilátoru mě velmi překvapilo, že spouštěné funkce jsou kompilovány vždy. Ve většině JIT kompilátorů se totiž měří, jak často jsou jednotlivé části kódu (typicky právě funkce či metody) spouštěny a kompilují se jen ty, u nichž kompilátor usoudí, že se to vyplatí. Kompilace je relativně časově náročný proces a kompilovat funkci, která je spuštěna jen několikrát za celou dobu běhu programu, by bylo neekonomické.

Důvody, proč SquirrelFish kompiluje všechny funkce, můžou být v zásadě dva: selektivní kompilace buď ještě není implementována, nebo je rozdíl rychlostí spuštění bajtkódu a nativního kódu tak velký a kompilace tak rychlá, že se opravdu vyplatí funkce kompilovat téměř ve všech případech.

Průběh kompilace

Jak přesně kompilace bajtkódu probíhá? SquirrelFish prochází bajtkód instrukci po instrukci a povede jednu ze dvou věcí:

  • U složitějších instrukcí vygeneruje do nativního kódu volání funkce, která implementuje funkcionalitu instrukce.
  • U jednodušších instrukcí se použije inlining, tzn. kód implementující instrukci je přímo vložen na její místo.

Posloupnost výsledných instrukcí nativního kódu je po vygenerování případně dále zoptimalizována.

Při rozhodování, zda použít inlining, musí být kompilátor opatrný. Tato technika totiž zvětšuje velikost kódu a díky omezené velikosti keší procesoru je obecně vykonávání většího kódu pomalejší. To může v konečném důsledku vyrušit čas uspořený absencí volání funkce.

Technika, kdy se volají funkce implementující původní instrukce bajtkódu, se nazývá context threading. Na první pohled se může zdát pomalá – jak se učí snad v každém kurzu assembleru, volání funkce je relativně drahá záležitost. V dnešních procesorech jsou ale volání a návraty z funkcí poměrně hodně zoptimalizovány a především jsou velmi dobře predikovatelné. Jsou tedy většinou rychlejší než nepřímé skoky používané u direct threadingu. V článku, který techniku context threadingu poprvé popsal, uvádí autoři zrychlení v řádu desítek procent.

Další informace

Pro podrobnější informace o kompilaci do nativního kódu doporučuji nahlédnout přímo do zdrojového kódu SquirrelFish – konkrétně především do souborů JavaScriptCore/jit/JIT­.cpp, JavaScriptCore/in­terpreter/Inter­preter.cpp a do souborů v adresáři JavaScriptCore/as­sembler.

Dobrým způsobem, jak najít všechny části související s kompilací, je vyhledat všechny výskyty řetězce #if ENABLE(JIT).

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

V příští části seriálu povídání o interpretu SquirrelFish dokončíme. Podíváme se na to, jak optimalizuje přístup k vlastnostem objektů, jak urychluje práci s regulárními výrazy a jaké další optimalizace jeho autoři připravují v blízké budoucnosti.

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: 8

Přehled komentářů

alblaho Díky
Jarek Pochvala
Roger Pekne
David Majda Re: Pekne
Pichi Re: Pekne
Anonymní Re: Pekne
Pichi Re: Pekne
Anonymní Re: Pekne
Zdroj: https://www.zdrojak.cz/?p=2893