Spekulativní provádění proti branchless kódu

Spekulativní provádění a kód bez větvení: skryté kompromisy výkonu

Moderní procesory provádějí miliardy operací za sekundu, ale rychlost přístupu k paměti roste pomaleji. Tento rozdíl vede k tomu, že čekání na data se stává hlavním zdrojem ztrát výkonu. Procesory se vyvinuly z pasivních vykonavatelů na aktivní manažery datového toku: out-of-order provádění, přeuspořádání závislostí a spekulativní provádění.

Predikce větvení umožňuje spouštět načítání předem, skrývající latenci paměti. Chyba predikce stojí 10–20 taktů, ale čekání z L3 nebo DRAM – stovky. Kód bez větvení eliminuje chybnou predikci, ale zbavuje procesor možnosti spekulovat.

Evoluce od sekvence k spekulaci

Rané systémy prováděly instrukce striktně sekvenčně. IBM System/360 Model 91 zavedl algoritmus Tomasulo pro out-of-order provádění: instrukce startují podle připravenosti operandů.

Spekulativní provádění se objevilo později v superskalárních procesorech jako Intel Pentium Pro (1995). Potrubí o 40 mikrooperacích drží desítky instrukcí v letu, predikující větvení podle historie.

for (size_t i = 0; i < n; i++) {
    if (arr[i] >= 0) {
          ... code_true ...;
    } else {
        ... code_false ...;
    }
}

Zde načítání arr[i] může způsobit prostoj na 10–100+ taktů, pokud data nejsou v L1. Procesor predikuje větev, začíná code_true, iniciuje prefetch. Při chybě – flush a restart.

Kód bez větvení vs. s větvením: závislost na mezipaměti

Zjednodušení s větvením:

if (arr[i] > 0) {
    result++;
}

Stává se:

result += (arr[i] > 0);

• Data v L1: kód bez větvení vítězí – žádná chybná predikce, minimální zpoždění.
• L2: neutrální, cena chyby predikce je malá.
• L3/DRAM: kód s větvením je rychlejší – spekulace spouští prefetch předem, skrývající latenci.

Kód bez větvení přenáší zpoždění do kritické cesty: procesor čeká na data před porovnáním, bez překrývání výpočty.

Hledání hodnoty: cena bezpodmínečných načítání

Originál:

Value result = default_value;
for (size_t i = 0; i < n; ++i) {
    if (keys[i] == target) {
        result = values[i];
    }
}
return result;

Kód bez větvení:

Value result = default_value;
for (size_t i = 0; i < n; ++i) {
    result = (keys[i] == target) ? values[i] : result;
}
return result;

V kódu bez větvení se values[i] načítá při každé iteraci, utrácející propustnost na celé pole. Originál čte pouze do shody.

Binární vyhledávání: řetězce závislostí

Kód s větvením:

while (low < high) {
    size_t mid = low + (high - low) / 2;
    if (keys[mid] < target)
        low = mid + 1;
    else
        high = mid;
}

Procesor spekulativně vypočítá další mid a prefetch keys[mid].

Kód bez větvení:

while (low < high) {
    size_t mid = low + (high - low) / 2;
    size_t step = (high - low) / 2;
    low  = (keys[mid] < target) ? mid + 1 : low;
    high = (keys[mid] < target) ? high    : mid;
}

Závislosti na výsledku porovnání blokují spekulaci: další mid čeká na zápis low/high.

• Polovina predikcí je nesprávná, ale časný prefetch překrývá flush.
• Kód bez větvení: více instrukcí, pozdní načítání, explicitní zpoždění paměti.

Co je důležité

• Spekulace skrývá latenci paměti, spouštějíc prefetch podle predikovaných větví.
• Kód bez větvení eliminuje chybnou predikci, ale zhoršuje výkon při přístupu k L3/DRAM.
• Profilujte na cílovém hardwaru: L1 – kód bez větvení, velká pole – kód s větvením.
• Konzolové porty her často trpí ignorováním těchto efektů.
• Závislosti v řetězcích kódu bez větvení blokují OoO-optimalizace.

Při náhodných datech v L1 dominuje kód bez větvení. Při vzorcích nebo velkých objemech vítězí kód s větvením díky spekulativním načítáním.

— Editorial Team