PHP: černá magie optimalizace

Když jsem včera psal o optimalizaci PHP skriptů pro rychlost, dostalo se mi v komentářích ostré kritiky. Zdálo se totiž, že řeším podružné detaily. Že tomu tak není, doufám dostatečně demonstrovala droboučká optimalizace jednoho konkrétního a smysluplného skriptu. Podařilo se čas potřebný k vykonání srazit z původních 30 minut na pouhé tři sekundy!

Za drastickým zrychlením stojí opět vhodné užití referencí a přiřazování. V minulém článku jsem leccos naznačil, dnes prozradím celé pozadí. Nevěřte však bulvárnímu titulku, nejde o žádnou černou magii. Znova opakuji, stačí jen pochopit, jak PHP funguje uvnitř. Ale nebojte se, není to nic složitého.

Reference counting do hloubky

Jádro PHP si v paměti ukládá jména proměnných odděleně od jejich hodnot. Bezejmennou hodnotu popisuje struktura zval. Ta nese kromě surových dat také informaci o typu (boolean, string, …) a ještě dvě položky refcount a is_ref. Ano, refcount je právě počítadlo pro již zmíněný reference counting.

$abc = 'La Trine';

Co dělá skutečně tento kód? Vytvoří v paměti novou hodnotu zval, jejíž datová složka ponese 8 znaků La Trine a typ bude indikovat string. Zároveň se do tzv. tabulky proměnných přidá nový záznam abc a bude odkazovat na tuto hodnotu zval.

Ještě něco. Ve struktuře zval inicializujeme počítadlo refcount na jedničku, protože existuje právě jedna proměnná ($abc), která na něj ukazuje.

// 10MB velký řetězec
$sA = str_repeat(' ', 1e7);

$sB = $sA;

Jak si PHP poradí s přiřazením na druhém řádku? Samozřejmě, vytvoří v tabulce proměnných nový záznam sB. Teď pozor – záznam bude odkazovat na stejný zval, na jaký odkazuje již záznam sA. A zároveň inkrementuje počítadlo refcount.

Což je skvělé! Není potřeba zabrat dalších 10MB paměti, nedojde k časově náročnému kopírování dat. Operace proběhne bleskově.

Nojo, ale z pohledu PHP programátora jde o dvě různé proměnné. Co když jednu změním?

$sB .= 'the end';

Žádný strach, o všechno je postaráno. Když vznikne požadavek na zápis do proměnné, PHP se podívá na odkazovaný zval a zkontroluje počítadlo refcount. Pokud refcount > 1, tak celou hodnotu zval zduplikuje a nechá sB odkazovat na tuto kopii. Samozřejmě ještě sníží refcount u původního zval.

Pro úplnost ještě dodám, že konstrukce unset($sB) zruší záznam sB v tabulce proměnných a dekrementuje příslušný refcount. A jakmile refcount padne k nule, z paměti uvolní strukturu zval – už na ni totiž žádná proměnná neodkazuje.

Klasické reference, penetrované do hloubky

Zatím je vše jasné? Tak pojďme na druhou lekci a ukažme si, jak jádro nakládá s klasickými referencemi.

$a = 'La Trine';
$b = & $a;

Jakým způsobem PHP vykoná první řádek, to už dobře víte. Co se ale děje pod kapotou v případě řádku druhého? Když jsem popisoval strukturu zval, zmínil jsem se o is_ref. Jde o boolean, indikující, zda hodnota zval je či není referencí. A právě teď přichází jeho patnáct minut slávy.

PHP vytvoří proměnnou $b úplně stejně, jako v příkladu bez použití reference, jen navíc nastaví is_ref na TRUE. V tuto chvíli se proměnné $a i $b (obě!) stávají referencemi, tak jak je známe.

Podstatný rozdíl přijde v okamžiku, kdy se pokusíme jednu proměnnou změnit. Protože is_ref je TRUE, vynechá se test na refcount a s ním celý mechanismus duplikování. Prostě se rovnou změní společná hodnota zval. I když… ale k tomu se hned dostaneme.

Můžeme vytvářet další reference $xyz = & $a, rušit je unset($b), princip zůstává stejný. Jádro pracuje s tabulkou proměnných a aktualizuje počítadlo refcount.

Stále všechno srozumitelné? Jestli náhodou ne, zkuste si přečíst článek ještě jednou a pomaleji. Nyní totiž bude potřeba maximální soustředěnost.

Půvab pomalu mizí

Zkuste se zamyslet nad tím, jak PHP vykoná následující kód:

$a = 'La Trine';
$b = & $a;
$c = $a;

Proměnné $a a $c odkazují na tentýž zval, mající vynulovaný is_ref. Proměnné $a a $b ale zase potřebují mít is_ref nastavený. To lze vyřešit leda tak, že budeme mít dvě hodnoty zval.

Jinými slovy, řádek č. 3 musí duplikovat hodnotu zval:

Výše uvedený algoritmus pro vytváření nových proměnných je proto potřeba doplnit o podmínku: pokud je refcount > 1 a „neodpovídá“ požadovaný is_ref, tak holt duplikuj a nekoukej, co kde lítá.

Obdobně, duplikovat se bude i v tomto případě:

$a = 'I love La Trine :-)';
$b = $a
$c = & $a;

Vidíte to? Vytváření reference duplikuje hodnotu proměnné. Kopie, s nastaveným is_ref, bude odkazována proměnnými $a a $c (jen pro úplnost, refcount = 2).

Možná si teď říkáte, co to je za šílenost, proč je jádro PHP tak špatně navrženo? Věřte mi, není. Jde o běžný problém sdíleného vs. exkluzivního přístupu, jen se nazývá jinak. Dalo by se tomu vyhnout, ale změna návrhu by natolik zkomplikovala práci s proměnnými, že by byla v globálu zcela kontraproduktivní.

Optimalizace Johnova skriptu

Konečně můžu vysvětlit trik stojící za optimalizací Johnova skriptu.

...
$arr = &$this->table;
foreach($ngram as $token) {
//    if(!array_key_exists($token, $arr)) {
//      $arr[$token] = array();
//    }
  $arr = &$arr[$token];
}
...

Mohlo by se zdát, že za úspěchem stojí odstranění funkce array_key_exists, která je nejspíš tak šíleně pomalá, až to celé stáhla ke dnu. No schválně, kdo si to myslel, ať mi pošle Nutellu Kdepak. Pes je zakopán jinde.

Teď už víte, že předávaná proměnná $arr odkazuje zval, mající nastavený bit is_ref a počítadlo refcount = 2 (hodnota je odkazována z $arr a zároveň samotným prvkem pole). Co je klíčové, tak že tento zval pojímá obrovské pole.

Při přiřazení do funkce array_key_exists se stane nevyhnutelné – zval se musí zduplikovat. Což doslova zatáhne brzdu jedoucímu skriptu. Kdyby se volala třeba funkce key(), která parametr přebírá referencí, nebo kdybychom porušili zapovězenou syntax Call-time pass-by-reference a argument vnutili referencí array_key_exists($token, &$arr), tak ke kopírování nedojde. A skript se 600× zrychlí.

Bílá magie optimalizace

Mým cílem bylo smést pověry a mýty kolem referencí. Že jsou něco jako ukazatele, že zrychlí kód. Pravda je taková, že všechny proměnné jsou de facto ukazatelé. Jen se liší způsob, jak s nimi jádro PHP pracuje.

Pokud tyto principy znáte, můžete je využit ve svůj prospěch (zdůrazňuji slovo „můžete“). Můžete efektivněji nakládat s řetězci nebo poli. Jakmile vám přejdou do krve, budete je využívat zcela podvědomě, stane se z nich Coding Standard.