0xDEADBEEF

RSS
««« »»»

Co vlastně benchmarkujete?

4. 8. 2018

Před nějakou dobou jsem narazil na článek, který se snažil testovat rychlost a paměťové nároky asociativních polí a různých variant objektů v PHP. Závěr byl ten, že objekty jsou skoro ve všech ohledech buď srovnatelné nebo lepší než asociativní pole, hlavně co se týká paměťových nároků1 .

Ale stačil jediný pohled, abych věděl, že je něco špatně. Benchmark asociativních polí vypadal takhle:

<?php
declare(strict_types=1);
error_reporting(E_ALL | E_STRICT);
const TEST_SIZE = 1000000;
$list = [];
$start = $stop = 0;

$start = microtime(true);

for ($i = 0; $i < TEST_SIZE; ++$i) {
  $list[$i] = [
    'a' => random_int(1, 500),
    'b' => base64_encode(random_bytes(16)),
  ];
}

ksort($list);

usort($list, function($first, $second) {
  return [$first['a'], $first['b']] <=> [$second['a'], $second['b']];
});

$stop = microtime(true);
$memory = memory_get_peak_usage();
printf("Runtime: %s\nMemory: %s\n", $stop - $start, $memory);

Co tento kus kódu měl měřit? Vytváření asociativních polí (v dalších variantách pak objektů) a pak práci s nimi, přece.

Ne tak docela. Děje se toho podstatně víc. Vytváření polí, volání funkce random_int, random_bytes, base64_encode, pak řazení podle klíče, která je více méně noop, další řazení podle obsahu interních struktur a alokace dočasných polí.

Na mém Haswell stroji s PHP 7.2.4 měřený úsek běží 8 vteřin. Znamená to, že to co mě zajímá trvá 8 vteřin? Ne, celá ta věc trvá osm vteřin. Kolik z nich jsem strávil měřením rychlosti přístupů do polí/objektů? To není bez podrobnějšího zkoumání možné říct.

Začal jsem se proto vrtat, kolik času zaberou jednotlivé fáze a výsledky jsou zajímavé (kdyby nebyly, nic bych nepsal).

PHP je naštěstí primitivní runtime, který se nesnaží o chytré optimalizace a měření je proto jednoduché (jak říkal Aleksey Shipilёv). Můžu například udělat v podstatě jakoukoli změnu a nebát se, že chytrý JIT kompletně eliminuje veškerý kód bez pozorovatelných efektů.

Samotná konstrukce polí/objektů je v podstatě zdarma. ksort řadí podle již seřazeného numerického klíče, je také zadarmo a nepřináší žádnou užitečnou informaci o chování datových struktur.

A pak jsou tu také funkce random_int, random_bytes, base64_encode. První dvě generují kryptograficky bezpečná náhodná čísla, což nejspíš nebude zadarmo. A také není. Jen tyto funkce zaberou jednu vteřinu času, tedy ±12% zbytečné režie, která opět neříká nic užitečného.

Teď poslední řazení. Porovnávací funkce uvnitř využívá spaceship operátor <=> mezi dvěma nově vytvořenými poli. To je velice elegantní, ale dočasné datové struktury je třeba alokovat a i když každá alokace je levná (viz pár odstavců výše), provádí se jich O(nlog(n)) a to se nastřádá.

Když to změním na

usort($list, function($first, $second) {
  $cmp = $first['a'] <=> $second['a'];
  if ($cmp !== 0) return $cmp;
  return $first['b'] <=> $second['b'];
});

test běží o 3 vteřiny rychleji. Nejde jen o případ optimalizace benchmarku, ale důkaz, že ±37% času tráví alokacemi, dealokacemi a počítáním referencí, tedy ne tím, co měl měřit. Dohromady tráví 50% času zbytečnou režií a výsledky jsou v ní utopené.

Závěry benchmarku o relativních rychlostech polí a různých objektů jsou v tomto případě stále platné, jen poměry se liší. Režie je částečně maskovala a bez ní jsou přibližně dvakrát větší.

Benchmarkování je komplikované a takhle by se to nemělo dělat. Je nutné izolovat měřený efekt a i tak čísla jsou pouhá data, bez pochopení, proč jsou taková jaká jsou, nemají význam. Říct "X je z nějakého důvodu rychlejší než Y a proto bychom ho měli používat", není dobrý nápad.

Jak varuje JMH: Do not assume the numbers tell you what you want them to tell.


  1. Ale i toto je možné optimalizovat. Virtuální stroj může asociativní pole se stejnou strukturou zkompilovat do podoby, která je interně k nerozeznání od objektů. Self to začal dělat v osmdesátých letech a dnes na tom stojí všechny moderní JavaScriptové VM. Pokud se chcete dozvědět víc, sledujte tento kurz.
píše k47 (@kaja47, k47)