funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

Výsledky PHP kvízu

23. 4. 2014 — k47

Před ně­ja­kou dobou jsem tu zve­řej­nil ma­ličký PHP kvíz, teď je načase od­ha­lit správné od­po­vědi.

Ty jsou ná­sle­du­jící:

  1. kolize hashů
  2. ve­li­kost CPU cache
  3. cache pre­fet­ching
  4. ha­sho­vání klíčů polí a cache pre­fet­ching

První otázka byla jed­no­du­chá a šlo po­cho­pi­telně o kolize hashů.

V PHP je všechno hash ta­bulka: pole, de­kla­ro­vané a ne­de­kla­ro­vané pro­měnné ob­jektu a do­konce i metody jsou or­ga­ni­zo­vány jako hash ta­bulky. Je­di­nou vý­jim­kou je SplFixedArray, které je in­terně or­ga­ni­zo­vané jako sku­tečné pole.

PHP pole (viz Ha­sh­Table ve zdro­já­cích PHP) má po vy­tvo­ření ka­pa­citu 8 (viz _zend_hash_init). Když do něj začnu při­dá­vat po­ložky a do­sáhnu této hra­nice, PHP pole zvětší svoji ka­pa­citu na dvoj­ná­so­bek (viz funkce zend_hash_do_resize).

Strin­gové klíče jsou ha­sho­vány funkcí DJBX33A (viz zend_inline_hash_func), ale ce­lo­čí­selné klíče se po­u­žijí přímo a co víc: strin­gové klíče, které ob­sa­hují číslo se na tohle číslo pře­ve­dou. Tohle uspo­řá­dání má pře­kva­pivý dopad na výkon: Když po­u­ží­vám PHP pole jako sku­tečné pole, tedy mám jen nu­me­rické klíče bez mezer z ur­či­tého in­ter­valu, jsou po­ložky se­řa­zeny přímo podle klíče. Po­ložka s in­de­xem 5 je tedy v paměti hned vedle po­ložky s in­de­xem 6 a to je dobré pro CPU cache. Kdy­bych klíče ha­sho­val, sou­sední indexy by se na­chá­zely na růz­ných mís­tech ta­bulky, které nijak ne­od­po­ví­dají jejich nu­me­ric­kému řazení (o tomto se ještě zmíním u čtvrté otázky).

Z tohoto důvodu pro kolizi ne­mu­sím slo­žitě hledat klíče, je­jichž hash bude ko­li­do­vat s jinými klíči (jak to před pěti lety udělal Jakub Vrána), ale prostě po­u­žiji ce­lo­čí­selné klíče, které přímo ko­li­dují. Pro­tože PHP pole začíná na ve­li­kosti 8 a zvět­šuje se na dvoj­ná­so­bek, stačí si vy­bí­rat klíče, které mají stejné $key % (pow(2, $n) * 8) pro nějaké do­sta­tečně velké $n, tedy nej­lépe $i * FACTOR. Já zvolil FACTOR=1048576, což od­po­vídá 8 * pow(2, 17), tedy ve­li­kosti 17x zvět­še­ného pole. FACTOR musí být větší než ka­pa­cita pole, jinak všechny klíče ne­bu­dou ko­li­do­vat do jed­noho místa, ale do ně­ko­lika.

Aby se tomu pře­de­šlo, stačí zvolit jiný způsob zvět­šo­vání ka­pa­city ta­bulky. Například začít na kapacitě 10 a novou velikost určit jako $ca­pa­city << 1`.

Dále k tématu útoků pomocí kolizí hash ta­bu­lek:


Druhá otázka byla o něco slo­ži­tější, pro­tože nejde o čistě zá­le­ži­tost PHP, ale toho, jak se chová pro­ce­sor na němž PHP běží.

Pří­činu snadno odhalí li­nu­xový ná­stroj perf pro čtení hard­wa­ro­vých čítačů a sta­tis­tik. Když ho spus­tím jako perf stat -e cache-misses -e instructions -e cycles -e LLC-prefetches php test.php u obou verzí pro­gramu bude hlásit při­bližně 7.5 mi­li­ardy vy­ko­na­ných in­strukcí, ale ostatní čísla se budou lišit. Roz­dílný bude hlavně počet cache-misses: 11.5 mi­li­onu proti 25.5 mi­li­onu. Cache-miss na­stane, když pro­ce­sor daný kus paměti nemá v in­terní cache, ke které může při­stu­po­vat velice rychle během ně­ko­lika málo taktů, a musí pro něj do hlavní paměti, odkud to trvá až 300 taktů. První verze kví­zo­vého pro­gramu opa­ko­vaně při­stu­puje k datům jenom z ome­ze­ného in­ter­valu a tedy všechno, co po­tře­buje k práci, se po­ho­dlně vejde do CPU cache. V pří­padě druhé verze chce data z celého roz­sahu a jenom poin­tery pro 2000000 ele­mentů by po­tře­bo­valy 16MB paměti (plus ob­jekty na které uka­zují). Mo­derní pro­ce­sory do­stupné pro běžné smr­tel­níky mají ma­xi­málně 8MB L3 cache (cache má ně­ko­lik úrovní, které se liší ve­li­kostí a rych­lostí pří­stupu a vždycky platí, že tyto dvě ve­li­činy jsou ne­přímo úměrné, L1 je velice malá, ale velice rychlá, L2 je prů­měrná, L3 velká, ale nej­po­ma­lejší), do které se ne­ve­jde 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ý pro­gram k datům při­stu­po­val ná­hodně. Běžné pro­gramy, které pra­cují s velkým roz­sa­hem dat ty­picky po­tře­bují nějaká data čas­těji než jiná a cache se po­stará o to, aby ob­sa­ho­vala ten nej­u­ži­teč­nější pod­mno­žinu dat.


Třetí otázka je na tom po­dobně jako ta druhá: pro řešení musím se­stou­pit úroveň pod PHP a perfem trochu proš­ťouch­nout pro­ce­sor. Ten­to­krát mě zajímá hlavně čítač udá­losti LLC-prefetches.

Pro­tože pří­stup do hlavní paměti trvá tak straš­livě dlouho, pro­ce­sory se snaží před-na­čí­tat (pre­fetch) data do cache, jakmile de­te­kují sek­venční prů­chod pamětí. Ten je v pro­gra­mech velice běžný, na­pří­klad u smyček, které pro­chá­zejí celé pole od za­čátku do konce, jeden ele­ment za druhým. Pro­ce­sor, který pre­fet­chuje, tak vsází na to, že v bu­doucnu bude chtít blok paměti, která je o kus dál. Když se strefí, po­třebná data pro další ite­race budou čekat v rychlé cache při­pra­vená pro čtení. RAM má sice mi­zerné la­tence, ale velice dobrou pro­pust­nost (ban­dwi­dth) v řádech de­sí­tek gi­ga­bajtů za vte­řinu. Když se celá pre­fetch ma­ši­ne­rie roz­jede, pro­ce­sor před-načítá bloky dat tak rychle, jak je RAM dokáže ser­ví­ro­vat a CPU je čte z cache jen s ma­lič­kými pro­dle­vami. V ně­kte­rých pří­pa­dech pre­fet­ching zcela skryje la­tence hlavní paměti a pi­pe­li­ning a OOO i la­tence cache.

Pre­fetch je velice efek­tivní, ale musí mít správné pod­mínky k práci, tedy nějaký před­ví­da­telný vzor prů­chodu pamětí. Když pro­gram nahání poin­tery nebo skáče na ná­hodná místa, pre­fetch nic ne­zmůže.

A právě tohle způ­so­buje rozdíl mezi oběma ver­zemi pro­gramu. Jeden čte sek­venčně a může využít pre­fetch, druhý čte ná­hodně a vždycky musí trpět cache-miss a la­tenci RAM. perf u jedné verze pro­gramu uka­zuje 3.8 mi­li­onu cache-miss a 13.2 mi­li­onu LLC-pre­fet­ches a u dru­hého 9.8 mi­li­onu cache-miss a 4.5 mi­li­onu LLC-pre­fet­ches (LLC zna­mená last level cache, tedy ty­picky L3). Pro­gram, který víc před­na­čítá má menší počet cache-miss a je rych­lejší.


Po­slední otázka je kom­bi­nací první a třetí. V jedné verzi pro­chá­zím polem, které zdán­livě vypadá, že má strin­gové klíče ob­sa­hu­jící jenom čísla, ve druhé má pole stejné klíče s krát­kým strin­go­vým pre­fi­xem a ve třetí stejné klíče se strin­go­vých su­f­fi­xem. První verze je nej­rych­lejší, druhá je po­ma­lejší a třetí je nej­po­ma­lejší (0.24s vs. 0.36s vs. 0.46s).

Jak už jsem psal u první otázky, strin­gové klíče, které mají ce­lo­čí­sel­nou hod­notu se zkon­ver­tují na in­te­gery a jejich hod­nota se bere jako jejich hash. První případ je nej­rych­lejší proto, že klíče jsou v ha­sh­ta­bulce řazené podle svého nu­me­ric­kého pořadí a při sek­venč­ním prů­chodu za­pra­cuje pre­fetch. Pokud před ně přidám strin­gový prefix, už se musí pro­hnat hash-funkcí a jejich pozice v hash ta­bulce nebude od­po­ví­dat jejich le­xi­ko­gra­fic­kému pořadí a to za­brání pre­fet­cheru dělat jeho práci.

Ale proč je verze s su­f­fi­xem po­ma­lejší než ta, která pre­fi­xuje? Pře­kva­pivě to sou­visí s hash funkcí a pre­fet­che­rem.

Funkce, kterou PHP po­u­žívá pro ha­sho­vá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, vy­ná­sobí 33, přičte k hashi a posune se na další. A tady leží řešení naší záhady. Když změním po­slední znak o jed­ničku, hash se změní o 33, když změním před­po­slední, hash se změní o 33*33. První znak má nej­větší dopad na změnu hashe, po­slední má nejmenší. V pre­fi­xové verzi pro­gramu se in­kre­men­tuje po­slední znak klíče a z jedné ite­race na druhou se hash zvětší o 33, tedy o fixní počet, který od­po­vídá fix­nímu kroku v paměti, který pre­fet­cher může de­te­ko­vat a využít. Na­proti tomu, když mám indexy se su­f­fi­xem, index se zvět­šuje o 33*33 = 1089, což v ha­sh­ta­bulce od­po­vídá kroku 8712 bajtů a s tím si pre­fet­cher, který umí fun­go­vat jenom v rámci jedné stránky paměti, ne­po­radí.

perf tuto teorii pěkně po­tvr­zuje:

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ý­sled­cích je za­jí­ma­vých ně­ko­lik věcí: Za prvé uka­zují, že i ve vy­so­ko­úrov­ňo­vých in­ter­pre­to­va­ných a re­la­tivně po­ma­lých ja­zy­cích jako PHP, jsou patrné níz­ko­úrov­ňové de­taily fun­go­vání CPU a cache a dopad na výkon může být v ně­kte­rých pří­pa­dech veliký. A za druhé uka­zují, že měření výkonu je zrádné. Různé pro­ce­sory mají různě velké, různě uspo­řá­dané a různě rychlé cache s různou aso­ci­a­ti­vi­tou a všechny tyto de­taily můžou mít velký dopad na fi­nální výkon pro­gramu. A co víc, na­mě­řená čísla se můžou měnit běh od běhu pro­gramu a do­slova jeden den může na­prosto stejný pro­gram běžet o něco po­ma­leji bez zjev­ných důvodů.

Další čtení:

@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články