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

18. 9. 2015

Aleksey Shipilёv v (ne)dávné době napsal velice obsáhlý článek o volání virtuálních metod v JVM: The Black Magic of (Java) Method Dispatch. Do detailů v něm popsal všechny způsoby, jak lze volat virtuální metody, vysvětlil všechny optimalizace, které JIT javovského virtuálního stroje dělá a otestoval jaký mají dopad na výkon.

Jde o velice hutné čtení, které přetéká výpisy x86 assembleru a low-level detaily fungování kompilátorů JVM. Několik z nich pro bylo i pro mě úplnou novinkou. Rozhodl jsem se proto tady shrnout ty nejzajímavější informace.

Java má nejenom tabulku virtuálních metod (vtable), ale také vtable pro každý implementovaný interface (itable). Pokud JVM nedokáže metodu inlinovat, je volání interface metody (bytecode invokeinterface) o něco pomalejší než volání "třídní" metody (bytecode invokevirtual).

Důvod je jasný: Hierarchie tříd v Javě tvoří strom a potomkové mohou metody pouze přidávat nebo přepisovat (ale ne odstraňovat). Potomkova vtable tedy obsahuje všechny zděděné metody na stejných pozicích jako předkova vtable a nakonec přidává své nové metody. Z toho důvodu je možné volání určité třídní metody přeložit jako skok na offset v této tabulce, který je stejný pro všechny potomky 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í virtuální metody jde velice rychlé (konec konců jde jen o pár instrukcí: skok na adresu, která se nachází na daném offsetu ve vtable), přesto není ideální. Problém spočívá pochopitelně v tom, že cíl skoku není staticky známý a může se měnit za běhu programu. To může způsobit branch miss-prediction (CPU předem neví, kam skočit, nebo skočí špatně, a tak musí počkat)¹ , ale hlavně to znemožní inlinování, což je jedna z nejdůležitějších optimalizačních technik, protože otevírá dveře dalším optimalizacím kódu.

Naproti tomu volání interface metody není možné uskutečnit jednoduchým skokem na offset, protože libovolná třída může implementovat libovolný počet interface a metody těchto interfaců netvoří jednu globální hierarchickou strukturu, jako metody tříd. Když volám interface metodu, v místě volání je známé jen statické jméno daného interface a instance třídy, která ho implementuje. Z instance musím zjistit o jakou třídu jde a pak iterativně projít její itable, najít v ní záznam, kde se nachází vtable požadovaného interfece a tam provést už známý skok na offset. Jak je vidět, to obnáší mnohem víc práce než v případě třídních metod. Ale naštěstí nic z toho není třeba dělat, pokud virtuální stroj dokáže metodu inlinovat.

JVM (respektive jeho C2 kompilátor) rutině provádí celou řadu spekulativních optimalizací. Může udělat class hierarchy analysis (CHA) a když například vidí, že daná abstraktní třída má jen jednoho konkrétního potomka (resp. jen jeden je právě načtený do JVM), může zcela devirtualizovat² a inlinovat všechna virtuální volání metod této abstraktní třídy a umožnit tak další optimalizace kódu.

JVM nejprve provádí profilování a když zjistí, že na jednom místě (callsite) se volá jen jedna implementace interface nebo třídní metody, inlinuje tělo této metody a před něj vloží jednoduchý guard, který kontroluje, zdali instance nemá jinou třídu. Když se změní, kód je deoptimalizován, proběhne nové profilování a kompilace s nově zjištěnými fakty. Stejně JVM nakládá s podmínkami - pokud se jedna větev během profilování vůbec nevykoná, JVM její tělo vůbec nezkompiluje, ale místo něho opět vygeneruje jen rychlý guard.

Pokud je callsite bimorfní (tedy z jednoho místa v programu se volá metoda na objektech dvou tříd, viz kus kódu níže), JVM inlinuje obě možné metody. Tyto dva bloky seřadí tak, že nejpravděpodobnější cesta je ta nejpřímější a na tu méně pravděpodobnou se musí odskočit (a ta také obsahuje guard pro případ, že se tam dostane 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 megamorfní callsite JVM typicky nestačí. Pokud by inlinovala všechny možné metody (nebo jen statické skoky na tyto metody), pak by byl výsledný kód příliš velký. Proto výsledný kód volá metody normální cestou jak je popsáno na začátku článku - pomalu a bez možnosti dalších optimalizací.

Avšak toto pravidlo má jednu výjimku - pokud je metoda volána na objektech jedné třídy velice často (ve více než 90% případů), tak tato metoda je inlinována, ostatní se volají jako obyčejné virtuální/interface metody.

Aleksey Shipilёv ještě zmiňuje jeden trik, jak lze určité megamorfní callsite, kde se volá relativně malý počet metod, transformovat na bimorfní, se kterými si JVM dokáže poradit, devirtualizovat, inlinovat a optimalizovat.

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 zapovězenou černou magii. Jeho fungování záleží na specifickém chování specifického JITu, které se může kdykoli v budoucnu změnit.

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

Většinu kontrol, zdali má proměnná hodnotu null, JVM vůbec nedělá. Toto je ošetřeno v handleru CPU výjimky SEGV, která je vyhozená při přístupu do paměti s adresou 0.

Do vygenerovaného kódu je nutné přidat checkpointy. Ty jsou potřeba například, když se například změnily optimistické předpoklady a JVM musí deoptimalizovat nějaký kód nebo chce spusit stop-the-world garbage collector. Než tyto věci může udělat, musí pozastavit všechna běžící vlákna a zaparkovat je v bezpečném stavu (například proto, aby nevykonávaly starý neplatný kód nebo neměnily data pod rukama GC). Toho je docíleno jednou instrukcí, která čte ze stránky paměti, která má nastavena přístupová práva na READ. Když je třeba přerušit vlákna, této stránce JVM nastaví přístupová práva na NONE, následující čtení vyvolá trap, předá kontrolu příslušnému trap handleru, který zaparkuje vlákno.

Kontrola těchto dvou stavů využívá page-table, je velice rychlá a nezdržuje běžící kód.

Dále k tématu:

JVM Internals
Inline cache
The JVM Backend and Optimizer in Scala 2.12 - V druhé polovině se mluví o tom co JIT dokáže a co nedokáže a co se optimalizátor Scaly snaží dělat, aby mu nadeběhl.
Zero-Overhead Metaprogramming - Rozšíření polymorphic inline cache na obecné dispatch chains, které dokáží nejen eliminovat režii virtuální metody, ale i komplikovanější věci, jako reflexivní metody nebo metaobjektové protokoly.
Virtually free - JVM callsite optimization by example
Devirtualization

Branch prediction a branch target prediction může v této situaci pomoci, ale jen pokud mají skoky opakující se a předvídatelný vzor.
Devirtualizace je jen nóbl jméno pro převedení virtuální metody na statickou. Statické metody mají mnoho výhod. Jednak představují statický cíl a jejich volání je tak pouhý nepodmíněný skok, který může CPU snadno předpovědět a neutrpět pipeline stall, ale hlavně (jak jsem už psal výše) je možné metody inlinovat, tedy vložit jejich těla na místa odkud se volají, což umožní provést další z celé řady optimalizací jako propagace konstant, odrolování smyček, eliminace mrtvého kódu, eliminace duplicit, loop hoisting, escape analysis atd. To je možné proto, že inlinovaný kód má k dispozici přesnější a bohatší kontext - proměnné se mohou ukázat jako konstanty, integery pocházejí jen z určitého rozmezí atd.
Například lidé ze Stack Overflow (který běží na C# a .NET), preferují použití statických metod, pokud je to jen možné: Heavy usage of static classes and methods, for simplicity and better performance. viz StackOverflow Update: 560M Pageviews a Month, 25 Servers, and It's All About Performance
Protože každá metoda v Javě je virtuální (vyjma final metod), JVM se během let stalo velice dobrým v devirtualizaci a spekulativní optimalizaci metod, ať už prostřednictvím profilování kódu, CHA nebo jinými prostředky. Toto je jeden z důvodů proč Java může generovat rychlejší kód než C++. C++ je kompilované předem a tedy v okamžiku kompilace nemá k dispozici stejné informace jako JVM JIT za běhu a nemůže tedy vygenerovat optimální kód pro konkrétní workload, ale musí se spokojit s generickým kódem, který volá virtuální metody.
Pro úplnost by se slušelo dodat, že existuje profile-guided optimization, kdy GCC vygeneruje binárku, která obsahuje čítače profileru, ta se nechá chvíli běžet na typickém problému a nasbírá statistiky za běhu, které se pak použijí pro vygenerování binárky, která by měla být o něco optimálnější a bližší tomu, co by JVM vygenerovalo za běhu. Problém je v tom, že jde o statické profilování a když se změní charakteristicky zátěže, program na to nemůže zareagovat, deoptimalizovat se a zkompilovat znovu a lépe. Sám jsem to nikdy nepoužil a většina mých informací o PGO pocházejí od Cliffa Clicka, který tvrdí, že PGO se v C++ skoro nepoužívá, zatímco JVM ho provádí milionkrát denně ještě před snídaní. Místo toho se v C++ virtuální metody ve výkonnostně kritickém kódu nepoužívají.