0xDEADBEEF

Optimalizace SplPriorityQueue

Existují dva druhy lidí: jedni v životě nepoužili haldu, druzí pro ní najdou uplatnění každou chvíli. A vzhledem k tomu, že právě bylo do PHP začleněno pár mých optimalizací této datové struktury, je jasné do jaké kategorie patřím.

\SplPriorityQueue je jedna ze základních tříd v PHP, implementuje prioritní frontu haldou a celá je napsaná v jazyce C. V situacích, kdy potřebuji získat top-k položek podle numerické priority, je mnohem efektivnější než \SplHeap. Pro něj je třeba implementovat vlastní compare metodu, což ve výsledku znamená, že pro každé porovnání (kterých je třeba udělat log(n) pro vložení nebo odstranění elementu), musí přejít z C kódu do PHP a to není zrovna nejrychlejší. Nepoděděná \SplPriorityQueue porovnání implementuje plně na straně jazyka C, nemusí odskakovat do PHP a ve výsledku je mnohem rychlejší. To jsem testoval někdy minule.

\SplHeap:
PHP -> C insert -> C cmp -> PHP compare

\SplPriorityQueue:
PHP -> C insert -> C cmp

I když \SplPriorityQueue je pro tohle použití rychlá, našlo se v ní několik příležitostí pro zrychlení. Stačilo vzít maličký benchmark, prohnat ho přes perf record a bylo jasno. Protože jde o kód v C, perf bez pomoci vyplivne horké funkce: memcpy, parsování argumentů a zend_compare.

Benchmark vypadal takhle:

$heap = new \SplPriorityQueue;
foreach ($items as $item) {
  $heap->insert($item, -$item->weight);
  if ($heap->count() > $k)
    $heap->extract();
}
return iterator_to_array($heap);

Vytvoří frontu a v ní akumuluje $k objektů s největší vahou (náhodně generovaný double 0-1, celkem 20000 položek). Nic moc se v něm neděje a každá neefektivita je vidět.

První bylo parsování parametrů. PHP má několik způsobů jak ověřovat parametry předané z dynamicky typované strany PHP userspace. Jednou z nich je funkce zend_parse_parameters, v \SplPriorityQueue::insert použitá takhle:

zend_parse_parameters(ZEND_NUM_ARGS(), "zz", &data, &priority)

Kolik parametrů bylo předáno, jejich typy (z znamená generický zval) a pak pointery na proměnné do nichž se mají přesunout. Je to obyčejná funkce, navíc vararg funkce a při každém zavolání musí parsovat string, což znamená gigantický switch a spoustu skoků.

PHP nabízí ještě jednu metodu toho samého za pomocí maker. Není tak stručná, ale je efektivnější.

ZEND_PARSE_PARAMETERS_START(2, 2)
  Z_PARAM_ZVAL(value);
  Z_PARAM_ZVAL(priority);
ZEND_PARSE_PARAMETERS_END();

Záměna první metody za druhou benchmark zrychlila o 15% – 20%.

Další potíž, kterou odhalil perf bylo volání memcpy. Jde o to, že \SplHeap a \SplPriorityQueue sdílí velkou část interní implementace. Hlavní rozdíl spočívá v tom, že \SplHeap uchovává zvaly (16B structy pro PHP hodnoty a spolu s jejich typovou informací), ale \SplPriorityQueue uchovává dvojice zvalů – jeden pro položku, druhý pro její prioritu.

Funkce kopírující interní data délku abstrahuje a vypadá takhle:

static zend_always_inline void spl_heap_elem_copy(spl_ptr_heap *heap, void *to, void *from) {
  assert(to != from);
  memcpy(to, from, heap->elem_size)
}

heap->elem_size je 16 pro \SplHeap a 32 pro \SplPriorityQueue. Jsou jen 2 možnosti, ale pro kompilátor jde o dynamickou délku. Nemůže memcpy inlinovat. V tomto případě kopírování jsou jen 2 nebo 4 instrukce (zkopírovat z paměti do xmm registrů a z nich zpět do paměti, xmm má 16 bajtů na délku). Generický memcpy je seriózní kus kódu, který si musí poradit se vším a samo volání má nezanedbatelnou režii.

Stačí malá změna, z délek se stanou konstanty a kompilátor může vše efektivně inlinovat.

if (heap->elem_size == sizeof(spl_pqueue_elem)) {
  memcpy(to, from, sizeof(spl_pqueue_elem));
} else {
  memcpy(to, from, sizeof(zval));
}

To na benchmarku přidá dalších asi 10%.

Poslední vylepšení není tak triviální, jako ty předchozí i když nic nového pro autory kompilátorů a JITů. Zakládá se na předpokladu, že nepoděděná \SplPriorityQueue bude často používána jen s celočíselnými nebo jen double prioritami a typy se v nich nebudou mísit. Inty třeba pro pořadí, double pro míru podobnosti nebo něco na ten způsob. V benchmarku nahoře $item->weight má typ double.

S tímhle předpokladem můžeme oportunisticky specializovat komparátor, pokud víme, že v haldě jsou přítomné jen int nebo double priority. Standardní funkce porovnávající zvaly, zend_compare, je velký komplikovaný switch. Musí být, aby zvládal všechny kombinace všech typů. Když ale víme, že budeme porovnávat jen double nebo inty, můžeme ho vyměnit za specializovaný, který porovnává přímo a efektivně.

Při prvním vložení do prázdné haldy se komparátor, pokud je to možné, specializuje. Při vkládání do neprázdné, se pak kontroluje, jestli typy sedí a pokud ne konparátor se změní zpátky na ten generický.

// kontrola, že třídu nikdo nepřepsal a komparátor je výchozí
if (!intern->fptr_cmp) {
  // typ priority
  int type = Z_TYPE(elem.priority);

  // komparátor pro daný typ
  spl_ptr_heap_cmp_func new_cmp =
    (type == IS_LONG) ? spl_ptr_pqueue_elem_cmp_long :
    ((type == IS_DOUBLE) ? spl_ptr_pqueue_elem_cmp_double : spl_ptr_pqueue_elem_cmp);

  // když je fronta prázdná, specializujeme pro typ priority
  if (intern->heap->count == 0) {
    intern->heap->cmp = new_cmp;

  // pokud došlo ke konfliktu typů, vrátíme se na generický komparátor
  } else if (new_cmp != intern->heap->cmp) {
    intern->heap->cmp = spl_ptr_pqueue_elem_cmp;
  }
}

Kontrola typů zabere asi 1% času v benchmarku, kde se neděje nic moc jiného. Pokud se používá genetický komparátor, relativní cena bude menší z důvodu, že se tráví víc času porovnáváním.

Identický mechanismus se může použít pro sledování typů a specializaci jakýchkoli datových struktur.

Všechny tři změny dohromady vedou k téměř dvojnásobnému zrychlení v případech, kdy se \SplPriorityQueue používá výhradně s int/double prioritami a menším zrychlení v případě smíšených typů. (benchmark tady)

       | PHP 7.4       | PHP 8         |  PHP 8 master
int    | 3.972 ms/iter | 3.455 ms/iter | 1.805 ms/iter
double | 4.112 ms/iter | 3.617 ms/iter | 1.939 ms/iter
mixed  | 4.141 ms/iter | 3.618 ms/iter | 2.731 ms/iter

JIT pak odřízne 0.3 – 0.4 ms od každého řádku.

To ale není všechno. V rukávu jsem měl ještě jeden trik.

insert i extract jsou log(n) operace a mnohdy chceme dělat tyhle dvě operace najednou – odstranit vrcholek haldy a nahradit ho jiným prvkem. V tom případě obnovu haldy zvládne jediná log(n) operace. Veřejné API to ale nenabízí.

Dá se to ale obejít: Při vložení nového elementu se hned nezapíše do haldy, ale nechá se bokem v předpokladu, že bude následovat extract operace. Pak můžeme efektivně spojit dvě logaritmické operace do jedné. Ale navíc, když odložený element je menší než současný vrcholek haldy, můžeme ho rovnou vrátit a práci s haldou úplně eliminovat. V případě top-k benchmarku, kde tahle dvojice volání dominuje, to vede k dalšímu zrychlení. Asi o 20 – 25%.

Problém je jen v tom, že když to samé napíšu na straně PHP userspace – uchovávat minimum haldy v proměnné a dělat dvojici insert, extract jen když je současný element větší než tohle minimum – je to mnohem rychlejší. V extrémním případě až 5× rychlejší, než co se dá dosáhnout optimalizací C kódu.

Ukazuje se, že cena přechodu z PHP do C (nebo cena volání členských funkcí jako takových), není nejmenší a může být efektivnější zůstat plně na straně PHP.

Extrémní varianta top-k testu může vypadat takhle:

$heap = new \SplPriorityQueue;

$count = 0;
$minWeigth = null;

foreach ($items as $item) {
  if ($count < $limit) {
    $heap->insert($item, -$item->weight);
    $count = $heap->count();
    $minWeigth = $heap->top()->weight;

  } else if ($item->weight > $minWeigth) {
    $heap->insert($item, -$item->weight);
    $heap->extract();
    $minWeigth = $heap->top()->weight;
  }
}

return iterator_to_array($heap);

Všechny styčné body s C jsou chráněné proměnnými na PHP straně. Tahle varianta běží (pro stejné hodnoty jako benchmark nahoře) 0.3 ms/iteraci v interpretru a 0.15 ms/iteraci pod JITem.

Nedává smysl dál optimalizovat něco, co se dá relativně snadno a mnohem efektivněji dosáhnout jinou cestou. (Ok, leda s výjimkou, že to o něco zrychlí i programy, které se nijak extra nesnaží.)

Nicméně tahle cena přechodu z PHP do C mě překvapila a začíná být jasné, že plným využitím potenciálu JITu, bude hrát čím dál tím větší roli. JIT nevidí do C funkcí (teoreticky může, ale v PHP tak nečiní), ty jsou pro něj černé skříňky, které musí brát, jak jsou. Představují bariéru pro optimalizace. JIT může perfektně znát typy argumentů, alokoval je do registrů, ale jakmile volá do C, musí je zabalit do zvalů, do formátu jak je očekává interpretr, aby si je na straně C funkce zase rozbalila. V nepříliš vzdálené budoucnosti tak může začít dávat smysl přepisovat nativní funkce z C do PHP.¹ V tom případě JIT uvidí skrz ně a může plně optimalizovat napříč programem.

Ten čas možná přišel už teď. Zkusmo jsem v PHP napsal kopii generické \SplHeap a v PHP 8 pod JITem je asi o 15% rychlejší než nativní verze.

1. Další možná cesta, je rozdělení C funkcí na část, která se stýká s interpretrem, a na jejich jádro. Jako příklad si vezměte funkci strtolower. Ta je definovaná takhle:

PHP_FUNCTION(strtolower)
{
  zend_string *str;

  ZEND_PARSE_PARAMETERS_START(1, 1)
    Z_PARAM_STR(str)
  ZEND_PARSE_PARAMETERS_END();

  RETURN_STR(php_string_tolower(str));
}

Má dvě logické části: jednak parsování a validaci parametrů z pole zvalů a druhak samotnou logickou část (tady je to volání php_string_tolower). Pokud by runtime a JIT věděl o tomto rozdělení, mohl by ho použít. Kdyby znal typy parametrů, mohl by zavolat přímo php_string_tolower. Nastrkal by parametry do registrů, uklidil by registry, které chce zachovat a celkově by volal přes standardní céčkovské ABI. Pokud by nemohl dokázat, že typy pasují, musel by volat klasickou cestou. A protože premisou JITů je to, že dynamické programy se za běhu chovají velice staticky, mohlo by to být efektivní v eliminaci režie VM, přičemž nebude třeba přepsat velkou část interního kódu. Rozdělování by ve velkém množství případů bylo poměrně mechanickou transformací.