Generování kódu za běhu (ve Scale)

Někdy je zkrátka potřeba dynamicky generovat kód.

Důvodů pro to může být mnoha: Například můžu mít nějakou formu externího doménového jazyka (DSL), který musí běžet rychle, nebo musí být staticky integrován do zbytku programu bez použití reflexe1, nebo chci provést nějakou instrumentaci nebo statickou analýzu existujícího kódu. V některých případech to může být zbytečné, ale jindy je dynamické generování kódu ta správná věc.

A když říkám dynamické generování kódu, nemyslím během kompilace pomocí klasických maker, ale za běhu, na základě nějakých data, které v době kompilace nejsou a nemohou být známé. Pokud nemluvíme o makrech céčkovského typu, je mezi statickým a dynamickým generováním kódu jen pramalý rozdíl. Oba potřebují kompilátor a program, který vygeneruje jiný program a pak ho nechá zkompilovat.

A jak se tohle dělá ve Scale ukážu právě teď.


Jako příklad budu používat AST reprezentující jednoduché aritmetické výrazy.

sealed trait Expr

case class Const(value: Int) extends Expr
case class Plus(x: Expr, y: Expr) extends Expr
case class Minus(x: Expr, y: Expr) extends Expr
case class Times(x: Expr, y: Expr) extends Expr

V něm můžu zapsat například výraz

val ast = Times(
  Plus(Const(1), Const(2)),
  Minus(Const(3), Const(4))
)

který reprezentuje (1 + 2) * (3 - 4).

Za povšimnutí stojí fakt, že AST reprezentuje program a když chci zjistit jeho hodnotu, musím tento program vykonat. Na to budu potřebovat interpreter, který rekurzivně prochází AST a vyhodnocuje onen program.

def evalExpr(e: Expr): Int = e match {
  case Const(x)    => x
  case Plus(x, y)  => evalExpr(x) + evalExpr(y)
  case Minus(x, y) => evalExpr(x) - evalExpr(y)
  case Times(x, y) => evalExpr(x) * evalExpr(y)
}

Výsledkem volání evalExpr(ast) je pak pochopitelně –3.

Kdybych chtěl, aby můj malý programovací jazyk uměl víc věcí, musel bych přidat další druhy AST uzlů, které by reprezentovaly nové operace nebo koncepty jako podmínky, smyčky nebo proměnné (aby tyto fungovaly, bylo by třeba změnit interpreter, aby jako další parametr bral mapování mezi proměnnými a jejich hodnotami).

Tento přístup funguje, ale interpretace má nezanedbatelnou režii. Program popisuje primitivní operace, které odpovídají jedné procesorové instrukci, ale na to aby ji interpreter vykonal musí procházet stromovou strukturu. volat metody a provádět pattern matching ve funkci evalExpr2.

Když ale program zkompiluji do nějaké nativnější formy (ať už nativního kódu nebo bytekódu, který je vzápětí přeložen JITem virtuálního stroje), zbavím se této režie a program může běžet znatelně rychleji.

V poslední verzi Scaly 2.11 se ke kompilaci dají použít takzvané quasiquotes a ToolBox API.

Nejprve musím importovat pár záludností.

import scala.reflect.runtime.currentMirror
import scala.tools.reflect.ToolBox
val toolbox = currentMirror.mkToolBox()
import toolbox.u._
import toolbox.{ u => universe }

A pak vytvořím metodu, která každou variantu Expr převede na odpovídající fragment kódu.

def compileExpr(e: Expr): universe.Tree = e match {
  case Const(x)    => q"$x"
  case Plus(x, y)  => q"${compileExpr(x)} + ${compileExpr(y)}"
  case Minus(x, y) => q"${compileExpr(x)} - ${compileExpr(y)}"
  case Times(x, y) => q"${compileExpr(x)} * ${compileExpr(y)}"
}

Kód pro kompilaci vypadá skoro stejně, jako kód pro interpretaci3. Jediný rozdíl je v tom, že zatímco program interpreteru se přímo vykoná, program kompilátoru – obalený interpolátorem q"..." se převede na kód. To co vypadá jako interpolace stringů ve skutečnosti nepracuje s textovou reprezentací programu, ale s AST, které Scala kompilátor interně používá k reprezentaci kódu. Obsah q"..." (q jako quasiquotes) je přeložen na potomky universe.Tree a na místa označená ${...} se rekurzivně vloží další kusy AST. A protože nejde o textové šablony, dá se s tím dělat mnohem víc věcí, které jsou popsány v dokumentaci quasiquotes a maker.

compileExpr ale neprovede kompilaci, jen připraví AST, se kterými si umí Scala kompilátor poradit. Ale předtím je ještě nutné výraz zabalit do funkce, kterou bude možné volat.

val qq = q"""
  () => {
    println("running function that was compiled during runtime")
    ${compileExpr(ast)}
  }
"""

Můžu si nechat vypsat, jak by asi vypadal zkompilovaný kód:

println(showCode(qq))

To ukáže něco jako:

(() => (1).+(2).*((3).-(4)))

Samotnou kompilaci pak provedu takto:

val f = toolbox.compile(qq)().asInstanceOf[() => Int]

A teď už mám funkci typu Unit => Int, kterou můžu volat jako jakoukoli jinou funkci.

f() // vypíše hlášku a vrátí -3

f obsahuje jen kód samotného výpočtu bez režie interpretace. A protože jde o jednoduchý bytecode, může být JITem dále optimalizován. I v případě interpreteru mi může JIT trochu pomoct spekulativními optimalizacemi, ale rozhodně nemůže aplikovat celou řadu triků a heuristik a metod, kterými se kompilátory naučily vylepšovat jednoduchý kód bez zbytečných abstrakcí a komplikací5.

Lispeři se teď musí smát, protože se ve Scale objevilo něco, co oni mají už od šedesátých let. Lispeři se však zbytku světa smějí tak jako tak a proto je můžeme ignorovat.


Já se o tyto techniky začal zajímat po jednom obzvláště neklidném snu, kdy jsem se rozhodl naprogramovat hrubý prototyp sloupcové databáze později pojmenované DilettanteDB. V mých testech se ukázalo, že zkompilovaný kód může být 30× rychlejší než naïvní interpretace. Výsledek dokáže skenovat data 10GB/s a vykonává pouhých 1.7 instrukcí za takt a i v jednom vláknu je omezený jen propustností pamětí. To je téměř ideální stav.4 Stejnou techniku ke kompilování SQL dotazů používá optimalizátor Catalyst ze Sparku.

Jediný problém na který jsem narazil byla pomalá kompilace. Scala kompilátor není ani rychlý ani kompaktní a proto, když ho chci na něco použít, musím ho načíst, nechat ho rozhýbat a to nějakou dobu trvá. První kompilace jedné funkce o padesáti řádcích trvala 3 vteřiny. Další už byly rychlejší, ale zdaleka ne tak rychlé, jak by se mi líbilo.


Když už jsem v tom, slušelo by se zmínit projekt Scala.meta, který se snaží vylepšit metaprogramování ve Scale, které má pořád svoje nedostatky. Jeden z nich je například fakt, že Scala kompilátor nezachovává nepotřebné informace jako je formátování nebo syntaktické konstrukce, které použil programátor (ale jejich jednodušší formy) a proto se nehodí pro určitou kategorii nástrojů.


Dále k tématu:


  1. I když jak se ukazuje, tak režii reflexe a metaobjektových protokolů je možné vhodnými technikami téměř zcela odstranit. Viz Zero-Overhead Metaprogramming Reflection and Metaobject Protocols Fast and without Compromises
  2. Pattern matching je možné pochopitelně nahradit metodou eval na třídě Expr. Virtuální volání někdy může být rychlejší než pattern matching, jindy pomalejší. Záleží na detailech a jak se s nimi popere just-in-time kompilátor.
  3. To není úplná náhoda, protože jak Erik Meijer ukazuje ve své poněkud vulgární přednášce The Lost Art of Denotational Semantics, interpreter je možné automaticky převést na kompilátor. Jako další příklad může posloužit pythonovský projekt PyPy, který vytváří tracing JIT kompilátory z interpreterů. PyPy zaznamenává trace akcí interpreteru a výslednou sekvenci instrukcí a operací pak optimalizuje až na binární kód. V PyPy je například napsána implementace PHP HippyVM nebo kompilátor lispovského Racketu.
  4. V takové situaci se dá zrychlit už jedině komprimací dat, jako to třeba dělá například 0×data H₂0. Viz In-Memory Processing, 0×data H20, Efficient Low Latency Java and GCs a An API for Distributed Computing.
  5. Viz poznámky pod Jak JVM volá virtuální metody a jaká temná božstva při tom uctívá. Kompilátor/JIT se jako první snaží zbavit abstrakcí, aby odhalil jádro kódu, které je možné jednoduše optimalizovat.

Flattr this!

Posted in Scala | 1 Comment

Pár poznámek k pár poznámkám o sloupcových databázích

Teorie je jednoduchá: Sloupcové databáze jsou takové, které ukládají data po sloupcích místo po řádcích, jak je v databázovém světě běžné.

To má několik zásadních výhod, které jsou v určitých situacích k nezaplacení. Když potřebuji přistoupit jen k několika málo sloupcům, načtu pouze jejich data a nemusím se obtěžovat s jinými položkami ze stejného řádku. V řádkových databázích je vždycky nutné načíst celý řádek, protože data se z disků načítají po blocích, které obsahují mnoho řádků najednou. Nemůžu si vynutit, aby mi disk poskytl jen bajty z těch pár sloupců, které mě zajímají. Dostanu všechno nebo nic. Naproti tomu ve sloupcové DB je každý sloupec uložen jako souvislý region dat. Jeden diskový blok tedy obsahuje jen a pouze data jednoho sloupce. V nejjednodušší podobě jde o velké pole (jehož prvky mají často fixní délku) pro každý sloupec (jako v případě MonetDB) nebo o sérii kratších segmentů (jako v X100).

Takovéto uspořádání dat se hodí pro OLAP, tedy když mě místo jednotlivých záznamů zajímají agregace jednoho nebo několika málo sloupců (např. tabulka jich má 50, ale v dotazu se dva vyskytují v podmínce a z několika dalších se počítají průměry). Protože jde koncepčně o pole, nalezení odpovídajících položek v různých sloupcích je triviální: jde o pouhý index * velikost položky a dotaz se dá přeložit do série jednoduchých a velice efektivních smyček.5

Sloupcové databáze jsou krásné (jak je vidět v The Design and Implementation of Modern Column-Oriented Database Systems), ale přesto o nich dneska nechci psát.

Nedávno jsem si přečetl článek Několik poznámek ke sloupcovým databázím, který ve mě zanechal příjemný hřejivý pocit, hlavně proto, že se zmiňoval o hardwaru, SIMD instrukcích a efektivitě práce s in-memory daty. Tam někde mě napadlo vyzkoušet, jak rychle taková teoretická in-memory databáze může běžet. Když z rovnice vypadnou všechny rotující disky, SSD nebo síťové karty, záleží jen na pamětech a procesoru. Z komplikovaného systému se stane něco triviálního, co je možné prozkoumat a pochopit. Například jaký vliv má komprese, SIMD operace, instrukce gather (která načte několik procesorových slov najedou, potenciálně paralelně), prefetch (která signalizuje procesoru, jaká data budou brzo potřeba)2 nebo non-temporal load4?

Ale tak daleko jsem se nedostal. Protože jak to vypadá na tom zas tak moc nezáleží, limitujícím faktorem je hlavně propustnost pamětí.

Napsal jsem triviální test, který definoval struct row s několika osmibajtovými položkami.

struct row {
        long a,b,c,d,e,f,g,h;
        long i,j,k,l,m,n,o,p;
};

Pak jsem vytvořil veliký špalek dat, který se vešel do paměti.

struct row *rows = malloc(sizeof(struct row) * 50000000);

for (int i = 0; i < 50000000; i++) {
        rows[i].a = 1;
}

Nakonec jsem jím proletěl během jedné krásné iterace.

for (int i = 0; i < 50000000; i++) {
        sum += rows[i].a;
}

Zaznamenával jsem výsledky s různým počtem položek ve structu row. V prvním řádku má row položky od a do p (dohromady 128 bajtů), v posledním obsahuje jen jedinou položku (8 bajtů). Výsledky byly celkem překvapivé.

longs bytes time throughput
16 128 B 320 ms ~
8 64 B 227 ms 13.1 GB/s
4 32 B 112 ms 13.3 GB/s
2 16 B 55 ms 13.5 GB/s
1 8 B 33 ms 11.3 GB/s

Jak je vidět, že i když sčítám jen hodnoty prvního atributu, rychlost klesá plus/mínus lineárně s přibývajícím počtem položek v řádku. Procesor totiž z paměti nenačítá data po 64-bitových slovech, ale po cache line, které mají 64 bajtů. Musí tedy z RAM vydolovat celých 64 bajtů, i když z nich využije jen jednu osminu a to věci značně zpomalí.

Dále je vidět, že rychlost je limitovaná propustností pamětí. V mém desktopu jsou dva 1333MHz DDR3 moduly, které by podle tabulek měly dokázat protlačit 2×10.6 GB za vteřinu. Jedno jádro běžící na plné otáčky dokáže rozpoutat takové peklo, že sežere většinu tohoto objemu. Kdybych použil všechna čtyři jádra, program by byl limitován propustností pamětí a běžel by v nejlepším případě ~2× rychleji. Hyperthreading by v tomto případě nepřinesl žádné zrychlení.

Z toho vyplývá, že v této situaci komplikované gather/prefetch instrukce nemají moc velký význam. Program ve všech případech běží s nízkým IPC (lehce nad 1 instrukci na takt pro velké row structy, skoro 1.2 pro row s jednou položkou). gather může načíst několik míst paměti, ale stejně jako normální load musí načítat celé cache line. Může tak skrýt latence, ale když je hlavním nepřítelem paměťová propustnost, nemá žádný pozitivní dopad.

Toto zjištění jen dále potvrzuje výhody sloupcových databází: I když se všechna data nacházízcela v paměti, je čtení po sloupcích rychlejší než po řádcích. V nejhorším případě, kdy mě zajímají všechny sloupce, bude stejně rychlé, jako čtení po řádcích. Podobná situace platí v případě diskových bloků1.

Propustnost je natolik limitující, že když mám struct row s 8 atributy

struct row {
        long a,b,c,d,e,f,g,h; // 64 bajtů
};

tak tato smyčka

for (int i = 0; i < N; i++) {
        sums[0] += rows[i].a;
}

běží stejně rychle jako tato

for (int i = 0; i < N; i++) {
        sums[0] += rows[i].a;
        sums[1] += rows[i].b;
        sums[2] += rows[i].c;
        sums[3] += rows[i].d;
        sums[4] += rows[i].e;
        sums[5] += rows[i].f;
        sums[6] += rows[i].g;
        sums[7] += rows[i].h;
}

Při 10GB/s nová cache-line dorazí každých 6.4 ns, což při 3 GHz odpovídá skoro 20 taktům a to stačí na vykonání všech movů, addů a instrukcí smyčky s rozumným ILP.6

MonetDB je na tom ještě hůř, protože v jednom okamžiku zpracovává jeden operátor. Musí tedy číst jeden nebo více sloupců a výsledná data, která budou použita v dalších operátorech, zapisovat do paměti. A k tomu si je nutné připočítat fakt, že některé sloupce můžou být zpracovávány několika různými operátory. Ve výsledku je tedy Monet propustností limitován mnohem více.

Logickým řešením (jak to dělají některé novější a rafinovanější, viz) je rozlámat sloupec na menší bloky, které se vejdou do nějaké úrovně cache (L1 nebo L2) a provést všechny operace na nich a pak se posunout na další blok. Jde tedy o jakýsi hybrid mezi zpracováváním po celých řádcích a po celých sloupcích. Když se dočasné výsledky vejdou do procesorových cache, není je třeba streamovat do hlavní paměti a propustnost paměti přestane představovat takový problém. CPU dokáže z cache tahat data mnohem větší rychlostí. V případě Haswellu to je 64 bajtů každý takt – tedy něco jako 192 GB/s pro každé jádro. A tady přijde ke slovu rychlý kód, SIMD instrukce a mikro-optimalizace, nebo jen jednoduché gcc -O3 -mavx2 -funroll-loops.

S tímhle vším na mysli jsem v jednom nestřeženém okamžiku zkusmo napsal DilettanteDB – program, který dotazy na nějakou hypotetickou sloupcovou databázi přeloží do javovského bytekódu. Výsledkem je jednoduchá smyčka, ktera v jedné iteraci proletí databázi, čte data plnou rychlostí 10GB/s a spočítá všechny požadované agregace. Najednou nevyhodnocuje jeden operátor, ale všechny.


Dále k tématu:


  1. Tady se sluší krátce zmínit o takzvaných cache-oblivious algoritmech, které berou v potaz, že data data jsou přístupná jen v blocích větších než jedno procesorové slovo, a chovají se optimálně, i když neznají velikost těchto bloků. Viz např. tohle nebo tohle nebo toto nebo tohleto.
  2. Jak se ukazuje, tak softwarový prefetch často nemá žádný pozitivní dopad (ale ani neublíží), protože hardwarový prefetch dělá svoji práci velice dobře.
  3. Program neužije celou přenosovou kapacitu obou modulů nejspíš kvůli tomu, jak je fyzická paměť mapována na jednotlivé moduly. Hlavní paměť používá high-order interleaving, kdy je fyzická paměť rozdělena na velké spojité kusy, které jsou rozděleny na paměťové banky. Když tedy čtu sekvenčně z paměti, čtu z jednoho paměťového modulu a dvojitou kapacita nemůžu využít. GPU naproti tomu mají low-order interleaving, kdy je jedno slovo namapované na modul 0, další na modul 1, další na modul 2 a tak dále dokola. To se hodí pro GPU model výpočtů, který je optimalizovaný pro vysoký paralelismus a průtok. Viz první kapitoly Programming on Parallel Machines – GPU, Multicore, Clusters and More (Aktualizace: Rozložením paměti na PC si nejsem tak jistý, viz: tento článek, který říká, že dual-channel paměti se netváří jako dvě 64-bitová zařízení, ale jako jedno 128 bitové a to znamená, že tam jde o low-order interleaving.)
  4. Jak se ukazuje, tak s non-temporal instrukcemi to není tak jednoduché a v tomto případě vůbec nemusejí pomoci, protože stejně načítají celou cache line.
  5. Tak je například implementován MonetDB. Každý operátor (porovnání, join, podmínka, atd) odpovídá jednomu předkompilovanému fragmentu v C. Tím se eliminuje režie interpreteru, který je v typické databázi volán nad každým sloupcem.
  6. A co je nejhorší, když paměť nesíhá dodávat data, v perfu se to ukáže jako obyčejný cache-miss, bez indikace, co ho způsobilo.

Flattr this!

Posted in CPU, DB, Paměť | Leave a comment

L1I cache a iTLB – když ani spekulace nepomůžou

Před několika dny Jan Smitka na twitter postnul výsledky benchmarků PHP7 a HHVM. Výsledek ukazuje, že PHP7 se rychlostí blíží HHVM a někdy ho i překonává. To je poněkud nečekané, protože, i když bylo PHP7 značně vylepšené a zrychlené, HHVM má plnohodnotný JIT kompilátor, který by měl vyhrát na celé čáře.

V benchmarcích byly také výsledky perfu a po chvíli zírání do stěny čísel jsem našel to, co by mohlo vysvětlovat, proč je HHVM pomalejší, než by člověk očekával: L1-icache-load-misses a iTLB-load-misses.

Abych vysvětlil proč jsou tyto dva čítače tak důležité, musím to vzít oklikou přes nejdůležitější část procesorů: cache.


Jak všichni jistě vědí, cache je malá a rychlá paměť, která se nachází na křemíkové placce procesoru a cachuje aktivní data. L1 cache může mít pro představu 32KB a latenci 3 takty. RAM naproti tomu může mít něco kolem terabajtu, ale data z ní putují se zpožděním až ٍٍ±300 taktů. Právě cache tvořící hierarchii o několika úrovních (L1 – prťavá & rychlá, L3 velká & pomalá1) v ideálním případě2 vytvoří iluzi, že paměť je nejenom velká ale také rychlá.3

Cache je zcela zásadní, protože rozdíl mezi čtením z registru a RAM je obrovský. Kdyby paměť dokázala dodat data v jednom taktu, cachování by nebylo třeba. V prehistorických dobách tomu tak bylo, ale rychlost CPU rostla rychleji než rychlost pamětí a to vedlo k uvedení cache – nejprve instrukční cache, pak datové, pak dalších úrovní a prefetch aparátu a dynamických spekulací. V tomto ohledu se nezasvěceným může zdát, že se procesory chovají podivně, ale není to proto, že to někomu připadalo jako dobrý nápad, ale proto, že to bylo nezbytné4.

A teď, co se stane, když data nejsou v L1 cache? Procesor zkontroluje L2, pak L3 a když neuspěje ani tam, jde rovnou do paměti a zaplatí za to pár desítkami nanosekund. Naštěstí moderní CPU jsou out-of-order superskalární bestie s SMT/Hyperthre­adingem při ruce, takže i když musí čekat na jeden load, v pipeline má připravené další instrukce, které můžou běžet nezávisle na probíhajícím čtení z paměti. Když bude mít veliké štěstí, podaří se mu vyplnit celou prodlevu užitečnou prací, nebo aspoň narazí na pár dalších load operací, které můžou čekat paralelně.

To není zas tak strašné.

Situace však může být o něco horší, když se do věci začne míchat virtuální paměť a mapování stránek. Program běží v procesu, který nepřistupuje k fyzické paměti (tu vidí je kernel operačního systém), ale k pouhé abstrakci – virtuální paměti. Ta poskytuje iluzi, že proces má pro sebe celý 32bitový nebo 64bitový adresní prostor, který je zcela oddělený od paměti jiných procesů. Aby to fungovalo svižně je potřeba adresy překládat za pomoci TLB (translation lookaside buffer) – maličkého kusu hardwaru, který pro aktuálně bežící proces cachuje mapování virtuálních stránek na fyzické.

Vždycky když chci načíst nějaký kus dat z paměti nebo cache, musím nejprve nechat TLB přeložit virtuální adresu na fyzickou a pak teprve najít, kde daný kus dat sídlí. V důsledku toho musí být TLB velice rychlá, což znamená, že žere hodně proudu a nemůže být moc velká.5,6

Co nastane, když kus paměti, který chci číst, leží ve stránce, jejíž mapování není v TLB? Nejen že musím čekat na samotná data než dorazí z RAM, ale předtím musím čekat než přečtu tabulku stránek (page table) a najdu v ní mapování požadované virtuální adresy. Tabulka stránek se nachází v paměti a má několik úrovní. Počet cest do paměti najednou nepříjemně roste a s nimi i latence. Avšak pořád je možné dělat několik takových čtení najednou.

Ale může být ještě hůř.

První cache byly instrukční, teprve po nich přibyly datové cache, pak další sdílené úrovně a pak ještě rychlejší instrukční cache. Jmenovitě L0 cache, která obsahuje instrukce dekódované na mikrooperace (šetří se tak práce dekodéru) a loop buffer, který obsahuje několik málo dekódovaných instrukcí horké smyčky.

Jak je vidět, instrukční cache má mnohem víc úrovní a to má velice dobrý důvod: Když data nejsou v cache, procesor může dělat něco jiného, může vykonávat jiné nezávislé operace, ale když nemá k dispozici následující instrukce, nemůže dělat vůbec nic, jen čekat7.

Teď si k tomu připočtěte situaci, kdy následující instrukce nejen že nejsou v cache, ale nachází se na stránce paměti, která není v TLB. Procesor musí nejdříve naplnit TLB a pak teprve hrábnout do paměti. Po celou tuhle dobu nemůže dělat vůbec nic.

A právě tuto situaci popisují události L1-icache-load-misses a iTLB-load-misses – L1 instrukční cache neobsahuje potřebný kus binárky a požadovaná stránka s binárkou není v instrukční TLB – jde o ty nejhorší možné situace, které můžou nastat. Čekáme, než nám šéf zavolá, co máme dělat.

perf ukazuje, že HHVM vyvolává nadměrně mnoho těchto dvou událostí a já se domnívám, že tohle má značný vliv na srovnání s PHP7.

Otázka zní: Proč?

Podle mých informací HHVM používá tracing JIT na úrovni základních bloků:

HHVM’s JIT uses a trace-based form of compilation that limits each trace to a single basic block where the input types are known at translation time (the „tracelet“ approach).

Basic block je kus kódu, který má jeden entry point a jeden exit point. Pokud HHVM specializuje a kompiluje každý blok zvlášť, vytváří velké množství malých segmentů instrukcí, které se nenachází nutně v pořadí odpovídajícímu zdrojovému kódu. Mezi segmenty (které začínají guardem kontrolujícím jesti precondition platí), se kontrola předává skoky. Není těžké si představit, že to povede k situaci, kdy CPU skáče na mnoho různých míst v paměti, které se nevejdou do L1I cache a jejich stránky nejsou v iTLB a to se projeví jako pomalý program a nadmíra L1-icache-load-misses a iTLB-load-misses.

Avšak bez podrobného zkoumání vygenerovaných binárek jde jen o odhady a spekulace.


  1. L3 často není výrazně rychlejší než RAM, ale šetří přenosovou kapacitu a proud. Když procesor nemusí pro data do RAM, ale je obsloužen z L3, nevytěžuje systémový bandwidth a DRAM kontrolér nemusí být pár nanosekund napájen, což má dopad na tepelné vlastnosti čipu. Centaur čip na Power8 procesorech od IBM, který se dá považovat za L4 cache nebo DRAM buffer, funguje podobně.
  2. Cache sází na tři aspekty: spatial locality, temporal locality a sekvenční povahu dat – tedy: když budu potřebovat nějaká data s největší pravděpodobností mě budou zajímat i ta, která se nachází v nejbližším okolí (data se načítají po větších blocích cache-line), když jsem nějaká data potřeboval teď, s největší pravděpodobností je budu potřebovat i za chvíli (data zůstanou v cache do té doby dokud je jiná potřebná nevytlačí) a když procházím data sekvenčně s největší pravděpodobností budu potřebovat i ta následující a CPU je prefetchne. Když přistupuji k datům na nepředvídatelných adresách v nepředvídatelném pořadí, cache nemá žádný vliv. Naštěstí se to nestává často, protože programy mají obvykle velice předvídatelný a pravidelný průběh.
  3. Na mnoha procesorech je možné zcela zakázat použití cache a výsledný stroj běží až komicky pomalu. Viz tato prezentace froze cache útoku.
  4. Některé věci nejsou nezbytné, ale jde o hříchy našich otců, kterých se nemůžeme zbavit, jako například barokní schéma kódování x86 instrukcí se všemi escape sekvencemi a prefixy.
  5. Některé procesory pro adresování dat v L1 cache používají virtuální adresu, kdy paralelně načtou data z L1 cache a zároveň v TLB vyhledají odpovídající fyzickou adresu a tu pak použijí k ověření, že je to správná cache line. Viz Adress translation.
  6. Bylo navrženo několik přístupů, jak odstranit tuto neefektivitu. Jeden z nich je zavést jakousi super-stránku, která pokrývá většinu paměti, je alokována při startu systému. Pro přeložení adresy v této stránce stačí zjisti, jestli adresa spadá do daného rozsahu a pak k ní přičíst offset, což je triviální a velice rychlá operace. Tento přístup se hodí pro serverové aplikace, jako například memcache, kdy na serveru běží jedna aplikace – jmenovitě memcached, která využívá naprostou většinu paměti serveru. Další přístup, jaký zvolili vývojáři architektury Mill, je použít jeden 64 bitový paměťový prostor, který je sdílen všemi procesy, ale stále poskytuje ochranu paměti. Proto, že jde o jeden prostor ve kterém různé aplikace nemůžou mít stejné adresy, aliasing nepředstavuje problém a v důsledku toho je možné adresovat data v cache pomocí virtuální adresy. TLB je potřeba jen, když data nejsou v cache a musí se pro ně do paměti. To ale bude samo o sobě trvat pár stovek taktů a tak nevadí, když je TLB velká a (relativně) pomalá.
  7. Hyperthreading technicky může mírně pomoci, protože zatímco jedno vlákno čeká, druhé má všechny prostředky jádra pro sebe a může v klidu pokračovat v práci.

Dále k tématu:

Flattr this!

Posted in CPU, Paměť, PHP, VM | Leave a comment

Za jak dlouho procesor vynásobí tisíc čísel

Jednoduchá otázka: Jak rychle dokáže počítač vynásobit tisíc celých čísel? Odpověď, která přijde na mysl jako první: jde o tisíc instrukcí a tedy o tisíc taktů, není tak úplně správná.

Tak předně instrukce celočíselného násobení na x86 procesorech (které nepatří mezi single cycle procesory) trvá 3 takty.

Dohromady to tedy musí trvat 3000 taktů.

Ne tak docela. Moderní procesory jsou pipelinované a i když instrukce trvá 3 takty procesor umí začít s jednou novou operaci každý takt. V každém taktu se tedy můžou překrývat tři fáze třech různých mul instrukcí.

Ok, takže to znamená 1002 taktů. Tisíc instrukcí započatých v tisíci taktech a pak počkat dva takty než doběhne ta úplně poslední.

Ono je to o něco málo složitější. Takhle jednoduše to funguje, pouze když na sobě nejsou jednotlivé instrukce závislé. Pokud nastane situace, že každá instrukce závisí na výsledku té předchozí, musí je procesor vykonávat jednu po druhé. Existují různé hardwarové triky, které v téhle situaci pomůžou jako třeba operand forwarding, kdy se výsledek nezapisuje do registru, ale rovnou se přesměruje do následující instrukce, ale ty pomůžou jen částečně a neodstraní hlavní problém, kterým je závislost operací.

I když v určitých případech nemusí závislost mezi instrukcemi představovat nutně velkou překážku. Pokud na výsledku jedné instrukce nezávisí tři následující, ale až ta za nimi, není nic ztraceno, jak ukazuje následující schéma (čas je na vodorovné ose).

nezávislé operace

+--------+
| 1      |
+--+-----+--+
   | 2      |
   +--+-----+--+
      | 3      |
      +--+-----+--+
         | 4      |
         +--+-----+--+
            | 5      |
            +--+-----+--+
               | 6      |
               +--------+



operace v řádcích na sobě závisí

+--------+  +--------+
| 1      |  | 5      |
+--+-----+-----+-----+--+
   | 2      |  | 6      |
   +--+-----+-----+-----+--+
      | 3      |  | 7      |
      +--+-----+-----+-----+--+
         | 4      |  | 8      |
         +--------+  +--------+


oprace závisí na výsledku předchozí

+--------+--------+--------+--------+--------+
| 1      | 2      | 3      | 4      | 5      |
+--------+--------+--------+--------+--------+

Takže to bude něco v rozmezí 1002–3000 taktů.

Ani tohle není úplná pravda. Mainstreamové procesory od doby Pentia Pro jsou out-of-order superskalární CPU. Dokáží tedy vykonat několik instrukcí najednou a OOO jádro dynamicky vybírá ty nezávislé, které na nic nečekají a ty provede. Současná generace procesorů má 4 ALU a dokáže tedy provést 4 mul instrukce každý takt (pokud na sobě nejsou závislé a nic jiného nestojí v cestě).

To tedy znamená, že tisíc čísel se dá vynásobit v 252 až 3000 taktech.

Skoro. Problém je v tom, že předchozí kalkulace počítají s tím, že operandy instrukcí jsou okamžitě k dispozici. Ale to není pravda. Data, která jsou násobena, se nachází někde v paměti a před použitím musí být natažena do procesoru a cesta z RAM do CPU je zatraceně dlouhá. Může trvat i něco kolem 100ns, což může pro změnu odpovídat 300 taktům procesoru. CPU se snaží, co může, aby tyto prodlevy a latence eliminovalo – má hlubokou cache hierarchii, data načítá ve větších blocích (cache line), data přednačítá a může provádět několik load operací paralelně (tedy spíš na ně čekat). Přesto v nejhorším případě může utrpět prodlevu 300 taktů na každé slovo paměti. V nejlepším případě procesor rozjede svojí magii a latence nebude vůbec patrná.

Takže když budeme předpokládat, že každá instrukce násobení načte jedno slovo z RAM1, může jich tisíc trvat od 252 taktů do 300000.

Skoro, ale může to být ještě lepší. Pokud kód násobí data, která jsou extrémně regulární – například násobí mezi sebou odpovídající elementy dvou polí – může kompilátor použít SIMD instrukce, které provádějí stejnou operaci mezi několika různými položkami vektoru nejednou (SIMD znamená Single Instruction Multiple Data).2 Poslední generace x86 procesorů přidávají do instrukční sady rozšíření AVX2, které pracuje s vektorovými registry délky 256 bitů a umí provádět většinu operací i s celými čísly (původní SIMD rozšíření SSE umělo pracovat jen s floaty). Jedna SIMD instrukce dokáže vynásobit dva registry ve kterých je 8 čtyřbajtových integerů – tedy provést 8 násobení najednou. I když latence těchto operací je 10 taktů, CPU dokáže začít jednu takovou operaci každý takt3.

To tedy znamená, že to v nejlepším případě bude trvat 129 taktů a v nejhorším pak 300 tisíc.

Takové rozmezí vypadá že je skoro správné. Zanedbává ostatní operace, které budou s největší pravděpodobností v takovém kódu přítomné jako třeba mov instrukce nebo instrukce smyček, ale když nejde o užitečný odhad, je aspoň reálný. Všechno záleží na detailech. Nebo jak řekl Linus Torvalds: Talk is cheap. Show me the code.


  1. A to je možné, protože x86 je register-memory architektura a instrukce můžou pracovat jak s registry tak i přímo s pamětí.
  2. Pro detailní rozbor SIMD, array/vector procesorů doporučuji tuto přednášku kurzu Computer Architecture
  3. Jde o instrukci VPMULLD. V případě floatů je situace ještě lepší: Procesor může začít dvě VFMADD (která toho dělá trochu víc, ale dá se použít jako jednoduché násobení) v každém taktu a trvají 5 taktů (viz. instruction tables),

Dále k tématu:

Flattr this!

Posted in CPU | 3 Comments

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!

Posted in JVM, Typy, VM | Leave a comment