Míchání intů a ulongů
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é mov
y, 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:
- 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ž.
- 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 4× ALU a 2× 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.
- 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
neboadd 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.