Bez typů se obejdeme, ale…

Však to znáte, něco tweetnete a jedna odpověď vás donutí napsat celý článek jako vysvětlení, co je tím vlastně myšleno.

Dneska to byla tato perla nevšední krásy (odsud):

Without soundness, types can merely be used as optimisation hints, but the generated code would still need to be able to back out.

Na první pohled tato věta může vypadat jen jako další nevýznamný příspěvek do debaty mezi příznivci staticky a dynamicky typovaných jazyků (které jsou téměř výhradně vedeny diletanty, mě nevyjímaje). Ve skutečnosti jde o hluboký princip. Když má jazyk nekorektní typový systém, typy představují jen nástin toho, co se bude s největší pravděpodobností dít, ale virtuální stroj musí být připraven na eventualitu, že věci nepůjdou podle plánu.

Jako příklad uvedu legendární vadu typového systému javy, ve kterém jsou pole kovariantní. Kovariance znamená, že jestliže B je potomek A, tak B[] je potomek A[].

class Animal {}
class Pony extends Animal {}

Pony[] ponies = { new Pony() };
Animal[] animals = ponies; // kovariance zafunguje zde

animals[0] = new Animal(); // tohle skončí výjimkou ArrayStoreException

O co jde. Na začátku jsem vytvořil pole poníků a pak ho přiřadil do proměnné typu pole zvířat a kovariance polí to povolila. Teď, když se do pole, na které ukazuje proměnná typu Animal[], snažím přiřadit objekt typu Animal (což je naprosto korektní operace), vyskočí na mě výjimka ArrayStoreException. Za běhu. A kompilátor neřekl ani popel, protože kovariance polí není korektní.

A co je na celé věci nejhorší: Za ta tuhle podivnost z dávnověku, kdy java neměla ani generika 1, všichni do dneška platíme. Protože tohle může nastat, virtuální stroj musí při každém vložení do pole provádět typecheck jestli typ elementu je podtypem přípustné třídy. Kdyby typový sytém neobsahoval tuto úchylku a pole by byla invariantní, runtime by měl naprostou jistotu a nemusel byl pokaždé dělat zbytečný typecheck3.

Virtuální stroj může v některých situacích nutnost této kontroly odstranit. Například pokud jde o pole objektů nějaké finální třídy nebo objektů třídy (nebo interface), která nemá potomky nebo je má, ale zatím nejsou natažené do JVM, někdy může být typecheck vytažen před smyčku a tak dále.

Jazyk s nekorektním typovým systémem může běžet rychle, jak je například vidět na všech moderních implementacích JavaScriptu. Toho je však dosaženo divokými a agresivními spekulacemi, které virtuální stroj provádí. Sází na to, že všechno poběží jako minule, že se typy stabilizují a specializuje kód pro to, co vypozoroval. Ale stále musí počítat s tím, že jeho předpoklady byly špatné nebo že se situace najednou změní. Typický guard, který hlídá předpoklady, je tvořen pár instrukcemi – kontrola typu a jeden podmíněný skok na místo, které si s problémem poradí, deoptimalizuje kód, přepne se do interpretru a začne znova.

Jestliže typový systém je korektní dá mi naprostou a nevyvratitelnou garanci toho, že určité stavy za žádných okolností nemůžou nastat a virtuální stroj a JIT s nimi nemusí vůbec ztrácet čas. To může vést k jednoduššímu VM, rychlejšímu kódu nebo rychlejší kompilaci, která je pro jazyky jako JavaScript velice důležitá, protože compile-time je run-time.

To však neznamená, že VM nebude spekulovat. Například takové JVM ve fázi profilování sleduje všechny callsite a když zjistí, že se z jednoho místa volají jen metody jedné třídy, místo zcela validního virtuálního volání metody optimisticky inlinuje tělo metody (pokud je malá) a před ní vloží guard, který se postará o situaci, kdy se na daný callsite dostane objekt jiné třídy.


Další věc, která internetem zní jako ozvěna, je tvrzení, že typy nejsou potřeba k rychlému programu, že je to jen a pouze dokumentace pro programátora. S druhou polovinou souhlasím, typy jsou formalizací myšlenek a předpokladů toho, co kód má dělat a na jakých datech. Ale s první částí tvrzení naprosto nesouhlasím a dolovím si tvrdit, že pravý opak je pravdou: Typy jsou zcela nepostradatelné pro rychlý běh programu. Háček je jenom v tom jaké typy. Protože, když říkám, že typy jsou nutné, nemyslím tím ty viditelné v kódu, ani ty, které odvodí Hindley–Milner, ale ty se kterými bude runtime pracovat.

Co dělá každý JavaScriptový virtuální stroj? Snaží se za běhu objevit takzvané skryté třídy (hidden class), které mají nějaký tvar, počet atributů nějakého druhu – tedy typy. Když jsou tyto typy známé, JIT může generovat mnohem rychlejší kód, protože nepracuje s horou hash tabulek, ale s bloky paměti, které mají jasně danou strukturu2.

Tohle předpokládá, že nějakou strukturu je možné objevit. Naštěstí to většinou platí, protože i když kód neobsahuje typové anotace a kompilátor nevynucuje korektnost, programy mají určitou implicitní strukturu – objekty předané jako argumenty nějaké funkci skoro vždycky vypadají velice podobně atd.

Pro rychlý běh tedy není tolik důležité jestli je jazyk staticky nebo dynamicky typovaný, ale jestli má statickou nebo dynamickou strukturu.


Pozn:

  1. Právě chybějící generika v prvních verzích javy mohou za toto kriminální chování. Stejnou vadou trpí i C#.
  2. Například: Když první verze virtuální stroje HHVM, vykonávaly kód napsaný v Hacku, což je ve své podstatě PHP s korektním(!) typovým systémem, tak všechny staticky známé typy zahodily a začaly dynamicky typy objevovat a specializovat kód.
  3. Další poněkud více esoterický příklad: Java kontroluje, jestli se index ke kterému přistupuji, nachází v poli a když je mimo, vyhodí ArrayIndexOutOfBoundsException. V dependetly typed jazycích může být délka pole obsažena v typu pole a v takovém případě je možné se zbavit těchto kontrol, protože typový systém garantuje, že nedojde ke čtení mimo pole.

Dále k tématu:

Flattr this!

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

Leave a Reply

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