Just-in-time kompilace

JIT (akronym pro just-in-time) je v informatice označení pro speciální metodu překladu využívající různé techniky pro urychlení běhu programů přeložených do mezikódu (např. CIL). Používá se například pro programovací jazyk Java. Program, který je spuštěn a prováděn, je v době provádění přeložen přímo do nativního strojového kódu počítače, na kterém je prováděn, čímž dochází k urychlení jeho běhu. Negativem této techniky je prodleva, kterou JIT kompilátor (nikoli interpret) stráví překladem do nativního kódu, a proto se do nativního kódu často překládají jen mnohokrát (řádově 10 000×) volané úseky programu. Hlavním problémem JIT je, že má málo času na provedení své práce. Tyto nevýhody lze eliminovat použitím trvalé cache. Naopak výhodou je, že je možné lépe optimalizovat pro daný procesor a využít jeho rozšířených instrukcí.

Druhy JIT kompilátorů

  1. Překlad v době instalace – k přeložení dochází v době instalace aplikace či komponenty. Výhodou je odstranění zpoždění, které způsobuje samotný překlad. V tomto případě se už nejedná o Just In Time, ale Ahead Of Time kompilaci.
  2. Opravdový JIT překladač – před spuštěním aplikace dojde k překladu a optimalizaci. Výsledek je srovnatelný s konvenčním překladačem. Nevýhodou je poměrně velké zdržení před spuštěním aplikace.
  3. Ekonomický JIT překladač – provádí částečný překlad programu. Jsou překládány jen ty části, k jejichž vykonání má dojít, a optimalizační algoritmy jsou vypnuty. Uskutečněné překlady jsou archivovány, aby se nemusely překládat znovu. Hlavní výhodou je menší paměťová náročnost.

Používané techniky

  • odstranění mrtvého kódu
  • vkládání těl metod
  • odstranění shodných podvýrazů
  • rozbalování smyček, ...

Podrobnosti

Zdrojový kód je přeložen do mezikódu známého jako bajtkód (anglicky bytecode). Bajtkód není strojový kód pro konkrétní počítač a je přenositelný mezi různými počítačovými platformami. Bajtkód je následně interpretován a spuštěn pomocí virtuálního stroje (tzv. aplikační virtualizace). Just In Time kompilátor může být použit jako způsob urychlení spouštění bajtkódu. V době, kdy má být vykonán blok kódu, přeloží JIT kompilátor některé či všechny jeho části do strojového kódu pro lepší výkon. Toto lze provést na soubor, na funkci nebo dokonce na libovolný fragment kódu. Překlad tedy může být proveden až za běhu, odtud název Just In Time – Právě v čas. Překlad může být uložen do souboru (disková cache) a pokud má být znovu použit později, není nutná opětovná kompilace.

Tradiční interpretové virtuální stroje budou interpretovat bajtkód obvykle s mnohem nižším výkonem. Některé interprety dokonce interpretují zdrojový kód bez mezikroku ho nejprve přeložit do bajtkódu, čímž dosahují ještě horšího výkonu. Staticky zkompilovaný kód nebo nativní kód je přeložen ještě před jeho spuštěním. Dynamické prostředí pro překlad pak umožňuje využití kompilátoru i za běhu programu. To poskytuje mnoho výhod JIT, ale programátor má raději kontrolu nad částmi kódu, které jsou přeloženy. Většina JIT systémů však umožňuje přeložit dynamicky generovaný kód, který poskytuje v mnoha situacích podstatné výkonnostní výhody oproti staticky kompilovanému kódu.

Všeobecný cílem užívání JIT technik je dosáhnout nebo překonat výkonnost statické kompilace při zachování výhod bajtkódové interpretace. V době překladu do bajtkódu je provedeno velmi náročné parsování původního zdrojového kódu a provedení základní optimalizace. Překlad z bajtkódu do strojového kódu je pak mnohem rychlejší, než překlad ze zdrojového kódu. Překladače z bajtkódu do strojového kódu jsou jednodušší na napsání, protože překladač generující přenositelný bajtkód již udělal mnoho práce. Navíc má běhové prostředí kontrolu nad kompilací stejně jako interpretovaný kód, díky čemuž může běžet v chráněném režimu.

Kompilace může být optimalizována pro cílový procesor a operační systém, v němž aplikace běží. JIT může vybrat takové instrukce, o nichž zjistí, že jsou daným procesorem podporovány. K zajištění tohoto stupně optimalizační specifikace se statickým kompilátorem se musí buď přeložit binárka pro každou zamýšlenou platformu či architekturu, nebo seskupit mnoho verzí částí kódu v rámci jedné binárky.

Systém JIT je schopen shromažďovat statistické údaje o tom, jak program aktuálně běží v prostředí, v němž je spuštěn, a může tak kód přeuspořádat a přeložit ho pro optimální výkon. Nicméně některé statické kompilátory mohou rovněž získat informace o cílovém běhovém prostředí.

Systém může provádět globální optimalizaci kódu bez ztráty výhod dynamického linkování a bez nutné režie spojené s funkcí statických kompilátorů a linkerů. Speciálně když se provádí globální substituce, může proces statické kompilace potřebovat běhové ověření a zajistit, aby virtuální volání nastalo pouze v případě, že aktuální třída objektu implementuje danou metodu, a dále ověřit splnění hraničních podmínek při přístupu k polím, které je nutné zpracovat v průběhu cyklu. S JIT kompilací může být v mnoha případech toto zpracování přesunuto mimo cyklus, což často přináší obrovský nárůst rychlosti.

Zpoždění při startu a optimalizace

JIT typicky způsobí mírné zpoždění v počátku spouštění aplikace kvůli času potřebnému k zavedení bajtkódu do paměti a jeho překladu. V angličtině se toto zpoždění nazývá "startup time delay". Obecně platí, že čím více optimalizace JIT provádí, tím lepší kód vygeneruje, ale tím se úměrně zvětší počáteční zpoždění. Proto JIT kompilátor musí dělat kompromis mezi dobou potřebnou pro optimalizaci překladu a kvalitou kódu, který má vygenerovat.

Nicméně občas je při spouštění mnoho času zabráno spíše kvůli I/O operacím, než kvůli JIT kompilaci. Například třídní datový soubor rt.jar pro Java Virtual Machine (dále jen JVM) má okolo 40 MB a JVM musí prohledávat velké množství dat v tomto obrovském souboru.

Jedna z možných optimalizací použitá prostředím JVM je kombinace interpretace a JIT kompilace. Kód aplikace je zpočátku interpretovaný, ale JVM monitoruje, které sekvence bajtkódu jsou často prováděny a přeloží je do strojového kódu pro přímé spuštění na hardwaru k maximalizaci rychlosti běhu. U zřídkakdy spouštěného bajtkódu je čas potřebný pro překlad ušetřen, čímž se redukuje počáteční zpoždění. Navíc program zabere čas spuštěním pouze potřebné menšiny svého kódu, díky čemuž je redukce doby překladu značná.

Správný kompromis se může měnit v závislosti na okolnostech. Například JVM má dva hlavní režimy - klient a server. V klientském režimu je provedena minimální kompilace a optimalizace k redukci doby spouštění. V režimu server jsou provedeny rozsáhlé optimalizace a kompilace k maximalizaci výkonu za obětování mnohem delšího času. Jiné Java JIT překladače využívají statistiky. Zjišťují kolikrát je metoda vyvolána a v kombinaci s velikostí bajtkódu heuristicky rozhodnou kdy co zkompilovat. Další překladače zase zjišťují počet spuštění kombinované s detekcí cyklů. Obecně je velmi těžké přesně předpovědět, jaké metody optimalizovat v krátce běžících a jaké v dlouhodobě běžících aplikacích.

Native Image Generator (NGEN), česky generátor nativního obrazu od společnosti Microsoft má jiný přístup ke snížení počátečního zpoždění. NGEN zkompiluje bajtkód do obrazu s nativním kódem počítače. Výsledkem je, že pro druhé a další spuštění není nutná běhová kompilace. Od. NET Frameworku verze 2.0 dodávané s Visual Studiem 2005 běží NGEN hned po instalaci nad všemi knihovnami DLL od Microsoftu. JIT pre-kompilace poskytuje způsob, jak zlepšit(zrychlit) dobu spuštění. Nicméně kvalita generovaného kódu nemusí být tak dobrá z podobných důvodů, jako u staticky zkompilovaného kódu bez možnosti optimalizací proveditelných pouze za běhu. Existují také implementace Javy, které kombinují ahead-of-time kompilátor, což je kompilace mezijazyka jakým je java bajtkód nebo .NET Intermedite Language do nativní(systémově závislé) binárky, s Just in Time kompilací.

Stále více moderních běhových prostředí, jako například Microsoft. NET Framework a většina implementací Javy jsou založené na Just In Time kompilaci.

Historie

První zveřejněný JIT kompilátor je obecně přičítán McCartymu k práci na jazyku LISP v roce 1960.[1] V jeho seminární práci Rekurzivní funkce symbolických výrazů a jejich strojové vyhodnocování, Část I, zmiňuje funkce, které jsou překládány za běhu programu, ušetří se tedy nutnost ukládat výstup kompilátoru na děrné štítky.[2] V roce 1968 Thompson představil metodu pro automatickou kompilaci regulárních výrazů do strojového kódu, který je poté spouštěn, aby mohl provést srovnávání na vstupním textu.[1][3] Významná technika pro odvozování zkompilovaného kódu pro interpretaci byla propagována Mitchellem v roce 1970, kterou implementoval pro experimentální jazyk LC.[1][4]

Smalltalk propagoval nové aspekty JIT kompilace. Například překlad do strojového kódu byl dělán na vyžádání, výsledek byl uložen do vyrovnávací paměti pro další použití. V okamžiku, kdy začala docházet volná paměť, systém začal části tohoto kódu mazat a znovu je vytvořil až pokud byly potřeba.[1][5] Jazyk Self firmy Sun tyto techniky velice vylepšil a jednu dobu se jednalo o nejrychlejší Smalltalk systém na světě; dosáhl až poloviční rychlosti optimalizovaného kódu jazyka C,[6] navíc s podporou objektového programování.

Self byl Sunem zavržen, výzkum se přesunul do jazyku Java, momentálně je využíván ve velké většině implementací Java Virtual Machine, například HotSpot, který je na těchto principech založen a bohatě využívá dostupnou výzkumnou základnu.

HP projekt Dynamo byl experimentální JIT kompilátor, kde bajtkódový formát a formát strojového kódu byl stejný; systém překládal strojový kód HPA-8000 na strojový kód HPA-8000. Nečekaně to vyústilo ke zrychlení, v mnoha případech až o 30 %, protože toto umožnilo provádět optimalizace na úrovni strojového kódu. Například vkládání kódu pro lepší využití cache, optimalizaci volání dynamických knihoven a mnoho jiných optimalizací za běhu programu, kterých konvenční kompilátory nebyly schopny.[7]

Reference

V tomto článku byl použit překlad textu z článku Just-in-time compilation na anglické Wikipedii.

  1. ↑ a b c d AYCOCK, J. A brief history of just-in-time. ACM Computing Surveys. 2003, s. 97–113. Dostupné online [cit. 2010-05-24]. DOI 10.1145/857076.857077. (anglicky) 
  2. ↑ MCCARTHY, J. Recursive functions of symbolic expressions and their computation by machine, Part I. Communications of the ACM. 1960, s. 184–195. Dostupné online [cit. 24 May 2010]. DOI 10.1145/367177.367199. (anglicky) 
  3. ↑ THOMPSON, K. Programming Techniques: Regular expression search algorithm. Communications of the ACM. 1968, s. 419–422. Dostupné online [cit. 2010-05-24]. DOI 10.1145/363347.363387. (anglicky) 
  4. ↑ MITCHELL, J.G. The design and construction of flexible and efficient interactive programming systems. [s.l.]: [s.n.], 1970. (anglicky) 
  5. ↑ DEUTSCH, L.P.; SCHIFFMAN, A.M. Efficient implementation of the Smalltalk-80 system. POPL '84: Proceedings of the 11th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages. 1984, s. 297–302. DOI 10.1145/800017.800542. (anglicky) 
  6. ↑ http://research.sun.com/jtech/pubs/97-pep.ps (webarchive)
  7. ↑ Ars Technica on HP's Dynamo