title 0xDEADBEEF
baseUrl https://deadbeef.k47.cz
language cs
outDir /home/drgonzo/k47deadbeef
remoteDir /home/drgonzo/mnt/k47deadbeef/
fullArticlesOnIndex 10
groupArchiveBy 
archiveFormat link
limitRss 15
fullArticlesInRss true
articlesMustBeSorted true
articlesMustNotBeMixed true
style| .b { font-family: sans-serif; font-size: 0.9em; line-height:1.5; max-width: 50em; margin: 2em 1em; padding: 1.5em; background-color: white }
style| body { background-color: #222 }
style| h1 { font-size:1em; display:inline; color:white;background:#222;padding:0.2em 0.4em }
style| a:hover { color:red }
style| a { background-color:#FFdde9 }
style| ::-moz-selection { background-color:pink }
style| pre { background-color: #efe9e9; padding: .4em; margin: -0.4em 0em; font-size: 1.1em; }
footer <div style="color:gray;clear:both;">píše k47 (<a href="https://twitter.com/kaja47">@kaja47</a>)</div>
fileSuffix .html
header <div class=r><h1><a style="background:none;" href="index">0x<span style="color:red">DEAD</span>BEEF</a></h1> <a style="color:#222" href="rss.xml">RSS</a></div>
allowComments true
shareLinks true
twitter.site @kaja47
tagFormat short
inline!


Co vlastně benchmarkujete? [php-benchmark]
=====
2018-08-04
# PHP, VM

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":[b]. 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:

/---code
<?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":[p]).

PHP je naštěstí primitivní runtime, který se nesnaží o chytré optimalizace a
měření je proto jednoduché ("jak říkal Aleksey Shipilёv":[sh]). 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ů":[mb].

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

/---code
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":[j]: *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":[s] 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":[k].

[b]: https://steemit.com/php/@crell/php-use-associative-arrays-basically-never
[mb]: http://funkcionalne.cz/2017/04/mikrobenchmarky-jsou-tezke/
[s]: https://en.wikipedia.org/wiki/Self_(programming_language)
[k]: http://www.wolczko.com/CS294/
[p]: https://en.wikipedia.org/wiki/Publication_bias
[sh]: https://www.youtube.com/watch?v=VaWgOCDBxYw
[j]: http://hg.openjdk.java.net/code-tools/jmh/rev/2985092a3a59


Java, Scala a regulární výrazy #5 - posesivní regexy a StackOverflowError [regex-5]
=====
2018-07-28
# Java, Scala, regex

"Minule jsem psal o hladových a líných regexech":[r4], 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)

/---code
"""(?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é.

/---code
("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.

/---code
"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:

- Jak jsem četl zdrojové kódy regexů, myslím, že by nebylo těžké napsat
knihovnu, které provádí reguláry nad libovolnými kolekcemi a ne jen řetězci
stringů.

[s]: https://github.com/dmlloyd/openjdk/blob/jdk10/master/src/java.base/share/classes/java/util/regex/Pattern.java
[r4]: regex-4


EDGE, TRIPS a hon za vyšším ILP [edge]
=====
2018-07-26
# CPU

Tiskem proletěla zpráva, že "Microsoft portoval Windows a Linux na vlastní
experimentální CPU architekturu E2":[ms]. 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":[df].
I když ne tak úplně, jde o omezený *dataflow* v technickém žargonu označovaný
"EDGE":[e] - *Explicit data graph execution*.

Článek "An Evaluation of the TRIPS Computer System":[ev] poskytne detaily o
prvotní EDGE architektuře "TRIPS":[tr], 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í":[pr]). 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):

/---code
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":[dv]
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":[m], 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:

- "Von Neumannovy lži":[http://funkcionalne.cz/2017/05/von-neumannovy-lzi/]
- "Dualismus hardwaru a softwaru, strojů a virtuálních strojů":[http://funkcionalne.cz/2016/03/dualismus-hardwaru-a-softwaru-stroju-a-virtualnich-stroju]
- "Čím více se věci mění, tím více zůstávají stejné":[http://funkcionalne.cz/2016/05/cim-vice-se-veci-meni-tim-vice-zustavaji-stejne]
- "Úvod do podivností moderního hardwaru, které vás budou budit ze spaní":[http://funkcionalne.cz/2016/07/uvod-do-podivnosti-moderniho-hardwaru-ktere-vas-budou-budit-ze-spani]
- "Za jak dlouho procesor vynásobí tisíc čísel":[http://funkcionalne.cz/2015/05/za-jak-dlouho-procesor-vynasobi-tisic-cisel]

[ms]: https://www.theregister.co.uk/2018/06/18/microsoft_e2_edge_windows_10/
[df]: https://en.wikipedia.org/wiki/Dataflow_architecture
[e]: https://en.wikipedia.org/wiki/Explicit_data_graph_execution
[ev]: https://www.cs.utexas.edu/users/mckinley/papers/trips-eval-asplos-2009.pdf
[tr]: https://www.cs.utexas.edu/~trips/prototype.html
[dv]: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/e2-heart2010.pdf
[pr]: https://en.wikipedia.org/wiki/Predication_(computer_architecture)
[m]: https://www.youtube.com/playlist?list=PLFls3Q5bBInj_FfNLrV7gGdVtikeGoUc9
[mz]: konec-intelu-a-moorova-zakona


Striktní a líné jazyky [striktni-a-line-jazyky]
=====
2018-06-24
# Scala, FP

"František Řezáč":[fr] napsal článek o tom, že "Operátory nejsou (vždy)
funkce":[op]. 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*":[e]). 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
jazyka[[1]], kde odloženého vyhodnocování bylo nezbytné k tomu, aby následující
kód neskonšil `NullPointerException`.

/---code
(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:

/---code
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*":[t], 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é *thunk*y.

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

Ve Scale je to možné emulovat takto:

/---code
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:

- "Dijkstra upozornil, že *short-circuit* operátory porušují pravidla
  distributivity":[d] a měli bychom se jim vyhýbat, neboť ztěžují porozumění
  programu.

---

1) Jmenoval se Lispy a byl zamýšlený jako skriptovací nástroj pro
"asciiblog":[a]. 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.

[fr]: https://twitter.com/calaverainfo
[op]: https://calavera.info/v3/blog/2018/05/21/operatory-nejsou-funkce.html
[a]: https://github.com/kaja47/asciiblog
[e]: https://en.wikipedia.org/wiki/Evaluation_strategy
[t]: https://en.wikipedia.org/wiki/Thunk
[d]: https://en.wikipedia.org/wiki/Short-circuit_evaluation


Syntéza datových struktur a programů [syntetizace]
=====
2018-06-21

"Generalized data structure synthesis":[g] 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":[t] 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":[f]).

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.

[g]: https://blog.acolyer.org/2018/06/21/generalized-data-structure-synthesis/
[t]: https://github.com/papers-we-love/papers-we-love/raw/master/design/out-of-the-tar-pit.pdf
[f]: http://funkcionalne.cz/2012/12/out-of-the-tar-pit/


ISPC, SPMD a SIMD [ispc-spmd-simd]
=====
2018-06-09
# CPU, SIMD

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

- "The story of ispc: origins (part 1)":[http://pharr.org/matt/blog/2018/04/18/ispc-origins.html]
- "The story of ispc: volta is born (part 2)":[http://pharr.org/matt/blog/2018/04/19/ispc-volta-is-born.html]
- "The story of ispc: going all in on volta (part 3)":[http://pharr.org/matt/blog/2018/04/20/ispc-volta-going-all-in.html]
- "The story of ispc: C's influence and implementing SPMD on SIMD (part 4)":[http://pharr.org/matt/blog/2018/04/21/ispc-volta-c-and-spmd.html]
- "The story of ispc: first benchmark results (part 5)":[http://pharr.org/matt/blog/2018/04/22/ispc-volta-first-results.html]
- "The story of ispc: first users and modern CPUs coming through (part 6)":[http://pharr.org/matt/blog/2018/04/23/ispc-volta-users-and-ooo.html]
- "The story of ispc: Bringing up AVX and giving something back to LLVM (part 7)":[http://pharr.org/matt/blog/2018/04/25/ispc-volta-avx.html]
- "The story of ispc: more on optimizations and performance (part 8)":[http://pharr.org/matt/blog/2018/04/26/ispc-volta-more-on-performance.html]
- "The story of ispc: the open source release and the end of volta (part 9)":[http://pharr.org/matt/blog/2018/04/27/ispc-volta-open-source.html]
- "The story of ispc: spreading the world and leaving Intel (part 10)":[http://pharr.org/matt/blog/2018/04/28/ispc-talks-and-departure.html]
- "The story of ispc: retrospective (part 11)":[http://pharr.org/matt/blog/2018/04/29/ispc-retrospective.html]

Všechno začalo s "*Larrabee*":[l] - 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*":[xp] 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áder[[1]] obohacených o široké SIMD jednotky +
4x"SMT":[ht]. 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":[mz]. 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.":[fm]. 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í:

- "Von Neumannovy lži":[http://funkcionalne.cz/2017/05/von-neumannovy-lzi/]
- "Závislost je špatná (pro vaše programy i pro váš hardware)":[http://funkcionalne.cz/2017/01/zavislost-je-spatna-pro-vas-program-i-pro-vas-hardware/]
- "Úvod do podivností moderního hardwaru, které vás budou budit ze spaní":[http://funkcionalne.cz/2016/07/uvod-do-podivnosti-moderniho-hardwaru-ktere-vas-budou-budit-ze-spani/]
- "Někdy je nejchytřejší nedělat nic chytrého (další kapitola nekonečného příběhu o optimalizaci)":[http://funkcionalne.cz/2016/03/nekdy-je-nejchytrejsi-nedelat-nic-chytreho-dalsi-kapitola-nekonecneho-pribehu-o-optimalizaci/optimalizaci]
- "ispc: A SPMD Compiler for High-Performance CPU Programming":[http://pharr.org/matt/papers/ispc_inpar_2012.pdf]
- "Sierra: A SIMD Extension for C++":[http://compilers.cs.uni-saarland.de/papers/lhh14.pdf]

---

1) Tyto jádra vycházejí z originálních "Pentií":[p], stejně jako z nich vycházely rané Atomy.

[m]: https://twitter.com/Love2Code/status/1004370909170487296
[s]: https://www.cs.cmu.edu/afs/cs/academic/class/15869-f11/www/lectures/07_gpucore.pdf
[l]: https://en.wikipedia.org/wiki/Larrabee_(microarchitecture)
[p]: https://en.wikipedia.org/wiki/P5_(microarchitecture)#P54C
[sp]: https://en.wikipedia.org/wiki/SPMD
[xp]: https://en.wikipedia.org/wiki/Xeon_Phi
[mz]: http://funkcionalne.cz/2013/11/poznamka-k-moorovu-zakonu-a-rychlosti-procesoru/
[fm]: http://funkcionalne.cz/2017/06/horici-kremik-nasobeni-matic/
[ht]: http://funkcionalne.cz/2015/01/hyper-threading-aneb-jak-sakra-muze-bezet-vic-vlaken-na-jednom-jadre/


Konec Intelu, konec Moorova zákona, konec světa takového jaký známe [konec-intelu-a-moorova-zakona]
=====
2018-04-06
# CPU

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)":[ht].

Některé z těchto instrukcí můžou být "SIMD, které dokáží o něco navýšit
výkon":[simd]. 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":[s]. 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":[s].

---

Pozn:

- Intel nejvíce profituje ze serverového trhu, kam prodává velký silikon. V této
  oblasti slibuje několik zajímavostí jako mnohajádrový je Xeon Phi nebo Xeony s
  FPGA.
- Pro ukázku bona fide "specializovaného hardwaru se podívejte třeba na TPU":[t].
- Doufám, že uspěje "otevřená architektura RISC-V":[r], která je na tuto
  budoucnost připravovaná.

---

Relevantní čtení:

- "Čím více se věci mění, tím více zůstávají stejné":[http://funkcionalne.cz/2016/05/cim-vice-se-veci-meni-tim-vice-zustavaji-stejne/] (historická perspektiva)
- "Závislost je špatná (pro vaše programy i pro váš hardware)":[http://funkcionalne.cz/2017/01/zavislost-je-spatna-pro-vas-program-i-pro-vas-hardware/] (závislosti limitují užitečné ILP)
- "Za jak dlouho procesor vynásobí tisíc čísel":[http://funkcionalne.cz/2015/05/za-jak-dlouho-procesor-vynasobi-tisic-cisel/]
- "Úvod do podivností moderního hardwaru, které vás budou budit ze spaní":[http://funkcionalne.cz/2016/07/uvod-do-podivnosti-moderniho-hardwaru-ktere-vas-budou-budit-ze-spani/]
- "Von Neumannovy lži":[http://funkcionalne.cz/2017/05/von-neumannovy-lzi/]
- "Dualismus hardwaru a softwaru, strojů a virtuálních strojů":[http://funkcionalne.cz/2016/03/dualismus-hardwaru-a-softwaru-stroju-a-virtualnich-stroju/]

[ht]: http://funkcionalne.cz/2015/01/hyper-threading-aneb-jak-sakra-muze-bezet-vic-vlaken-na-jednom-jadre/
[simd]: http://funkcionalne.cz/2013/11/poznamka-k-moorovu-zakonu-a-rychlosti-procesoru/
[s]: https://www.eejournal.com/article/fifty-or-sixty-years-of-processor-developmentfor-this/
[t]: https://www.youtube.com/watch?v=fhHAArxwzvQ
[r]: https://en.wikipedia.org/wiki/RISC-V


Meltdown, Spectre a branch prediction [meldown-spectre-branch-prediction]
=====
2018-01-31
# CPU

Na Poslední Sobotě, kde jsem mluvil o Meltdown a Spectre ("slajdy zde":[sl]),
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":[fbp] a
trochu i "tady":[fbh]. Š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":[w].
Mnohem lepší úvod však "poskytuje Dan Luu na svém blogu":[d]. Pokud vás toto
téma zajímá, rozhodně si jeho článek přečtěte. ("Už jsem ho tu vychvaloval":[b])

Zajímavý ja také paper "The YAGS Branch Prediction Scheme":[y], 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":[n].
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)":[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":[r] chránící před druhou variantou útoku
Spectre. Nepřímý skok, který by se zkompiloval jako prosté

/---code
jmp *%r11
\---

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

/---code
  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í:

- "Branch Prediction and the Performance of Interpreters - Don't Trust Folklore":[f] - branch prediction je natolik efektivní, že správně odhaduje závislé skoky v interpretech.
- "Čím více se věci mění, tím více zůstávají stejné":[fc]
- "KPTI/KAISER Meltdown Initial Performance Regressions":[http://www.brendangregg.com/blog/2018-02-09/kpti-kaiser-meltdown-performance.html]

[sl]: https://deadbeef.k47.cz/files/meltdown.pdf
[fbp]: http://funkcionalne.cz/2014/11/branch-prediction-modernich-procesoru/
[fbh]: http://funkcionalne.cz/2016/07/uvod-do-podivnosti-moderniho-hardwaru-ktere-vas-budou-budit-ze-spani/
[fc]: http://funkcionalne.cz/2016/05/cim-vice-se-veci-meni-tim-vice-zustavaji-stejne/
[w]: https://en.wikipedia.org/wiki/Branch_predictor#Implementation
[d]: https://danluu.com/branch-prediction/
[y]: http://web.eecs.umich.edu/~tnm/papers/yags.pdf
[n]: https://www.cs.utexas.edu/~lin/papers/hpca01.pdf
[btb]: https://en.wikipedia.org/wiki/Branch_target_predictor
[r]: https://support.google.com/faqs/answer/7625886
[f]: https://hal.inria.fr/hal-01100647/document
[b]: branch-prediction


Poznámky k výkonu [poznamky]
=====
2017-12-28
# JVM, CPU

Před nějakou dobou mi twitterem proletěla prezentace *Adventures in efficiency
and performance* ("slajdy":[sli], "video":[vid]), 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:

/---code
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:

/---code
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":[cmov]), 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:

/---code
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ů":[n] 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í":[sg]).

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).

/---code
     | -- 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í:

- "Hořící křemík & násobení matic":[n]
- "Mikrobenchmarky jsou těžké":[mb]
- "Závislost je špatná (pro váš program i pro váš hardware)":[za]
- "Von Neumannovy lži":[vn]
- "Mýtus o O(1) paměti":[my]
- "Za jak dlouho procesor vynásobí tisíc čísel":[ti]
- "Intel 64 and IA-32 Architectures Optimization Reference Manual":[opt]
- "Úvod do podivností moderního hardwaru, které vás budou budit ze spaní":[uv]

[h]: hugetables
[sli]: https://d-d.me/talks/scalaworld2017/
[vid]: https://www.youtube.com/watch?v=8mFl8fywIP4
[opt]: https://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-optimization-manual.html
[n]: http://funkcionalne.cz/2017/06/horici-kremik-nasobeni-matic/
[mb]: http://funkcionalne.cz/2017/04/mikrobenchmarky-jsou-tezke/
[vn]: http://funkcionalne.cz/2017/05/von-neumannovy-lzi/
[my]: http://funkcionalne.cz/2016/09/mytus-o-o1-pameti/
[za]: http://funkcionalne.cz/2017/01/zavislost-je-spatna-pro-vas-program-i-pro-vas-hardware/
[ti]: http://funkcionalne.cz/2015/05/za-jak-dlouho-procesor-vynasobi-tisic-cisel/
[uv]: http://funkcionalne.cz/2016/07/uvod-do-podivnosti-moderniho-hardwaru-ktere-vas-budou-budit-ze-spani/
[cmov]: https://en.wikipedia.org/wiki/Predication_(computer_architecture)
[sg]: https://en.wikipedia.org/wiki/Gather-scatter_(vector_addressing)


Java, Scala a regulární výrazy #4 - líné regexy a StackOverflowError [regex-4]
=====
2017-12-19
# Java, Scala, regex

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

/---code
("\uD83D\uDC09 "*100000).matches(".*")
\---

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

/---code
("\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 `char`y a je hned následovaný jedno`char`ovou
mezerou. `.` tedy střídavě matchuje jeden a dva `char`y a proto vždy dělá
rekurzivní volání a eventuálně přeteče zásobník ("kód ve třídě Curly":[c],
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ě":[r].

[c]: https://github.com/dmlloyd/openjdk/blob/jdk9/jdk9/jdk/src/java.base/share/classes/java/util/regex/Pattern.java#L4339
[d]: http://www.fileformat.info/info/unicode/char/1f409/index.htm
[r]: regex-5


Java, Scala a regulární výrazy #3 - rychlost [regex-3]
=====
2017-12-05
# Java, Scala, regex

Jak je na tom výkon regulárních výrazů ve srovnání s ručně psanými parsery?

Otestoval jsem to na parsování logů webserveru.

Regulární výraz vypadá takhle:

/---code
"""^(\S++) (\S++) (\S++) \[([^]]++)\] "((?:\\"|[^"])++)" (\d++) (\d++|-) "((?:\\"|[^"])*+)" "((?:\\"|[^"])*+)".*$""".r
\---

"Kód ručně napsaného parseru má 55 řádků":[g] a zabral mi přibližně stejně
dlouho jako odladění regexu. Obě varianty vyprodukují identické výsledky.

Jako vstupní data jsem použil vzorek 1680000 řádků logu "k47.cz":[k]. Regex je
zpracuje za 9.26 vteřiny. Ruční variantě to trvá 1.3 vteřiny a z toho asi 0.3
vteřiny zabere jen alokace pod-řetězců.

Ve výsledku je regex asi 7x pomalejší než ručně psaný kód.

[k]: https://k47.cz
[g]: https://gist.github.com/kaja47/5252063daabdd19b69caac524d8b0e6c


Java, Scala a regulární výrazy #2 - rychlost [regex-2]
=====
2017-11-27
# Java, Scala, regex

Stará poučka říká, že v Javě bychom měli regulární výrazy vždy dopředu
zkompilovat a pak je opakovaně používat, protože kompilování je časově náročné.

"V Javě je na to volání":[p] `Patten.compile("^===+$")`. "Ve Scale je možné
použít kompaktnější zápis":[r] za pomocí kouzel implicitních metod
`"^===+$".r`.

Ale jak pomalé to vlastně je? To se dá jednoduše zjistit.

Vytáhl jsem JMH, napsal benchmark, který hledá jednoduchý vzor. Jednou vzor
nekompiluje, podruhé používá předkompilovaný vzor a potřetí hledá regex jen
když je to nezbytně nutné.

/---code
@State(Scope.Thread)
class regex {

  var lines: Array[String] = _
  val regex = """^===+$""".r

  @Setup def prepare() = {
    lines = io.Source.fromFile("export.txt").getLines.toArray
  }

  @Benchmark def notCompiled(): Int =
    lines.count(l => l.matches("^===+$"))

  @Benchmark def compiled(): Int =
    lines.count {
      case regex() => true
      case _ => false
    }

  @Benchmark def compiledWithCheck(): Int =
    lines.count { l => (l.length > 0 && l.charAt(0) == '=') && regex.findFirstMatchIn(l).nonEmpty }
}
\---

Jako testovací data jsem použil kompletní export zdrojových textů blogu
"k47.cz":[k], které mají dohromady něco kolem 8 MB a 143000 řádek textu.

Výsledky jsou následující:

/---code
Benchmark           Mode   Cnt    Score    Error  Units
notCompiled        thrpt     6   28,936 ±  2,298  ops/s
compiled           thrpt     6   94,120 ±  1,195  ops/s
compiledWithCheck  thrpt     6  526,849 ± 96,101  ops/s
\---

Kompilovaný regex je tři-a-něco-krát rychlejší než nekompilovaný. Ale ten
zaostává za případem, kdy se vyhodnocování regexu úplně vyhnu. Přitom regex by
měl selhat hned potom, co přečte první znak a tedy by neměl dělat víc práce,
než explicitní kontrola. Ale očividně má nezanedbatelnou režii.

Pokud regex nebude často prováděn, je rychlejší dělat něco jako:

/---code
// zkompilovaný regex
val linkRegex = """(?x) " ([^"]+?) " : \[ ([^\]\n]+?) \]""".r
val linkCheck = "\":["

// používat ho následovně
if (txt.contains(linkCheck)) {
  linkRegex.replaceAllIn(txt, m => makeLink(m))
}
\---

Narychlo zkontrolovat, jestli zdrojový řetězec obsahuje nějakou fixní část
regexu a teprve potom nechat regex dělat těžkou práci. Ale jako v případě každé
optimalizace je třeba profilovat a benchmarkovat.

Tento přístup zrychlil renderování textu "asciiblogu":[a] o 75%.


Relevantní čtení:

- "Mikrobenchmarky jsou těžké":[m]

[m]: http://funkcionalne.cz/2017/04/mikrobenchmarky-jsou-tezke/
[k]: https://k47.cz
[a]: https://github.com/kaja47/asciiblog
[p]: https://docs.oracle.com/javase/7/docs/api/java/util/regex/Pattern.html
[r]: https://www.scala-lang.org/api/current/scala/util/matching/Regex.html


Java, Scala a regulární výrazy [regex-1]
=====
2017-11-26
# Java, Scala, regex

Poslední dobou zjišťuji, že práce s regulárními výrazy v Javě a Scale je
neuspokojivá, matoucí a API nikdy nenabízí přesně to, co bych chtěl.

Scala má "krásně vypadající metodu":[rf] `Regex#replaceAllIn(String, Match =>
String)`. Na první pohled je všechno jasné: Každý výskyt regulárního výrazu v
prvním argumentu je předán funkci `Match => String`. Objekt typu `Match`
reprezentuje výskyt vzoru. Funkce ho vezme jako argument a vyprodukuje string,
který ho nahradí. Co by na tom mohlo být komplikovaného, žeano?

Jednoduché volání, které na první pohled vypadá jako identita, není bezpečné:

/---code
regex.replaceAllIn(str, (m: Match) => m.group(0))
\---

`m.group(0)` představuje celou shodu (ostatní indexy jsou uzávorkované výrazy v
regexu, `m.group(1)` jsou první závorky, `m.group("named")` jsou
závorky pojmenované `named`) .

V čem je problém?

V tom, že výsledek funkce se nepoužije verbatim pro nahrazení, ale je
interpretován. Každý výskyt řetězců `$0` - `$9` je interpretován jako podvýraz
a `\$` znamená literál `$`. Když vstupní data obsahují dolar následovaný
číslem, skončí to přinejlepším výjimkou, přinejhorším to udělá něco nečekaného.
A to není to, co by člověk čekal nebo chtěl. V dokumentaci je toto chování
dobře popsané, ale nepůsobí to, že by to tak mělo být.

Korektní verze by měla vypadat takhle:

/---code
regex.replaceAllIn(str, (m: Match) => Regex.quoteReplacement(m.group(0)))
\---

Interpretace stringu je přežitek "starších API":[rp], které nenabízely
nahrazení přes fukci:

/---code
regex.replaceAllIn(str, replace: String)
\---

V tomto případě nemůžu specifikovat logiku, která vypočítá nahrazovací string a
proto jsou použity zpětné reference jako `$0` - `$9`. Ty poskytují aspoň nějakou
rudimentární flexibilitu.

Problém je v tom, že výsledný string musí být escapován a *hned potom* je
interpretován (pro `$` a `\$`), což je zbytečná práce, která stojí zbytečný čas.[[1]]

Ocenil bych jasné API s metodami jako

- `Regex#replaceAllByPattern`
- `Regex#replaceAllByString`

které jasně říkají, co dělají a uživatel si může vybrat přesně to chování,
které potřebuje.

---

1) Dodatek: I když má `quoteReplacement` měřitelnou režii, je téměř
zanedbatelná. "Implementace počítá s tím":[i], že v naprosté většině případů
nebude třeba nic escapovat.

[rf]: https://www.scala-lang.org/files/archive/nightly/2.12.x/api/2.12.x/scala/util/matching/Regex.html#replaceAllIn(target:CharSequence,replacer:scala.util.matching.Regex.Match=%3EString):String
[rp]: https://www.scala-lang.org/files/archive/nightly/2.12.x/api/2.12.x/scala/util/matching/Regex.html#replaceAllIn(target:CharSequence,replacement:String):String
[i]: http://hg.openjdk.java.net/jdk10/master/file/be620a591379/src/java.base/share/classes/java/util/regex/Matcher.java#l809


Java - zostřování obrázků
======
2017-11-21
# Java

V Javě se dají obrázky jednoduše zostřit pomocí tříd "Kernel":[k] a "ConvolveOp":[c].

/---code
def sharpen(src: BufferedImage): BufferedImage = {
  val kernel = new Kernel(3, 3, Array(-1f, -1f, -1f, -1f, 9f, -1f, -1f, -1f, -1f))
  val op = new ConvolveOp(kernel, ConvolveOp.EDGE_NO_OP, null)
  op.filter(src, null)
}
\---

Klasický příklad matice pro zostření, která je zmíněna snad v každém tutoriálu:

/---code
-1 -1 -1
-1  9 -1
-1 -1 -1
\---

Znamená to znásobit hodnotu pixelu 9x a odečíst od něj hodnoty všech
sousedních. To zostří obrázek, ale efekt je příliš silný. Když chci jemnějí
detaily, je potřeba jiná matice. Důležité je, aby její součet byl 1.

Takováhle matice povede k delikátnějšímu zostření:

/---code
-0.1 -0.1 -0.1
-0.1  1.8 -0.1
-0.1 -0.1 -0.1
\---

Funkce, která dělá zostředí volitelné intenzity, může vypadat takhle:

/---code
def sharpen(src: BufferedImage, strength: Float): BufferedImage = {
  require(strength > 0 && strength < 1)
  val arr = Array.fill[Float](9)(-strength)
  arr(4) = 8 * strength + 1
  val kernel = new Kernel(3, 3, arr)
  val op = new ConvolveOp(kernel, ConvolveOp.EDGE_NO_OP, null)
  op.filter(src, null)
}
\---

[k]: https://docs.oracle.com/javase/8/docs/api/index.html?java/awt/image/Kernel.html
[c]: https://docs.oracle.com/javase/8/docs/api/index.html?java/awt/image/ConvolveOp.html


Koherence cache a atomické operace [koherence-cache-atomicke-ops]
=====
2017-10-07
# CPU

Pokud vás zajímají nízkoúrovňové detaily procesorů a konkrétně jak
multi-procesorový systém udržuje koherentní pohled na celou paměť
prostřednictvím MESI protokolu, budou vás zajímat tyhle dva články:

- "Cache coherency primer":[https://fgiesen.wordpress.com/2014/07/07/cache-coherency/]
- "Atomic operations and contention":[https://fgiesen.wordpress.com/2014/08/18/atomics-and-contention/]

Jestli vám to nestačí a chcete se dozvědět víc (ideálně *všechno*), doporučuji
tuto bichli:

- "A Primer on Memory Consistency and Cache Coherence":[b]

Relevantní čtení:

- "Memory Barriers: a Hardware View for Software Hackers":[p]
- "Diving Deeper into Cache Coherency":[dd]
- "Memory Barriers/Fences":[f]
- "Cache Coherence - Onur Mutlu":[v2]
- "Computer Architecture - Cache Coherence Protocols":[v1]
- "Memory Coherence in Shared Virtual Memory Systems":[sh] (Tohle je zajímavý
  článek. Píše o tom, jak postavit systém s koherentní sílenou pamětí z
  několika strojů. Používá klasický princip *one more level of indirection*).

[b]: https://class.stanford.edu/c4x/Engineering/CS316/asset/A_Primer_on_Memory_Consistency_and_Coherence.pdf
[p]: http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.07.23a.pdf
[f]: https://mechanical-sympathy.blogspot.cz/2011/07/memory-barriersfences.html
[dd]: http://psy-lob-saw.blogspot.cz/2013/09/diving-deeper-into-cache-coherency.html
[sh]: http://www.cs.virginia.edu/~zaher/classes/CS656/li.pdf
[v2]: https://www.youtube.com/watch?v=flbg-MKkwmk
[v1]: https://www.youtube.com/watch?v=L5FtGNMGyRM


Nejrychlejší hashmapa pod sluncem [robin-hood-hashmap]
=====
2017-10-05
# DS

Článek "I Wrote The Fastest Hashtable":[hash] popisuje, jak může vypadat
nejrychlejší hashmapa pod sluncem, která poráží všechny vysoce optimalizované
konkurenty.

Interně nepoužívá běžné *open addressing*, *linear probing* ani "cucko
hashing":[ch], ale o něco méně známou techniku Robin Hood hashování. Ta se
nesnaží snížit množství kolizí ale průměrnou délku kolizního řetězce. Odtud
pochází onen Robin Hood v názvu: bohatým bere (krátký řetěz kolizí) a chudým
dává (dlouhý řetěz kolizí).

To efektivně vede k `log(n)` nejhoršímu času přístupu a možnosti naplnit
tabulku velice blízko 100%

V lineárním *probingu* je běžné, že dlouhé kolizní řetězce rostou nejrychleji.
To dává smysl - zabírají hodně slotů a proto je velká šance, že do nich spadnou
další klíče a délka řetězce dál naroste. Robin Hood při vložení efektivně
provádí insertion sort, který řadí podle počtu slotů o kolik je klíč vzdálený
od své ideální pozice.

Krátké kolizní řetězce mají také výhodu, že kdy žádaný klíč bude blízko, může
se nacházet na stejné cache line jako první zkontrolovaný slot a proto není
třeba načítat další data z RAM.

Relevantní čtení:

- "Kolize hashů pro mírně pokročilé":[kol]
- "Robin Hood Hashing should be your default Hash Table implementation ":[robin1]
- "More numerical experiments in hashing: a conclusion":[robin2]

[hash]: https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/
[kol]: http://funkcionalne.cz/2016/02/kolize-hashu-pro-mirne-pokrocile/
[ch]: https://en.wikipedia.org/wiki/Cuckoo_hashing
[robin1]: http://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/
[robin2]: http://www.pvk.ca/Blog/more_numerical_experiments_in_hashing.html


Dekódování x86 instrukcí [x86-decode]
=====
2017-09-23
# CPU

x86 je barokní architektura, která na sebe za čtyři dekády existence nabalila
spoustu bahna. Jde o jedinou z mála "přežívajících CISC ISA":[risc] a má
všechno, co od se od takové sady očekává: Mraky instrukcí proměnné délky, různé
adresovací módy a zpětnou kompatibilitu s relikty minulosti.

Ale "kolik instrukcí moderní x86 se všemi rozšířeními vlastně má":[how]? Tuto
otázku překvapivě není jednoduché zodpovědět. Záleží jak člověk počítá. Počet
položek v Intelích manuálech, počet mnemonických zkratek, počet forem? Může
jich být něco mezi 1503 a 6000 podle toho, co je považováno za unikátní
instrukci.

A teď jak tohle dokáže procesor dekódovat? x86 kraluje severům, desktopům a
laptopům a nejde jen o důsledek prehistorického nasazení v IBM PC. Moderní x86
se umí hýbat a když všechno jede jak má, dokážou každý takt vykonat 4-5
instrukcí. To znamená načíst z paměti/cache, dekódovat, provést a zapsat
výsledek až pěti operací proměnné délky z tisíců různých forem.

Nejjednodušší je pochopitelně podvádět a nic nedekódovat. Proto procesory nesou
L0 cache určenou pro instrukce již dekódované na interní mikro-operace.

Moderní x86 jádra, ale i přesto dokážou rychle dekódovat proud čerstvých
instrukcí. Klíčem je paralelní *pre-decode*, který nejdřív zjistí jen délky
instrukcí.

Příklad: Jádro v každém taktu natáhne 16B kódu, *pre-decode* pro každý bajt z
tohoto bloku zjistí, jak by byla instrukce dlouhá, kdyby začínala na této
pozici. To se dá udělat paralelně, protože není třeba brát zřetel na
závislosti. x86 navíc není zas tak barokní, vypadá na první pohled a má určitou
regularitu, kdy velké skupiny instrukcí mají stejnou délku. To značně
zjednodušuje návrh *pre-decode* fáze.

Délky instrukcí se spočítají za jeden takt a pošlou se do další fáze pipeline.

Tam je už třeba brát v potaz sekvenci instrukcí. Když má první instrukce délku
3 bajty, dekodér přeskočí 3 bajty (a tedy všechny délky, který *pre-deceode*
spekulativně spočítal). Teď je jasné, že na pozici +3B začíná validní
instrukce, délka je už spočítaná a dekodér jen zjistí, do jaké funkční jednotky
onu operaci poslat.

V procesoru není velký switch s ramenem pro každou podobu každé instrukce, ale
tato znalost je rozložena napříč čipem.

Relevantní čtení:

- "Breaking the x86 ISA":[isa] (prezentace o pokusech zjistit nezdokumentované
  instrukce na x86 procesorech)
- "What's the definition of RISC?":[risc]
- "Za jak dlouho procesor vynásobí tisíc čísel":[f1]
- "Hyper-threading aneb Jak sakra může běžet víc vláken na jednom jádře?":[f2]
- "L1I cache a iTLB – když ani spekulace nepomůžou":[f3]
- "Hardware is the new software":[hwsw] ("paper":[hwswp])

[how]: https://fgiesen.wordpress.com/2016/08/25/how-many-x86-instructions-are-there/
[isa]: https://www.blackhat.com/docs/us-17/thursday/us-17-Domas-Breaking-The-x86-ISA.pdf
[hwsw]: https://blog.acolyer.org/2017/06/19/hardware-is-the-new-software/
[hwswp]: https://www.microsoft.com/en-us/research/wp-content/uploads/2017/05/baumann-hotos17.pdf
[risc]: https://danluu.com/risc-definition/
[f1]: http://funkcionalne.cz/2015/05/za-jak-dlouho-procesor-vynasobi-tisic-cisel/
[f2]: http://funkcionalne.cz/2015/01/hyper-threading-aneb-jak-sakra-muze-bezet-vic-vlaken-na-jednom-jadre/
[f3]: http://funkcionalne.cz/2015/05/l1i-cache-a-itlb-kdyz-ani-spekulace-nepomuzou/


Energetická efektivita programovacích jazyků [energeticka-efektivita]
=====
rel: datacentrum-z-mobilu
2017-09-21

Software má dopad na svět. Pozitivní i negativní. Tím negativním je spotřeba
energie, která někde musí být vyrobená a většinou je to z fosilních paliv. V
roce 2015 byl Evropský průměr kolem 0.35kg CO<sub>2</sub> na vyrobenou
kilowatthodinu. Jeden server s 1000W zdrojem tedy za rok přispěje ke 3 tunám
CO<sub>2</sub> v atmosféře. To je něco, co bychom stále měli mít na srdci.

Neotřelým nápadem bylo například "postavit datacentrum ze zrecyklovaných
mobilů":[d], o kterém jsem se tu už zmiňoval. Mobilní procesory mají dobrý
poměr výpočetní výkon per watt a navíc není třeba vyrábět nový hardware.

Otázkou efektivity se také zabírá paper "Energy Efficiency across Programming
Languages":[p].

Výsledek je celkem nepřekvapivý: Rychlejší jazyky, tedy ty ve kterých je možné
napsat řešení, která vypočítá výsledek co nejrychleji, spotřebují méně energie.
Jde o klasické kandidáty C, C++ a také mnohem novější "Rust":[r]. Java se za
nimi drží v závěsu. I když vztah mezi časem a energií není zcela lineární,
kompilované jazyky jasně vedou v absolutní spotřebě joulů.

Měření byla provedena na drobných benchmarcích a nikoli velkých produkčních
aplikacích. Je tedy třeba brát čísla s rezervou, jak to zmiňoval "Cliff Click
zmiňoval ve svém podcastu":[ccp], když mluvil o "srovnání Javy s C++":[cccc].
Například aplikace napsaná v PHP nemusí nutně spolykat 28x víc šťávy než její C
protějšek, když většinu času stráví čekáním na databázi, která je napsaná ve
vysoce optimalizovaném C++. Podobně tomu je s regulárními výrazy, kde i
neefektivní interpretované jazyky používají rychlé regex jádro.

Když už tu píšu o efektivitě, měl bych se taky zmínit o jejím pravém opaku - o
bitcoinu. Ten je největším provinilcem na poli zbytečně propálené energie. Dnes
celá síť spolyká víc energie než dokáže vyprodukovat nukleární reaktor a
předpokládá se, že v roce to bude víc než celé Dánsko. To je děsivé číslo.
Naštěstí se začínají objevovat "návrhy jak bitcoinu podobnou síť použít ke
smysluplné práci":[bc].

[p]: http://greenlab.di.uminho.pt/wp-content/uploads/2017/09/paperSLE.pdf
[ccp]: cliff-click-podcast
[bc]: https://blog.acolyer.org/2017/09/06/rem-resource-efficient-mining-for-blockchains/
[d]: datacentrum-z-mobilu
[cccc]: http://www.cliffc.org/blog/2017/09/18/java-vs-cc-the-podcast/
[r]: rust-a-parsery


Programming and Performance podcast [cliff-click-podcast]
=====
2017-09-19

"Cliff Click":[ccb] začal s podcastem *Programming and Performance*. Zatím jsou
k dispozici dvě epizody: "Of Bugs and Coding Styles":[ccbc] a "Java vs
C/C++":[cccc], a nebojím se, že do budoucna bude mít nouzi o zajímavá témata.
Přece jenom je to *ten* Cliff Click, který přivedl JIT v JVM na světlo světa a
pracoval v Azulu, vyvíjející vlastní procesory speciálně určené pro Java
aplikace.

Z jeho minulých přednášek mi v paměti utkvěly například: "Java on a 1000 Cores
- Tales of Hardware / Software CoDesign":[j1000], "A Crash Course in Modern
Hardware":[ccmh] nebo "A JVM Does That?":[ajdt].

[ccb]: http://www.cliffc.org/blog/
[cccc]: http://www.cliffc.org/blog/2017/09/18/java-vs-cc-the-podcast/
[ccbc]: http://www.cliffc.org/blog/2017/09/16/of-bugs-and-coding-styles/
[j1000]: https://www.youtube.com/watch?v=5uljtqyBLxI
[ajdt]: https://www.youtube.com/watch?v=uL2D3qzHtqY
[ccmh]: https://www.infoq.com/presentations/click-crash-course-modern-hardware


B-stromy, persistence, copy-on-write a Btrfs [btrfs-paper]
=====
2017-09-17
# FS

"B-trees, Shadowing, and Clones":[bt], Ohad Rodeh

Tento paper položil základy Btrfs - *copy-on-write* souborového systému (FS),
který podporuje efektivní vytváření snapshotů a klonů.

Jako u mnoha jiných FS jsou i tady B-stromy použité jako klíčová datová
struktura. Jediná odlišnost oproti běžným návrhům je fakt, že se změny
neprovádí na místě a nedochází k přepisování existujících dat.

Lidi z funkcionálních kruhů tohle dobře znají. Jde o obyčejné "plně
persistentní stromy":[p] založené na kopírování cesty od listu ke kořeni. V
hantýrce FS podivínů se této technice říká *shadowing*, ale jde o stejný
princip - při modifikaci B-stromu (používají se B+stromy, které mají v listech
ukazatele na datové stránky), je vytvořena nová cesta od listu ke kořeni. Odtud
pochází ono *copy-on-write* - při zápisu se vždy kopíruje, nikdy se
nepřemazávají stará data, ale je vytvořena nová kopie. Staré verze existují na
disku dokud na ně něco odkazuje a pak jsou odstraněny garbage collectorem.

Logicky z těchto starých persistentních verzích je možné vytvářet *snapshoty* a
klony, tedy editovatelné historické větve souborového systému, které s tím
původním sdílí maximum možných dat. To je opět klasické strukturální sdílení
(*structural sharing*), které každý FP akolyta zná jako vlastní boty.

Ve světě souborových systémů je třeba se vypořádat s explicitní alokací a
uvolňováním smazaných bloků. Protože navrhovaný FS může sdílet datové bloky a
strukturu B-stromů mezi různými klony, je nutné pro každý z nich udržovat čítač
referencí, který udává kolik pointerů odkazuje na ten který blok. Čítače
referencí jsou také udržovány v *copy-on-write* B-stromech. (CoW mechanismus je,
jak je vidět, důležitý pro odolnost systému proti pádu.)

Čítače referencí umožňují levné klonování - stačí jen zkopírovat kořen stromu a
aktualizovat refcount všech potomků (nově na ně ukazuje o jeden rodič více).
Všechny další změny se provádějí líně.

Z odkazovaného článku vychází Btrfs, ale ten je - jako funkční systém a nejen
prototyp - mnohem "komplikovanější":[b].

Relevantní čtení:

- "Persistentní datové struktury":[p]
- "Střeva databází":[s]

[p]: http://funkcionalne.cz/2016/08/persistentni-datove-struktury/
[bt]: https://liw.fi/larch/ohad-btrees-shadowing-clones.pdf
[b]: https://btrfs.wiki.kernel.org/index.php/Main_Page#Developer_documentation
[s]: http://funkcionalne.cz/2016/01/streva-databazi/


Rust a parsery [rust-a-parsery]
=====
2017-09-15

Možná bych měl dát Rustu druhou šanci. Když jsem ho "před nějakou dobou
zkoušel":[d], něco mi na něm nesedělo a místo toho jsem začal experimentovat s
D. Poslední dobou ale stále častěji slyším pozitivní ohlasy na Rust a jeho
slibný systém vlastnictví objektů.

Zajímavý příklad silných stránek jazyka je "Nom, a byte oriented, streaming,
zero copy, parser combinators library in Rust:[nom]. Jak název napovídá, jde o
efektivní knihovnu *parser kombinátorů* napsanou v Rustu. Na jednu stranu
poskytuje vysokoúrovňové a skoro-deklarativní API *parser kombinátorů* (parser
vzniká kompozicí menších parserů za pomocí různých kombinátorů), na druhou
stranu nabízí nativní rychlost (Rust kompilátor používá "LLVM jako back
end":[ok]), nekopíruje paměť a přitom je bezpečný. Rust nepovolí získat pointer
do neplatného bufferu, všechno pohlídá systém vlastnictví objektů.

Relevantní čtení:

- "Writing parsers like it is 2017":[pars]
- "System programming in Rust: beyond safety":[sys]

[d]: http://funkcionalne.cz/2017/06/jazyk-d-a-radix-sort/
[nom]: http://spw15.langsec.org/papers/couprie-nom.pdf
[pars]: https://blog.acolyer.org/2017/08/15/writing-parsers-like-it-is-2017/
[sys]: https://blog.acolyer.org/2017/06/14/system-programming-in-rust-beyond-safety/
[ok]: optimalizujici-kompilator


Velké stránky paměti [hugetables]
=====
2017-09-13
# CPU

"Transparent Hugepages: measuring the performance impact":[t]

Praktická demonstrace toho jaký dopad může mít povolení velkých stránek paměti.

Mapování z virtuální na fyzickou adresu je spravováno na úrovni stránek. Ty na
x86 můžou mít několik velikostí: 4kB, 2MB nebo 1GB. Operační systém udržuje
toto mapování v paměti jako stromy (přesněji řečeno *trie*). Aby procesor
nemusel při každém přístupu do paměti procházet tímto stromem, který je taky v
paměti (nebo v lepším případě v cache), obsahuje malou cache nazývanou TLB
(*translation lookaside buffer*) pro mapování několika naposledy použitých
stránek. To vede ke stavu, že pokud chci číst ze stránky, která je v TLB, je to
rychlé, ale pokud chci číst z té, která tam není, OS musí provést *page table
walk*, najít příslušné mapování, přeložit adresu a to celou operaci značně
zpomalí. Velké stránky byly zavedeny z pochopitelných důvodů: Je jimi možné
pokrýt větší část virtuální paměti a snížit tak počet drahých *TLB miss*.

Odkazovaný článek uvádí případ Java aplikace s 200GB haldou, na které povolení
velkých stránek vede k nezanedbatelnému zrychlení. Program před změnou trávil
10% taktů jen překladem virtuální adresy na fyzickou a *page table walk*
namísto užitečné práce.

Relevantní čtení:

- "L1I cache a iTLB - když ani spekulace nepomůžou":[itlb]
- "JVM Anatomy Park #2: Transparent Huge Pages":[jap2] (ze série "JVM Anatomy
  Park":[jvm-anatomy-park])
- "How Bad Can 1GB Pages Be?":[bad] (někdy můžou velké stránky uškodit, všechno
  závisí na kontextu)

[t]: https://alexandrnikitin.github.io/blog/transparent-hugepages-measuring-the-performance-impact/
[itlb]: http://funkcionalne.cz/2015/05/l1i-cache-a-itlb-kdyz-ani-spekulace-nepomuzou/
[jap]: jvm-anatomy-park
[jap2]: https://shipilev.net/jvm-anatomy-park/2-transparent-huge-pages/
[bad]: http://www.pvk.ca/Blog/2014/02/18/how-bad-can-1gb-pages-be/


Deanonymizace agregovaných dat [deanonymizace]
=====
2017-09-11
# algo

"Trajectory recovery from Ash: User privacy is NOT preserved in aggregated
mobility data":[t]

Tohle je něco podle mého gusta. Článek ukazuje, že je možné z agregovaných
pozičních dat zpětně zrekonstruovat trajektorie jednotlivých lidí. Vychází
ze dvou předpokladů:

- lidé jsou v systému po dlouhou dobu (dvě sousední epochy obsahují agregované
  pozice víceméně stejných uživatelů)
- lidé se pohybují předvídatelně

Na těchto tezích je možné vybudovat systém, který zrekonstruuje jednotlivé
trajektorie s poměrně velkou přesností.

Když například mobilní operátor prodá agregovaná data, třetí strana z nich může
vytěžit denní trajektorie uživatelů. To jí samo o sobě poskytne informaci, kde
jednotliví lidé pracují nebo kde bydlí. Můžou zajít dál a přidat další
informace, například místa plateb a spojit tuto pseudonymní trajektorii s
konkrétní identitou.

Zajímavý je také fakt, že snížení rozlišení vede ke zvýšení přesnosti
rekonstrukce trajektorií.

Relevantní čtení:

- "Leave your phone at the door: side channels that reveal factory floor secrets":[p]

[t]: https://blog.acolyer.org/2017/05/15/trajectory-recovery-from-ash-user-privacy-is-not-preserved-in-aggregated-mobility-data/
[p]: https://blog.acolyer.org/2016/11/09/leave-your-phone-at-the-door-side-channels-that-reveal-factory-floor-secrets/


Optimalizující kompilátor [optimalizujici-kompilator]
=====
2017-09-09

"Understanding Compiler Optimization - Chandler Carruth - Opening Keynote
Meeting C++ 2015":[v]

Přednáška, která představuje fungování optimalizujícího kompilátoru.
Má tři hlavní fáze:

- úklid po frontendu kompilátoru, (nedělá žádné optimalizace, jen vygeneruje
  LLVM IR v "SSA":[ssa] formě)
- kanonizace IR (rozdílný kód, který je funkčně shodný vede k identickému IR)
- *collapse abstractions*

Tři klíčové abstrakce se kterými se potýká:

- functions, calls, and the call graph
- memory, loads and stores
- loops

[v]: https://www.youtube.com/watch?v=FnGCDLhaxKU
[ssa]: https://en.wikipedia.org/wiki/Static_single_assignment_form


Identifikace zašifrovaných videí [video]
=====
2017-09-07

"Beauty and the Burst: Remote Identification of Encrypted Video Streams":[https://beautyburst.github.io/beautyburst.pdf]

Myšlenka je jednoduchá: Online video je přenášené jako série video fragmentů,
jejichž velikost závisí na informačním obsahu dané scény. Série velikostí
představuje unikátní otisk pro každé video. Třetí strana, která pozoruje
velikosti paketů může zjistit, jaké video uživatel sleduje, a to i když je
provoz plně zašifrovaný. Pouhé velikosti zasílaných bloků stačí k velice přesné
identifikaci. ISP tak například může zjistit co jednotliví uživatelé sledují.


Heterogenní persistentní kolekce [hhamt]
=====
2017-09-05
# DS, Funkcionální programování

"Efficient Immutable Collections":[t], Michael Steindorfer

Tohle je něco podle mého gusta, *tour de force* diplomová práce (*thesis*, co
to je vlastně česky?), která zkoumá všechny možné postupy, jak implementovat
paměťově efektivní kolekce v prostředí JVM. A když říkám všechny, myslím
skutečně všechny. Autor Michael Steindorfer se nezalekne žádného problému a
nezastaví se před ničím.

---

Začalo to "Bagwellem inspirovanými":[bag] HAMT - *hash array mapped tries* -
efektivní metodou jak reprezentovat persistentí funkcionální hashmapy jako
velice široké a mělké stromy, které našly uplatnění ve standardní knihovně
Scaly a Clojure.

Ale u toho to neskončilo a Steindorfer začal postupně prezentovat sérii
zlepšení.

První z nich byl CHAMP ("Optimizing Hash-Array Mapped Tries for Fast and Lean
Immutable JVM Collections":[champ]), který drobnou změnou interní struktury
snížil spotřebu paměti, rychlost iterace a kontrolu rovnosti dvou kolekcí.

Jednou ze změn je kanonizace, kdy kolekce obsahující stejná data mají vždy
stejnou reprezentaci. To obecně neplatí, když přidávám a mažu prvky. Pokud je
kolekce vždy kanonická, jsem si jistý, že když se liší jejich struktura, jde o
dvě rozdílné kolekce a nemusím kontrolovat nic dalšího. Pokud je struktura
stejná, kolekce můžou být stejné, ale abych to potvrdil, musím je rekurzivně
porovnávat do hloubky.

Autor se pak začal zabývat specializací ("Code Specialization for Memory
Efficient Hash Tries":[spec]), tedy generováním Java tříd, které neobsahují
odkaz na pole (jak je běžné v implementaci HAMT), ale heterogenní pole
klíčů/hodnot a podstromů (respektive specializovaných primitivních hodnot) je
inlinováno přímo do těla třídy jako její atributy. To značně sníží paměťové
nároky, protože není třeba uchovávat hlavičku vnitřního pole, které je většinou
velice malé.

Problém spočívá v kombinatorické explozi počtu tříd. V naivním případě je
potřeba vygenerovat jednu třídu pro každou možnou podobu struktury uzlu. Autor
k tomu přistoupil pragmaticky. Většina stromů je malá, obsahuje nejčastěji dva
nebo tři potomky a u těchto malých stromů specializace přinese největší redukci
místa. Proto stačí vygenerovat specializace jen pro tyto případy a získat tak
největší prospěch s nejmenšími náklady.

Logickým vyústěním byla jeho PhD práce ("Efficient Immutable Collections":[t]),
která kombinuje všechny do té doby publikované články a rozvíjí je o krok dál,
směrem k efektivní reprezentaci multimap.

Ukazuje se, že stejné techniky inline bitmap, které jsou použité v HAMT k
rozlišení případů prázdný slot/klíč+hodnota/podstrom, lze rozšířit pro
diskriminaci mezi libovolným množstvím heterogenních případů, tedy například
mapování klíč->hodnota/klíč->množina hodnot a tak efektivně reprezentovat
multimapy.

Autor také krátce "prezentoval své výsledky":[vid].

Relevantní čtení:

- "Persistentní datové struktury":[pers]
- "Kolize hashů pro mírně pokročilé":[kol]

[vid]: http://www.youtube.com/watch?v=D8Y294vHdqI
[t]: https://michael.steindorfer.name/publications/phd-thesis-efficient-immutable-collections.pdf
[champ]: http://michael.steindorfer.name/publications/oopsla15.pdf
[spec]: http://michael.steindorfer.name/publications/gpce14.pdf
[pers]: http://funkcionalne.cz/2016/08/persistentni-datove-struktury/
[kol]: http://funkcionalne.cz/2016/02/kolize-hashu-pro-mirne-pokrocile/
[bag]: http://infoscience.epfl.ch/record/64398?ln=en


JVM Anatomy Park [jvm-anatomy-park]
=====
2017-09-03
# JVM, Java

Velice zajímavá série krátkých článků "Alekseye Shipilёva":[tw] o vnitřnostech a
vnitřním fungování JVM.

- "JVM Anatomy Park #1: Lock Coarsening and Loops":[https://shipilev.net/jvm-anatomy-park/1/]
- "JVM Anatomy Park #2: Transparent Huge Pages":[https://shipilev.net/jvm-anatomy-park/2-transparent-huge-pages/]
- "JVM Anatomy Park #3: GC Design and Pauses":[https://shipilev.net/jvm-anatomy-park/3-gc-design-and-pauses/]
- "JVM Anatomy Park #4: TLAB allocation":[https://shipilev.net/jvm-anatomy-park/4-tlab-allocation/]
- "JVM Anatomy Park #5: TLABs and Heap Parsability":[https://shipilev.net/jvm-anatomy-park/5-tlabs-and-heap-parsability/]
- "JVM Anatomy Park #6: New Object Stages":[https://shipilev.net/jvm-anatomy-park/6-new-object-stages/]
- "JVM Anatomy Park #7: Initialization Costs":[https://shipilev.net/jvm-anatomy-park/7-initialization-costs/]
- "JVM Anatomy Park #8: Local Variable Reachability":[https://shipilev.net/jvm-anatomy-park/8-local-var-reachability/]
- "JVM Anatomy Park #9: JNI Critical and GC Locker":[https://shipilev.net/jvm-anatomy-park/9-jni-critical-gclocker/]
- "JVM Anatomy Park #10: String.intern()":[https://shipilev.net/jvm-anatomy-park/10-string-intern/]
- "JVM Anatomy Park #11: Moving GC and Locality":[https://shipilev.net/jvm-anatomy-park/11-moving-gc-locality/]
- "JVM Anatomy Park #12: Native Memory Tracking":[https://shipilev.net/jvm-anatomy-park/12-native-memory-tracking/]

Shipilёv také přednášel o "JVM benchmarkovacím nástroji
JMH":[https://www.youtube.com/watch?v=VaWgOCDBxYw]

Relevantní čtení:

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

[tw]: https://twitter.com/shipilev/
[virt]: http://funkcionalne.cz/2015/09/jak-jvm-vola-virtualni-metody-jaka-temna-bozstva-musi-vzyvat-aby-to-bylo-aspon-trochu-rychle/


Datacentrum z mobilů [datacentrum-z-mobilu]
=====
2017-09-01

"Towards deploying decommissioned mobile devices as cheap energy-efficient
compute nodes":[dp]

Další zajímavost o které píše *The Daily Paper* - nápad postavit datacentrum z
vyřazených mobilů namísto klasických serverových kudů křemíku. To má několik
výhod, které mě zcela fascinovaly:

- Moderní smartphony mají výkonné procesory a několik giga paměti.
- Jejich poměr výkon/watt je velice příznivý.
- Jde o vyřazené telefony, které jsou zrecyklované jako jádro datacentra. To je
  zelené řešení, které neprodukuje CO<sub>2</sub> na výrobu nového hardware.
- Mobily mají baterii. Není tedy potřeba UPS/distribuovanou UPS a telefony
  můžou ve špičkách konzumovat víc energie než na kolik je dimenzováno
  datacentrum. Když později běží nevytížené, baterie se dobije.

Relevantní čtení:

- "The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines":[dc]
- "Determining application-specific peak power and energy requirements for ultra-low power processors":[https://blog.acolyer.org/2017/05/23/determining-application-specific-peak-power-and-energy-requirements-for-ultra-low-power-processors/]

[dp]: https://blog.acolyer.org/2017/08/25/towards-deploying-decommissioned-mobile-devices-as-cheap-energy-efficient-compute-nodes/
[dc]: http://www.morganclaypool.com/doi/abs/10.2200/S00193ED1V01Y200905CAC006


Propustnost pamětí [propustnost-pameti]
=====
2017-08-30
# CPU, paměť

"Memory bandwidth":[https://fgiesen.wordpress.com/2017/04/11/memory-bandwidth/],
Fabian Giesen

Tenhle článek ukazuje jaká je relativní propustnost pamětí vzhledem k CPU a
GPU. I když absolutní propustnost stoupá, s tou relativní to není tak slavné.

- Prastarý MOS 6502 z roku 1975 má propustnost 4B / instrukci
- Nové Core i7 má propustnost kolem 1B / instrukci (detaily v článku)
- Pokud beru v potaz SIMD, má ono Core i7 propustnost 0.125B / skalární operaci v SIMD instrukci
- Grafická karta GeForce GTX 1080Ti má propustnost 0.09B / skalární operaci v SIMD instrukci

Jak je vidět, tak relativní propustnost pamětí klesá i přes všechny pokroky
Moorova zákona.

Grafické karty mají paměti s obrovskou absolutní propustností, ale také mají
obrovské množství výpočetních jednotek (v případě GPU jde o velice široké SIMD
procesory, ale to je detail).

K tomu musíme přičíst, že absolutní latence DRAM klesla 4-5x od 80 let,
ale takt procesorů se zvýšil o tři řády.

To je důvod, proč jsou cache paměti na straně hardwaru a lokalita přístupu k
paměti na straně softwaru tak důležité. Procesory jsou (většinou) dostatečně
rychlé, RAM představuje úzké hrdlo.

Relevantní čtení:

- "Hořící křemík & násobení matic":[l1] (optimalizace násobení matic spočívá hlavně v lepším využití procesorové cache)
- "Lokalita v grafech a negrafech":[l2] (lokalita je důležitá)
- "Mýtus o O(1) paměti":[l3]
- "Úvod do podivností moderního hardwaru, které vás budou budit ze spaní":[l4]
- "What every programmer should know about memory":[l5]
- "Why do CPUs have multiple cache levels?":[https://fgiesen.wordpress.com/2016/08/07/why-do-cpus-have-multiple-cache-levels/]

[l1]: http://funkcionalne.cz/2017/06/horici-kremik-nasobeni-matic/
[l2]: http://funkcionalne.cz/2017/02/lokalita-v-grafech-a-negrafech/
[l3]: http://funkcionalne.cz/2016/09/mytus-o-o1-pameti/
[l4]: http://funkcionalne.cz/2016/07/uvod-do-podivnosti-moderniho-hardwaru-ktere-vas-budou-budit-ze-spani/
[l5]: http://funkcionalne.cz/2013/03/what-every-programmer-should-know-about-memory/


Branch prediction (implementace v procesorech) [branch-prediction]
=====
2017-08-28
# CPU

Dan Luu napsal dobrý článek o tom, "jak funguje a jak je implementována *branch
prediction*":[dl] v procesorech a proč je důležité, aby byla co nejpřesnější.

V běžném kódu je nepodmíněný skok (*branch*) průměrně každou pátou instrukcí. V
pipelinovaných procesorech je cíl skoku známý až v pozdějších fázích pipeline,
ale procesor potřebuje znát cíl co nejdříve, aby mohl začít načítat a dekódovat
instrukce, a v pipline nevznikla bublina. To řeší *branch predictor*, který
odhaduje díl skoku na základě dřívějšího chování. Většina skoků se chová
předvídatelně a velká část z nich je ve smyčkách. Když skočil stokrát, s
největší pravděpodobností skočí i teď.

*Branch miss* (tedy špatný odhad) znamená zahození celé pipeline, která
obsahuje instrukce z nesprávné větve programu. Pro pipeline s hloubkou 20 to
tedy znamená ztrátu ~20 taktů. Pokud je každá pátá instrukce skok a procesor by
nedělal žádné odhady vedlo by to ke ~4x zpomalení.

V článku jsou prezentovány *predictory* se vzrůstající sofistikovaností, které se
snaží zachytit stéle komplikovanější a komplikovanější vzory a omezit
patologické chování (BP je založen na hashování a proto se okrajově dotýká
hashmap, bloom filterů, count-min skečů a "kolizí hashů":[kol]).

Co největší přesnost je potřeba, protože (v prezentovaném modelu) i pouhých 5%
nepřesnosti vede k poklesu výkonu o ~20%. Proto vývoj v tomto oboru neustává.

Některé novější *predictory* jsou popsány například v:

- "The YAGS Branch Prediction Scheme":[yags] (snaží se eliminovat kolize výčtem
  negativních případů, zároveň jsou tu vysvětleny další druhy *predictorů*)
- "Dynamic Branch Prediction with Perceptrons":[perc] (BP založený na
  jednoduchých neuronových sítích, které se snaží naučit lineární funkci namísto
  historických tabulek)

Ale to ani zdaleka není vyčerpávající seznam. Mnoho dalších metod a zlepšení
bylo navrženo od té doby.

Relevantní čtení:

- "Branch prediction moderních procesorů":[bp]

[dl]: https://danluu.com/branch-prediction/
[perc]: https://www.cs.utexas.edu/~lin/papers/hpca01.pdf
[yags]: http://web.eecs.umich.edu/~tnm/papers/yags.pdf
[bp]: http://funkcionalne.cz/2014/11/branch-prediction-modernich-procesoru/
[kol]: http://funkcionalne.cz/2016/02/kolize-hashu-pro-mirne-pokrocile/