PHP kvíz (aktualizováno)

Dneska vám přináším malý PHP kvíz. Každou jeho část představuje krátký kus kódu, který s maličkou změnou najednou začne běžet pomaleji, i když dělá stejné množství práce. Vaším úkolem je poznat co to způsobuje a proč. Odpovědi můžete psát do komentářů.

(Update: Přidal jsem jeden nový kvíz a přidal měření na desktopovém CPU, na kterém rozdíly mnohem víc vynikají).


Na začátek něco jednoduchého:

define('FACTOR', 1);

$arr = [];
for ($i = 0; $i < 100000; $i++) {
        $arr[$i * FACTOR] = 1;
}

Pokud je konstanta FACTOR rovna jedné, smyčka na Atomu proběhne ze 40 milisekund. Pokud se FACTOR rovná 1048576, vykoná se za 84 vteřin.

Co to způsobuje a jak?


Další dvě otázky jsou už o něco zajímavější.

define('INTERVAL', 1000);

$arr = [];
for ($i = 0; $i < 2000000; $i++) {
  $arr[$i] = ['a' => 1+1];
}

$start = microtime(true);

for ($i = 0; $i < 1000000; $i++) {
  $arr[mt_rand(0, INTERVAL-1)];
}

$time = microtime(true) - $start;

Pokud má konstanta INTERVAL hodnotu 1000, poslední smyčka na netbookovém Atomu trvá 3 vteřiny, pokud má hodnotu 2000000, trvá 3.7 vteřin; na desktopovém Haswellu je to pak 0.9 vteřiny pro INTERVAL=1000 a 0.14 vteřiny pro INTERVAL=2000000. Proč je kód až 6× pomalejší, když se indexy generuji z většího intervalu? V jiném jazyku nebo virtuálním stroji by tento rozdíl mohl být ještě větší.


Třetí otázka se nese v podobném duchu.

$arr = [];
for ($i = 0; $i < 500000; $i++) {
  $arr[$i] = ["a" => 1+1];
}

$start = microtime(true);

for ($i = 0; $i < 500000; $i++) {
  $idx = mt_rand(0, 500000-1);
  $idx = $i; // tenhle řádek odstraním
  $arr[$idx];
}

$time = microtime(true) - $start;

Poslední smyčka na netbookovém Atomu proběhne za 1.5 vteřiny, když odstraním řádek $idx = $i, kód běží o víc jak 20% pomaleji (1.8s). Na Haswellu se smyčka vykoná za 0.11 vteřin a pokud odstraním onen řádek, tak za 0.4 vteřiny, tedy skoro čtyřikrát pomaleji. Proč, i když dělám stejné množství práce, ale index se neinkrementuje o jedničku, všechno déle? I tady platí, že v jiném jazyce nebo jiném prostředí by rozdíl mohl být mnohokrát větší.


Dodatečně přidám ještě jednu kvízovou otázku.

$arr = [];
$prefix = ""; // prefix mastavím na "x"
for ($i = 0; $i < 2000000; $i++) {
        $arr[$prefix.$i] = $i;
}

$start = microtime(true);

for ($i = 0; $i < 2000000; $i++) {
  $arr[$prefix.$i];
}

$time = microtime(true) - $start;
echo $time, "\n";

Pokud je proměnná prefix prázdný string, poslední smyčka trvá 0.24 vteřiny, pokud se $prefix rovná stringu „x“, trvá 0.36 vteřiny, ale když místo prefixu použiji postfix (indexace přes $arr[$i.$prefix]), trvá 0.46 vteřiny. Proč se tak děje?

Odpovědi pište do komentářů, za pár dnů tady zveřejním správné odpovědi.

flattr this!

Posted in Paměť, PHP | 4 Comments

Haldy nejsou tak velké, jak se se zdají být

Nedávno jsem narazil na zajímavý test, který se snažil nahrubo určit kolik paměti potřebují různé datové struktury na JVM: kolekce z Javy, Scaly, Googlí Guava a kolekce Trove specializované pro primitivní typy. Test probíhal tak, že nastartoval JVM s 1GB heap, vytvořil danou kolekci, začal přidávat jeden element za druhým až do okamžiku, kdy došla paměť a virtuální stroj vyhodil OutOfMemoryError. Potom autoři prohlásili, že daná kolekce s výsledným počtem elementů zabere plus/mínus jeden gigabajt paměti.

To všechno vypadalo celkem rozumně až do okamžiku, kdy jsem si prošel výsledky. Z nich vyplývalo, že do jednoho gigabajtu paměti se vejde Trove TIntArrayList (který ukládá neboxované integery) o délce nejvýše 10485760 elementů. Neboli 40 megabajtů dat.

Tady něco nehraje. Čekal jsem, že to bude desetkrát až dvacetkrát více.

Hned jsem začal vrtat v implementaci Trove kolekcí, zdrojácích testu a měřit velikosti objektů a za chvíli jsem zjistil, že Trove TIntArrayList je implementován polem, které má výchozí kapacitu 10 a když se naplní, alokuje větší pole, překopíruje do něj starý obsah a přidá nová data. Velikost nového pole se rovná staré velikost posunuté o jeden bit doleva. A 10 << 20 je právě 10485760, což znamená, že test narazil na OOM, když TIntArrayList prováděl jednadvacáté zvětšení. V ten okamžik se na haldě nacházelo staré pole délky 10M a snaha alokovat nové o délce 20M selhala. Ale i když sečteme velikosti těchto dvou polí, dostaneme pouhých 120MB dat na 1GB haldě než JVM začne kapitulovat.

Tady pořád něco nehraje.

Nastartoval jsem tedy VisualVM, abych se podíval, co se ve virtuálním stroji doopravdy děje a hned mě to udeřilo do očí: generační garbage collector.

Pokud JVM používá tento GC, rozdělí haldu do několika oblastí: eden, survivor a old a žádná z nich není dost velká na to, aby pojala gigantické pole. A protože data nemůžou přečnívat z jedné oblasti do druhé, není možné alokovat pole větší než nejmenší z těchto regionů, což bude nejspíš survivor, který je tvořen dvěma nezávislými polovinami mezi kterými se kopírují data.

Tato teorie také vysvětluje, proč „fragmentované“ kolekce, které nepotřebují velká souvislá pole, mají v testu naměřenou poměrně velkou kapacitu, která je rozhodně větší než by odpovídalo rozdílu mezi boxovanými a primitivními typy.

Nejsnadnější způsob, jak tento problém řešit, když na něj narazíte, je nastavit větší heap a dál se o nic nestarat.

flattr this!

Posted in JVM, Paměť | 5 Comments

Poznámka k Moorovu zákonu a rychlosti procesorů

Potom, co rychlost procesorů začala v roce 2004 stagnovat, věřili jsme, že stejným exponenciálním tempem poroste počet jader procesoru. Kdyby se předpovědi vyplnily, všichni bychom teď měli stroje se stovkou jader. Z tohoto úhlu pohledu to může zdát, jako by výkon CPU více méně stagnoval. Naštěstí to ale není pravda. Současné generace procesorů jsou na stejné frekvenci rychlejší než ty minulé, protože mají výrazně lepší paměťový systém a cache. Díky tomu nemusí tolik času strávit čekáním na data z hlavní paměti a můžou dělat něco užitečného. Současné procesory mají také výrazně širší vektorové (SIMD) jednotky. Ty můžou vykonat v jednom taktu jednu operaci na několika hodnotách najednou a jejich šířka se neustále zvětšuje. SSE mělo šířku 128 bitů, AVX uvedené v procesorech Sandy Bridge v roce 2011 mělo šířku 256 bitů, AVX512 plánované na rok 2015 bude mít šířku 512 bitů s výhledem na další rozšíření v následujících letech. Každé takové zdvojnásobení šířky může zdvojnásobit výkon vektorizovaných operací. I když i tohle exponenciální rozšiřování má nějaký horní limit, kde přestane dávat smysl. Ale plánovaných 512 bitů je více než dost, do každého AVX512 registru (kterých bude k dispozici 32) se vejde 16 čtyřbajtových hodnot nebo 8 osmibajtových. Můžu tak provést a = a + b * c, tedy vynásobit 16 a 16 čísel a sečíst je s 16 jinými čísly v jediném taktu.

Vliv vektoriace na výkon je obrovský, ale přesto není přímo podporována v programovacích jazycích jako first class citizen.


Mimochodem v současnosti máme procesory se stovkami jader, jenom jim říkáme GPU.

flattr this!

Posted in CPU, Paměť | 1 Comment

Tak jak je to s tou rychlostí procesorů a pamětí?

Jedna stará moudrost říká: „procesory jsou rychlé, paměť je pomalá“.

Ale tahle jednoduchá poučka nedokáže popsat dramatické rozdíly mezi oběma světy. Procesory jsou totiž neuvěřitelně rychlé a většinu času čekají na paměť, která se v porovnání s nimi pohybuje tempem prastarých ledovců. Data z RAM dorazí se zpožděním přibližně 100ns. Za tu dobu 3GHz CPU odbije 300 taktů křemíkového srdce. Ale to jsou takty, instrukcí může stihnout ještě víc – moderní procesory mají několik portů a na každém z nich může být prováděna jedna instrukce. Starší Intely mají 6 portů, nejnovější Haswelly pak rovnou 8. Taková bestie pak stihne provést až 2400 instrukcí v době, než data dorazí z paměti. Navíc některé z nich mohou být SIMD instrukce, které provádějí jednu operaci na několika položkách najednou (víc info zde a zde). CPU by dokázalo provést ohromné množství výpočtů, kdyby na data nikdy nemusel čekat a vždycky je měl po ruce (plus tohle bude exponenciálně větší problém u kvantového počítání). Procesory tyto latence, které můžou mít tragický dopad na výkon programu, maskují jak jenom mohou: několik úrovní cache, prefetching, load/store buffery, Out-of-order execution, branch prediction a spekulativní provádění kódu. Rychlosti CPU posledních několik let nijak výrazně nerostou, ale ani nemusí, protože stejně jenom většinu času zahálejí. Paměť musí zrychlit.


Abych si tohle ověřil, napsal jsem jednoduchý program, který otestuje kolik cache-miss zvládne procesor za vteřinu. Kód dělá jenom to, že ve smyčce zapisuje na náhodné indexy v poli data. Pokud je pole mnohem větší než největší cache, ke které má přístup jedno jádro procesoru, a indexy skutečně náhodné, každá operace s polem způsobí cache-miss (data nejsou v rychlé cache a musí dorazit z hlavní paměti).

Zjednodušený testovací program zde:

val size     = 1 << 26  // == 64M x 8B long == 512MB
val sizeMask = size - 1

val iterations = 10000000 // 10M

val data            = Array.fill(size) { util.Random.nextInt(2) } // 0 - 1
val randomPositions = Array.fill(size) { util.Random.nextInt(size) }

var iteration = 0
var i = 0

while (iteration < iterations) {
  // polem randomPositions procházím sekvenčně
  // prefetcher procesoru se postará, že požadovaná data budou v cache
  val pos = randomPositions(i & sizeMask)

  // instrukce load, add, store
  // load vždy způsobí cache miss
  data(pos) += 1

  i += 1
  iteration += 1
}

Výsledný čas while smyčky na mém starém Core2 E6300 s 2MB L2 cache a DDR2 je přibližně 570ms, tedy 57ns na jeden cache-miss a to je poněkud málo. Výsledek by měl být ± dvojnásobný.

Co se tady jenom děje?

Odpověď je jednoduchá: procesory jsou bestie a dokážou se vypořádat s tím, když jim schválně házím klacky pod nohy. CPU totiž dělá věci paralelně a spekulativně.

Už mnoho let jsou všechny procesory Out-of-order (OOO), tedy nevykonají jednu instrukci a teprve až potom se posunou na další, ale instrukce do nich proudí, jsou paralelně dekódovány, řadí se do front, vykonávají se zároveň na různých portech (ne každý port dokáže vykonat každou instrukci), některé čekají, jiné jednou dál. Valí se vpřed jako lavina a procesor přesto udržuje iluzi, že se instrukce vykonávají sekvenčně (je to jako kdyby žongloval padesát míčků a motorovou pilu).

Například první dva řádky kódu se smyčce jsou na sobě závislé a tak se musí provést sekvenčně, ale obě inkrementace na ničem závislé nejsou a tak se můžou provést zároveň na volných ALU (Haswell má např. 4 ALU). A stejně tak CPU může najednou čekat na dvě probíhající load operace, které vyvolaly cache-miss.

Procesory pak také provádějí kód spekulativně, když nějaká instrukce čeká na data nebo na dokončení, CPU se snaží odhadnout, co se bude dít dál, začít dekódovat instrukce, vykonávat je s tím, že až se dokončí operace, která všechno blokuje a ukáže se, že předpoklady byly správné, spousta práce už bude hotova. Když se odhad mýlil, všechna spekulativní práce se zahodí a začne se znovu. Procesory si to můžou dovolit, protože většinu času stejně jenom na něco čekají. Takhle funguje branch prediction, který se snaží odhadnout cíl skoku (u smyček je to velice předvídatelné), nebo prefetching který spekulativně načítá data z hlavní paměti do cache, když vidí, že paměť procházím sekvenčně.

A právě souhra těchto dvou aspektů ukazuje, proč je testovací kód dvakrát rychlejší, než by měl: CPU už zná hodnotu i, může spekulovat a začít vykonávat další iteraci smyčky zatímco předchozí iterace čeká na data z paměti. Spekulativní iterace narazí na vlastní cache-miss a taky začne čekat zároveň s předchozí iterací. Tohle efektivně srazí latenci paměti na polovinu a s tím i dobu běhu programu.

Pokud se náhodou stane, že první iterace přepíše hodnotu na které spekulativní iterace závisí (např. v poli randomPositions po sobě následují dva stejné indexy), CPU to pozná, invaliduje spekulativní data a zopakuje poslední iteraci smyčky. Spekulativní práce nikdy neovlivní chování programu, protože její efekty nejsou vidět mimo pořadí.

Ještě pro úplnost několik čísel:
Pokud má pole data délku 1 << 26 (512MB) smyčka trvá 570ms.
Pokud má délku 1 << 27 (1024MB) smyčka trvá 760ms, za což nejspíš může TLB a cache-miss na tabulku stránek (well fuck!).
Pokud se provádí jenom zápis, tedy data(pos) = 1 místo data(pos) += 1, trvá to jenom 390ms.


Abych mohl zjistit skutečný čas, který trvá jeden cache-miss, musím zamezit spekulativnímu chování. To se dá udělat jednoduše tak, že se do kódu vnese datová závislost. Neinkrementuji tedy proměnnou i o jedničku, ale o 1 nebo 2 v závislosti na hodnotě načtené z pole data (které je plné náhodných čísel):

while (iteration < iterations) {
  val pos = randomPositions(i & sizeMask)
  val d = data(pos)
  data(pos) = d + 1

  // datová závislost, o kolik se posune i závisí na hodnotě na kterou se čeká
  i += (if ((d & 1) == 0) 1 else 2)
  iteration += 1
}

Teď už smyčka trvá podstatně déle: 1460ms – 146ns na jeden cache-miss.

Udělal jsem několik testů z různou velikostí pole data, výsledky jsou v následující tabulce (může za ně cache, stránkování paměti a TLB):

délka velikost doba
1 << 27 1024MB 1700ms
1 << 26 512MB 1460ms
1 << 25 256MB 1320ms
1 << 24 128MB 1240ms
1 << 23 64MB 1200ms
1 << 22 32MB 1130ms
1 << 21 16MB 1000ms
1 << 20 8MB 770ms
1 << 19 4MB 415ms
1 << 18 2MB 200ms

Pro srovnání ještě přidám verzi, která neskáče na náhodné indexy, ale prochází polem sekvenčně:

while (iteration < iterations) {
  // pos je sekvenční
  val pos = i & sizeMask
  data(pos) += 1

  i += 1
  iteration += 1
}

Tahle smyčka se provede za pouhých 19ms, tedy 1.9ns na iteraci, což odpovídá ± 5 taktům CPU.


** Závěr **

Doufám, že jsem tady aspoň částečně ukázal, že procesory jsou velice rafinované stroje a inženýři v Intelu a AMD strávili roky, aby implementovali celé plejády triků a optimalizací, díky kterým program běhá rychle i za velice nepříznivých podmínek. Na druhou stranu taky musí být jasné, že když chování CPU budeme znát a využijeme ho, můžou být naše programy mnohem rychlejší, ale často je tohle chování složité a komplexní a na výsledek má vliv mnoho faktorů.


Další čtení:

flattr this!

Posted in CPU, Paměť | Leave a comment

Co je vůbec objektové a funckionální programování?

Dlouhou dobu jsem nechápal objektové programování. Věděl jsem, co to je a jak ho používat, ale nechápal jsem ho na základní úrovni, chyběl mi hluboký vhled do hlavních myšlenek, tedy to, o co se vždycky snažím: neklouzat po povrchu, ale proniknout přímo do epicentra a odtud se propracovávat směrem ven.

Zásadní myšlenky jsou to nejdůležitější, a musíme je znát, abychom skutečně pochopili, co nám to které paradigma přináší. Bohužel tyhle základy často vnímáme pokroucené skrz optiku jazyka, které se k danému paradigmatu hlásí. Ideu nahrazujeme artefaktem. Interface implementací.

Java je populární objektově orientovaný jazyk, takže když známe Javu známe OOP, žejo?

Ani v nejmenším. Javě jako jazyku a kultuře, která kolem něj vyrostla, se podařilo zdeformovat pojem OOP. Zavedla vlastní termíny a pojmy a abstrakce a artefakty a vzory, které se OOP týkají jenom okrajově, ale většinové publikum je přijalo jako podstatu OOP. Já jsem nebyl výjimkou.

Jaké jsou tedy ty hlavní myšlenky OOP a FP?

Jsou to ty, kterým se daný styl programování odlišuje od všech ostatních.


Nejdůležitější ideou objektového programování je polymorfismus (a s ním spojený late bindind).

Někdo uvádí, že gró OOP leží v pojmech identita, zapouzdření a kompozice, ale myslím si, že to není tak úplně pravda.

Zapouzdření je fakt, že objekt má svůj protokol, který specifikuje množinu zpráv na které umí odpovět a není jiný způsob jak se podívat přímo do útrob objektu. Ale aby to mělo smysl, potřebuje polymorfismus – tedy možnost, že na jednu zprávu může každý objekt odpovědět po svém. Kdybychom ho něměli, pak by zapouzdření nedávalo smysl, protože by šlo jenom o jiný fixní pohled na interní data. Každý polymorfní objekt může být interně reprezentován zcela odlišně, ale s ostaními částmi systému komunikuje stejným protokolem.

Kompozice je způsob jak organizovat části programu a je to zase polymorfismus, který umožňuje, aby jeden objekt odpovídal přímo a jiný akci delegovat na jiný objekt.

Identita je zákeřná mrcha, která nejenom, že není zásadní, ale je dokonce na škodu. Jde o problematický koncept, protože nás nutí přemýšlet v rámci objektů, které existují jako konkrétní místa v paměti a ne v rámci univerzálně platných dat a faktů. Také přímo navádí k programování s měnitelným stavem (a pozorovatelný měnitelný stav je špatný, protože do programů vnáší zbytečnou složitost, často způsobenou tím, že spolu nějaké části programu komunikují změnami sdíleného stavu a komunikaci by v OOP měla probíhat jedině prostřednictvím zpráv). Identita se dá simulovat v systémech, které ji nemají (id sloupce v relačních databázích) a naopak se dá zapomenout v systémech, které ji mají (definuji vlastní protokol, který se k objektům chová jako k hodnotám). Zajímavě se k tomuto problému staví Concept-oriented programming, které zcela odděluje pojmy objekt a identita.

Typy pak v OOP světě slouží jako (staticky ověřitelná) klasifikace objektů. Když objekt má daný typ, znamená to, že umí odpovídat na danou množinu zpráv.

Mimochodem všimněte si, že jsem k popisu OOP nepoužil slova jako třída, interface, metoda nebo dědičnost. Nejsou zásadní a dokážeme se bez nich obejít.


Naproti tomu hlavní ideou funkcionálního programování je referenční transparentnost. Nejsou to funkce vyšších řádů, monády, lamba kalkul, ani žádné pokročilé matematické koncepty. Je to jenom tenhle jeden pojem.

Funkce je referenčně transparentní, když její výsledek je daný jedině jejími argumenty a ničím jiným. To má spoustu implikací: volání funkce můžeme nahradit jejím tělem nebo rovnou výsledkem a na chování programu se nic nezmění, o programu pak můžeme začít uvažovat jako o soustavě rovnic, funkce jsou funkcemi v matematickém slova smyslu a nemůžou mít žádné vedlejší účinky a všechny hodnoty jsou neměnné. To všechno vyplývá z hlavní myšlenky FP.

Díky tomu jsou funkcionální programy přímočaré a jednodušší na pochopení. Stačí sledovat vstupy a výstupy, nemusím si pamatovat, jaké vedlejší účinky má daná funkce a jak to ovlivní chování celého systému. Spousta starostí jednoduše zmizí. Neměnné typy zcela odstraní mutnost defenzivního programování, protože neměnnou věc nikdo nezmění. Všichni můžou mít kopii a programátoři můžou v klidu spát. To je požehnání pro paralelní kód, ale má svoje místo i v klasickém nudném jednovláknovém kódu.

Kvůli těmto pravidlům FP jazyky můžou být líné, snadno paralelizovatelné a užitečné pro paralelní programování. Když je hodnota neměnná, nemusím hlídat, kdo ji kde a jak změní, ale můžu ji zcela volně sdílet mezi libovolným počtem vláken (což je také dobré pro CPU cache, které si mezi sebou nemusí přehazovat horkou cache-line pro zápis). Tohle je hlavní z důvodů, proč funkcionální programování v posledních letech získává na popularitě.

Pokud si teď říkáte: „to všechno je pěkné, ale mě se to netýká, protože programuji v PHP/Javě/C“, tak vězte, že funkcionálně se dá programovat v každém jazyce. V některých je to snažší, ale jde to ve všech. Stačí psát kód, který se opírá o tu jednu stěžejní myšlenku referenční transparentnosti.


Takže co dál? Objektově nebe funcionálně? Odpověď zní překvapivě: obojí. V následujících letech se masově rozšíří objektově funkcionální paradigma, které spojuje to nejlepší z obou světů: OOP pro organizaci a modularizaci programů a FP kvůli referenční transparentnosti, neměnným typům a snazšímu paralelnímu programování.

Dále k tématu:

flattr this!

Posted in Funkcionální programování, OOP | 7 Comments