Escape analysis

1. 6. 2016 — k47

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í¹ , 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

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.