0xDEADBEEF

Jak přesunout 1 až 16 bajtů do SIMD registru

Zase jsem zašel příliš hluboko. Zkouším, jak rychlá může být hash-mapa pro jedno specifické použití a měl jsem už dávno přestat. Ale na tom pocitu, když mikro-benchmarku spadne další nanosekunda, je něco návykového. I když ve finále je zajímavější, co se člověk naučí cestou, než finální výsledek.

Problém je jednoduchý: Jak co nejrychleji dostat 1-16 bajtů z paměti do XMM registru a nevyvolat u toho segfault. Na rychlosti záleží. Mluvíme tu o jednotkách nanosekund.

Hlavní komplikace spočívá v tom, že velikost čteného pole není konstantní a bajt za jeho koncem už může ležet v nenamapované stránce paměti.

Nejjednodušší varianta memcpy + __builtin_ia32_loaddqu je pomalá. Jednak volá funkci z libc, což v tomto kontextu je samo o sobě příliš drahé, ale její kód je plný skoků, smyček (jinak by nezvládal proměnnou délku) a přesunů dat z paměti do paměti. Jedno vadí z důvodu branch misspredict, druhé kvůli latenci L1 cache, která bývá mezi 3 a 5 takty a i to je moc. (Říkal jsem že jde o nanosekundy, nebo ne?)

V jazyce D to vypadá takhle:

import gcc.builtins;

ubyte16 maskedLoadCopy(char* arr, ulong len) {
  char[16] tmp = 0;
  tmp[0 .. len] = arr[0 .. len];
  return __builtin_ia32_loaddqu(tmp.ptr);
}

Na zásobníku leží dočasné pole vyplněné nulami, do něj se zkopíruje len bajtů a pak se to šoupne do xmm registru.

Když to rozeberu, je třeba splnit 3 podmínky: Zkopírovat do vektoru jen potřebné bajty, nečíst z nenamapované paměti a udělat to co nejsvižněji. Proto jsou podmínky, smyčky a použití paměti pro dočasné výsledky instrukce non grata. Fragment výše má tohle všechno a proto trvá asi 7 ns na mém stroji (i5-4570).

Nadešel čas na špinavé triky.

První podmínku (dostat do xmm jen to, co je třeba) může vyřešit prostý manévr, kdy načteme celý 16 B vektor a vymaskujeme, co je potřeba.

ubyte16 maskedLoad1(char* arr, ulong len) {
  ubyte16 mask = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
  ubyte16 val = __builtin_ia32_loaddqu(arr);
  ubyte16 lenVec = cast(ubyte) len;
  ubyte16 cmp = __builtin_ia32_pcmpgtb128(lenVec, mask);
  return val & cmp;
}

S časem asi 2 nanosekundy jde o suverénně nejrychlejší variantu. Má ale jedno ale. movdqu (přes __builtin_ia32_loaddqu) čte i nezarovnaná data, v tom není problém. Ale konec, který vyjede mimo pole, může zabrousit do nenamapované stránky paměti a segfaultnout.

Mohli bychom si vypůjčit některé techniky odsud, ale tam řeší memset, který nastavuje paměť a cesta přes RAM je, jak padlo výše, pomalá.

Chce to instrukce pro maskovaný load, kde neaktivní elementy nevyvolají fault, když zabrousí do nenamapované paměti. x86 nabízí vmaskmovps a vmaskmovd. Splňují požadavek, jen mají granularitu 4B. Tady je potřeba bajtová granularita.

Nicméně přesto je můžeme použít pro načtení celých 1-4 intů s tím, že poslední slovo se přečte skalárně. Konec tohoto slova bude zarovnaný stejně jako konec pole a nemůže přetéct do další stránky. Jeho obsah pak shiftneme, aby bajty seděly a pak skalární vektor vložíme na příslušné místo ve vektoru.

ubyte16 maskedLoad2(char* arr, ulong len) {
  int4 positions = [0, 1, 2, 3];
  int4 lengths   = cast(uint) (len / 4);
  int4 mask = __builtin_ia32_pcmpgtd128(lengths, positions);
  int4 vec = cast(int4)__builtin_ia32_maskloadps(cast(int4*)arr, mask);

  ulong base = (len/4)*4;
  auto end = arr+len;
  uint lastWord = *(cast(uint*)(end-4));
  lastWord = ((len & 3) == 0) ? 0 : lastWord;
  lastWord >>= ((4-len-base)*8);
  int4 lastVec = lastWord;

  int4 ll = cast(int) (len/4);
  int4 lastMask = __builtin_ia32_pcmpeqd128(ll, positions);

  return cast(ubyte16) (vec | (lastVec & lastMask));
}

Jde o relativně hodně instrukcí, ale to příliš nevadí. Všechno zůstává v registrech a nejsou tam komplikované skoky. Není nutné pochopit, co se v programu děje, nejspíš jsou v něm stejně chyby a používání SIMD je forma mentálního mučení. Je to o něco rychlejší než naivní varieta, asi 3.5 ns.

Jeden maličký problém spočívá v korektnosti. Vypořádá se s přesahem dál, ale ne zpět. Chci načíst 1 B, první ve stránce paměti, skalární load načte 4B na adresách [-3, -2, -1, 0 ], první tři zasahují do předešlé stránky a můžou faultnout. Dalo by se to jistě obejít ještě komplikovanější aritmetikou, ale na tu nemám mozek.

Někdy se musí udělat krok stranou a přidat další špinavý trik. Paměť je vždy mapovaná po stránkách, které mají minimálně 4 kB. Když jsem víc jak 16 bajtů před hranicí stránky, můžu použít rychlou verzi, která je v té situaci bezpečná. Když se nacházím v riskantní zóně u konce stránky, použiju pomalou, která si poradí s přesahem na konci.

Pravda, přidá to jeden skok, ale ten je předvídatelný. Ve většině případů se použije rychlá verze, pomalá jen okrajově, něco jako v 1/256 případech. Branch predictor rychle pochytí, že se má hnát cestou rychlé větve.

ubyte16 maskedLoad(char* arr, ulong len) {
  enum pageSize = 1 << 12;
  auto p = cast(size_t) arr;
  if ((pageSize - (p % pageSize)) > len) {
    return maskedLoad1(arr, len);
  } else {
    return maskedLoad2(arr, len);
  }
}

Ve finálním hybridu pak příliš nezáleží, co bude pomalá verze. Je volána jen zřídka. Bezpečná a jednoduchá nouzovka s memcpy bude perfektně stačit.

• Diskuze o stejném tématu