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_re­size).

Stringové klíče jsou hashovány funkcí DJBX33A (viz zend_inline_hash_fun­c), 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!

This entry was posted in CPU, Paměť, PHP. Bookmark the permalink.

One Response to Výsledky PHP kvízu

  1. Jakub Vrána says:

    Ještě jednou díky za tento poučný kvíz. Já konkrétně jsem se dozvěděl, že PHP číselné klíče nehašuje. Skoro bych se vsadil, že to dřív bylo jinak. Ale pravda je taková, že použití jejich hodnoty místo haše má ve většině případů značnou výhodu.

Leave a Reply

Your email address will not be published. Required fields are marked *