0xDEADBEEF

RSS odkazy english edition
««« »»»

Míchání intů a ulongů

10. 12. 2021 #protip #x86 #low level

Jaký dopad může mít míchání znaménkových 4B intů a bezznaménkových 8B longů?

V jazyce D jsem, infikován javismy, psal horké smyčky, kde čítač měl typ int. Na JVM docela běžná věc, primitivní typy mají znaménka a délku pole udává int. V D je to docela jinak, délka má typ size_t, což je na 64bit x86 alias pro ulong.

Jaký je rozdíl mezi těmito dvěma smyčkami:

// size_t
for (size_t i = 0; i < xs.length; i++) {
  s += xs[i];
}

// int
for (int i = 0; i < xs.length; i++) {
  s += xs[i];
}

V duchu minulého protipu jsem to otestoval.1 Na historickém Sandy Bridge (který svou relativní primitivností zvýrazňuje všechny nedostatky2 ) verze size_t trvá 4.481s a verze int 6.249 s.

Proč tomu tak je, ukáže letmý pohled do binárky.

size_t verze:

mov  (%rsi),%edx
add  $0x4,%rsi
add  %rdx,%rax
cmp  %rcx,%rsi
jne  10

int verze:

mov    (%rsi,%rax,4),%eax
add    $0x1,%edx
add    %rax,%r8
movslq %edx,%rax
cmp    %rdi,%rax
jb     10

movslq je GNU jméno instrukce movsxd -- move with sign-extension. Stará se o znaménkovou konverzi intu na ulong, v tomto případě nutnou pro případ, kdyby znaménkový čítač přetekl. Její přítomnost jednak znamená instrukci navíc ve smyčce a druhak o jednu instrukci delší řetězec závislostí (add->movslq->cmp oproti add->cmp).

perf ukazuje následující vytížení portů pro size_t verzi:

 40 311 025 511      instructions              #    2,95  IPC
 13 661 611 118      cycles
  7 395 388 057      uops_dispatched_port.port_0   # ALU
  7 188 818 745      uops_dispatched_port.port_1   # ALU
  4 007 412 503      uops_dispatched_port.port_2   # load
  4 004 155 145      uops_dispatched_port.port_3   # load
     12 874 138      uops_dispatched_port.port_4   # store
  9 662 950 761      uops_dispatched_port.port_5   # ALU + branch

40G instrukcí, ale jen 32G μoperací. cmp a jb instrukce jsou interně spojeny do jedné, jak jsem psal minule.

int verze:

 47 941 169 029      instructions              #    2,54  IPC
 18 853 108 379      cycles
  9 882 302 990      uops_dispatched_port.port_0   # ALU
  9 832 352 758      uops_dispatched_port.port_1   # ALU
  4 015 557 195      uops_dispatched_port.port_2   # load
  4 022 308 602      uops_dispatched_port.port_3   # load
      4 706 776      uops_dispatched_port.port_4   # store
 12 393 520 065      uops_dispatched_port.port_5   # ALU + branch

48G instrukcí, 40G μoperací. Jako minule je vidět nevyvážené využití portů. movsxd a add běží na portech 0, 1 a 5, cmp+jb jen na portu 5.

Tady za pozornost stojí mov elimination - mikroarchitektonická optimalizace, která eliminuje přesuny z registru do registru. Instrukci jako mov %rax, %rbx se vůbec nedostane na back-end. Přesun je plně realizován ve fázi přejmenovávání registrů. Procesor si poznamená, že architektonický registr rbx ukazuje na fyzický registr, na nějž se mapuje rax. Pořád je nutné instrukci dekódovat a zabírá místo v L1$, L0$ a zdroje front-endu, není tak úplně zadarmo, ale jejich cena je malá. Podle Agnera například Zen 3 zvládá 4 mov %al, %bl za takt, ale 6 mov %rax, %rbx. První varianta s malými částmi registrů musí jít na backend a blokovat jednu ze 4 ALU, ale v druhá variantě je přesun eliminován a limitujícím faktorem je jak rychle běží register renaming fáze.

Mov elimination funguje pro prosté movy, ale movslq, se svou trochou aritmetiky, není eliminován3 , musí na jeden z portů back-endu a proto je vidět v perfu a proto je smyčka pomalejší.


Poznámky:

  1. Smyčky nahoře jsem zabalil do jednoduchých funkcí, které začínají pragma(inline, false); asm { ""; }, aby kompilátor nic neinlinoval a nesnažil se být příliš chytrý1 . I když funkci zakážu inlinovat, GCC je přesto dost chytrý a když vidí, že výsledek funkce závisí jen na vstupu, vyhodnotí ji jen jednou a výsledek používá, jak je třeba.

    Takhle se může stát, že

ulong sink = 0;
foreach (i; 0 .. 1000) {
  sink ^= func(arr);
}

optimalizuje na

auto tmp = func(arr);
foreach (i; 0 .. 1000) {
  sink ^= tmp;
}

a pak neměřím, co si myslím, že měřím. asm { ""; } tomu udělá přítrž.

  1. Současné mikroarchitektury mají velice široké back-endy, třeba Graviton 3 má 15 portů. V tom kontextu to může vypadat, že pak podobné starosti nemají žádnou cenu. Menší, pravda, ale ne nulovou. Čím víc portů, tím víc paralelní práce a menší počet instrukcí stále povede ke zrychlení. U zmíněného gravitonu má back-end 4x ALU a 2x branch, pro skalární int operace jenom asi dvakrát tolik, co Sandy Bridge.

    Navíc pro paralelní stroje, čím dál větší roli hraje délka řetězce závislostí. Pokud jsou instrukce datově závislé, musí být provedeny sekvenčně. V takové situaci pomůže rozbití závislostí na straně SW nebo ještě větší out-of-order okna na straně HW.

  2. Podle tohohle článku to vypadá, že inteí Golden Cove jádra umí eliminovat závislé instrukce s jednoduchou aritmetikou. Smyčky se závislými instrukce inc, dec nebo add imm běží s IPC 5.5 - 5.7. Stejný mechanismus by technicky mohl být použitý pro eliminaci znaménkového rozšíření, které by pak mělo nulovou latenci a obě smyčky by běžely stejně rychle.
píše k47 (@kaja47, k47)