Podmíněná inkrementace v x86

21. 4. 2023 #low level #CPU #x86

Všichni víme, že x86 je barokní instrukční sada, obtěžkaná historickými podivnostmi, které je prokleta s sebou v zájmu zpětné kompatibility valit dál jako křemíkový Sysyfos.

Jako ukázka několika detailů, co mě otravují, poslouží prostý jednořádek:

x += (x == 1)

Kompilátor ho (nejčastěji) přeloží na sekvenci instrukcí xor, cmp, sete, add.

xor    %eax,%eax
cmp    $0x1,%edx
sete   %al
add    %edx,%eax

cmp porovná registr s konstantou a na základě výsledku nastaví příznaky do registru FLAGS.
sete přesune bit z FLAGS do GP (general purpose) registru. V cílovém registru ale změní jen spodní bajt a archaická pravidla x86 trvají na tom, že pokud se změní pouze část 32bit registru (al, ah nebo ax), zbytek zůstane nezměněný. x86-64 se šílenství nesnažil nijak napravit, jen k němu přidal dodatek, že pokud se přepíše dolních 32 bitů (eax) z 64 bit registru (rax), dojde k vynulování horní poloviny. Z těchto důvodů fragmentu musí předcházet xor pro vynulování cílového registru. Ale i kdybychom si byli jisti, že kromě dolního bajtu je registr nulový, kompilátor přesto xor vygeneruje, protože to je důležité z hlediska výkonu. Vynulování pomoci xor rax, rax (nebo dalších metod³ ) explicitně přeruší řetězec závislostí a out-of-order CPU tak dostane víc prostoru pro spekulace. Pokud by k vynulování nedošlo, vytvoří se falešná závislost, kdy CPU musí čekat na výsledek předchozí operace zapisující do našeho registru, než může rozjet jinak nezávislý řetězec instrukcí.¹
add nakonec přičte jedničku nebo nulu

Proč na tom záleží? Tohle je jedna z těch věcí, kdy to je většinou jedno, ale když na tom jednou záleží, záleží na tom zatraceně hodně. Vzory jako tento se používají pro branchless programování, kdy se snažíme nahradit špatně předvídatelné podmíněné skoky aritmetikou a cmovy, abychom omezili cenu, kterou platíme za branch-miss. Rozdíl může být značný. Může. Jako obvykle záleží na detailech. Program psaný stylem s minimem skoků typicky provede více instrukcí (přes žádné z nich nepřeskakuje, výpočty se provedou tak jako tak, jen nakonec dojde k jejich zahození nebo použití přes cmov). Na druhou stranu, protože nemarní tolik času čekáním, než se pipeline vzpamatuje z špatné spekulace, může být rychlejší. Anebo ne. Záleží na situaci.

Protože triviální podmíněná inkrementace potřebuje 4 instrukce, limituje to o něco užitečnost branchless technik. Pravda xor je prakticky zadarmo, moderní CPU nesou kus HW speciálně pro detekci tzv. zero-idiomů a když nějaký takový objeví, instrukci vyřídí ve stádiu přejmenovávání registrů a vůbec neputuje na backend. Přesto se procesorem musí protlačit 4 instrukce, 10 bajtů.

Šlo by to udělat lépe.

Pokud mám x += (x == 0). Kompilátor to přeloží na cmp, adc. Jedno porovnání, jedno add with carry. Hotovo. Funguje to ale jen v konkrétním případě porovnávání s nulou.

ARM v8 je v tomto ohledu flexibilnější: fragment se přeloží na cmp + cinc při porovnání s jakoukoli konstantu.

cmp     w0, #1
cinc    w0, w0, eq

cmp instrukce v ARMovém světě není nic víc než alias pro subs. Instrukce nastavující příznaky se od svých prostých protějšků liší příponou s.²
cinc je alias pro csinc podmínečně inkrementující registr:
csinc(a, b, flag) = flag ? a : b + 1

V ideálním světě stačí dvě instrukce, ARM to dokáže, x86 nikoli. Jeho podivnosti a historická zátěž to znemožňují.

Další příklad mírně otravných podivností je instrukce vptest.

Měl jsem program, který ve smyčce (jako boční výpočet) testoval, jestli se určitý element nachází v příslušném vektoru. Něco jako tohle:

remaining = stuff.length

foreach (i; stuff) {
  vec = lddqu(arr[i])
  ...
  res = cmpeq(vec, query)
  remaining -= !vptestz(res, res)
}

if (remaining == 0) {
  success
}

Kompilátor remaining -= !vptestz(res, res) přeložil na očekávanou čtveřici instrukcí xor, vptest, setXX, sub.

vptest samotný nastavuje příznaky zero a carry na základě bitového součinu dvou vektorů.

vptest(int8 a, int8 b) {
  ZF = (a & b) == 0   // vptestz
  CF = (~a & b) == 0  // vptestc
}

Pokud změním podmínku a nepočítám, v kolika iteracích hledaný element ještě nebyl nalezen, ale v kolika už byl, kompilátor vygeneruje o dvě instrukce kratší sekvenci vptest + adc a tahle změna samotná zrychlí program o 4%. (A v tomto konkrétním případě pochybuji, že další zrychlení je možné bez kompletní změny algoritmu.)

missing = 0;

foreach (i; stuff) {
  ...
  missing += vptestc(0, a);
}

if (missing == 0) {
  success
}

Funguje to zhruba takto:

~0 -> samé jedničky
~0 & a -> a
vptestc(0, a) -> CF = a == 0, platí pokud element nebyl nalezen
a == 0 pokud element nebyl nalezen

Jako dodatek přidám ještě jednu manifestaci podmíněné inkrementace, na kterou jsem narazil ve zdrojácích PHP:

return (size - !!size) >> 3;

Jde o součást alokátoru, konkrétně kód zjišťující jak velkou třídu objektů použít. Protože se volá při každé alokaci, vyplatí se ho optimalizovat, co to jen jde. Kryptický kód tady nevadí, rychlost je přednější.

Teď nezáleží přesně jaký je jeho výzanam, ale že se přeloží jako cmp + adc.

cmp    $1,  %rsi
adc    $-1, %rsi
shr    $3,  %rsi

Dvojitá negace dělá v podstatě tohle:

size - ((size == 0) ? 0 : 1)

A cmp + adc dělá tohle:

rsi - 1   // cmp není nic víc než sub, který zahodí výsledek a nechá jen příznaky
carry_borrow = (rsi < 1) ? 1 : 0;
rsi += (-1) + carry_borrow;

Záleží na implementaci. Tady v poznámce 6 se píše, že intel dokáže přejmenovávat bajtové části registrů jako AL, AH nezávisle na velkém registru EAX/RAX. To je v mém případě k ničemu z důvodu, že add dokáže sčítat jen registry stejné velikosti, dva 32 bitové, neumí 32 bit + 8 bit.
Instrukce nastavující příznaky představují pro OOO jádro určitou komplikaci. Jednak mají o jeden vstup víc a druhak OOO mašinérie musí sledovat změné bity v registru příznaků dokud je nějaká další instrukce nepřepíše, protože na nich nějaká budoucí instrukce může záviset. Ve světě x86 téměř každá instrukce změní nějaký příznak, ale OOO jádro si s tím dokáže poradit, takže to nebude asi zas tak velký problém.
Tady: Zen 3 zvládá eliminovat 5.72 instrukcí každý takt přes xor, ale jen 3.81 přes mov r, 0. Graviton 3 to má naopak: jen 1 instrukci přes xor, 5.71 přes mov.

0xDEADBEEF

Podmíněná inkrementace v x86