0xDEADBEEF

Iterace směrem k nule

Má smysl iterovat směrem k nule namísto klasického způsobu od nuly k maximu?

V určitých případech může.

Jednoduchá tradiční iterace vygeneruje tradiční binárku v níž se vyjímá svatá trojice add, cmp, jne.

for (size_t i = 0; i < n; i++) {
  sum += arr[i];
}

add    (%rdi),%rax
add    $0x8,%rdi
cmp    %rdx,%rdi
jne    47

Naproti tomu iterace pozpátku vygeneruje něco jiného. Všimněte si, že proměnná i má znaménkový typ long.

for (long i = n-1; i >= 0; i--) {
  sum += arr[i];
}

add    (%rdi,%rsi,8),%rax
sub    $0x1,%rsi
jae    47

Explicitní porovnání přes cmp už není potřeba. Je to proto, že aritmetické operace nastaví příslušné příznaky carry, zero, sign, overflow. Carry/borrow se rozsvítí, když se i potopí do záporných čísel a to je přesně okamžik, na který čeká instrukce jae, aby přestala.

Na OOO strojích absolutní počet instrukcí nemusí příliš vypovídat o rychlosti. V tomto případě ano. Na mojí vykopávce (Sandy Bridge laptop) je to 2.6 sekund versus 1.6 sekund. Ale jako vždy záleží na detailech, v tomto případě mikroarchitektonických.

Například jen podle počtu instrukcí by člověk čekal, že pomalý program poběží 2.1 vteřiny, ale v realitě to bylo něco kolem 2.6 vteřiny. perf pro pomalý program hlásí 37,05% frontend cycles idle. Co se tady děje?

Vysvětlení poskytne pohled na schéma daného procesoru a konkrétně na porty – paralelní exekuční jednotky, které dělají skutečnou práci. SB jich má 6, ale ne každý port umí všechno, dva jsou ALU, jeden ALU + branch, dva load, jeden store.

perf umí ukázat, kolik μoperací skončí na každém portu. Tady se už nebavíme o instrukcích, neboť frontend rozbije některé komplikovanější x86 operace na několik menších. V naprosté většině případů jde o aritmetické operace adresující paměť, které se rozbijí na dva μopy.

Rychlý program:

2 282 534 330      uops_dispatched_port.port_0   # ALU
2 240 990 323      uops_dispatched_port.port_1   # ALU
2 258 424 338      uops_dispatched_port.port_2   # load
2 256 833 103      uops_dispatched_port.port_3   # load
4 562 802 937      uops_dispatched_port.port_5   # ALU + branch

Testuje se 4.5 miliardy iterací a jak je vidět, port 5, který má na starosti skoky, je zaneprázdněný každý takt, load část add instrukce se rozloží do portů 2 a 3, sčítání do portů 0 a 1 a sub je kde? Tady se do hry dostává tzv. macro fusion – mikroarchitektonická optimalizace, která sloučí jednoduchou instrukci nastavující příznak (cmp, add, sub atp.), a následující skok, který na základě onoho příznaku skáče, do jedné interní operace, která je nedělená provedena na portu 5. Ve finále procesor dokáže odbavit jednu iteraci rychlé smyčky každý takt.

Pomalý program:

3 948 154 967      uops_dispatched_port.port_0   # ALU
3 755 921 928      uops_dispatched_port.port_1   # ALU
2 268 785 072      uops_dispatched_port.port_2   # load
2 261 047 982      uops_dispatched_port.port_3   # load
5 861 314 056      uops_dispatched_port.port_5   # ALU + branch

Stejné jako předtím, jen každý z portů 0, 1 a 5 odbavil zhruba 1.5 miliardy μop navíc. V ideálním světě by extra aritmetickou instrukci dostaly na starosti porty 0 a 1, které na to mají místo, aby nedocházelo k blokování skákajícího portu 5. Pak by bylo možné, aby obě smyčky běžely ±stejně rychle. Bohužel scheduler (neboli reservation station) není tak chytrý a práci rozkládá rovnoměrně, blokuje port 5 a to bude důvod, proč program běží pomaleji, než by měl. (Nebo v tom může být něco jiného, nejsem vševědoucí bůh jako Agner Fog nebo Travis Down.)¹

Ok, ale tohle jsou data pro jednu dekádu starý stroj, může někdo namítat, nové procesory nebudou tak hloupé. Ano i ne. Na jednu stranu jde o příklad co a jak může ovlivňovat běh programu, když se skutečně začínají počítat poloviny nanosekund. Na druhou stranu to byla právě mikroarchitektura Sandy Bridge, která začala dekádu odvozených mikroarchitektur, éru, jež se teprve teď chýlí ke konci. Posledních 10 let byly procesory intelu sobě podobné do té míry, že je možné velice přesně modelovat jejich chování stejným modelem, do nějž se jen nalije pár parametrů popisující danou generaci křemíku.

Ale pravda je, že moderní stroje jsou širší a agresivnější než ty staré. Zen 3 a Sunny Cove mají 10 portů, Gracemont dokonce 17 portů a to jde o malé jádro, které hraje druhé housle po dobu větších Sunny Cove kousků. Zvládnou víc instrukcí paralelně a mají menší riziko, že daná kombinace instrukcí nesedne na typy exekučních jednotek.

Jo a jinak, pochopitelně, s -O3 je tenhle triviální případ vektorizován do pekla a zpátky.

K tématu

• Iterace křížem krážem
• x86 macro-op fusion notes

1. Tady:

Note that in some cases instructions which can go to wide variety of ports, such as add may execute on a port that is under contention by other instructions rather than on the less loaded ports: a scheduling quirk that can reduce performance. Why that happens is not fully understood.