Es ist ja so, dass ein Befehl auf der CPU nicht nur ausgeführt wird, er muss auch aus dem Speicher geladen und dekodiert werden. Heutige CPUs dekodieren schonmal den nächsten Befehl, wärend der aktuelle noch ausgeführt wird. Und der übernächste wird zeitgleich aus dem Speicher geholt. Das nennt man Prozessor-Pipeline [1] und das ist cool.
Uncool wird es allerdings, wenn der CPU Befehle vorbereitet hat, die dann doch garnicht ausgeführt werden. Das passiert zum Beispiel bei Sprüngen, wenn auf einmal der Code woanders weiter geht als die Pipeline es erwartet hat. Da gibt es auch wieder eine Menge Techniken um die Sprungvorhersage gut zu machen. Aber das will ich nicht weiter vertiefen.
Betrachten wir lieber folgendes Beispiel:
int min(int a, int b) {
if (b < a)
return b;
return a;
}
Hier kann die Sprungvorhersage nichts tun. Was ist wahrscheinlicher, dass a kleiner ist als b oder doch nicht? Die Wahrscheinlichkeit liegt bei 50%. Wäre es nicht cool, wenn man die kleinere Zahl ausrechnen könnte? Dann braucht man keine Verzweigung im Programmpath und die Pipeline kann wunderschön arbeiten.
Man kann. Es gibt eine Seite mit lauter Bit Twiddling Hacks [2]. Und da gibt es noch viel mehr:
Compute the sign of an integer Detect if two integers have opposite signs Compute the integer absolute value (abs) without branching Compute the minimum (min) or maximum (max) of two integers without branching Determining if an integer is a power of 2
Um das Minimum zweier Interger Zahlen zu berechnen, kann man also folgende Formel verwenden:
int x; // we want to find the minimum of x and y
int y;
int r; // the result goes here
r = y ^ ((x ^ y) & -(x < y)); // min(x, y)
Um das ganze mal zu testen habe ich mir ein kleines Programm geschrieben, welches die kleinere von zwei Zufallszahlen bestimmt. Leider, oder zum Glück, wird die Funktion std::min() weg optimiert, so dass man keine Aussage mehr treffen kann, ob die Sprungvorhersage greift oder nicht. Also habe ich meine eigne min() Funktion geschrieben. Einmal mit einer if() und einmal mit der Rechnung.
Valgrind [3] bringt ein branch-prediction Profiler mit. Die Bedienung ist einfach und das Ergebnis eindeutig. Da ich euch nicht langweilen will, hier gleich das Ergebnis:
Die Details meines Tests werde ich das nächste Mal posten. Muss das erst etwas aufarbeiten.
[1] http://de.wikipedia.org/wiki/Pipeline_%28Prozessor%29
[2] http://www-graphics.stanford.edu/~seander/bithacks.html
[3] http://valgrind.org/docs/manual/cg-manual.html