0xDEADBEEF

[RSS]
««« »»»

Co vlastně benchmarkujete?

4. 8. 2018

Před ně­ja­kou dobou jsem na­ra­zil na článek, který se snažil tes­to­vat rych­lost a pa­mě­ťové nároky aso­ci­a­tiv­ních polí a růz­ných va­ri­ant ob­jektů v PHP. Závěr byl ten, že ob­jekty jsou skoro ve všech ohle­dech buď srov­na­telné nebo lepší než aso­ci­a­tivní pole, hlavně co se týká pa­mě­ťo­vých nároků1 .

Ale stačil jediný pohled, abych věděl, že je něco špatně. Ben­chmark aso­ci­a­tiv­ních polí vy­pa­dal 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? Vy­tvá­ření aso­ci­a­tiv­ních polí (v dal­ších va­ri­an­tách pak ob­jektů) a pak práci s nimi, přece.

Ne tak docela. Děje se toho pod­statně víc. Vy­tvá­ř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 in­ter­ních struk­tur a alo­kace do­čas­ných polí.

Na mém Haswell stroji s PHP 7.2.4 měřený úsek běží 8 vteřin. Zna­mená 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ě­ře­ním rych­losti pří­stupů do polí/ob­jektů? To není bez po­drob­něj­šího zkou­mání možné říct.

Začal jsem se proto vrtat, kolik času za­be­rou jed­not­livé fáze a vý­sledky jsou za­jí­mavé (kdyby nebyly, nic bych nepsal).

PHP je na­štěstí pri­mi­tivní run­time, který se ne­snaží o chytré op­ti­ma­li­zace a měření je proto jed­no­du­ché (jak říkal Alek­sey Shi­pi­lёv). Můžu na­pří­klad udělat v pod­statě ja­kou­koli změnu a nebát se, že chytrý JIT kom­pletně eli­mi­nuje veš­kerý kód bez po­zo­ro­va­tel­ných efektů.

Sa­motná kon­strukce polí/ob­jektů je v pod­statě zdarma. ksort řadí podle již se­řa­ze­ného nu­me­ric­kého klíče, je také za­darmo a ne­při­náší žádnou uži­teč­nou in­for­maci o cho­vání da­to­vých struk­tur.

A pak jsou tu také funkce random_int, random_bytes, base64_encode. První dvě ge­ne­rují kryp­to­gra­ficky bez­pečná ná­hodná čísla, což nej­spíš nebude za­darmo. A také není. Jen tyto funkce za­be­rou jednu vte­řinu času, tedy ±12% zby­tečné režie, která opět neříká nic uži­teč­ného.

Teď po­slední řazení. Po­rov­ná­vací funkce uvnitř vy­u­žívá spa­ce­ship ope­rá­tor <=> mezi dvěma nově vy­tvo­ře­nými poli. To je velice ele­gantní, ale do­časné datové struk­tury je třeba alo­ko­vat a i když každá alo­kace je levná (viz pár od­stavců výše), pro­vádí se jich O(nlog(n)) a to se na­střá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 rych­leji. Nejde jen o případ op­ti­ma­li­zace ben­chmarku, ale důkaz, že ±37% času tráví alo­ka­cemi, de­a­lo­ka­cemi a po­čí­tá­ním re­fe­rencí, tedy ne tím, co měl měřit. Do­hro­mady tráví 50% času zby­teč­nou režií a vý­sledky jsou v ní uto­pené.

Závěry ben­chmarku o re­la­tiv­ních rych­los­tech polí a růz­ných ob­jektů jsou v tomto pří­padě stále platné, jen poměry se liší. Režie je čás­tečně mas­ko­vala a bez ní jsou při­bližně dva­krát větší.

Ben­chmar­ko­vání je kom­pli­ko­vané a takhle by se to nemělo dělat. Je nutné izo­lo­vat měřený efekt a i tak čísla jsou pouhá data, bez po­cho­pení, proč jsou taková jaká jsou, nemají význam. Říct „X je z ně­ja­kého důvodu rych­lejší než Y a proto bychom ho měli po­u­ží­vat“, není dobrý nápad.

Jak varuje JMH: Do not assume the num­bers tell you what you want them to tell.


  1. Ale i toto je možné op­ti­ma­li­zo­vat. Vir­tu­ální stroj může aso­ci­a­tivní pole se stej­nou struk­tu­rou zkom­pi­lo­vat do podoby, která je in­terně k ne­ro­ze­znání od ob­jektů. Self to začal dělat v osm­de­sá­tých letech a dnes na tom stojí všechny mo­derní Ja­vaScrip­tové VM. Pokud se chcete do­zvě­dět víc, sle­dujte tento kurz.
píše k47 (@kaja47, k47)