0xDEADBEEF

RSS

Co vlastně benchmarkujete?

4. 8. 2018

Před nějakou dobou jsem narazil na článek, který se snažil testovat rychlost a paměťové nároky asociativních polí a různých variant objektů v PHP. Závěr byl ten, že objekty jsou skoro ve všech ohledech buď srovnatelné nebo lepší než asociativní pole, hlavně co se týká paměťových nároků1 .

Ale stačil jediný pohled, abych věděl, že je něco špatně. Benchmark asociativních polí vypadal takhle:

<?php
declare(strict_types=1);
error_reporting(E_ALL | E_STRICT);
const TEST_SIZE = 1000000;
$list = [];
$start = $stop = 0;

$start = microtime(true);

for ($i = 0; $i < TEST_SIZE; ++$i) {
  $list[$i] = [
    'a' => random_int(1, 500),
    'b' => base64_encode(random_bytes(16)),
  ];
}

ksort($list);

usort($list, function($first, $second) {
  return [$first['a'], $first['b']] <=> [$second['a'], $second['b']];
});

$stop = microtime(true);
$memory = memory_get_peak_usage();
printf("Runtime: %s\nMemory: %s\n", $stop - $start, $memory);

Co tento kus kódu měl měřit? Vytváření asociativních polí (v dalších variantách pak objektů) a pak práci s nimi, přece.

Ne tak docela. Děje se toho podstatně víc. Vytváření polí, volání funkce random_int, random_bytes, base64_encode, pak řazení podle klíče, která je více méně noop, další řazení podle obsahu interních struktur a alokace dočasných polí.

Na mém Haswell stroji s PHP 7.2.4 měřený úsek běží 8 vteřin. Znamená to, že to co mě zajímá trvá 8 vteřin? Ne, celá ta věc trvá osm vteřin. Kolik z nich jsem strávil měřením rychlosti přístupů do polí/objektů? To není bez podrobnějšího zkoumání možné říct.

Začal jsem se proto vrtat, kolik času zaberou jednotlivé fáze a výsledky jsou zajímavé (kdyby nebyly, nic bych nepsal).

PHP je naštěstí primitivní runtime, který se nesnaží o chytré optimalizace a měření je proto jednoduché (jak říkal Aleksey Shipilёv). Můžu například udělat v podstatě jakoukoli změnu a nebát se, že chytrý JIT kompletně eliminuje veškerý kód bez pozorovatelných efektů.

Samotná konstrukce polí/objektů je v podstatě zdarma. ksort řadí podle již seřazeného numerického klíče, je také zadarmo a nepřináší žádnou užitečnou informaci o chování datových struktur.

A pak jsou tu také funkce random_int, random_bytes, base64_encode. První dvě generují kryptograficky bezpečná náhodná čísla, což nejspíš nebude zadarmo. A také není. Jen tyto funkce zaberou jednu vteřinu času, tedy ±12% zbytečné režie, která opět neříká nic užitečného.

Teď poslední řazení. Porovnávací funkce uvnitř využívá spaceship operátor <=> mezi dvěma nově vytvořenými poli. To je velice elegantní, ale dočasné datové struktury je třeba alokovat a i když každá alokace je levná (viz pár odstavců výše), provádí se jich O(nlog(n)) a to se nastřádá.

Když to změním na

usort($list, function($first, $second) {
  $cmp = $first['a'] <=> $second['a'];
  if ($cmp !== 0) return $cmp;
  return $first['b'] <=> $second['b'];
});

test běží o 3 vteřiny rychleji. Nejde jen o případ optimalizace benchmarku, ale důkaz, že ±37% času tráví alokacemi, dealokacemi a počítáním referencí, tedy ne tím, co měl měřit. Dohromady tráví 50% času zbytečnou režií a výsledky jsou v ní utopené.

Závěry benchmarku o relativních rychlostech polí a různých objektů jsou v tomto případě stále platné, jen poměry se liší. Režie je částečně maskovala a bez ní jsou přibližně dvakrát větší.

Benchmarkování je komplikované a takhle by se to nemělo dělat. Je nutné izolovat měřený efekt a i tak čísla jsou pouhá data, bez pochopení, proč jsou taková jaká jsou, nemají význam. Říct "X je z nějakého důvodu rychlejší než Y a proto bychom ho měli používat", není dobrý nápad.

Jak varuje JMH: Do not assume the numbers tell you what you want them to tell.


  1. Ale i toto je možné optimalizovat. Virtuální stroj může asociativní pole se stejnou strukturou zkompilovat do podoby, která je interně k nerozeznání od objektů. Self to začal dělat v osmdesátých letech a dnes na tom stojí všechny moderní JavaScriptové VM. Pokud se chcete dozvědět víc, sledujte tento kurz.

Java, Scala a regulární výrazy #5 - posesivní regexy a StackOverflowError

28. 7. 2018

Minule jsem psal o hladových a líných regexech, naznačil jejich implementaci a ukázal případ, kdy líný regex může předejít přetečení zásobníku a StackOverflowError.

V java implementaci regexů existuje ještě třetí druh opakování, vedle greedy a lazy (hladových a líných), jsou ještě possesive regexy. Zapisují se jako .*+, .++, .?+ a .{m,n}+, jsou hladové, nikdy nedělají backtracking a v případech, kdy by obyčejné hladové opakování backtrackovalo, selžou.

Například regex (ve Scale string se třemi uvozovkami je brán jak je, není třeba v něm skoro nic escapovat, ideální pro regexy)

"""(?x)  " ( \\" | [^"] )++ "  """.r

začne hledat od první dvojité uvozovky, hladově konzumuje všechno, co je escapovaná uvozovka nebo jakýkoli jiný znak kromě uvozovky, až narazí na ukončovací uvozovku a když ji najde, nikdy neustoupí o krok zpět. Chová se tedy do jisté míry atomicky (kdo neví, tak (?x) na začátku znamená, že mezery se ignorují).

Posesivní regexy mohou vést k odmítnutí některých stringů, které by hladové nebo líné regexy přijaly. Ale na druhou stranu regex selže brzo a nebude zkoušet všechny permutace. Jde tedy o druh optimalizace.

Často právě posesivní regexy jsou to, co člověk chce. Hodí se, když chci hledat až do určitého symbolu, který jasně indikuje, kde posesivní regex skončí. Často mívají formu a [^a]++ a.

Protože nedělají backtracking jsou implementovány iterativně a nemůžou skončit StackOverflowError.

Například následující dva regexy testují to samé.

("a " * 1000000).matches("(a+ )+")
("a " * 1000000).matches("(a+ )++")

První skončí StackOverflowError, ale druhý doběhne v pořádku. (Kdo neví, tak násobení stringu ve Scale ho opakuje.)

Navíc: Protože nedělají backtracking, logicky u nich nehrozí případy katastrofického backtrackingu.

Opět dva případy: První je obyčejný hladový regex, druhý je possesive regex.

"ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCCX".matches("A(B|C+)+D")
"ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCCX".matches("A(B|C++)+D")

Druhý dojede v mikrosekundě, ale první bude trvat celou věčnost právě proto, že začne zkoušet všechny možnosti a dojde ke kombinatorické explozi.

Posesivní regex bude vyhodnocován takto: A pasuje, zkusí B, nic, C++ sedne a sebere všechna C, zkusí D, selže, ++ zajistí, že nevrátí žádné C zpátky, nezkusí další varianty a celý regex selže.


Pozn:




EDGE, TRIPS a hon za vyšším ILP

26. 7. 2018

Tiskem proletěla zpráva, že Microsoft portoval Windows a Linux na vlastní experimentální CPU architekturu E2. Pročetl jsem pár publikací o architektuře a na pohled vypadá zajímavě. Tedy aspoň z technického pohledu je ambiciózní, jestli povede k reálnému produktu, si netroufám odhadovat.

To nejlepší na začátek: Microsoft se rozhodl vytvořit dataflow stroj. I když ne tak úplně, jde o omezený dataflow v technickém žargonu označovaný EDGE - Explicit data graph execution.

Článek An Evaluation of the TRIPS Computer System poskytne detaily o prvotní EDGE architektuře TRIPS, vyvíjené v akademickém prostředí. Její autoři se snažili dosáhnout vysokého ILP (instrukční paralelismus) v malém a úsporném procesoru a mít všechny výhody out-of-order bez křemíkové a energetické režie OoO.

CPU provádí bloky až 128 instrukcí bez skoků (kompilátor se je snaží nahradit predikací). Blok commitne atomicky jako celek a uvnitř se chová jako dataflow. Instrukce nezapisují výsledky do registrů, ale přímo je směřují závislým instrukcím. Pokud je blok dostatečně velký, může obsahovat velké množství instrukčního paralelismu (TRIPS jádro má 16 ALU) a díky jeho explicitní dataflow povaze je prováděn jako na OoO jádře. Závislosti mezi instrukcemi nemusí za běhu analyzovat procesor, ale jsou identifikovány už v procesoru.

Pro představu to může vypadat nějak takhle (hypotetický pseudokód):

i1: READ R1 i3     // přečte z globálního registru a data nasměruje instrukci i3
i2: READ R2 i3 i4  // to samé, ale pošle je instrukcím i3 a i4 najednou
i3: ADD i4         // až obdrží data, sečte je a výsledek pošle instrukci i4

Toto uspořádání řeší problémy, kterými trpěly obecné dataflow architektury. Ale jako obvykle komplikované větvení kódu se nekamarádí s ILP, protože vede k malým blokům instrukcí.

Paper Dynamic Vectorization in the E2 Dynamic Multicore Architecture představuje další pokrok již pod taktovkou Microsoftu. Jde o první nástřel z roku 2010, ale přesto ukazuje několik zajímavých inovací, jako například dynamické spojování několika fyzických jader do jednoho logického. Jedno fyzické jádro v gangu provádí nespekulativní kód a ty ostatní jsou použité pro spekulace. Po spojení jader tak vznikne agresivní superskalární OoO CPU. To dodá procesoru flexibilitu - na jedné straně v něm může běžet mnoho malých jader na druhé několik málo velice mocných jader pro jednovláknové programy.

Další chuťovkou je vektorový mód, kterého je dosaženo kombinací všech skalárních ALU v jádře. Nepotřebuje tedy novou sadu registrů nebo nové funkční jednotky, ale používá všechny existující hardwarové prostředky.

Všechno tohle EDGE šílenství je honem za stále ILP - TRIPS měl 16 ALU a výzkumníci dospěli k závěru, že ideální stroj s nekonečným množstvím funkčních jednotek a masivním instrukčním blokem by dokázal provádět desítky až stovky instrukcí každý takt. Jeden z prototypů E2 měl údajně mít 32 ALU.

Za ILP se dříve hnalo Itanium a všichni víme jak to s tímto dítkem Intelu a HP dopadlo. O podobný kousek se snaží i architektura Mill, ale jde cestou kompletně statického VLIW. Historie nedává příliš optimismu, že by to mohlo vyjít.

Jedním z mnoha problémů Itania byl fakt, že potřebovalo pokročilý kompilátor, který by dokázal ohnout kód tak, aby sedl na masivně paralelní spekulativní predikované srdce čipu. Stejně to budou potřeboval EDGE (a Mill) procesory. Pokud nebudou k dispozici, můžou skončit jako produkty s nevyužitým potenciálem.

Ale také nemusí, když končí moorův zákon, efektivita, i když v porovnání s exponenciálními zisky minulosti jen marginální, může hrát značnou roli.


K tématu:




Striktní a líné jazyky

24. 6. 2018

František Řezáč napsal článek o tom, že Operátory nejsou (vždy) funkce. To je pravda a není k tomu třeba dodávat nic víc.

Stojí to ale za pozornost jen v případě striktních jazycích typu C a Java, kde jsou argumenty funkce vyhodnoceny vždy před jejím zavoláním (applicative order/call by value). V takovém prostředí není jednoduše možné napsat vlastní funkci OR nebo AND, která se chová stejně jako vestavěné operátory || nebo &&. Ty v klasické sortě céčku podobných jazyků vyhodnotí druhý argument jen pokud je to nezbytně nutné. Toho bez funkcí vyššího řádu (jak FR podotknul) není možné dosáhnout. Proto v nich operátory zaujímají speciální místo.

Mě to koplo nedávno, když jsem psal interpret jednoduchého lipovského jazyka1 , kde odloženého vyhodnocování bylo nezbytné k tomu, aby následující kód neskonšil NullPointerException.

(if (and (nil? x) (.nonEmptx x)) (something))

V líných jazycích nebo těch, které podporují call-by-name nebo call-by-need, operátory v principu nemají speciální postavení2 a jsou to jen další metody.

Ve Scale můžu napsat vlastní funkci OR takto:

def OR(a: Boolean, b: => Boolean): Boolean = if (a) true else b

Typ => Boolean označuje call-by-name boolean. b není vyhodnoceno při zavolání funkce, namísto toho bude vyhodnoceno na každém místě, kde je v těle funkce použito. Kompilátor call-by-name parametr zabalí do anonymní funkce, která je pak opakovaně volána.

Nejde ale o plně líné neboli call-by-need vyhodnocování jako například v Haskellu. V něm je nevyhodnocený výraz reprezentován strukturou běžně nazývanou thunk, která ukazuje na kód. Když je přinucena se vyhodnotit (například pattern matchingem), je odkazovaný program vykonán a thunk je atomicky zaměněn na výsledek. Líné jazyky mají tu vlastnost, že nevyhodnocené nemusí být jen argumenty funkce, ale celé datové struktury. Můžu mít masivní strom, ale když jsem četl jen z jedné cesty k listům, všechny nenavštívené odbočky zůstanou jako nevyhodnocené thunky.

Call-by-need je tedy call-by-name doplněné s memoizací.

Ve Scale je to možné emulovat takto:

def f(_a: => X) = {
  lazy val a = _a
  ???
}

Když někde použiji proměnnou a dojde k jejímu vyhodnocení jen jednou a výsledná hodnota se bude recyklovat při každém dalším použití.


Poznámky:


  1. Jmenoval se Lispy a byl zamýšlený jako skriptovací nástroj pro asciiblog. Psalo se v něm příjemně, ale nakonec jsem ho nahradil za javascript vestavěný do Javy.
  2. Kompilátor o nich ví a proto bych si dovolil odhadovat, že pro ně vygeneruje lepší kód.



Syntéza datových struktur a programů

21. 6. 2018

Generalized data structure synthesis stojí za přečtení. Prezentuje nástroj Cozy, který - jak říká název článku - umí syntetizovat datové struktury operace nad nimi, které jsou nejen korektní, ale také efektivní. Nechci opakovat, co už shrnul Adrian Colyer, přečtěte si to, teď hned, je to důležité pro následující odstavce.

Jde o perfektní doplněk k Out of the Tar Pit a možná chybějící článek nutný k tomu, aby vize načrtnutá v tar pit paperu (pokud nechcete číst, tady jsem ho kdysi shrnul).

Autor tar pit paperu mluví o esenciální a vedlejší komplexitě, přičemž ta esenciální je ta důležitá, jde o nutnou složitost problému nebo domény, chcete-li. Vedlejší komplexita nemá žádnou hodnotu pro uživatele, jen je někdy nutná pro dosažení efektivity a dostatečného výkonu. Esenci musíme nějak vyjádřit a vedlejší složitostí bychom se měli vyhnout.

Na tom není nic kontroverzního, ale teď jak toho dosáhnout. V tar pit paperu se mluví o logickém a funkcionálním programování, deklarativním stylu a relačním datovém modelu.

A tady do hry vstupuje Cozy - nadefinuji nezbytný stav bez ohledu na efektivní reprezentaci, tak jak o něm přemýšlejí uživatelé, deklarativně popíšu operace nad ním, jako v tar pit utopii a Cozy, nebo nějaký jeho pokročilý potomek, z této kostry syntetizuje její efektivnější verzi - efektivní datové struktury specializované pro dané operace a efektivní kód. Z esenciálního popisu vygeneruje všechnu vedlejší komplexitu a odvozený stav.


Heuristiky a strategie prohledávání stavového prostoru, můžou být pochopitelně rozšířeny strojovým učením.




ISPC, SPMD a SIMD

9. 6. 2018

Maxime Chevalier tweetla odkaz na zajímavou sérii článků mapující počátky a vývoj kompilátoru ISPC (Intel SPMD program compiler) + do toho vysvětlí jak funguje SPMD programovací model, který je využívaný pro programování grafických karet.

Všechno začalo s Larrabee - prototypem procesoru určeném pro segment, který okupuje GPGPU. Samotné první Larrabee skončilo jen u prototypu a neprodávalo se. Následující mikroarchitektury Knights Corner (57-61 jader) a Knights Landing (64-72 jader), hromadně nazývané produktovým jménem Xeon Phi si však úspěšně našly místo v superpočítačích.

Larrabee a jeho následovníci byli navrženi jako čip, ktrerý nese velké množství jednoduchých in-order jáder1 obohacených o široké SIMD jednotky + 4xSMT. SIMD od počátku mělo šířku 512 bitů (tedy tolik jako AVX-512, které se později dostalo do obyčejných Skylake čipů). Taková šířka znamená, že jedna SIMD instrukce pracuje s 16 čtyřbajtovými inty/floaty. To je hodně práce v jedné operaci.

Teď jak tento spící potenciál využít? Nejde jen o Larrabee určené pro superpočítače, ale i běžné čipy. Když bylo uvedeno AVX, došlo ke zdvojnásobení šířky SIMD jednotek (z 128 butů na 256 bitů) a tedy k ±zdvojnásobení výpočetní síly. Další zdvojnásobení přichází teď s poslední generací procesorů Intel, které podporují AVX-512. Jak podotýká autor odkazovaných článků, takové zrychlení jsme viděli naposledy v devadesátých letech.

Jednou možnost je automatická vektorizace kódu - ta funguje, ale nejde o programovací model, je to jen optimalizace na kterou se uživatel nemůže na 100% spolehnout. Další alternativou je psát přímo v assembleru nebo za pomocí intrinsic funkcí. To ale není příliš produktivní způsob práce.. Další varianta je pak SPMD - single program multiple data. Jde o to, že se paralelní program rozřízne podélně a místo abych se zdržoval explicitním paralelismem, píšu sériový program, který pracuje s jedním elementem vstupu. Mnoho instancí tohoto programu pak může běžet v mnoha vláknech, ale také můžou být přeloženy pro SIMD. V takovém případě SIMD jednotka s 16 lajnami bude provádět 16 instancí programu vedle sebe. Je to jako kdyby 16 vláken pochodovalo zcela identickým rytmem, jednu instrukci za druhou. Překlad je celkem triviální, ale poněkud nezvyklý. V přítomnosti podmínek, smyček, goto, break a continue, je nutné některé SIMD lajny vymaskovat jako neaktivní a tak podobně. Ve své podstatě jde o glorifikovanou funkci map.


Relevantní čtení:


  1. Tyto jádra vycházejí z originálních Pentií, stejně jako z nich vycházely rané Atomy.



Konec Intelu, konec Moorova zákona, konec světa takového jaký známe

6. 4. 2018

Apple oznámil, že plánují opustit procesory Itelu a chtějí přejít k vlastním čipům. Zatím se neví, jakou architekturu zvolí, zda-li to bude ARM nebo nějaká proprietární ISA. Všichni však blahořečí Apple a vyzdvihují, že jejich mobilní procesory jsou v jednovláknovém provozu stejně rychlé jako křemík od Intelu.

Když to čtu, skřípu zuby. Samozřejmě, že mají stejně výkonné čipy, bylo by mnohem víc neobvyklé, kdyby je neměli. To co předvádí Apple ve svých A11 nebo Intel v Xeonech je velice blízko nejzazšího maximum. Za současných podmínek není možné z jednoho vlákna vytěžit nic víc.

Procesor běžící na 2-3 GHz, který dokáže v ideálním případě provést 4 instrukce každý takt (IPC) představuje limit. Nic lepšího křemíkový průmysl nesvede vyprodukovat. Tedy aspoň co se obecného kódu týká.

Vyšší takty vedou k obrovsky narůstajícím ztrátám tepla, proto ty 2-3 GHz, a nespecializovaný kód neobsahuje instrukční paralelismus, který by bylo možno vytěžit, proto ~4 IPC.

Intelovské procesory mají praktické maximální IPC někde mezi 4-5. Power od IBM nebo Sparc od Oraclu jsou širší, plánované pro odpravení 8 instrukcí každý takt, ale to je jen kvlůli 8x SMT (tedy to, čemu Intel říká hyperthreading).

Některé z těchto instrukcí můžou být SIMD, které dokáží o něco navýšit výkon. SIMD ale začínají přesahovat do sféry specializovaných programů, které provádějí masivní množství výpočtů, ne typický general purpose kód plný podmínek a větvení. Pro tyto speciálních trapně paralelní případy už máme ideální nástroj: GPU.

Příslib architektury Mill o tom, že statický velice široký VLIW stroj dokáže vydolovat nebývalý instrukční paralelismus (ILP), se setkává s oprávněnou skepsí. Když už se jim podaří uspět, bude to spíš v oblasti MIPS na watt. Specializace pro danou mikro-architekturu a jádra bez masivní OOO mašinérie (ale zato s obrovským počtem funkčních jednotek), může být energeticky efektivní.

Je ale stále ve hvězdách jestli se něco ze slibů zcela nové architektury skutečně vyplní. Jednovláknový IPC se moc nezlepší a nezáleží kolik plochy čipu tomu věnujeme, změna bude vždy jen v jednotkách procent. Zcela jisté je, že budoucnost bude patřit specializovanému hardwaru. Jinak není možné dosáhnout žádného razantního zvýšení efektivity.

Jsme na konci jedné éry. Všichni mají nejlepší procesory na světě a nestojí to za řeč. Teď je potřeba udělat další velký krok do divočin, kde už neplatí Moorův zákon.


Pozn:


Relevantní čtení:




Meltdown, Spectre a branch prediction

31. 1. 2018

Na Poslední Sobotě, kde jsem mluvil o Meltdown a Spectre (slajdy zde), jsem dostal dotaz jak jsou implementovány branch predictory. Něco jsem odpověděl, ale z trhanců vzpomínek mi nepřipadá, že šlo o uspokojivou odpověď. Proto jsem se rozhodl o tom něco málo napsat a hlavně poskytnout odkazy na autoritativní zdroje.

O branch prediction (BP) jsem se zmiňoval na funkcionálně.cz tady a trochu i tady. Šlo ale jenom o dopady BP na výkon, ne detaily nebo principy implementace. O tom se něco dá vyčíst z článku na wikipedii. Mnohem lepší úvod však poskytuje Dan Luu na svém blogu. Pokud vás toto téma zajímá, rozhodně si jeho článek přečtěte. (Už jsem ho tu vychvaloval)

Zajímavý ja také paper The YAGS Branch Prediction Scheme, který prezentuje, jak může vypadat o něco sofistikovanější, ale přesto klasická implementace.

Branch predictor nemusí být implementován jen pomocí tabulek historie skoků, ale i neuronovými sítěmi. Tím se AMD chlubili při ohlášení své mikroarchitektury Zen. Ale co tím vlastně myslí je otázka, na kterou nikdo nezná přesněou odpověď. Nejspíš nejde o nijak komplikované neuronosítě, ale o perceptrony, jak je popsáno v Dynamic Branch Prediction with Perceptrons. Predikce musí být rychlá, ideálně dostupná v jednom taktu, navíc je vždy tlak na to, aby extra hardware zabíral co nejméně místa čipu a konzumoval co nejméně energie.

x86 procesory mají několik nezávislých mechanismů pro predikci skoků. Jednak je již zmíněný to branch predictor, který odhaduje, zdaji bude skok proveden nebo ne a dále jsou to mechanismy odhadující, kam povede nepřímý skok. Jde jednak o branch target buffer (BTB) pro obecné skoky a pak return stack buffer (RSB) pro predikci cílů ret instrukcí. Protože ret se typicky vrátí na místo call instrukce, je RSB implementován jako jednoduchý zásobník. call na vrchol zásobníku vrazí svojí adresu a ret ji vyjme.

Toho je možné využít pro retpoline chránící před druhou variantou útoku Spectre. Nepřímý skok, který by se zkompiloval jako prosté

jmp *%r11

se se správnými přepínači GCC/LLVM namísto toho zkompiluje jako

  call set_up_target;

capture_spec: // nekonečná smyčka slouží jako trampolína, kde uvázne spekulativní exekuce
  pause;
  jmp capture_spec;

set_up_target:
  mov %r11, (%rsp); // tady se přepíše návratová adresa na zásobníku
  ret; // ret se vrátí na přepsanou adresu

Dojde náhradu za pár korespondujících call/ret instrukcí a na zásobníku se přepíše návratová adresa. To znemožní, aby byl spekulativně vykonán neznámý kód. Predikce ret použije adresu z RSB, která povede do nekonečné smyčky, a procesor poté, co odhalí, že jde o chybu, skočí nespekulativně na správnou adresu. Má to dopady na výkon, protože kód běží, jako kdyby byly spekulace a predikce zakázány.

Relevantní čtení:




Poznámky k výkonu

28. 12. 2017

Před nějakou dobou mi twitterem proletěla prezentace Adventures in efficiency and performance (slajdy, video), kde autor mluvil o tom jak dosáhnout výkonu na JVM a vyprávěl o hardwaru. Některé informace mi přišly nedostatečné, tady jsou moje poznámky.

V části "Good" failed speculations uvádí:

Both branches will be executed in parallel, only one of them will be retired

Ukázkový kód vypadá takhle:

def foo(a: Array[Int], idx: Int) = {
  val s = a[idx]
  if (s < 0) idx + idx
  else idx - idx
}

Záleží, jak bude kód zkompilován. Na jednu stranu může být převeden na compare+branch instrukce, které povedou k tomu, že CPU bude dynamicky spekulovat a bude záležet na branch prediction. Na druhou stranu to může vést k něčemu jkao tohle:

def foo(a: Array[Int], idx: Int) = {
  val s = a[idx]      //
  val add = idx + idx //
  val sub = idx - idx // nezávislé operace, všechny tři můžou běžet najednou

  if (s < 0) add else sub // zkompilováno jako cmov instrukce bez skoku
}

Poslední if nepředstavuje skok, ale instrukci cmov (conditional move), která na základě porovnání přesune buď add nebo sub. Nejde o větvení programu a tedy ani nehrozí žádná penalizace při špatném odhadu skoku (branch mispredict).

Nevím přesně, co myslel těmi good failed speculation. Současné x86 procesory (pokud se nemýlím) se nesnaží spekulativně provést obě větve podmínky a retire jen tu správnou.

Další příklad, který je mnohem komplikovanější než je prezentováno:

val a: Array[Array[Int]] = ...
val i = 0
while (i < n) {
  val j = 0
    while (j < n) {
      if (fast) {
        a[i][j] += a[i][j]
      } else { // slow
        a[j][i] += a[j][i]
      }
      j += 1
    }
  i += 1
}

Autor tvrdí, že rychlá verze (větev fast) byla 3x rychlejší až do příchodu Intel Skylake procesorů, které pak uvedly nějakou blíže nespecifikovanou změnu, která to změnila.

Pomalá větev může být rychlá, záleží na řadě faktorů jako například jak velká jsou data a jak jsou uspořádaná v paměti.

Jde o to, že rychlá verze přečte všechny elementy pole a[i] jeden za druhým než se posune na následující pole a[i+1]. Pomalá verze přečte první element ze všech polí a pak se posune na druhý element. Rychlá verze čte sekvenčně bloky paměti, druhá skáče z místa na místo.

Pokud je dat málo a vejdou se do cache, není moc co řešit (ale rychlá verze je stále preferovaná, protože se dá snáze vektorizovat bez scatter/gather instrukcí).

Rychlá verze funguje tak dobře, protože hardware počítá s tímto chováním. Data z paměti tahá po cache line blocích (64B na současných x86). Když se dotknu prvního intu v poli, dalších 16 jich už čeká v cache, připravené pro rychlé čtení. CPU navíc dopředu načítá data, která budou pravděpodobně potřeba (prefetch), takže sekvenční průchod je zcela ideální.

Prefetcher ale nemusí načítat jen data, která leží těsně vedle, ale dokáže detekovat kroky konstantní délky. Pokud jsou vnitřní pole malá a alokovaná sekvenčně, prefetcher rozpozná vzdálenost k dalšímu požadovanému prvku (stride) a načte ho dopředu. (Je ale méně efektivní, protože pořád musí vytáhnout celou cache line, za které použiji jen první prvek a než se dostanu k jeho sousedu, může být už vyhozená z cache).

     | -- a[0] ----- | -- a[1] ----- | -- a[2] ----- | -- a[3] -----

slow:  ^               ^               ^               ^
       |<-a[0].length->|<-a[0].length->|<-a[0].length->|

fast:  ^^^^^^^^^^^^^   ^^^^^^^^^^^^^

Pokud jsou vnitřní pole alokována různě na haldě, tak to také nemusí být problém. Prefetcher zvládne pracovat na několika místech paměti najednou (něco jako 64 různých stránek). Kdyby tedy vnější pole bylo menší než tento limit, prefetcher by stále pomohl.

I když jsou vnitřní pole rozesetá všude na haldě, ani to nemusí být konec. Záleží totiž i na použitém garbabe collectoru. Některé GC dělají kompakci haldy tak, že přesouvají objekty v pořadí ve kterém na ně narazí při procházení referencí. V tomto případě GC může narazit na pole a, zkopíruje ho na jedno místo a pak z něj začne procházet všechny reference na vnitřní pole a jedno po druhém je kopírovat vedle sebe. To povede k obnovení dobré lokality jako na schématu o něco výše.

Skylake mohl uvést větší cache, prefetch na více stránkách paměti, více paralelních přístupů do paměti, větší OOO okno. Vliv může mít také asociativita cache a cache eviction policy.

Nebudu tady teď mluvit scatter/gather SIMD instrukcích a dalších věcech, protože by to zabralo příliš místa a tenhle článek je už tak dost dlouhý.

Zjistit co je rychlejší a hlavně proč je jako vždycky komplikované.

Relevantní čtení:




Java, Scala a regulární výrazy #4 - líné regexy a StackOverflowError

19. 12. 2017

Jednou z nepříjemných vlastností regexů v Javě je to, že můžou snadno skončit přetečením zásobníku a StackOverflowError. Regexy dělají backtracking, jsou implementovány rekurzivně a proto jde o nevyhnutelnou eventualitu.

Nejběžnější druhy opakování .*, .+ a .{m,n} jsou greedy (lakomé, hladové nebo jak je to česky) a snaží se pojmout co nejdelší vstup. Když následující část regexu selže, začnou s backtrackingem a postupně upouštějí z požraného vstupu, dokud následující část uspěje. Aby to fungovalo, potřebují si pamatovat kam skočit zpátky a tato pozice je (často) uchována na zásobníku při rekurzivním volání.

Když mám například regex .+.{5}, první část .+ pojme celý vstup, pak zjistí, že následující regex .{5} pro pět libovolných znaků nepasuje, ustoupí o jeden znak, zkusí znovu, nepasuje, opět ustoupí a tak dále dokud nepojme všechno kromě pěti posledních znaků. Teprve potom .{5} sedne a celý regex skončí úspěchem.

Naproti tomu líné (anglicky lazy nebo také reluctant) opakování .*?, .+? a .{m,n}? se snaží pojmout jen absolutní minimum, ideálně nic. V případě nouze, kdy následující regex selže, pojme jedno další opakování a pak otestuje následující část regexu.

V regexu .+?.{5} první část .+? nejprve nepožere nic, otestuje následující část, když ta selže, požere jedno opakování víc, zkusí znovu a tak dále.

Hladová a líná opakování nezmění jestli regex selže nebo ne, může změnit jen jak bude vstupní string rozdělen mezi uzávorkované skupiny.

Z výše popsaných důvodů vyplývá, že hladové regexy někdy můžou skončit výjimkou StackOverflowError, zatímco líné proběhnou úspěšně.

Například toto

("\uD83D\uDC09 "*100000).matches(".*")

skončí StackOverflowError. Vstupem je řetězec, ve kterém se sto tisíckrát opakuje symbol draka, který je hned následovaný mezerou. Naproti tomu varianty

("\uD83D\uDC09 "*100000).matches(".*?")
("\uD83D\uDC09 "*100000).matches(".*+")

skončí úspěšně, protože se liší způsobem, jakým je regex prováděn.

Java obsahuje optimalizaci, že když jedno opakování regexu pojme stejný počet znaků jako minulé opakování, nevolá se rekurzivně, ale ve smyčce. Symbol \uD83D\uDC09 zabírá dva chary a je hned následovaný jednocharovou mezerou. . tedy střídavě matchuje jeden a dva chary a proto vždy dělá rekurzivní volání a eventuálně přeteče zásobník (kód ve třídě Curly, metody match0, match1, match2).

Líná varianta si nemusí pamatovat, kam skočit zpátky a proto je implementována smyčkou, která nevyčerpá zásobník a neselže.

Tohle se týká jen případů, kdy se opakuje jednoduchý neuzávorkovaný vzor (jako třeba ., \W, \S atd.) a je to problém/řešení jen pro stringy obsahující několikabajtové znaky. Ale ty nejsou zas tak vzácné v pro texty s emoji.

Něco jako (a|b+)+? se vykonává vždy rekurzivně. Vnitřní implementace regexů je komplikovaná a aktivně se snaží předejít mnoha případům katastrofického backtrackingu. Proto se někdy jednoduchý vzor provádí poměrně překvapivě.

Co přetečení a katastrofickému backtrackingu předchází mnohem spolehlivěji jsou takzvané posesivní regexy, ale o nich něco napíšu příště.


5. 12. 2017 Java, Scala a regulární výrazy #3 - rychlost
27. 11. 2017 Java, Scala a regulární výrazy #2 - rychlost
26. 11. 2017 Java, Scala a regulární výrazy
21. 11. 2017 Java - zostřování obrázků
7. 10. 2017 Koherence cache a atomické operace
5. 10. 2017 Nejrychlejší hashmapa pod sluncem
23. 9. 2017 Dekódování x86 instrukcí
21. 9. 2017 Energetická efektivita programovacích jazyků
19. 9. 2017 Programming and Performance podcast
17. 9. 2017 B-stromy, persistence, copy-on-write a Btrfs
15. 9. 2017 Rust a parsery
13. 9. 2017 Velké stránky paměti
11. 9. 2017 Deanonymizace agregovaných dat
9. 9. 2017 Optimalizující kompilátor
7. 9. 2017 Identifikace zašifrovaných videí
5. 9. 2017 Heterogenní persistentní kolekce
3. 9. 2017 JVM Anatomy Park
1. 9. 2017 Datacentrum z mobilů
30. 8. 2017 Propustnost pamětí
28. 8. 2017 Branch prediction (implementace v procesorech)



píše k47 (@kaja47)