Escape analysis
Dneska jenom krátce: Nedávno jsem zakopl o paper popisující partial escape analysis a napadlo mě, že bych tu mohl napsat pár slov o tom, co je escape analysis vlastně zač (termín s dovolením nebudu překládat a vystačím si s kurzívovou metodou).
Escape analysis je optimalizační technika používaná v kompilátorech, JITech a virtuálních strojích k eliminaci určitých alokací, která povede ke zrychlení programu. Jde v podstatě o to, že pokud objekt neunikne z metody (odtud to escape), není ho třeba alokovat na haldě, ale postačí alokace na zásobníku. Když metoda skončí, její rámec je zahozen a s ním jsou automaticky dealokovány i všechny objekty na zásobníku. Díky tomu není třeba ztrácet čas alokací1 , ulehčí se práce garbage collectoru a protože zásobník je skoro vždy horký v cache, je práce s ním velice rychlá. Kompilátor může jít ještě o krok dál a provést scalar replacement, kdy objekt není alokován ani na zásobníku, ale jeho členské proměnné skončí v registrech CPU.
Objekt/pole unikne pokud:
- je návratovou hodnotou metody
- je přiřazen do statické proměnné
- je přiřazen do členské proměnné jiného objektu, který uniká
- je předán jako argument metody (včetně implicitního argumentu
this
)
Jde o tranzitivní vlastnost. Kompilátor může alokovat na zásobníku jen pokud dokázal, že objekt za žádných okolností nemůže uniknout a z toho důvodu musí být konzervativní.
Jako v případě každé jiné optimalizace, je nutné k dobré funkci escape analysis inlinovat. Inlinování rozšíří kontext, na kterém JIT provádí analýzu a to vede k lepším výsledkům.
class X { // metoda `doSomething` vrací Int, neuniká z ní `this` // pointer a je dost malá na to, aby byla inlinována def doSomething(): Int = ??? } def f(): Int = { // objekt `x` neuniká z metody a může být alokován // na zásobníku val x = new X x.doSomething() }
Efekt inlinování je vidět na následujícím kusu kódu.
// objekt x uniká z této metody def f(): X = new X def g(): Int = { // pokud je metoda `f` inlinována, JIT zjistí, že // objekt x neuniká z metody `g` a tedy může být // alokován na zásobníku pokud však `f` není // inlinována, alokuje objekt, vrátí ho a `g` se // s ním musí vypořádat val x = f() x.doSomething() }
Přímočará escape analysis uspěje jen když si je jistá, že objekt nemůže uniknout nehledě na řídící struktury, podmínky a cykly. Pokud se však kód metody větví a v jedné větvi smyčky nic neuniká, ale v jiné, která se provede jen zřídka, uniká, JIT to vzdá a prohlásí, že objekt uniká.
Triviální příklad:
def f(): X = { val x = new X if (x.doSomething() != 0) { // v téhle větvi `x` neuniká null } else { // v téhle ano x } }
Tohle je právě téma na začátku zmíněného paperu popisující partial escape analysis v GraalVM, která si dokáže poradit s podmínkami a control flow. Kompilátor generuje kód, který provádí alokaci na haldě až na poslední chvíli, kdy je jasné, že osud objektu je zpečetěn a nemůže se stát nic jiného, než že unikne z metody. Ale než tento okamžik nastane, objekt žije na haldě nebo v registrech.
Výsledek může odpovídat tomuto pseudokódu:
def f(): X = { val x1, x2, x3 = scalarReplacedFieldsOfX if (x.doSomething() != 0) { // nic se nealokuje null } else { // tady proběhne alokace, objekt je // rematerializován na haldě val x = new X setFields(x, x1, x2, x3) s } }
V určitých benchmarcích použití partial escape analysis vede k redukci alokací o 58% a zrychlení programu o 33%.
Zmíněný GraalVM je projekt poskytující API, kterým je možné řídit chování JVM JITu. S touto kontrolou nad kompilátorem je možné na JVM jednoduše naroubovat podporu jazyků, které se chovají jinak než Java a které tedy standardní JIT nekompiluje ideálním způsobem. S GraalVM není třeba při implementaci nového jazyka začínat od nuly, protože má k dispozici všechny prostředky JVM jako je GC a efektivní JIT, který dokáže kód optimalizovat a (hlavně) deoptimalizovat.
O JRuby backendu založeném na Truffle a GraalVM píše Chris Seaton na svém blogu. Jeden z nejzajímavějších článků je ten, kde popisuje, jak překonali MRI Ruby s rozšířeními napsanými v céčku tím, že interpretovali C kód spolu Ruby kódem pomocí GraalVM.
Další přístup k eliminaci alokací je escape detection (letmo zmíněná Cliff Clickem), kterou používal Azul na jejich JVM běžící na jejich hardware.
Escape detection je optimistický přístup - všechny objekty jsou alokovány na zásobníku s tím, že hardware detekuje, jestli neunikl pointer na zásobník. Když unikl, procesor vyvolá výjimku, jejíž handler přesune objekt na haldu a přepíše pointer. Tento postup údajně vede k velice efektivní redukci alokací, protože je agresivní, nemusí mít 100% důkaz a sám o sobě dělá to, co partial escape analysis.
Dále k tématu:
- Jak JVM volá virtuální metody, jaká temná božstva musí vzývat, aby to bylo aspoň trochu rychlé
- Bez typů se obejdeme, ale...
- Java vs. C Performance - Cliff Click v této přednášce tvrdí, že alokace na zásobníku nemá na výkon žádný vliv.
- IonMonkey: Evil on your behalf
- C2 Partial Escape Analysis (2021)
Poznámky:
- Za alokaci se platí dvakrát v propustnosti paměti. Poprvé, když vytvářím objekt, musím jeho blok paměti načíst z RAM do cache, vynulovat (aspoň v případě JVM), přepsat užitečnými daty. Podruhé, když už není třeba, je vyhozen z cache a musí být zapsán zpátky do RAM na místo, kam patří na haldě. Tohle zabolí zvláště v případě objektů, které žijí jen deset nanosekund - po velice krátké době k nim už nikdy nepřistoupím, ale stále je třeba dodržet cache coherence protokol a zapsat je zpátky do RAM. I když propustnost pamětí je typicky velká, není nekonečná a obrovské tempo alokací na mnohajádrovém procesoru může trubky pořádně přiškrtit. Proto je alokace na zásobníku tak efektivní - opakovaně používá stejný blok paměti který je stále v cache a do RAM skoro vůbec nepřistupuje.