Warum wird ein sortiertes Array in C++ schneller verarbeitet? Das Geheimnis der Branch Prediction

Einleitung: Eine der unerwartetsten Fragen in der Welt von C++

Stellen Sie sich folgende Situation vor: Sie schreiben eine einfache Schleife in C++, die die Elemente eines großen Arrays summiert, aber nur diejenigen, die einen bestimmten Schwellenwert überschreiten. Sie führen den Code aus, er funktioniert... normal. Dann entscheiden Sie sich, das Array vorher zu sortieren und führen es erneut aus. Und plötzlich stellen Sie fest, dass der Code 2-3 Mal schneller ausgeführt wird! Wo ist der Haken? Magie des Compilers? Ein Fehler im Benchmark?

Diese Frage, die vor über zehn Jahren auf Stack Overflow gestellt wurde, hat tausende Aufrufe gesammelt und sorgt immer noch für hitzige Diskussionen. Heute werden wir sie auf PythonLib gründlich analysieren, mit echten Beispielen in C++ und einem tiefen Eintauchen in die Architektur moderner Prozessoren. Sie erfahren nicht nur warum das passiert, sondern auch, wie Sie diesen Effekt nutzen können, um Ihren Code zu beschleunigen.

1. Das Phänomen nachvollziehen: Der überraschende Code

Lassen Sie uns ein einfaches Programm schreiben, das diesen Effekt deutlich demonstriert. Wir benötigen ein Array mit 100.000 ganzen Zahlen. Wir füllen es mit Zufallswerten und messen dann die Zeit für die Summierung aller Elemente, die 128 überschreiten.

#include <iostream>\n#include <vector>\n#include <algorithm>\n#include <chrono>\n#include <random>\n\nint main() {\n    const int SIZE = 100000;\n    const int THRESHOLD = 128;\n    \n    // Erstellen eines unsortierten Arrays\n    std::vector<int> data(SIZE);\n    std::mt19937 rng(42);\n    std::uniform_int_distribution<int> dist(0, 255);\n    for (auto& val : data) {\n        val = dist(rng);\n    }\n\n    // Summieren für das unsortierte Array\n    auto start = std::chrono::high_resolution_clock::now();\n    long long sum_unsorted = 0;\n    for (int i = 0; i < SIZE; ++i) {\n        if (data[i] >= THRESHOLD) {\n            sum_unsorted += data[i];\n        }\n    }\n    auto end = std::chrono::high_resolution_clock::now();\n    auto time_unsorted = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();\n    std::cout << "Unsortiertes Array: " << time_unsorted << " µs, Summe = " << sum_unsorted << std::endl;\n\n    // Array sortieren\n    std::sort(data.begin(), data.end());\n\n    // Summieren für das sortierte Array\n    start = std::chrono::high_resolution_clock::now();\n    long long sum_sorted = 0;\n    for (int i = 0; i < SIZE; ++i) {\n        if (data[i] >= THRESHOLD) {\n            sum_sorted += data[i];\n        }\n    }\n    end = std::chrono::high_resolution_clock::now();\n    auto time_sorted = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();\n    std::cout << "Sortiertes Array: " << time_sorted << " µs, Summe = " << sum_sorted << std::endl;\n\n    std::cout << "Beschleunigung: " << (double)time_unsorted / time_sorted << "x" << std::endl;\n    return 0;\n}

Bei der Kompilierung ohne Optimierungen (Flag -O0) wird der Unterschied gering sein, aber wenn Sie -O2 oder -O3 in GCC/Clang aktivieren, erhalten Sie ein beeindruckendes Ergebnis: Das sortierte Array wird 3-6 Mal schneller verarbeitet.

2. Die Anatomie des Prozessors: Woher kommt der Unterschied?

Der Schlüssel zur Lösung ist ein Mechanismus namens Branch Prediction (Sprungvorhersage). Moderne Prozessoren sind Pipeline-Maschinen. Sie führen Befehle nicht einzeln aus, sondern unterteilen sie in Phasen (Abruf, Dekodierung, Ausführung, Rückschreiben). Damit die Pipeline nicht stillsteht, versucht der Prozessor vorherzusagen, welcher Codepfad (if oder else) als nächstes ausgeführt wird, und beginnt, die Befehle vorab zu laden.

In unserem Beispiel ist die Bedingung if (data[i] >= THRESHOLD) ein Verzweigungspunkt. Für ein sortiertes Array funktioniert die Vorhersage