funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

Jak optimalizovat deoptimalizací

28. 3. 2015 — k47

Když jsem si při­pra­vo­val dnešní před­nášku na Po­slední Sobotu, ve které jsem plá­no­val od­ha­lit všechny po­div­nosti v cho­vání a výkonu PHP polí, a hrabal se v céč­kov­ských zdro­já­cích Zend enginu, omylem se mi po­vedlo napsat rych­lejší verzi funkce, kterou PHP po­u­žívá k ha­sho­vání stringů. Za­jí­mavé na celé věci byl hlavně fakt, že zrych­lení jsem dosáhl tím, že jsem se zbavil low-level op­ti­ma­li­zací a napsal funkci mnohem hlou­pěji, hůře a méně ra­fi­no­vaně.

Někdy méně je zkrátka více, worse is better a kom­pi­lá­tor se v kom­bi­naci s mo­der­ním hard­ware po­stará o zbytek.

Jak už jsem dříve psal, PHP po­u­žívá ha­sho­vací funkci DJBX33A, která není příliš dobrá, pro­tože útoč­ník může snadno uhod­nout klíče s ko­li­du­jí­cími hashi. Při práci s ta­ko­vými klíči se kon­stantní časová slo­ži­tost, pro kterou hash ta­bulky uctí­váme a mi­lu­jeme, změní na slo­ži­tost li­ne­ární. Hash-flood útok na sebe pak ne­ne­chá dlouho čekat. Jak se říká: tvoje hash ta­bulka je jenom tak dobrá, jak dobrá je tvoje hash funkce. Ale na druhou stranu je DJBX33A aspoň rychlá.

V pod­statě vypadá ná­sle­dovně:

long DJBX33A(const unsigned char *key) {
  unsigned long hash = 5381;
  while(*key) hash = 33 * hash + *key++;
  return hash;
}

Po­tře­buje pro­vést jen pár in­strukcí na každý znak ha­sho­va­ného stringu.

V PHP má pak ná­sle­du­jící zna­telně méně ele­gantní podobu:

unsigned long zend_inline_hash_func(const char *str, int len) {
  unsigned long hash = 5381UL;

  /* variant with the hash unrolled eight times */
  for (; len >= 8; len -= 8) {
    hash = ((hash << 5) + hash) + *str++;
    hash = ((hash << 5) + hash) + *str++;
    hash = ((hash << 5) + hash) + *str++;
    hash = ((hash << 5) + hash) + *str++;
    hash = ((hash << 5) + hash) + *str++;
    hash = ((hash << 5) + hash) + *str++;
    hash = ((hash << 5) + hash) + *str++;
    hash = ((hash << 5) + hash) + *str++;
  }
  switch (len) {
    case 7: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
    case 6: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
    case 5: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
    case 4: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
    case 3: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
    case 2: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
    case 1: hash = ((hash << 5) + hash) + *str++; break;
    case 0: break;
  }

  return hash;
}

Smyčka je osm­krát odro­lo­vaná a místo ná­so­bení pro­vádí jeden shift a jeden součet (odro­lo­vání má pře­kva­pivě velký dopad na rych­lost).

To dává smysl, pro­tože sčí­tání, bitové ope­race a bitové posuny jsou rychlé ope­race a ná­so­bení patří mezi ty pomalé. Ně­které pra­staré RISC pro­ce­sory do­konce ani ná­so­bit ne­u­měly a místo toho musel pro­gram pro­vést ně­ko­lik součtů. (Teď pominu na­pří­klad fakt, že P4 měly pomalé shift in­strukce, pro­tože to už je dávná his­to­rie.)

Na sou­čas­ných pro­ce­so­rech má ná­so­bení (imul) la­tenci tři takty; shift a součet pak jeden takt, ale každý takt jich může být vy­ko­náno ně­ko­lik (viz). Ve světle těchto sku­teč­ností to vypadá, že se ma­nu­ální op­ti­ma­li­zace vy­platí a kód je ide­ální.

Až na to, že všechny ope­race jsou zá­vislé jedna na druhé.

To mi nedalo a po chvíli pokusů a omylů jsem vy­pro­du­ko­val ná­sle­du­jící verzi hashe, který si se svým PHP před­kem v oš­k­li­vost v ničem nezadá.

#define M1 (33UL)
#define M2 (33UL*33)
#define M3 (33UL*33*33)
#define M4 (33UL*33*33*33)
#define M5 (33UL*33*33*33*33)
#define M6 (33UL*33*33*33*33*33)
#define M7 (33UL*33*33*33*33*33*33)
#define M8 (33UL*33*33*33*33*33*33*33)

unsigned long MS[8] = { 1, M1, M2, M3, M4, M5, M6, M7 };


unsigned long ilp_hash(const char *str, int len) {
  unsigned long hash = 5381UL;

  for (; len >= 8; len -= 8) {
    hash *= M8;

    hash += M7 * str[0];
    hash += M6 * str[1];
    hash += M5 * str[2];
    hash += M4 * str[3];
    hash += M3 * str[4];
    hash += M2 * str[5];
    hash += M1 * str[6];
    hash +=      str[7];

    str += 8;
  }

  hash *= MS[len];

  switch (len) {
    case 7: hash += M6 * str[len-7]; /* fallthrough... */
    case 6: hash += M5 * str[len-6]; /* fallthrough... */
    case 5: hash += M4 * str[len-5]; /* fallthrough... */
    case 4: hash += M3 * str[len-4]; /* fallthrough... */
    case 3: hash += M2 * str[len-3]; /* fallthrough... */
    case 2: hash += M1 * str[len-2]; /* fallthrough... */
    case 1: hash +=      str[len-1]; break;
    case 0: break;
  }

  return hash;
}

A vý­sle­dek je na mém Haswellu pře­kva­pivě rych­lejší. Na dlou­hých klí­čích do­konce vý­razně rych­lejší. Spo­čí­tání 100 mi­li­onu hashů trvá takhle dlouho:

délka klíčezend_inline_hash_funcILP_hashrozdíl
4280 ms253 ms-10%
6337 ms280 ms-16%
10504 ms440 ms-12%
20949 ms755 ms-20%
502824 ms1764 ms-37%
1006028 ms3667 ms-39%

Nová verze ne­po­u­žívá ite­ra­tivní verzi hashe, ale ekvi­va­lentní formu

hash * 33n-1 + Σ(ki * 33n-i-1). ) Ta má tu výhodu, že jedna ite­race není zá­vislá na té před­chozí, což je hlavní pro­blém pů­vodní im­ple­men­tace: Jednu ite­raci hashe může vy­po­čí­tat až potom, co je před­chozí ite­race do­kon­čená. Stejně tak z poin­teru str může číst až po tom, co byl in­kre­men­to­ván. Není možné využít příliš mnoho ILP (in­struction level pa­ral­le­lism). Mo­derní hard­ware může čás­tečně pomoci, když se pustí do di­vo­kého pře­jme­no­vá­vání re­gis­trů, ale kde nic není, ani out-of-order jádro nebere.

ILP verze může všechny movy pro­vá­dět na­jed­nou, každý takt začít s jedním ná­so­be­ním a o tři takty poz­ději ho při­číst k pro­měnné hash. Chytrý kom­pi­lá­tor (v tomto pří­padě GCC) pře­loží ná­so­bení 33 na rych­lejší ope­race a pře­kva­pivě to udělá i v pří­padě ná­so­bení (n * 33 * 33), které mohou být pro­ve­deny také pa­ra­lelně s ná­so­be­ním před­cho­zích ite­rací.

Vý­sled­kem tohoto apli­ko­va­ného di­le­tant­ství je funkce, která po­tře­buje méně in­strukcí, méně taktů pro­ce­soru a má vyšší ILP (v exrém­ních pří­pa­dech perf hlásí re­kord­ních 4.18 in­strukce za takt) a to jenom proto, že její jed­not­livé kroky jsou na sobě ne­zá­vislé a hard­ware je tedy může vy­ko­nat pa­ra­lelně.

A pointa: PHP hashe ne­po­čítá zas tak často a (stejně jako Java) ve string ob­jektu ukládá už jednou spo­čí­taný hash. Navíc ha­sho­vání už tak po­tře­buje jen pár taktů na každý znak ře­tězce. Takže i když je moje funkce o něco rych­lejší, ak­ce­le­race nemá ve vý­sledku skoro žádný dopad.

No jo, co na­dě­lám.

Dále k tématu:

@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články