Spekulative Ausführung vs verzweigungsfreier Code

Spekulative Ausführung und verzweigungsfreier Code: Versteckte Leistungskompromisse

Moderne Prozessoren führen Milliarden von Operationen pro Sekunde aus, aber die Speicherzugriffsgeschwindigkeiten wachsen langsamer. Diese Lücke bedeutet, dass das Warten auf Daten zu einer Hauptursache für Leistungsverluste wird. Prozessoren haben sich von passiven Ausführern zu aktiven Datenfluss-Managern entwickelt: Out-of-Order-Ausführung, Abhängigkeits-Neuordnung und spekulative Ausführung.

Die Sprungvorhersage ermöglicht es, Ladevorgänge frühzeitig zu starten und so die Speicherlatenz zu verbergen. Eine Fehlvorhersage kostet 10–20 Zyklen, aber das Warten auf L3 oder DRAM dauert Hunderte. Verzweigungsfreier Code eliminiert Fehlvorhersagen, nimmt dem Prozessor aber die Fähigkeit zur Spekulation.

Entwicklung von sequenzieller zu spekulativer Ausführung

Frühe Systeme führten Befehle streng sequenziell aus. Der IBM System/360 Model 91 führte den Tomasulo-Algorithmus für Out-of-Order-Ausführung ein: Befehle starten, wenn Operanden bereit sind.

Spekulative Ausführung entstand später in superskalaren Prozessoren wie dem Intel Pentium Pro (1995). Eine 40-Micro-Op-Pipeline hält Dutzende von Befehlen in der Ausführung, wobei Sprünge basierend auf der Historie vorhergesagt werden.

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

Hier kann das Laden von arr[i] zu einer Verzögerung von 10–100+ Zyklen führen, wenn die Daten nicht in L1 sind. Der Prozessor sagt den Sprung voraus, startet code_true und initiiert Prefetch. Bei einer Fehlvorhersage – Flush und Neustart.

Verzweigungsfrei vs. verzweigungsbehaftet: Cache-Abhängigkeit

Vereinfacht mit Verzweigung:

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

Wird zu:

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

• Daten in L1: verzweigungsfrei gewinnt – keine Fehlvorhersage, minimale Verzögerung.
• L2: neutral, die Kosten der Fehlvorhersage sind gering.
• L3/DRAM: verzweigungsbehaftet ist schneller – Spekulation löst Prefetch frühzeitig aus und verdeckt Latenz.

Verzweigungsfrei verschiebt die Verzögerung in den kritischen Pfad: Der Prozessor wartet auf Daten vor dem Vergleich, ohne Berechnungen zu überlappen.

Wertsuche: Die Kosten bedingungsloser Ladevorgänge

Original:

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

Verzweigungsfrei:

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

Bei verzweigungsfreiem Code lädt values[i] bei jeder Iteration, was Bandbreite für das gesamte Array verschwendet. Das Original liest nur bis zu einer Übereinstimmung.

Binäre Suche: Abhängigkeitsketten

Verzweigungsbehaftet:

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

Der Prozessor berechnet spekulativ das nächste mid und prefetched keys[mid].

Verzweigungsfrei:

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

Abhängigkeiten vom Vergleichsergebnis blockieren Spekulation: Das nächste mid wartet auf low/high-Schreibvorgänge.

• Die Hälfte der Vorhersagen ist falsch, aber frühes Prefetch überlappt den Flush.
• Verzweigungsfrei: mehr Befehle, spätere Ladevorgänge, explizite Speicherverzögerungen.

Wichtige Erkenntnisse

• Spekulation verdeckt Speicherlatenz durch Auslösen von Prefetch bei vorhergesagten Sprüngen.
• Verzweigungsfrei eliminiert Fehlvorhersagen, verschlechtert aber die Leistung bei L3/DRAM-Zugriff.
• Profiling auf Zielhardware: L1 – verzweigungsfrei, große Arrays – verzweigungsbehaftet.
• Konsolenspiel-Portierungen leiden oft unter der Vernachlässigung dieser Effekte.
• Abhängigkeiten in verzweigungsfreien Ketten blockieren OoO-Optimierungen.

Mit zufälligen Daten in L1 dominiert verzweigungsfreier Code. Mit Mustern oder großen Volumen gewinnt verzweigungsbehafteter Code aufgrund spekulativer Ladevorgänge.

— Editorial Team