funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

Escape analysis

1. 6. 2016 — k47

Dneska jenom krátce: Ne­dávno jsem zakopl o paper po­pi­su­jící par­tial escape ana­ly­sis a na­padlo mě, že bych tu mohl napsat pár slov o tom, co je escape ana­ly­sis vlastně zač (termín s do­vo­le­ním nebudu pře­klá­dat a vy­sta­čím si s kur­zí­vo­vou me­to­dou).

Escape ana­ly­sis je op­ti­ma­li­zační tech­nika po­u­ží­vaná v kom­pi­lá­to­rech, JITech a vir­tu­ál­ních stro­jích k eli­mi­naci ur­či­tých alo­kací, která povede ke zrych­lení pro­gramu. Jde v pod­statě o to, že pokud objekt ne­u­nikne z metody (odtud to escape), není ho třeba alo­ko­vat na haldě, ale po­stačí alo­kace na zá­sob­níku. Když metoda skončí, její rámec je za­ho­zen a s ním jsou au­to­ma­ticky de­a­lo­ko­vány i všechny ob­jekty na zá­sob­níku. Díky tomu není třeba ztrá­cet čas alo­kací1 , ulehčí se práce gar­bage collec­toru a pro­tože zá­sob­ník je skoro vždy horký v cache, je práce s ním velice rychlá. Kom­pi­lá­tor může jít ještě o krok dál a pro­vést scalar repla­ce­ment, kdy objekt není alo­ko­ván ani na zá­sob­níku, ale jeho člen­ské pro­měnné skončí v re­gis­trech CPU.

Objekt/pole unikne pokud:

Jde o tran­zi­tivní vlast­nost. Kom­pi­lá­tor může alo­ko­vat na zá­sob­níku jen pokud do­ká­zal, že objekt za žád­ných okol­ností nemůže unik­nout a z toho důvodu musí být kon­zer­va­tivní.

Jako v pří­padě každé jiné op­ti­ma­li­zace, je nutné k dobré funkci escape ana­ly­sis in­li­no­vat. In­li­no­vání roz­šíří kon­text, na kterém JIT pro­vádí ana­lýzu a to vede k lepším vý­sled­ků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 in­li­no­vání je vidět na ná­sle­du­jí­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 ana­ly­sis uspěje jen když si je jistá, že objekt nemůže unik­nout ne­hledě na řídící struk­tury, pod­mínky a cykly. Pokud se však kód metody větví a v jedné větvi smyčky nic ne­u­niká, ale v jiné, která se pro­vede jen zřídka, uniká, JIT to vzdá a pro­hlásí, že objekt uniká.

Tri­vi­á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 po­pi­su­jící par­tial escape ana­ly­sis v Gra­alVM, která si dokáže po­ra­dit s pod­mín­kami a con­t­rol flow. Kom­pi­lá­tor ge­ne­ruje kód, který pro­vádí alo­kaci na haldě až na po­slední chvíli, kdy je jasné, že osud ob­jektu je zpe­če­těn a nemůže se stát nic jiného, než že unikne z metody. Ale než tento oka­mžik na­stane, objekt žije na haldě nebo v re­gis­trech.

Vý­sle­dek může od­po­ví­dat tomuto pseu­do­kó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­či­tých ben­chmar­cích po­u­žití par­tial escape ana­ly­sis vede k re­dukci alo­kací o 58% a zrych­lení pro­gramu o 33%.

Zmí­něný Gra­alVM je pro­jekt po­sky­tu­jící API, kterým je možné řídit cho­vání JVM JITu. S touto kon­t­ro­lou nad kom­pi­lá­to­rem je možné na JVM jed­no­duše na­rou­bo­vat pod­poru jazyků, které se cho­vají jinak než Java a které tedy stan­dardní JIT ne­kom­pi­luje ide­ál­ním způ­so­bem. S Gra­alVM není třeba při im­ple­men­taci nového jazyka za­čí­nat od nuly, pro­tože má k dis­po­zici všechny pro­středky JVM jako je GC a efek­tivní JIT, který dokáže kód op­ti­ma­li­zo­vat a (hlavně) de­op­ti­ma­li­zo­vat.

O JRuby bac­kendu za­lo­že­ném na Tru­f­fle a Gra­alVM píše Chris Seaton na svém blogu. Jeden z nej­za­jí­ma­věj­ších článků je ten, kde po­pi­suje, jak pře­ko­nali MRI Ruby s roz­ší­ře­ními na­psa­nými v céčku tím, že in­ter­pre­to­vali C kód spolu Ruby kódem pomocí Gra­alVM.

Další pří­stup k eli­mi­naci alo­kací je escape de­tection (letmo zmí­něná Cliff Clic­kem), kterou po­u­ží­val Azul na jejich JVM běžící na jejich hard­ware.

Escape de­tection je op­ti­mis­tický pří­stup – všechny ob­jekty jsou alo­ko­vány na zá­sob­níku s tím, že hard­ware de­te­kuje, jestli ne­u­nikl poin­ter na zá­sob­ník. Když unikl, pro­ce­sor vyvolá vý­jimku, jejíž han­dler pře­sune objekt na haldu a pře­píše poin­ter. Tento postup údajně vede k velice efek­tivní re­dukci alo­kací, pro­tože je agre­sivní, nemusí mít 100% důkaz a sám o sobě dělá to, co par­tial escape ana­ly­sis.


Dále k tématu:

Po­známky:

  1. Za alo­kaci se platí dva­krát v pro­pust­nosti paměti. Poprvé, když vy­tvá­řím objekt, musím jeho blok paměti načíst z RAM do cache, vy­nu­lo­vat (aspoň v pří­padě JVM), pře­psat uži­teč­nými daty. Po­druhé, když už není třeba, je vy­ho­zen 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ě ob­jektů, které žijí jen deset na­no­sekund – po velice krátké době k nim už nikdy ne­při­stou­pím, ale stále je třeba do­dr­žet cache co­he­rence pro­to­kol a zapsat je zpátky do RAM. I když pro­pust­nost pamětí je ty­picky velká, není ne­ko­nečná a ob­rov­ské tempo alo­kací na mno­ha­já­dro­vém pro­ce­soru může trubky po­řádně při­škr­tit. Proto je alo­kace na zá­sob­níku tak efek­tivní – opa­ko­vaně po­u­žívá stejný blok paměti který je stále v cache a do RAM skoro vůbec ne­při­stu­puje.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články