funkcionálně.cz

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

Jak JVM volá virtuální metody, jaká temná božstva musí vzývat, aby to bylo aspoň trochu rychlé

18. 9. 2015 — k47

Alek­sey Shi­pi­lёv v (ne)dávné době napsal velice ob­sáhlý článek o volání vir­tu­ál­ních metod v JVM: The Black Magic of (Java) Method Dispatch. Do de­tailů v něm popsal všechny způ­soby, jak lze volat vir­tu­ální metody, vy­svět­lil všechny op­ti­ma­li­zace, které JIT ja­vov­ského vir­tu­ál­ního stroje dělá a otes­to­val jaký mají dopad na výkon.

Jde o velice hutné čtení, které pře­téká výpisy x86 as­sem­bleru a low-level de­taily fun­go­vání kom­pi­lá­torů JVM. Ně­ko­lik z nich pro bylo i pro mě úplnou no­vin­kou. Roz­hodl jsem se proto tady shr­nout ty nej­za­jí­ma­vější in­for­mace.


Java má neje­nom ta­bulku vir­tu­ál­ních metod (vtable), ale také vtable pro každý im­ple­men­to­vaný in­ter­face (itable). Pokud JVM ne­do­káže metodu in­li­no­vat, je volání in­ter­face metody (by­te­code invokeinterface) o něco po­ma­lejší než volání „třídní“ metody (by­te­code invokevirtual).

Důvod je jasný: Hi­e­rar­chie tříd v Javě tvoří strom a po­tom­kové mohou metody pouze při­dá­vat nebo pře­pi­so­vat (ale ne od­stra­ňo­vat). Po­tom­kova vtable tedy ob­sa­huje všechny zdě­děné metody na stej­ných po­zi­cích jako před­kova vtable a na­ko­nec při­dává své nové metody. Z toho důvodu je možné volání určité třídní metody pře­lo­žit jako skok na offset v této ta­bulce, který je stejný pro všechny po­tomky určité třídy.

class A {
  def method1 = A1
  def method2 = A2
  def method3 = A3
}

class B extends A {
  override def method2 = B9000
  def method4 = B9001
}
vtable A:
method1 -> A1
method2 -> A2
method3 -> A3

vable B
method1 -> A1
method2 -> B9000
method3 -> A3
method4 -> B9001

I když se může zdát, že volání třídní vir­tu­ální metody jde velice rychlé (konec konců jde jen o pár in­strukcí: skok na adresu, která se na­chází na daném off­setu ve vtable), přesto není ide­ální. Pro­blém spo­čívá po­cho­pi­telně v tom, že cíl skoku není sta­ticky známý a může se měnit za běhu pro­gramu. To může způ­so­bit branch miss-pre­diction (CPU předem neví, kam skočit, nebo skočí špatně, a tak musí počkat)1, ale hlavně to zne­možní in­li­no­vání, což je jedna z nej­dů­le­ži­těj­ších op­ti­ma­li­zač­ních tech­nik, pro­tože ote­vírá dveře dalším op­ti­ma­li­za­cím kódu.

Na­proti tomu volání in­ter­face metody není možné usku­teč­nit jed­no­du­chým skokem na offset, pro­tože li­bo­volná třída může im­ple­men­to­vat li­bo­volný počet in­ter­face a metody těchto in­ter­faců ne­tvoří jednu glo­bální hi­e­rar­chic­kou struk­turu, jako metody tříd. Když volám in­ter­face metodu, v místě volání je známé jen sta­tické jméno daného in­ter­face a in­stance třídy, která ho im­ple­men­tuje. Z in­stance musím zjis­tit o jakou třídu jde a pak ite­ra­tivně projít její itable, najít v ní záznam, kde se na­chází vtable po­ža­do­va­ného in­ter­fece a tam pro­vést už známý skok na offset. Jak je vidět, to obnáší mnohem víc práce než v pří­padě tříd­ních metod. Ale na­štěstí nic z toho není třeba dělat, pokud vir­tu­ální stroj dokáže metodu in­li­no­vat.


JVM (re­spek­tive jeho C2 kom­pi­lá­tor) rutině pro­vádí celou řadu spe­ku­la­tiv­ních op­ti­ma­li­zací. Může udělat class hi­e­rar­chy ana­ly­sis (CHA) a když na­pří­klad vidí, že daná abs­traktní třída má jen jed­noho kon­krét­ního po­tomka (resp. jen jeden je právě na­čtený do JVM), může zcela de­vir­tu­a­li­zo­vat2 a in­li­no­vat všechna vir­tu­ální volání metod této abs­traktní třídy a umož­nit tak další op­ti­ma­li­zace kódu.

JVM nej­prve pro­vádí pro­fi­lo­vání a když zjistí, že na jednom místě (call­site) se volá jen jedna im­ple­men­tace in­ter­face nebo třídní metody, in­li­nuje tělo této metody a před něj vloží jed­no­du­chý guard, který kon­t­ro­luje, zdali in­stance nemá jinou třídu. Když se změní, kód je de­op­ti­ma­li­zo­ván, pro­běhne nové pro­fi­lo­vání a kom­pi­lace s nově zjiš­tě­nými fakty. Stejně JVM na­kládá s pod­mín­kami – pokud se jedna větev během pro­fi­lo­vání vůbec ne­vy­koná, JVM její tělo vůbec ne­zkom­pi­luje, ale místo něho opět vy­ge­ne­ruje jen rychlý guard.

Pokud je call­site bi­morfní (tedy z jed­noho místa v pro­gramu se volá metoda na ob­jek­tech dvou tříd, viz kus kódu níže), JVM in­li­nuje obě možné metody. Tyto dva bloky seřadí tak, že nej­prav­dě­po­dob­nější cesta je ta nej­pří­mější a na tu méně prav­dě­po­dob­nou se musí od­sko­čit (a ta také ob­sa­huje guard pro případ, že se tam do­stane objekt jiné třídy).

abstract class Base {
  def meth
}

class A extends Base {
  def meth
}

class B extends Base {
  def meth
}


val x: Base = getBase()
x.meth // může být A nebo B

Na me­ga­morfní call­site JVM ty­picky ne­stačí. Pokud by in­li­no­vala všechny možné metody (nebo jen sta­tické skoky na tyto metody), pak by byl vý­sledný kód příliš velký. Proto vý­sledný kód volá metody nor­mální cestou jak je po­psáno na za­čátku článku – pomalu a bez mož­nosti dal­ších op­ti­ma­li­zací.

Avšak toto pra­vi­dlo má jednu vý­jimku – pokud je metoda volána na ob­jek­tech jedné třídy velice často (ve více než 90% pří­padů), tak tato metoda je in­li­no­vána, ostatní se volají jako oby­čejné vir­tu­ální/in­ter­face metody.

Alek­sey Shi­pi­lёv ještě zmi­ňuje jeden trik, jak lze určité me­ga­morfní call­site, kde se volá re­la­tivně malý počet metod, trans­for­mo­vat na bi­morfní, se kte­rými si JVM dokáže po­ra­dit, de­vir­tu­a­li­zo­vat, in­li­no­vat a op­ti­ma­li­zo­vat.

abstract class Base {
  def meth
}

class A extends Base {
  def meth = ???
}

class B extends Base {
  def meth = ???
}

class C extends Base {
  def meth = ???
}


val x: Base = getBase()

if (x.isInstanceOf[A]) {
  x.meth // monomorfní callsite
} else {
  x.meth // bimorfní callsite
}

Ale tento trik se počítá mezi za­po­vě­ze­nou černou magii. Jeho fun­go­vání záleží na spe­ci­fic­kém cho­vání spe­ci­fic­kého JITu, které se může kdy­koli v bu­doucnu změnit.


Mezi další per­ličky patří ještě tyto dvě věci:

Vět­šinu kon­t­rol, zdali má pro­měnná hod­notu null, JVM vůbec nedělá. Toto je ošet­řeno v han­dleru CPU vý­jimky SEGV, která je vy­ho­zená při pří­stupu do paměti s ad­re­sou 0.

Do vy­ge­ne­ro­va­ného kódu je nutné přidat chec­kpointy. Ty jsou po­třeba na­pří­klad, když se na­pří­klad změ­nily op­ti­mis­tické před­po­klady a JVM musí de­op­ti­ma­li­zo­vat nějaký kód nebo chce spusit stop-the-world gar­bage collec­tor. Než tyto věci může udělat, musí po­za­sta­vit všechna běžící vlákna a za­par­ko­vat je v bez­peč­ném stavu (na­pří­klad proto, aby ne­vy­ko­ná­valy starý ne­platný kód nebo ne­mě­nily data pod rukama GC). Toho je do­cí­leno jednou in­strukcí, která čte ze stránky paměti, která má na­sta­vena pří­stu­pová práva na READ. Když je třeba pře­ru­šit vlákna, této stránce JVM na­staví pří­stu­pová práva na NONE, ná­sle­du­jící čtení vyvolá trap, předá kon­t­rolu pří­sluš­nému trap han­dleru, který za­par­kuje vlákno.

Kon­t­rola těchto dvou stavů vy­u­žívá page-table, je velice rychlá a ne­zdr­žuje běžící kód.


Dále k tématu:


  1. Branch pre­dictionbranch target pre­diction může v této si­tu­aci pomoci, ale jen pokud mají skoky opa­ku­jící se a před­ví­da­telný vzor.
  2. De­vir­tu­a­li­zace je jen nóbl jméno pro pře­ve­dení vir­tu­ální metody na sta­tic­kou. Sta­tické metody mají mnoho výhod. Jednak před­sta­vují sta­tický cíl a jejich volání je tak pouhý ne­pod­mí­něný skok, který může CPU snadno před­po­vě­dět a ne­u­tr­pět pi­pe­line stall, ale hlavně (jak jsem už psal výše) je možné metody in­li­no­vat, tedy vložit jejich těla na místa odkud se volají, což umožní pro­vést další z celé řady op­ti­ma­li­zací jako pro­pa­gace kon­stant, odro­lo­vání smyček, eli­mi­nace mrt­vého kódu, eli­mi­nace du­pli­cit, loop ho­is­ting, escape ana­ly­sis atd. To je možné proto, že in­li­no­vaný kód má k dis­po­zici přes­nější a bo­hatší kon­text – pro­měnné se mohou ukázat jako kon­stanty, in­te­gery po­chá­zejí jen z ur­či­tého roz­mezí atd.

Na­pří­klad lidé ze Stack Over­flow (který běží na C# a .NET), pre­fe­rují po­u­žití sta­tic­kých metod, pokud je to jen možné: Heavy usage of static clas­ses and me­thods, for sim­pli­city and better per­for­mance. viz Stac­kO­ver­flow Update: 560M Page­views a Month, 25 Ser­vers, and It's All About Per­for­mance

Pro­tože každá metoda v Javě je vir­tu­ální (vyjma final metod), JVM se během let stalo velice dobrým v de­vir­tu­a­li­zaci a spe­ku­la­tivní op­ti­ma­li­zaci metod, ať už pro­střed­nic­tvím pro­fi­lo­vání kódu, CHA nebo jinými pro­středky. Toto je jeden z důvodů proč Java může ge­ne­ro­vat rych­lejší kód než C++. C++ je kom­pi­lo­vané předem a tedy v oka­mžiku kom­pi­lace nemá k dis­po­zici stejné in­for­mace jako JVM JIT za běhu a nemůže tedy vy­ge­ne­ro­vat op­ti­mální kód pro kon­krétní workload, ale musí se spo­ko­jit s ge­ne­ric­kým kódem, který volá vir­tu­ální metody.

Pro úpl­nost by se slu­šelo dodat, že exis­tuje pro­file-guided op­ti­mi­zation, kdy GCC vy­ge­ne­ruje bi­nárku, která ob­sa­huje čítače pro­fi­leru, ta se nechá chvíli běžet na ty­pic­kém pro­blému a na­sbírá sta­tis­tiky za běhu, které se pak po­u­žijí pro vy­ge­ne­ro­vání bi­nárky, která by měla být o něco op­ti­mál­nější a bližší tomu, co by JVM vy­ge­ne­ro­valo za běhu. Pro­blém je v tom, že jde o sta­tické pro­fi­lo­vání a když se změní cha­rak­te­ris­ticky zátěže, pro­gram na to nemůže za­re­a­go­vat, de­op­ti­ma­li­zo­vat se a zkom­pi­lo­vat znovu a lépe. Sám jsem to nikdy ne­po­u­žil a vět­šina mých in­for­mací o PGO po­chá­zejí od Cliffa Clicka, který tvrdí, že PGO se v C++ skoro ne­po­u­žívá, za­tímco JVM ho pro­vádí mi­li­on­krát denně ještě před sní­daní. Místo toho se v C++ vir­tu­ální metody ve vý­kon­nostně kri­tic­kém kódu ne­po­u­ží­vají.

@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články