0xDEADBEEF

Prefix popcount

Mám rád esoterické triky – maličké kousky kódu, které dělají něco velice specifického, aniž by bylo na první pohled vidět, co to přesně je, ale je pro ně dobrý důvod, protože to dělají velice efektivně. Všechny ty bit twiddling hacks, to je ono.

Nedávno jsem se snažil vektorizovat jeden algoritmus a hlavní problém představovaly datové závislosti. Program načetl vektor 4 integerů z adresy p, provedl magické SIMD rituály a přes movmskps vyprodukoval bitovou masku. Pak nad maskou udělám popcnt, o výsledek se zvedne adresa p a smyčka pokračuje další iterací. V tom tkví datová závislost – nemůžu začít další iterace dokud je ta současná hotová, protože dřív než na jejím konci neznám adresu nových dat. Datová závislost měla 11 taktů, což znamená, že na 3 Ghz skylake laptopu můžu udělat maximálně 272 milionů iterací. Nic moc.

Brzdila mě instrukce popcnt. Ta má na intelích procesorech už od pravěku latenci 3 takty a sedí přímo v řetězci instrukcí představujících datovou závislost. Ne ideální.

Kdyby se mi podařilo odstranit 1 takt, maximální rychlost by stoupla z 272 M/s na 300 M/s.

A odseknout jeden takt můžu, když změním tohle

int mask = movmskps(vec)
p += popcnt(mask);

na tohle

int mask = movmskps(vec)
p += (0x20192 >> x) & x;

2 instrukce a 2 takty.

Jak to funguje? Jde o to, že algoritmus produkoval 4 bitovou masku, kde bylo vždy nastaveno jen pár bitů na začátku. Prefix jedniček, zbytek nuly.

0b0001 -> 1
0b0011 -> 2
0b0111 -> 3
0b1111 -> 4

popcnt to zvládne, ale je mnohem obecnější. V tomto případě stačí jednoduché mapování 4 hodnot na 4 výsledky.

Když magickou konstantu napíšu v binárním tvaru a vyznačím klíčová místa, bude to jasnější.

//_0100_____011__10_1_
(0b0100000000110010010 >> x) & x

Shift a maskování provede jednu ze 4 variant.

0b0100000000110010010
                   &>
                &&>>>
           &&&>>>>>>>
  &&&&>>>>>>>>>>>>>>>

Extrahuje bity jedné ze čtyř délek prefixu, které jsou v konstantě odsazené o specifický počet míst.

Je to tedy užitečné? Ne moc. Na Intelu je to o takt rychlejší a výsledky jsou měřitelně lepší. Ale na Zenech od AMD popcnt trvá jen jeden takt a jádro jich zvládne 4 každý takt, takže tam by to bylo pomalejší.

Nakonec jsem to nepoužil, protože vektorizovaná verze algoritmu nebyla nikdy rychlejší než jednoduchá skalární smyčka. Takže nic.

Ale je to obecná technika. S její pomocí můžu do 8B registru zakódovat 16 nibblů a třemi instrukcemi vylovit jeden z nich. Tři takty může být rychlejší než L1 cache hit.

(c >> (i << 2)) & 0xf

Takhle třeba můžu zjistit délku utf8 code pointu ve 4 instrukcích a 4 taktech, což může být na některých mikrocrchitekturách s L1 cache pomalejší než 3 takty (velké intely od Skylaku, ARM Cortex-A76 v rpi5), rychlejší, než dekódování pomocí tabulky. (I když v tomhle konkrétním případě se přímo nabízí použít pshufb na x86, tbl na ARMech pro snadnou vektorizaci.)

int getCodepointLength(ubyte c) {
  ulong lengths = 0x4322111111111111UL;
  return (lengths >> (c >> 4) * 4) & 0b1111;
}

Bonus: Zjistit, jestli je znak z množiny <>"'& a má se escapovat v HTML, se dá třemi instrukcemi bez tabulky v paměti.

bool shouldEscape(ubyte c) {
  return ((c * 4611686024533006830UL) & 45150860542208UL) == 68736319744UL;
}

I když je to zajímavé a bavilo mě to objevit (musel jsem napsat program, který konstanty převážně hrubou silou objevil), není to nijak užitečná věc. x86 má přesně pro tyto případy instrukci pcmpestrm a pak existuje lepší obecný SIMD přístup nezávisející na specializovaných instrukcích.