0xDEADBEEF

Top-k v PHP 7 a 8

PHP a rychlost se v jedné větě nevyslovuje příliš často a když už tak převážně v negativním smyslu. Přesto limitem jsou jen naše ambice. Někdy můžeme chtít vylovit top-k položek z několika desítek tisíc a chceme to udělat za pár milisekund, protože proč ne.

V PHP mám na výběr z několika způsobů jak vybrat top-k dle určitého kritéria. Můžu řadit nebo se uchýlit k použití SplHeap/SplPriorityQueue. Pár možností jsem otestoval v PHP 7.4.11 a pak v nově vydaném PHP 8 zhruba následujícím způsobem (kompletní benchmark zde)

$k = 25;
// === usort ===
usort($items, function ($a, $b) {
  return $b->weight <=> $a->weight;
});
return array_slice($items, 0, $k);

// === index + asort ===
$indexedWeights = array_fill(0, count($items), 0.0);
foreach ($items as $i => $item) {
  $indexedWeights[$i] = $item->weight;
}
asort($indexedWeights, SORT_NUMERIC);
$indexes = array_reverse(array_slice($indexedWeights, -$k, null, true), true);
return array_intersect_key($items, $indexes);

// === heap ===
$heap = new class extends \SplHeap {
  function compare($a, $b) {
    return $a->weight <=> $b->weight;
  }
};
foreach ($items as $item) {
  $heap->insert($item);
  if ($heap->count() > $k)
    $heap->extract();
}
return iterator_to_array($heap);

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

// === priority queue + guard ===
$heap = new \SplPriorityQueue;
foreach ($items as $item) {
  if ($heap->count() >= $k) {
    if ($item->weight > $heap->top()->weight) {
      $heap->insert($item, -$item->weight);
      $heap->extract();
    }
  } else {
    $heap->insert($item, -$item->weight);
  }
}
return iterator_to_array($heap);

Výsledky pro PHP 7 (na i5-2520M):

Naivní usort stejně jako heap je pomalý. Nejspíš to má na svědomí prostý fakt, že efektivní C kód volá zpět do PHP pro provedení komparátoru. Naproti tomu rychlejší SplPriorityQueue (stejní složitost n log(k) jako heap) provádí porovnání plně na straně C. Z PHP jen zavolám insert určitého objektu s určitou váhou a porovnání a balancování heapu běží plně na straně C.

Zajímavé je taky, že varianta index + asort, která vstup převede na pole jehož klíč je numerický index a hodnotou váha dle níž se řadí, aby se dal použít asort, je ještě o něco rychlejší než SplPriorityQueue. Za rychlost může nejspíš fakt, že poté, co je struktura připravena, řazení běží zcela na straně C kódu (plus data mají lepší lokalitu). I když je asymptoticky pomalejší, reálná rychlost pro reálná data jako vždy hraje větší roli. To je dobrá zpráva, takhle nemám k dispozici jen top-k, ale rovnou top-cokoli. Stačí jednou seřadit a můžu vytáhnout jakoukoli stránku výsledku. To otevírá nové možnosti.

Řádky heap + guard a priority queue + guard jsou nejrychlejší. U nich záleží na selektivitě guard podmínky, ta je závislá na vstupních datech. Podmínka přidá konstantní čas per element, ale může odfiltrovat zbytečnou O(log(n)) operaci. Pokud brzo vychytá velká čísla, filtruje velice efektivně. Na druhou stranu v případě plně seřazeného vstupu je pomalejší než naivní použití SplPriorityQueue. Na reálných řadách je stále znatelně svižnější, než všechny ostatní varianty.

Poslední sloupec pak ukazuje zpomalení, když se vstup zvětší 10×. Není na nich nic překvapivého. Všechno sedí dle asymptotické složitosti. Zajímavé jsou varianty s guard podmínkami, které jsou rychlejší, než by odpovídalo nárůstu dat, ale to také dává perfektní smysl.

Když jsem napsal první verzi tohohle článku (což bylo někdy v srpnu), PHP 8 ještě nebylo oficiálně vydané. Spekuloval jsem, jaký dopad může mít JIT a jaká bude cena přechodu z PHP do C runtime, která v tomhle testu má poměrně velký vliv a jestli bude aspoň nějak moci optimalizovat volání C funkcí ze zkompilovaného PHP, kde jsou známé typy proměnných. Teď, když je PHP 8 oficiálně venku, nemůžu se spokojit jen s planými spekulacemi.

V čerstvě zkompilovaném PHP 8 jsem rozjel benchmark znovu přes php8 -d'zend_extension=modules/opcache.so' -d'opcache.enable_cli=1' -d'opcache.jit_buffer_size=128M'

(Pokud jsem se dobře díval, opcache a tedy ani JIT není pro CLI ve výchozím stavu povolený, což mi přijde paradoxní. V dokumentaci se přímo zmiňují, že JIT bude mít největší dopad na „nestandardní“ aplikace, které netráví většinu času čekáním na odpověď databáze. Konzolové programy jsou přesně tyhle nestandardní aplikace.)

Poslední sloupec udává relativní zrychlení s JITem pro případ top-25 z 20000 prvků. První dva jsou o něco pomalejší, ale tomu bych nevěnoval velkou pozornost. Jde jen o procenta a JIT je v první ostré verzi. Nebojím se, že se situace změní. Nicméně důležitá je jedna věc: Testy, kde program přebíhá z C do PHP a nazpátek nedoznaly velkého zrychlení. heap o něco málo, ale nijak závratně. Naproti tomu testy běžící z většiny v PHP, zrychlily znatelně.

Ještě by se mi líbilo, kdyby PHP při řazení s příznakem SORT_NUMERIC řadilo pomocí radix sortu. Ten by mohl poskytnout celkem zásadní zrychlení, ne pouhá procenta, ale násobky. Asi bych to měl udělat sám, však víte, co se říká o free software: „Bez politických cílů je to jen neplacená práce.“ Ne tohle, to druhé, co se říká: „Udělej si to sám a neotravuj.“ Měl bych už jen proto, abych mohl zmateným masám tvrdit, že PHP je nejrychlejší v řazení.

(Dodatek: Od napsání článku jsem se do toho pustil a prototyp radixového řazení bývá 3x-4× rychlejší.)