Java a JIT
Úvod
V tomto textu budou nastíněny některé techniky používané v JIT kompilátorech Javy. K pochopení některých těchto technik je třeba vědět, jak to chodí v Javě pod pokličkou. Z toho důvodu budou stručně popsány i vnitřnosti JVM. Zájemci o hlubší pochopení problematiky nechť se odpíchnou od použitých zdrojů.
Java Virtual Machine
Java Virtual Machine (JVM) je abstraktní stroj (tzv. virtuální stroj), který má pro platformu Java stejný význam jako procesor (CPU) a správce paměti (MMU) pro klasické jazyky. Stejně jako CPU disponuje instrukční sadou a stejně jako MMU se stará o správu paměti. Jak instrukční sada, tak paměťový model vykazují jisté zvláštnosti, které (mimo jiné) budou nastíněny v následujících kapitolách.
Následující kapitoly berte jakožto letmý a zjednodušený náhled do vnitřností JVM.
Paměťový model
Specifikace definuje sadu datových oblastí, které mají být spravovány JVM. Většinou není přesně definována jejich struktura, ale jejich chování.
Každé vlákno má PC registr, který obsahuje adresu právě probíhající instrukce (pakliže právě prováděná metoda není nativní).
Každé vlákno má také svůj vlastní JVM zásobník, v němž jsou rámce. Rámce jsou podobné rámcům z normálních programovacích jazyků. Jeden rámec odpovídá jednomu volání metody. Rámec obsahuje mimo jiné zásobník operandů (nad ním se provádí výpočty - viz níže) a lokální proměnné (= jak parametry volání metody (i skrytý this parametr), tak normální lokální proměnné).
Halda je datová oblast sdílená všemi vlákny, ve které se nachází všechny objekty a další dynamické struktury JVM. Za obsah haldy je odpovědný garbage collector, který uvolňuje nepoužívaný prostor.
Oblast metod je oblast, ve které se nachází informace o třídách (je vlastně podobná segmentu "text" z UNIXových systémů). Informace o třídách zahrnuje fond konstant i kód metod. Fond konstant (constant pool) obsahuje nejenom klasické konstanty známé v době kompilace, ale také i jména tříd, metod či odkazů nutných k úspěšnému linkování.
Jakožto speciální oblast je možno uvažovat i pracovní prostor vlákna, ve kterém si vlákno udržuje svoje kopie dat z haldy (resp. z jednotlivých instancí). To je mimochodem jeden z důvodů proč je třeba synchronizovat. Tento prostor není vyžadován specifikací, pouze doporučen.
Instrukční sada
Instrukční sada JVM je zásobníková tj. nepoužívá registry, veškeré výpočty se uskutečňují pomocí zásobníku operandů (operand stack). Oproti klasickým instrukčním sadám běžných architektur má některá rozšíření např. monitory (zámky), podporu objektů a vyjímky.
Instrukce se skládají z opcode a operandů. Opcode je 1 byte, některé instrukce operandy nemají. V mnemotechnických názvech instrukcí se (tam kde to má smysl) používá konvence TNAME, kde T je identifikace typu, se kterým se pracuje (např. i pro integer, l pro long atd.). Pracuje se se stejnými typy jako v Javě, pouze typy byte, char a short se automaticky konvertují na integer (a obráceně), takže s nimi žádná instrukce nepracuje přímo (kromě práce s poli). Instrukční sada není otrogonální, tj. většina funkcí pracuje s integery, menšina navíc s longy a téměř žádné se zbylými typy (nutno použít konverzí).
Následuje krátký a neúplný přehled instrukcí rozčleněný dle funkce. Zájemci o kompletní výčet nechť nahlédnou do specifikace.
-
Load a Store instrukce slouží k přenosu hodnot mezi zásobníkem operandů a lokálními proměnnými.
Instrukce mají buďto operand implikovaný instrukcí či následuje 1 bytový index do fondu lokálních proměnných.
Př. rodina instrukcí iload, istore, iconst či speciální instrukce wide, která dovoluje instrukcím přistupovat k lokálním proměnným na dvoubytových indexech. -
Aritmetické instrukce (pracují pouze se zásobníkem operandů).
Př. instrukce iadd, isbu, imul, ixor, iinc a instrukce porovnávání dcmpg (integery se neporovnávají přímo, ale pouze přes podmíněné skoky). -
Konverze typů (konverze nemusí zachovat znaménko ani přesnost).
Př. i2l (integer -> long), l2i (long -> integer), i2b (integer -> byte - výsledek je stále integer, ale ořezaný). -
Manipulace se zásobníkem operandů.
Př. pop (vybrání prvku), dup (duplikace prvku), swap (prohození vrcholu zásobníku). -
Práce s objekty a poli.
Př. new (vytvoření instance - na ní nutno pomocí invokespecial zavolat metodu <init>), getfield, putfield (práce s atributy instance), newarray (vytvoření pole), arraylength (délka pole), instanceof. -
Předávání řízení.
Př. ifeq (skok při shodě vrcholu zásobníku), ifnull, tableswitch a lookupswitch (implementace konstrukce switch), goto (skok), athrow (vyhození vyjímky), invokevirtual (volání metody), invokeinterface (volání metody na rozhraní), invokespecial (volání konstruktorů, privátních metod či metod předka), invokestatic (volání statických metod). -
Synchronizace.
Instrukce monitorenter, monitorexit.
Just-in-Time kompilace
Jelikož se Java procesory neprosadily a interpretace bytekódu na konvenčních procesorech je přiliš pomalá, bylo třeba vymyslet nějaký způsob, jak provádění kódu urychlit. Myšlenka nativních metod umožňuje zrychlení některých specifických operací, ale přilišné zvětšení výkonnosti obecných programů to nepřináší.
Proti kompilaci přímo do nativního kódu místo do bytekódu hovoří zejména narušení ideji "compile once, run everywhere" (přelož jednou, spusť všude), takže v současné době jediným projektem, který se tím zabývá je GCJ z GNU Compilers Collection, kdy se na společný backend nasadí Java frontend.
Jakýmsi hybridem mezi kompilací do nativního kódu přímo a za běhu je kompilace celé třídy při jejím načtení, přičemž dochází k uložení zkompilované třídy do cache. Podobný mechanismus používá Python, z dostupných JVM dříve takto pracovalo Kaffe (než se z něj stal research project), teď se zdá že používají klasický JIT. Sdílení přeloženého kódu má výhody i nevýhody. Výhodou je možnost sdílení přeložených tříd, což je věc, která trochu redukuje nenažranost Javy, a urychlení startu. Nevýhodou je nutnost řešit problémy, kdy provést nový překlad, co všechno znovu přeložit (detekce závislostí), jak zajistit bezpečnost (komu umožnit sdílení a kdy), jak poznat různé verze stejné třídy apod.
Just-in-Time kompilace je rozšíření JVM o myšlenku dynamické (re-)kompilace kódu. Zjednodušené řečeno jde o překlad bytekódu v okamžiku, kdy se vykonává, bez uložení do externí cache. Většina nevýhod předchozích systému odpadá, bohužel také odpadají některé výhody. Odpadají problémy se sdílením kódu, ale odpadá i výhoda tohoto sdílení. Nevýhodou oproti přímé kompilaci je požadavek na rychlost převodu, tj. optimalizace nemohou být výpočetně náročné.
Mainstream (Sun a IBM) JVM používá pouze JIT. Třetím do party je Oracle JVM, přičemž Oracle dodává i překladač Javy do nativního kódu. Zbylá JVM (Symantec, Kaffe, OpenJVM a různé výzkumné projekty od Sunu i IBM) taktéž ve většině používají JIT.
Spousta problémů týkajících se JIT se týká i ostatních způsobů kompilace do nativního kódu. Zejména nutnost tak jako tak mít ve výsledku i interpret bytekódu (Java umožňuje dynamické nahrávání tříd), hlídat si přetečení/podtečení zásobníků, korupci haldy, race condition vláken a správné ošetření vzniku vyjímky (při vyvolání vyjímky se musí provést instrukce do místa vzniku vyjímky, žádná další již ne).
Urychlování běhu bytekódu spočívá nejenom v překladu do nativního kódu, ale uplatňují se i běžné optimalizační techniky. Nejužšími místy Javových programů jsou: časté volání metod (v OOP metodologii se hojně používají get/set metody, které jsou velmi malé a volají se velmi často), časté volání virtuálních metod (každá nestatická a neprivátní metoda (kromě konstruktorů) je volána virtuálně), kontrola mezí a null ukazatelů, ošetřování vyjímek, instanceof testy a synchronizovaný kód.
Široce používané techniky v JIT kompilátorech jsou známé i z klasických kompilátorů: rozbalování smyček, eliminace mrtvého kódu, vkládání těl metod a eliminace shodných podvýrazů. Vesměs veškeré JIT kompilátory také používají mechanismus detekce "hotspots", tj. míst v kódu, u kterých se vyplatí obětovat nějaký čas pro kompilaci do nativního kódu. Taktéž použití nativních vláken je široce rozšířené.
V následujícím textu popíši stručně některé techniky JIT kompilace používané v JIT kompilátorech firem Sun a IBM. Většina technik je společná oběma kompilátorům, proto mezi nimi nebudu rozlišovat, u některých technik ani není známo zda a popř. jak jsou implementovány. Nicméně všechny popsané techniky jsou či byly používány. Obecně se věří, že IBM JIT je kvalitnější, i když IBM JRE jako celek má občas problémy s kompatibilitou. Osobně jsem žádná měření neprováděl.
Sun JIT existuje ve skutečnosti ve dvou verzích: Java HotSpot Client VM a Java HotSpot Server VM. Prvně zmíněný je určen pro klientské programy, tj. programy, u nichž je doba nabíhání důležitá a proto provádí spíše méně náročné optimalizace. Druhý je určen pro serverové programy, u nichž nevadí, že chvíli po startu jsou pomalejší, jelikož provádí náročnější optimalizace. Velké množství popsaných technik je společné oběma verzím.
Používané techniky
Určování metod vhodných k JIT překladu (hotspot detection)
Jednoznačným kandidátem na metody vhodné k překladu jsou ty metody, jejichž překladem se nejvíce získá. To je ovšem značný problém, proto se zavádí heuristika, že nejlepšími kandidáty jsou nejčastěji volané metody a metody, které běží nejdéle. Jedním ze způsobů jak toto řešit je mít u každé metody čítač volání, který je inicializován na určitou předem danou hodnotu. Pakliže je čítač volání snížen na nulu, kód metody se přeloží. Metody obsahující smyčky dostanou nižší prahovou hodnotu (v závislosti na odhadované délce trvání smyček), čímž se simuluje výběr metod, které běží nejdéle. Běží-li některá smyčka přiliš dlouho (při interpretaci bytekódu se počítá počet iterací), tak se uprostřed výpočtu provede kompilace a běh smyčky pokračuje již v přeloženém kódu.
Inlining metod
Je rozdíl mezi virtuálními a nevirtuálními (či statickými) metodami. U prvně daných není zřejmé jaká metoda se zavolá. Prázdné metody se inlinují vždy. Zbylé metody se inlinují pouze uvnitř smyček či jsou-li nepřímo ze smyček volány. Statické a nevirtuální metody se inlinují na základě několika kritérií, např. velikostí metody (velikosti bytekódu), nárůstu počtu lokálních proměnných a proměnných na zásobníku (příliš mnoho proměnných komplikuje alokaci registrů v pozdějších fázích kompilace). Při inlinování virtuálních metod se vychází z předpokladu, že cílová třída nemá potomky. To umožňuje nalézt metodu, která se bude za takéhoto předpokladu volat. Vygenerovaný kód poté provede nalezení skutečné metody, která se má provést a pakliže se shoduje, použije se inlinovaná metoda. V opačném případě se zavolá metoda virtuální.
Optimalizace kontrol hodnoty null (null checking)
Do data-flow se propaguje, zda již test na null proběhl či nikoliv. Na základě této informace se pak lze rozhodnout zda test generovat či nikoliv. Tato optimalizace se ve skutečnosti nemusí moc používat, protože se obvykle používají hardware traps pro detekci null ukazatelů (popsáno dále).
Optimalizace kontrol mezí polí
Existuje několik algoritmů na optimalizaci kontrol mezí polí. Jediným ověřeným použitím je Guptův algoritmus, který je použit v IBM JIT, i když ve vylepšené podobě. Zájemci o bližší seznámení nechť si algoritmus vyhledají. V podstatě jde o data-flow analýzu, která spojuje či eliminuje testy mezí.
Loop versioning
Jednoduché smyčky přes pole, jejichž indukční proměnná má počáteční a koncovou mez, které jsou ve smyčce invariantní, a mají posun, který je konstantní, nepotřebují složité testy mezí polí vždy, když se do pole přistupuje. Proto je možno použít techniku verzování smyček: vytvoří se dvě stejné smyčky. Při běhu kódu se nejprve provede test na meze pole, pakliže je test v pořádku provede se první verze smyčky bez kontroly mezí. Není-li test v pořádku, tak je třeba provést druhou verzi smyčky, která provádí kontroly tak jak má. Druhá verze je nutná kvůli zajištění provedení všech instrukcí, tak jak mají být provedeny a vyhození vyjímky na tom místě, na kterém má být vyhozena.
Alokace registrů
Registry je možno alokovat klasickým algoritmem barvení grafů, tak jak se používá ve statických kompilátorech (ten je použit i v Java HotSpot Server VM) nebo se nabízí použít rychlejších algoritmů, které však neprodukují tak optimální přiřazení. Jeden takový algoritmus je použitý v IBM JIT: Kód (kódem je myšlen kód metody) je rozdělen do dlaždic (tiles), kde smyčka = 1 dlaždice a kód mezi dvěma přilehlými smyčkami = 1 dlaždice. Jedna dlaždice představuje prostor pro separátní alokaci registrů. Registry se přiřazují nejprve proměnným na zásobníku (pokud možno všem; je třeba si uvědomit, že kompilátor ví kolik hodnot bude v kterém místě kódu na zásobníku, jelikož veškeré instrukce berou pevný počet hodnot ze zásobníku a také pevný počet hodnot na něj vrací - jak je to vyřešeno v Javě 1.5, s ohledem na metody s proměnným počtem paramterů, mi není známo). Pakliže některé zbydou (o čemž by se na ia32 dalo pochybovat), tak se přiřadí lokálním proměnným a to v pořadí určeném počtem jejich užití v rámci dané dlaždice.
Identifikace idiomů v bytekódu
Java kompilátory, narozdíl od kompilátorů klasických jazyků, neprovádí nad vygenerovaným kódem (bytekódem) žádné přeuspořádání instrukcí. Z toho důvodu a z důvodu omezené instrukční sady lze zpětně z přeloženého kódu zrekonstruovat, alespoň přibližně, původní zdrojový text. Což mimo jiné způsobilo vynoření se různých obfuskátorů (mění bytekód) a jejich protějšků dekompilerů. Vyhledem k tomu, že cesta "klasický strukturovaný jazyk" -> "bytekód pro zásobníkový stroj" -> "klasický procesor" může být někdy neefektivní, tak byla vyvinuta technika identifikace idiomů. Idiom je kus bytekódu, který odpovídá nějakému jasně danému Javovému kódu, např. přiřazení s inkrementací. Takovýto idiom může být přeložen lépe, s minimalizací použití zásobníku, což ve výsledku ušetří nějaké registry.
Optimalizace přetypování
Objektové přetypování (např. při přiřazení) je náročný test, jelikož je nutno traverzovat objektovou hierarchii. Jednoduchá optimalizace je pamatovat si poslední úspěšně přetypovaný objekt.
Optimalizace vyjímek
NullPointerException, ArrayIndexOutOfBoundsException a dělení nulou jsou implementovány hardwarovou vyjímkou (hw trap), jejíž handler při zachycení vyjímky okamžitě volá aktuální handler. Handlery jsou uloženy na zásobníku vlákna. Aby se dal identifikovat aktuální handler, i v přeloženém kódu, tak se adresa aktuálního handleru uchovává ve speciální lokální proměnné.
Code scheduling
Klasické přeřazování instrukcí je pro JIT přiliš pomalé. Zajímavý a jednoduchý algoritmus je použit v IBM JIT: V pozadí algoritmu stojí tabulka, kde sloupce odpovídají pipelines a řádky počtu tiků hodin. Vygenerovaná instrukce si nese informaci o vstuních registrech, výstupním registru, přistupované paměti, omezení na pipelines a zda může vyhodit vyjímku. Veškeré tyto informace jsou dodány ve formě bitových vektorů. Při umisťování do tabulky se bere ohled na konflikty s dalšími instrukcemi, je proto nutné vyřešit registrové či paměťové závislosti. Také je třeba zaručit, aby instrukce, která může generovat vyjímku, nebyla dána mimo pořadí, protože je nutno přesně dodržet místo, kde se vyjímka vyhodí. Až se tabulka zaplní, tak se kód zapíše na cílové místo, tabulka se vyprázdní a jede se dál.
Zdroje
- The Java Virtual Machine Specification
http://java.sun.com/docs/books/vmspec/ - The Java HotSpot Performance Engine Architecture (White Paper)
http://java.sun.com/products/hotspot/whitepaper.html - The Java HotSpot Virtual Machine, v1.4.1 (White Paper)
http://java.sun.com/products/hotspot/docs/whitepaper/Java_Hotspot_v1.4.1/Java_HSpot_WP_v1.4.1_1002_1.html - Overview of the IBM Java Just-in-Time Compiler
http://www.research.ibm.com/journal/sj/391/suganuma.html