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 <a href="http://php.vrana.cz/zakerne-pole.php">pěkně zapotil</a>.
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.
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.)
AoJ(2014-03-30 20:44)
Úž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: 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.
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.
Michal(2014-05-22 11:48)
K otázce č.1: Lépe je vidět problém zde http://nikic.github.io/2011/12/28/Supercolliding-a-PHP-array.html
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 <a href="http://php.vrana.cz/zakerne-pole.php">pěkně zapotil</a>.
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.