Branch prediction moderních procesorů

Před nějakou dobou jsem narazil na článek z roku 2010, který testoval, jak si branch prediction procesorů té doby poradí s různými opakujícími se vzory skoků v programu. Došel k závěru, že když procesor nedokáže skoky předvídat, může být výsledný program až 6× pomalejší, než když předvídá perfektně. Rozhodl jsem se test zopakovat a zjistit, jak je na tom současný hardware.

Rychlost branch instrukce (neboli podmíněného skoku) závisí na tom, jestli je její podmínka předvídatelná. Pokud procesor dokáže správně uhodnout, zdali má skočit na jiné místo programu nebo pokračovat s následující instrukcí, je skok skoro zadarmo. Ale pokud procesor neví nebo uhodne špatně, následuje takzvaný pipeline stall, kdy CPU zahodí všechnu rozdělanou práci a začne číst, dekódovat a vykonávat instrukce ze správného místa.

Toto chování souvisí s faktem, že všechny současné procesory jsou pipelinované. Každá instrukce vyžaduje několik nezávislých kroků, typicky to jsou fetch, decode, execute a write-back, kdy je instrukce načtena z paměti, dekódována, vykonána a výsledky zapsány zpátky do paměti. Kdysi dávno procesory vzaly jednu instrukci, vykonaly sekvenčně všechny čtyři fáze a teprve potom se posunuly na další. V honbě za vyšším výkonem CPU začala provádět všechny fáze najednou pro různé instrukce. Zatímco jedna instrukce zapisuje do paměti, následující se vykonává, následující je dekódována a následující je načítaná z paměti. Najednou se v procesoru nachází několik instrukcí za letu. Současné procesory mají pipeline s více kroky než jsou ony čtyři a navíc jsou superskalární, což znamená, že v každém taktu dokážou zpracovat několik instrukcí. Z těchto důvodů je počet instrukcí „za letu“ je mnohem vyšší. Délka pipeline souvisí s navyšováním taktu: Čím vyšší frekvence, tím méně času má signál dostat se skrz jednu fázi pipeline, když se zvýší počet kroků, každý může být o něco kratší. Současné x86 mají něco mezi 12–15 fázemi a když je hezky zvládnout zpracovat 4 instrukce za takt, Itanium zvládne stabilně 12 a chystaný Mill až 33.

Teď si představte, že se v tomto perfektním soustrojí vyskytne podmíněný skok. Část CPU, která načítá instrukce na začátku pipeline, se musí rozhodnout, jestli načte následující instrukci, nebo tu na kterou branch může skočit. Podmínka, která to určuje, není zatím vykonána a ještě několik taktů nebude, dokud se neprobojuje na druhý konec pipeline. To je však příliš dlouhá doba a procesor si nemůže dovolit čekat. V ten okamžik na scénu nastoupí branch predictor a pokusí se to uhodnout. Když se trefí, všechno jede jako na drátkách, když se zmýlí, nastane pipeline stall, procesor musí zahodit všechnu práci do které se spekulativně pustil a začít načítat instrukce ze správného místa a prohnat je skrz celou pipeline a tedy ztratit množství času odpovídající délce pipeline.

Naštěstí je většina skoků v programu velice dobře předvídatelná. Například smyčky, které projedou mnoho iterací a během každé z nich branch instrukce skočí na začátek, kromě té poslední, kdy propadne. Procesory používají mnoho různých variant branch predictorů, které zaznamenávají minulé chování podmíněných skoků a předpokládají, že se stejné nebo podobné chování bude opakovat i v budoucnu. Někdy mají několik různých predictorů a jeden meta-predictor, který učiní finální rozhodnutí. Tímto způsobem dosahují impresivních výsledků, kdy mají skoro vždycky pravdu.

Branch predictor je velice důležitá část CPU, protože v typických programech představují skoky každou šestou až osmou instrukci a pipeline stall znamená obrovské zdržení. Například Pentium-Pro, Pentium 2 a Pentium 3 měly pipeline s více jak 12 fázemi, mispredict stál něco mezi 10 a 15 takty a i když měly pokročilý dynamický branch predictor, který fungoval s 90% přesností, ztrácely 30% výkonu kvůli těm 10 zmýleným procentům. Pentium 4 měl pipeline dlouhou 31 taktů a to pravděpodobně způsobovalo jeho nepřesvědčivé výkony.

V současných velkých procesorech jen přibližně 6 až 8 procent plochy čipu skutečně provádí výpočty, zbytek se stará, aby tento zlomek křemíku měl stále co na práci. Jde o branch predition jednotky, několik úrovní cache, out-of-order engine, virtuální registry, spekulace, prefetching a další hardware, který bojuje proti latenci a zrychluje běžný kód, který je typický tím, že obsahuje hodně skoků.


Zpátky ke zmíněnému článku. Ten testoval rychlost skoků na kódu, který vypadal nějak takto:

for (int i = 0; i < max; i++) if (<condition>) sum++;

Podmínka měla tvar (i & constant) == 0. Volbou různé konstanty se dá snadno vytvořit krátký opakující se vzor. Původní výsledky zkombinované s těmi mými vypadají následovně:

|-------------------------------------------------------------------------------------
| Condition              | Pattern     |   2010  |  Intel Atom      | Intel Haswell i5
|                                      |         |     -O0 |    -O3 |    -O0 |   -O3
|-------------------------------------------------------------------------------------
| (i & 0x80000000) == 0  | TTTTTTTT    |  322 ms |  388 ms | 374 ms | 211 ms | 86 ms
| (i & 0xffffffff) == 0  | FFFFFFFF    |  276 ms |  334 ms | 374 ms | 218 ms | 86 ms
| (i & 1) == 0           | TFTFTFTF    |  760 ms |  602 ms | 371 ms | 216 ms | 86 ms
| (i & 3) == 0           | TFFFTFFF    |  513 ms |  427 ms | 378 ms | 219 ms | 86 ms
| (i & 2) == 0           | TTFFTTFF    | 1675 ms |  441 ms | 373 ms | 213 ms | 85 ms
| (i & 4) == 0           | TTTTFFFF    | 1275 ms |  642 ms | 378 ms | 214 ms | 85 ms
| (i & 8) == 0           | 8T 8F ...   |  752 ms |  546 ms | 370 ms | 214 ms | 85 ms
| (i & 16) == 0          | 16T 16F ... |  490 ms |  446 ms | 377 ms | 214 ms | 85 ms
| xorshift rand len 8    | random      |  ---    | 1212 ms | 680 ms | 234 ms | 86 ms
| xorshift rand len 16   | random      |  ---    | 1284 ms | 676 ms | 230 ms | 86 ms
| xorshift rand len 32   | random      |  ---    | 1328 ms | 679 ms | 228 ms | 86 ms
| xorshift rand len 64   | random      |  ---    | 1428 ms | 676 ms | 227 ms | 86 ms
| xorshift rand len 128  | random      |  ---    | 1475 ms | 676 ms | 227 ms | 86 ms
| xorshift rand len 256  | random      |  ---    | 1560 ms | 679 ms | 229 ms | 85 ms

Sloupec 2010 ukazuje časy naměřené v onom článku na neznámém procesoru a s neznámým počtem iterací. Z toho důvodu nevěnujte žádnou pozornost rozdílu v absolutních číslech mezi těmito a mými časy. V následujících sloupcích jsou časy na Atomu reprezentující low-end všech low-endů a na desktopovém i5 Haswellu, reprezentujícím rozumný křemík. V obou případech byl testovací kód kompilovaný gcc s příznaky -O0 (bez optimalizací) a -O3 (maximální optimalizace). K tomu jsem přidal pár pseudo-náhodných testů, ve kterých se opakoval náhodný vzor určité délky (vygenerovaný přes xorshift RNG).

Jak je z výsledků vidět, tak i prachobyčejný levný Atom určený do netbooků v nejhorším případě běží 2× pomaleji a současné rozumné procesory v žádném z testů nepocítí žádné zpomalení. Branch prediction jednotky doznaly znatelného zlepšení a dokáží perfektně detekovat dlouhé opakující se vzory, pokud jsou přítomny. Když má skok skutečně náhodný charakter, nepomůže ani svěcená voda.

Zajímavé jsou také výsledky -O3 optimalizace. Na Haswellu kód s -03 je jenom rychlejší, ale na Atomu smaže rozdíly mezi ideálními a neideálními případy a všechno najednou běží tak, jako kdyby branch predictor vždycky uhodl správně. Kouzlo spočívá v tom, že GCC se rozhodlo if (<condition>) sum++ nekompilovat jako podmíněný skok, ale jako instrukci CMOV neboli conditional move. Ta funguje tak, že přesune data mezi dvěma místy, ale jen pokud je splněná určitá podmínka. CMOV je vykonána v každém případě, ale může nebo nemusí mít svůj efekt. Protože nejde o podmíněný skok, procesoru nehrozí pipeline stall a kód běží stabilní rychlostí. Pokud je skok nepředvídatelný, zrychlení může být znatelné (jak je vidět tak pro náhodné vzory je to až 2.5×), ale to není zas tak běžný případ.

Pro úplnost: -O0 vygeneruje následující instrukce:

test   %eax,%eax        ; kontrola podmínky
jne    40065a           ; skočí za následující instrukci, pokud podmínka neplatí
addl   $0x1,-0x8(%rbp)  ; inkrementuje sum

-O3 vygeneruje něco na způsob tohoto:

test   %edx,%eax        ; kontrola podmínky
cmove  %ecx,%ebx        ; pokud podmínka platí, přesune ecx do ebx
lea    0x1(%ebx),%ecx   ; ecx ← ebx + 1

CMOV je jediná podmíněná x86 instrukce, ale například 32bitový ARM nebo Itanium má podmíněné skoro všechno a může tedy dělat například podmíněné aritmetiku. ARM to má kvůli chybějícím/slabým branch predictorům, Itanium proto, že bylo navrženo pro masivní ILP a software pipelining (z toho důvodu má 64 1-bitových predikátových registrů a rotující registry).


Když se podívám na podrobné informace vygenerované programem perf, který poskytuje přístup k interním čítačům CPU, dostanu velice podrobný pohled, co se děje pod kapotou.

|------------------------------------------------------------------------------------------------------
| Condition              | Intel Atom
|                        | -O0                                  | -O3
|                        |    time | branch-miss | instr |  IPC |   time | branch-miss | instr |  IPC
|------------------------------------------------------------------------------------------------------
| (i & 0x80000000) == 0  |  388 ms |       0,01% |   893 | 1,41 | 374 ms |       0.02% |   600 | 0,98
| (i & 0xffffffff) == 0  |  334 ms |       0,01% |   799 | 1,48 | 374 ms |       0.02% |   599 | 0,99
| (i & 1) == 0           |  602 ms |       0,02% |   851 | 0,86 | 371 ms |       0.02% |   600 | 0,99
| (i & 3) == 0           |  427 ms |       0,01% |   823 | 1,18 | 378 ms |       0.02% |   600 | 0,97
| (i & 2) == 0           |  441 ms |       0,01% |   850 | 1,18 | 373 ms |       0.02% |   599 | 0,98
| (i & 4) == 0           |  642 ms |       0,02% |   849 | 0,81 | 378 ms |       0.02% |   598 | 0,97
| (i & 8) == 0           |  546 ms |       6,27% |   850 | 0,95 | 370 ms |       0.02% |   600 | 0,99
| (i & 16) == 0          |  446 ms |       3,15% |   846 | 1,16 | 377 ms |       0.02% |   599 | 0,98
| xorshift rand len 8    | 1212 ms |       0,04% |  1625 | 0,82 | 680 ms |       0,03% |   901 | 0.81
| xorshift rand len 16   | 1284 ms |       4,15% |  1637 | 0,78 | 676 ms |       0,03% |   900 | 0.81
| xorshift rand len 32   | 1328 ms |       7,53% |  1645 | 0,75 | 679 ms |       0,03% |   901 | 0.81
| xorshift rand len 64   | 1428 ms |      12,87% |  1653 | 0,70 | 676 ms |       0,03% |   900 | 0.81
| xorshift rand len 128  | 1475 ms |      15,43% |  1658 | 0,68 | 676 ms |       0,03% |   900 | 0.81
| xorshift rand len 256  | 1560 ms |      20,32% |  1650 | 0,64 | 679 ms |       0,03% |   900 | 0.81

|------------------------------------------------------------------------------------------------------
| Condition              | Intel Haswell i5
|                        | -O0                                  | -O3
|                        |    time | branch-miss | instr |  IPC |  time  | branch-miss | instr |  IPC
|------------------------------------------------------------------------------------------------------
| (i & 0x80000000) == 0  |  211 ms |       0.00% |   800 | 1,07 |  86 ms |       0.00% |   600 | 1.99
| (i & 0xffffffff) == 0  |  218 ms |       0.00% |   701 | 0,91 |  86 ms |       0.00% |   600 | 1.99
| (i & 1) == 0           |  216 ms |       0.00% |   751 | 0,99 |  86 ms |       0.00% |   600 | 1.99
| (i & 3) == 0           |  219 ms |       0.00% |   725 | 0,94 |  86 ms |       0.00% |   600 | 1.99
| (i & 2) == 0           |  213 ms |       0.00% |   750 | 1,00 |  85 ms |       0.00% |   600 | 1.99
| (i & 4) == 0           |  214 ms |       0.00% |   750 | 0,99 |  85 ms |       0.00% |   600 | 1.99
| (i & 8) == 0           |  214 ms |       0.00% |   750 | 0,99 |  85 ms |       0.00% |   600 | 1.99
| (i & 16) == 0          |  214 ms |       0.00% |   750 | 0,99 |  85 ms |       0.00% |   600 | 1.99
| xorshift rand len 8    |  234 ms |       0.00% |  1625 | 1,96 |  86 ms |       0.01% |   900 | 2.98
| xorshift rand len 16   |  230 ms |       0.00% |  1638 | 2,01 |  86 ms |       0.01% |   900 | 2.99
| xorshift rand len 32   |  228 ms |       0.00% |  1644 | 2,04 |  86 ms |       0.01% |   900 | 2.99
| xorshift rand len 64   |  227 ms |       0.00% |  1652 | 2,06 |  86 ms |       0.01% |   900 | 2.99
| xorshift rand len 128  |  227 ms |       0.06% |  1657 | 2,06 |  86 ms |       0.01% |   900 | 2.99
| xorshift rand len 256  |  229 ms |       0.01% |  1649 | 2,05 |  85 ms |       0.01% |   900 | 2.99

Sloupec branch-miss ukazuje kolik podmíněných skoků bylo špatně předpovězeno, instr počet vykonaných instrukcí a IPC počet instrukcí vykonaných v jednom taktu. Jak je vidět úplně napravo, v tomto testu rozumný procesor dneška zvládá vykonat dvě až tři instrukce každý takt a téměř žádný skok není chybně předpovězen.


Dále k tématu:

flattr this!

Posted in CPU | Leave a comment

Procesory a jejich architektura (sebrané spisy)

Moderní procesory jsou velice komplikované křemíkové bestie a mnoho lidí neví, nebo má jen mlhavou představu, co se děje uvnitř a co způsobuje, že některé programy běží neuvěřitelně rychle a jiné tak pomalu, že si člověk stihne uvařit kafe a udělat něco k jídlu.

Pokud se chcete dozvědět, jak CPU fungují, připravil jsem pro vás seznam článků, videí, paperů a knih, které vám na této cestě za poznáním pomůžou a do nejmenších detailů osvětlí fantastická soukolí Stroje.

Obecné

Detaily procesorů a architektur

Algoritmy a datové struktury využívající vlastnosti CPU ve svůj prospěch

Mill CPU

Názorná série videí, která představuje chystanou architekturu Mill a během toho ukáže, jak fungují současné procesory a jak se od nich Mill liší.

Concurrency

Java, JVM

flattr this!

Posted in CPU, Paměť | Leave a comment

Types will carry you over the Monads

Teď nechci zabřednout do bažin internetu a napsat další monádový tutoriál, ale jen zveřejnit jeden postřeh, díky kterému jsem pochopil sílu Applicatives:

Vždycky, když jsi v úzkých, následuj typy a ty tě dovedou do cíle.


Funkce bind definovaná na monádě má typ:

bind :: M a -> (a -> M b) -> M b

Ten říká, že mám nějaké M a a pak funkci z a do M b a když je nějak zkombinuji, dostanu M b. Z typu je vidět, že do funkce a -> M b musím dodat a, které je uvězněno v M a a jinak není možné pokračovat. Monády tedy popisují operace, které jsou sekvenční a jeden krok závisí na výsledku toho předchozího.

Pokud tedy například M a reprezentuje asynchronní operaci, která eventuálně vyprodukuje hodnotu typu a, argument a -> M b představuje další async akci, která k tomu, aby vůbec začala, potřebuje znát a – tedy předchozí výsledek. Jde tedy o řetězení async operací, které je jasně patrné z typu funkce.


Applicative definuje jednu funkci, které tady budu říkat apply 1 a která má typ:

apply :: M a -> M (a -> b) -> M b

Ten říká, že mám nějaké M a a nějaké M (a -> b) (tedy funkci a -> b uvnitř M) a když je nějak zkombinuji, dostanu M b. Ale na rozdíl od předchozího případu, M (a -> b) nepotřebuje a k tomu aby začal pracovat.

Pokud je M opět asynchronní operace, pak druhý argument představuje jinou asynchronní operaci, která nezávisle na prvním argumentu vyprodukuje funkci a -> b. Když jsou oba dva argumenty připraveny, je možné zavolat funkci z druhého argumentu s výsledkem toho prvního a dostat tak výsledek reprezentovaný async operací M b.

Opět: I tohle je patrné z typu funkce a není možné to udělat jinak a stále vyhovovat typové signatuře.


Pro úplnost ještě uvedu funktor, jehož funkce fmap má typ:

fmap :: M a -> (a -> b) -> M b

Když by M byla zase async operace, pak argument a -> b představuje pure transformaci výsledku této operace, který sám nedělá žádná async kouzla.

To všechno je zas patrné z pouhého typu.

Ještě se sluší dodat, že každá monáda je applicative a každá applicative je funktor.

Doufám, že jsem tedy nakonec nenapsal další monádový tutoriál, ale něco, co bude aspoň trochu užitečné, A mimochodem: Titulek je variace na jméno alba We will carry you over the mountains od Magyar Posse.


Dále k tématu:


  1. V Haskellu tahle funkce má jiné pořadí argumentů a nese jméno (<*>), které může být podobně jako axaxaxas mlö vysloveno jen jako posměšný a krutý smích autorů Haskellu.

flattr this!

Posted in Funkcionální programování, Typy | 1 Comment

PHP DOM, SimpleXML a Matcher

Však to znáte: Tak dlouho chodíte se džbánem pro vodu, až si na to napíšete framework. Já jsem tak dlouho crawloval a robotoval, až jsem si na to napsal Matcher. I když k frameworku má velice daleko, protože jde jen o dvě třídy.

Pokud chci v PHP extrahovat data z HTML dokumentu, mám na výběr mezi dvěma zly: DOM a SimpleXML.

Kód, který používá DOM může vypadat nějak takto:

$dom = @ \DOMDocument::loadHTML($htmlString);
$xpath = new \DOMXpath($dom);
$nodes = $xpath->query('//div[@class="post"]');
$res = [];
foreach ($nodes as $node) {
  $res[] = [
    'id'    => $xpath->query('@id', $node)->item(0)->textContent,
    'date'  => $xpath->query('div[@class="date"]', $node)->item(0)->textContent,
    'title' => $xpath->query('h2', $node)->item(0)->textContent,
    'text'  => $xpath->query('div[@class="body"]', $node)->item(0)->textContent,
  ];
}

Jde o víc psaní než by se mi líbilo. Navíc s každou úrovní zanoření požadovaných dat přibude jedna vnitřní smyčka.

SimpleXML se může zdát jako lepší volba, protože má na první pohled přehlednější API, ale to je jenom past na nepozorné. Tak předně SimpleXML nedokáže načíst HTML dokument a je nutno ho nejdřívě naparsovat DOMem a teprve potom importovat do SimpleXML.

$dom = @ \DOMDocument::loadHTML($htmlString);
$xml = simplexml_import_dom($dom);
$nodes = $xml->xpath('//div[@class="post"]');
$res = [];
foreach ($nodes as $node) {
  $res[] = [
    'id'    => (string) $node->xpath('@id')[0],
    'date'  => (string) $node->xpath('div[@class="date"]')[0],
    'title' => (string) $node->xpath('h2')[0],
    'text'  => dom_import_simplexml($node->xpath('div[@class="body"]')[0])->textContent,
  ];
}

SimpleXML dále neumí extrahovat textové elementy, neumí získat textový obsah celého podstromu elementů a hlavně špatně vyhodnocuje XPath dotazy.

Pokud mám dokument, který vypadá takto:

<el>
  <crap>i dont' care about this</crap>
  this is really important
  <crap>this is crap</crap>
</el>

za žádnou cenu nemůžu extrahovat text „this is really important“. Ani přes API ani přes XPath dotaz. A když chci získat celý textový obsah elementu <el> včetně dětí <crap>, musím <el> importovat do DOMu a na něm zavolat textContent. Bohužel právě tohle jsou věci, které při crawlování HTML dokumentů dělám velice často. Na jedné straně tedy mám DOM, který má barokní API a na druhé straně SimpleXML, která má API velice jednoduché, ale nepoužitelné.

Právě z těchto důvodů jsem si napsal Matcher, se kterým je parsování a extrakce dat z HTML až trapně jednoduchá.

V Matcheru by výše uvedený příklad vypadal krásně deklarativně:

$m = Matcher::multi('//div[@class="post"]', [
  'id'    => '@id',
  'date'  => 'div[@class="date"]',
  'title' => 'h2',
  'text'  => 'div[@class="body"]',
])->fromHtml();

$m($htmlString);

Výsledný Matcher je obyčejná funkce, která na vstupu vezme HTML řetězec a vrátí data, jejicž tvar odpovídá tomu, jak byl Matcher deklarován.

[
  ['id' => '...', 'date' => '...', 'title' => '...', 'text' => '...'],
  ['id' => '...', 'date' => '...', 'title' => '...', 'text' => '...'],
  ['id' => '...', 'date' => '...', 'title' => '...', 'text' => '...'],
  ...
]

Pokud nechci pole polí, ale pole objektů. Stačí vzor přetypovat na objekt a výsledek bude mít požadovanou strukturu.

$m = Matcher::multi('//div[@class="post"]', (object) [
  'id'    => '@id',
  'date'  => 'div[@class="date"]',
  'title' => 'h2',
  'text'  => 'div[@class="body"]',
])->fromHtml();

Pokud chci extrahovat vnořená data, nemusím psát vnitřní smyčky, ale jenom do sebe vnořím Matchery. Kód je stále krásně deklarativní a výsledná data mají stále strukturu odpovídající vzoru.

$m = Matcher::multi('//div[@class="post"]', [
  'id'    => '@id',
  'date'  => 'div[@class="date"]',
  'title' => 'h2',
  'text'  => 'div[@class="body"]',
  'tags'  => Matcher::multi('.//div[@class="tag"]'),
  'comments' => Matcher::multi('.//div[@class="comments"]', [
    'name' => 'div[@class="name"]'
    'text' => 'div[@class="text"]'
  ]),
])->fromHtml();

Výsledek:

[
  [
    'id' => '...',
    'date' => '...',
    'title' => '...',
    'text' => '...',
    'tags' => ['...', '...'],
    'comments' => [[
      'name' => '...',
      'text' => '...'
    ], [
      ...
    ]],
  ],
  ...
]

Když je potřeba nalezené řetězce nějak upravit, můžu použít Matcher single, který nevrátí pole, ale jen první nalezený element a následně metodu map, která transformuje výsledek Matcheru požadovanou funkcí.

$m = Matcher::multi('//div[@class="post"]', [
  'id'    => Matcher::single('@id')->asInt(),
  'date'  => Matcher::single('div[@class="date"]')->map('strtotime'),
  'title' => 'h2',
  'text'  => 'div[@class="body"]',
  'tags'  => Matcher::multi('.//div[@class="tag"]'),
  'meta'  => function ($node) { return doSomethingWithDomNode($node); }
])->fromHtml();

K dispozici jsou ještě metody: asInt, asFloat, first (matcher vrátí jenom první výsledek z kolekce) nebo regex (na výsledek matcheru aplikuje regulérní výraz a to i rekurzivně).

Ve výsledku může třeba takhle vypadat crawler, který používá Matcher, Atrox\Curl a Atrox\Async a je schopný crawlovat paralelně.

flattr this!

Posted in PHP, Web | 4 Comments

Výsledky PHP kvízu

Před nějakou dobou jsem tu zveřejnil maličký PHP kvíz, teď je načase odhalit správné odpovědi.

Ty jsou následující:

  1. kolize hashů
  2. velikost CPU cache
  3. cache prefetching
  4. hashování klíčů polí a cache prefetching

První otázka byla jednoduchá a šlo pochopitelně o kolize hashů.

V PHP je všechno hash tabulka: pole, deklarované a nedeklarované proměnné objektu a dokonce i metody jsou organizovány jako hash tabulky. Jedinou výjimkou je SplFixedArray, které je interně organizované jako skutečné pole.

PHP pole (viz HashTable ve zdrojácích PHP) má po vytvoření kapacitu 8 (viz _zend_hash_init). Když do něj začnu přidávat položky a dosáhnu této hranice, PHP pole zvětší svoji kapacitu na dvojnásobek (viz funkce zend_hash_do_resize).

Stringové klíče jsou hashovány funkcí DJBX33A (viz zend_inline_hash_func), ale celočíselné klíče se použijí přímo a co víc: stringové klíče, které obsahují číslo se na tohle číslo převedou. Tohle uspořádání má překvapivý dopad na výkon: Když používám PHP pole jako skutečné pole, tedy mám jen numerické klíče bez mezer z určitého intervalu, jsou položky seřazeny přímo podle klíče. Položka s indexem 5 je tedy v paměti hned vedle položky s indexem 6 a to je dobré pro CPU cache. Kdybych klíče hashoval, sousední indexy by se nacházely na různých místech tabulky, které nijak neodpovídají jejich numerickému řazení (o tomto se ještě zmíním u čtvrté otázky).

Z tohoto důvodu pro kolizi nemusím složitě hledat klíče, jejichž hash bude kolidovat s jinými klíči (jak to před pěti lety udělal Jakub Vrána), ale prostě použiji celočíselné klíče, které přímo kolidují. Protože PHP pole začíná na velikosti 8 a zvětšuje se na dvojnásobek, stačí si vybírat klíče, které mají stejné $key % (pow(2, $n) * 8) pro nějaké dostatečně velké $n, tedy nejlépe $i * FACTOR. Já zvolil FACTOR=1048576, což odpovídá `8 * pow(2, 17)`, tedy velikosti 17× zvětšeného pole. FACTOR musí být větší než kapacita pole, jinak všechny klíče nebudou kolidovat do jednoho místa, ale do několika.

Aby se tomu předešlo, stačí zvolit jiný způsob zvětšování kapacity tabulky`. Například začít na kapacitě 10 a novou velikost určit jako $capacity << 1.

Dále k tématu útoků pomocí kolizí hash tabulek:


Druhá otázka byla o něco složitější, protože nejde o čistě záležitost PHP, ale toho, jak se chová procesor na němž PHP běží.

Příčinu snadno odhalí linuxový nástroj perf pro čtení hardwarových čítačů a statistik. Když ho spustím jako perf stat -e cache-misses -e instructions -e cycles -e LLC-prefetches php test.php u obou verzí programu bude hlásit přibližně 7.5 miliardy vykonaných instrukcí, ale ostatní čísla se budou lišit. Rozdílný bude hlavně počet cache-misses: 11.5 milionu proti 25.5 milionu. Cache-miss nastane, když procesor daný kus paměti nemá v interní cache, ke které může přistupovat velice rychle během několika málo taktů, a musí pro něj do hlavní paměti, odkud to trvá až 300 taktů. První verze kvízového programu opakovaně přistupuje k datům jenom z omezeného intervalu a tedy všechno, co potřebuje k práci, se pohodlně vejde do CPU cache. V případě druhé verze chce data z celého rozsahu a jenom pointery pro 2000000 elementů by potřebovaly 16MB paměti (plus objekty na které ukazují). Moderní procesory dostupné pro běžné smrtelníky mají maximálně 8MB L3 cache (cache má několik úrovní, které se liší velikostí a rychlostí přístupu a vždycky platí, že tyto dvě veličiny jsou nepřímo úměrné, L1 je velice malá, ale velice rychlá, L2 je průměrná, L3 velká, ale nejpomalejší), do které se nevejde celý woking set a tím pádem CPU musí číst data z pomalé hlavní paměti. Důležitý je také fakt, že kvízový program k datům přistupoval náhodně. Běžné programy, které pracují s velkým rozsahem dat typicky potřebují nějaká data častěji než jiná a cache se postará o to, aby obsahovala ten nejužitečnější podmnožinu dat.


Třetí otázka je na tom podobně jako ta druhá: pro řešení musím sestoupit úroveň pod PHP a perfem trochu prošťouchnout procesor. Tentokrát mě zajímá hlavně čítač události LLC-prefetches.

Protože přístup do hlavní paměti trvá tak strašlivě dlouho, procesory se snaží před-načítat (prefetch) data do cache, jakmile detekují sekvenční průchod pamětí. Ten je v programech velice běžný, například u smyček, které procházejí celé pole od začátku do konce, jeden element za druhým. Procesor, který prefetchuje, tak vsází na to, že v budoucnu bude chtít blok paměti, která je o kus dál. Když se strefí, potřebná data pro další iterace budou čekat v rychlé cache připravená pro čtení. RAM má sice mizerné latence, ale velice dobrou propustnost (bandwidth) v řádech desítek gigabajtů za vteřinu. Když se celá prefetch mašinerie rozjede, procesor před-načítá bloky dat tak rychle, jak je RAM dokáže servírovat a CPU je čte z cache jen s maličkými prodlevami. V některých případech prefetching zcela skryje latence hlavní paměti a pipelining a OOO i latence cache.

Prefetch je velice efektivní, ale musí mít správné podmínky k práci, tedy nějaký předvídatelný vzor průchodu pamětí. Když program nahání pointery nebo skáče na náhodná místa, prefetch nic nezmůže.

A právě tohle způsobuje rozdíl mezi oběma verzemi programu. Jeden čte sekvenčně a může využít prefetch, druhý čte náhodně a vždycky musí trpět cache-miss a latenci RAM. perf u jedné verze programu ukazuje 3.8 milionu cache-miss a 13.2 milionu LLC-prefetches a u druhého 9.8 milionu cache-miss a 4.5 milionu LLC-prefetches (LLC znamená last level cache, tedy typicky L3). Program, který víc přednačítá má menší počet cache-miss a je rychlejší.


Poslední otázka je kombinací první a třetí. V jedné verzi procházím polem, které zdánlivě vypadá, že má stringové klíče obsahující jenom čísla, ve druhé má pole stejné klíče s krátkým stringovým prefixem a ve třetí stejné klíče se stringových suffixem. První verze je nejrychlejší, druhá je pomalejší a třetí je nejpomalejší (0.24s vs. 0.36s vs. 0.46s).

Jak už jsem psal u první otázky, stringové klíče, které mají celočíselnou hodnotu se zkonvertují na integery a jejich hodnota se bere jako jejich hash. První případ je nejrychlejší proto, že klíče jsou v hashtabulce řazené podle svého numerického pořadí a při sekvenčním průchodu zapracuje prefetch. Pokud před ně přidám stringový prefix, už se musí prohnat hash-funkcí a jejich pozice v hash tabulce nebude odpovídat jejich lexikografickému pořadí a to zabrání prefetcheru dělat jeho práci.

Ale proč je verze s suffixem pomalejší než ta, která prefixuje? Překvapivě to souvisí s hash funkcí a prefetcherem.

Funkce, kterou PHP používá pro hashování klíčů, vypadá takto:

long DJBX33A(const unsigned char *key) {
        long hash = 5381;
        while(*key) hash = 33*hash + *key++;
        return hash;
}

Vezme jeden znak klíče, vynásobí 33, přičte k hashi a posune se na další. A tady leží řešení naší záhady. Když změním poslední znak o jedničku, hash se změní o 33, když změním předposlední, hash se změní o 33*33. První znak má největší dopad na změnu hashe, poslední má nejmenší. V prefixové verzi programu se inkrementuje poslední znak klíče a z jedné iterace na druhou se hash zvětší o 33, tedy o fixní počet, který odpovídá fixnímu kroku v paměti, který prefetcher může detekovat a využít. Naproti tomu, když mám indexy se suffixem, index se zvětšuje o 33*33 = 1089, což v hashtabulce odpovídá kroku 8712 bajtů a s tím si prefetcher, který umí fungovat jenom v rámci jedné stránky paměti, neporadí.

perf tuto teorii pěkně potvrzuje:

perf stat -e cache-misses -e instructions -e cycles -e LLC-prefetches php test.php

no prefix
         2 812 318 cache-misses
     6 386 561 958 instructions              #    2,33  insns per cycle
     2 745 568 076 cycles
        10 578 170 LLC-prefetches

prefix
         9 575 382 cache-misses
     6 690 346 583 instructions              #    1,73  insns per cycle
     3 874 722 279 cycles
        25 827 757 LLC-prefetches

suffix
        13 671 528 cache-misses
     6 983 481 506 instructions              #    1,54  insns per cycle
     4 534 416 656 cycles
        14 652 597 LLC-prefetches

Na výsledcích je zajímavých několik věcí: Za prvé ukazují, že i ve vysokoúrovňových interpretovaných a relativně pomalých jazycích jako PHP, jsou patrné nízkoúrovňové detaily fungování CPU a cache a dopad na výkon může být v některých případech veliký. A za druhé ukazují, že měření výkonu je zrádné. Různé procesory mají různě velké, různě uspořádané a různě rychlé cache s různou asociativitou a všechny tyto detaily můžou mít velký dopad na finální výkon programu. A co víc, naměřená čísla se můžou měnit běh od běhu programu a doslova jeden den může naprosto stejný program běžet o něco pomaleji bez zjevných důvodů.

Další čtení:

flattr this!

Posted in CPU, Paměť, PHP | 1 Comment