Spekulatywne wykonywanie przeciw branchless kodowi

Wykonanie spekulacyjne i kod bez rozgałęzień: ukryte kompromisy wydajności

Współczesne procesory wykonują miliardy operacji na sekundę, ale prędkość dostępu do pamięci rośnie wolniej. Ta luka sprawia, że oczekiwanie na dane staje się głównym źródłem strat wydajności. Procesory ewoluowały od pasywnych wykonawców do aktywnych menedżerów przepływu danych: wykonanie poza kolejnością, przeorganizowanie zależności i wykonanie spekulacyjne.

Przewidywanie rozgałęzień pozwala uruchamiać ładowania z wyprzedzeniem, ukrywając opóźnienie pamięci. Błąd przewidywania kosztuje 10–20 taktów, ale oczekiwanie z L3 lub DRAM — setki. Kod bez rozgałęzień eliminuje błędne przewidywania, ale pozbawia procesor możliwości spekulacji.

Ewolucja od sekwencji do spekulacji

Wczesne systemy wykonywały instrukcje ściśle sekwencyjnie. IBM System/360 Model 91 wprowadził algorytm Tomasulo do wykonania poza kolejnością: instrukcje startują, gdy operandy są gotowe.

Wykonanie spekulacyjne pojawiło się później w superskalarnych procesorach takich jak Intel Pentium Pro (1995). Potok na 40 mikrooperacji utrzymuje dziesiątki instrukcji w locie, przewidując rozgałęzienia na podstawie historii.

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

Tutaj załadowanie arr[i] może spowodować przestój na 10–100+ taktów, jeśli danych nie ma w L1. Procesor przewiduje gałąź, zaczyna code_true, inicjuje prefetch. Przy błędzie — flush i restart.

Branchless vs branchful: zależność od pamięci podręcznej

Uproszczenie z rozgałęzieniem:

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

Staje się:

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

• Dane w L1: branchless wygrywa — brak błędnych przewidywań, minimalne opóźnienie.
• L2: neutralnie, koszt błędu przewidywania jest mały.
• L3/DRAM: branchful szybszy — spekulacja uruchamia prefetch z wyprzedzeniem, ukrywając opóźnienie.

Branchless przenosi opóźnienie na ścieżkę krytyczną: procesor czeka na dane przed porównaniem, bez nakładania obliczeń.

Wyszukiwanie wartości: koszt bezwarunkowych ładowań

Oryginał:

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

Branchless:

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

W branchless values[i] jest ładowane w każdej iteracji, zużywając przepustowość na całą tablicę. Oryginał czyta tylko do dopasowania.

Wyszukiwanie binarne: łańcuchy zależności

Branchful:

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

Procesor spekulacyjnie oblicza następny mid i prefetch keys[mid].

Branchless:

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;
}

Zależności od wyniku porównania blokują spekulację: następny mid czeka na zapis low/high.

• Połowa przewidywań jest błędna, ale wczesny prefetch nakłada się na flush.
• Branchless: więcej instrukcji, późne ładowania, jawne opóźnienia pamięci.

Co jest ważne

• Spekulacja ukrywa opóźnienie pamięci, uruchamiając prefetch według przewidywanych gałęzi.
• Branchless eliminuje błędne przewidywania, ale pogarsza wydajność przy dostępie do L3/DRAM.
• Profiluj na docelowym sprzęcie: L1 — branchless, duże tablice — branchful.
• Porty konsolowe gier często cierpią z powodu ignorowania tych efektów.
• Zależności w łańcuchach branchless blokują optymalizacje OoO.

Przy losowych danych w L1 branchless dominuje. Przy wzorcach lub dużych wolumenach branchful wygrywa dzięki spekulacyjnym ładowaniom.

— Editorial Team