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:

Poznámky:

  1. 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.

Flattr this!

This entry was posted in Algo, JVM, VM. Bookmark the permalink.

8 Responses to Escape analysis

  1. Ladislav Thon says:

    Zajímavá věc s tou partial escape analysis, LuaJIT nebo Dart VM dělají něco podobného pod názvem allocation sinking. Efekt téhle optimalizace je dobře vidět na programech, které používají hodně value-like objektů.

  2. Díky za článek.

    PS. Některé odkazy vedou na 404.

  3. Lopata says:

    Na Truffle a Graal myslím dělá nějaký Čech, už si přesně nepamatuji kdo, ale každopádně slušná práce, kdyby tak na tom rozjeli PHP a pohřbili všechny ty stávající zendy a hiphopy, ale to se bohužel nikdy nestane.

    Alokace na zásobníku v C++ je v rukou programátora a to je podle mě hlavní důvod, proč se s C++ dá více optimalizovat výkon lépe než s JVM/Javou. By mě zajímalo jestli tyhle optimalizace – GraalVM – už dokážou být „výkonnější“, než ten C++ programátor sám :), asi ještě ne, ale ta doba, kdy to tak bude, už se celkem přiblížila.

  4. Asi 6 lidí v ČR na GraalVM & Trufflu pracuje. Potřebujeme však víc.

    A doba, kdy C bylo rychlejší než jiné jazyky je pryč: http://www.youtube.com/watch?…

  5. v6ak says:

    Teoreticky by šlo ke každé metodě generovat metadata typu „tento parametr neuniká“, pak by se mohly rozšířit obzory i bez inlineování. Ale nemusí to být až tak jednoduché, graf vzájemných volání může být cyklický (rekurze), pak se to komplikuje, pokud bychom to chtěli mít maximálně powerful. (Na druhou stranu, tady by se assi spíš použil nějaký iterativní algoritmus.

    Napadá mě ale, jak si escape analysis poradí s deoptimalizací polymorfního volání:

    1. Mám metodu x, která alokuje objekt e. Jediné místo, kam objekt uniká, je jedno polymorfní volání jiného objektu p . Logicky nelze s jistotou tvrdit, že objekt nemůže unikat.
    2. JVM ale zjistí, že tato metoda je jednoznačná (například k danému rozhraní Y existuje jen jediná implementace) a rozhodne se jí inlineovat.
    3. Spustí se metoda x (a nějakou dobu běží).
    4. Načte se nová třída, která ale přidává novou implementaci rozhraní Y. Optimalizace z kroku 2 se musí deoptimalizovat.

    Co ale s tím udělá JVM? Po kroku 2 se nabízí, že inlineování zasáhne do rozhodování o escape analysis. Pokud ale se kvůli tomu rozhodne JVM alokovat zmíněný objekt na zásobníku, musí si poradit s následnou deoptimalizací v kroku 4, odkdy tato optimalizace nemusí být korektní. Co víc: tato deoptimalizací může nastat, zatímco metoda x běží, a obecně vzato je potřeba přealokovat i již alokované objekty e. Z toho mi vychází, že pokud JVM takovéto situaci neumí předejít (což by asi bylo obtížné, znamenalo by to nejspíš nějak oddělovat spekulativně inlineovaný kód, což by šlo proti smyslu spekulativního inlineování a asi by to ani nebylo jednoduché), není to 100% konzervativní optimalizace.

    • Odpovědí jsou safepointy a GC map. Než JVM může načíst novou třídu musí všechna vlákna přivést do safepointu (což by měla být volání metod nebo hrany smyšek). V safepointu VM díky GC map zná obsah zásobníku a registrů a proto může beze strachu deoptimalizovat. Potom, co classloading doběhne, některá vlákna budou pokračovat v interpreteru místo JITovaného kódu, jehož předpoklady classloading porušil.

      • v6ak says:

        Díky. Safepointy tak nějak znám, spíš jsem se zamyslel, jak moc doslova mám brát větu „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í.“. Pokud z toho JVM vybruslí přes safepointy, je to OK, ale už to není „za žádných okolností“.

Leave a Reply

Your email address will not be published. Required fields are marked *