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.14 vteřiny pro INTERVAL=1000 a 0.9 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!

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

6 Responses to PHP kvíz (aktualizováno)

  1. Jakub Vrána says:

    Výborný kvíz!

    Jednička je téměř jistě způsobena kolizí klíčů v hash tabulce, do které PHP prvky pole ukládá. Ale překvapuje mě, že to jde tak jednoduše, já jsem se u toho před pěti lety pěkně zapotil.

    Dvojka a trojka je podle mě chyták. Nápověda svádí k tomu myslet si, že PHP přistupuje k prvkům pole sekvenčně, ale to PHP nedělá (možná jen u SplFixedArray, ale to se v příkladu nepoužívá). Je možné, že u dvojky se ten začátek pole vejde do nějakých keší přímo u procesoru a PHP s tím tedy vlastně nemá nic společného? U trojky bych tipnul, že za to bude moci opět procesor a jeho preemptivní čtení paměti.

  2. v6ak says:

    Ta jednička je schválně zavádějící? Pokud factor nastavím na 1048577 (tedy o jedničku vyšší než ten problematický), vrátí se to k původní rychlosti. Tedy jasně kolize.

    Nejjasnější mi přijde trojka. Analogicky prý dokonce i procházení pole pozpátku trvá déle, protože poruším paměťovou lokalitu. Co teprve náhodný průchod, kde v principu by neměla pořádně fungovat žádná predikce. Jak jsi tweetoval, náhodné čtení z paměti je pomalejší než sekvenční čtení z disku.

    Analogicky trojka, ale tam jen vylezu z velikosti keše.

    Proč je v PHP zpomalení menší? Asi kvůli reprezentaci pole – AFAIK se ukládá jako takový hybrid mezi HashMap a LinkedList. V tomto případě čtu podle indexu a nezapisuju, tak by to mělo být principiálně srovnatelné s HashTable.

    (Otázka potom taky je, jak se reprezentují samotné hodnoty – jestli jde o primitivní typy, nebo jestli se to – byť třeba vnitřně – řeší přes referenční typy. Jakmile by šlo o referenční typy, bylo by relativní zpomalení o něco menší.)

    (A další otázkou jsou alokace v paralelních vláknech a správa paměti včetně různých heap compaction mechansmů apod.)

  3. AoJ says:

    Úžasné úlohy.

    (1)
    Vše opravdu ukazuje na kolizi, ale nelíbí se mi to číslo. My ze staré školy v tom vidíme 1MB. Rád bych tenhle příklad někdy lépe prozkoumal.

    (2)
    Používáme-li v php číselnou řadu jako indexy, první kolize se nám objeví s indexem 8448. To se krásně pamatuje :). PHP ukládá kolize jako „linked list“ a u kolizních hashů prochází všechny prvky dokud nenarazí na požadovaný klíč. Všechny prvky s indexem < 8448 jsou tedy na prvním místě kolizní tabulky a přístup k nim je konstantní. INTERVAL tedy můžeme nastavit až na 8448, aby nedošlo k proklamovanému zpomalení.

    @Jakub 1000 položek pole je asi už příliš, aby to mohl procesor udržovat ve své cache.

    (3)
    Při čtení dat z paměti procesor načte vždy i trochu dat z okolí, šahat do RAM je prostě drahé, to už náš učili ve školce :). Nejvíce z toho těží právě sekvenční čtení paměti jako třeba postupné procházení pole v PHP, které je v paměti uložené v jednom bloku.

    V tomhle příkladu je jedno, jestli pole čteme od půlky, od začátku nebo např. od ($i – 10). Pokaždé by měla zafungovat cache procesoru.

    Nenapadá mě jiný důvod jak tohle chování vysvětlit. PHP v tomhle pokud vím nedělá žádnou optimalizaci a prostě načte jen to, co mu řekneme.

    @v6ak u tohohle příkladu by mělo být naprosto jedno, jestli pole budu procházet od začátku nebo od konce. Procesor si přednačítá data z obou stran, efekt by měl být stejný.

  4. v6ak says:

    4: Rozdíl mezi „x“ a "" nevypadá moc záhadně. V jednom případě se indexuje čísly, ve druhém stringy. Nejspíš tu bude nějaká operace na číslech levnější.

    Nicméně rozdíl mezi prefixem a suffixem vypadá divně, tak nevím.

  5. Jan Prachař says:

    1.
    PHP upravuje interně délku pole podle počtu prvků v něm. Prvky pole jsou indexované celočíselně od nuly. Pokud tedy jako FACTOR zvolíme mocninu 2, která je větší než konečný počet elementů, skončí všechny hodnoty v indexu 0, kde jsou kvůli kolizím uloženy jako double linked list.

    2., 3.
    Příčina není jistě v implementaci PHP ale „níž“, jak i sám autor naznačuje.

    4.
    Pokud je klíč numerický řetězec, převede ho PHP na integer a při přístupu k prvům pole ho již nemusí hashovat. Případ s prefixem „x“ je tedy pomalejší, protože dochází k hashování. A případ s postfixem je ještě o fous pomalejší, protože u každého klíče je třeba před hashováním zjistit, že není numerický a to u postfixu trvá déle než u prefixu úměrně délce cifry.

  6. Michal says:

    K otázce č.1:
    Lépe je vidět problém zde http://nikic.github.io/…P-array.html

Leave a Reply

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