Predication

In diesem Artikel wird untersucht, warum gewöhnliche if-Anweisungen die Ausführungsdauer erheblich verlangsamen können und wie man dem entgegenwirken kann. Um die Ursprünge dieses Phänomens besser zu verstehen, ist ein grundlegendes Verständnis von Branch Prediction erforderlich.

Um die Ausführungsgeschwindigkeit von Code zu verbessern, verwendet die CPU das sogenannte Pipelining, um die Pipeline maximal auszulasten. Dieser Effekt kann jedoch durch sogenannte Pipeline-Flushes beeinträchtigt werden. Um dieses Thema genauer zu verstehen, hier ein kurzes Beispiel: Das folgende Programm zählt die Anzahl der Zahlen, die größer als 50 sind. Da die Zahlen mithilfe einer Zufallsfunktion und Modulo 101 generiert werden, liegen sie immer im Bereich von 0 und 100. Aus diesem Grund sollte der Counter in der if-Bedingung in etwa der Hälfte der Schleifendurchläufe erhöht werden.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
  int counter = 0;
  for (int i = 0; i < 100000; i++)
  {
    if (rand() % 101 > 50)
    {
      counter++;
    }
  }
  printf("%d", counter);
  return 0;
}

Warum genau ist diese Implementierung langsam? Die CPU versucht mithilfe der sogenannten Branch Prediction, zukünftige Programmzeilen vorherzusagen und vorzeitig auszuführen. Da die nächste Zufallszahl noch nicht bekannt ist, muss die CPU raten, ob der Counter erhöht wird oder nicht. Anhand dieser Entscheidung werden der Pipeline neue Instruktionen zugeführt. Wenn die Vorhersage jedoch falsch ist, wird ein Pipeline-Flush ausgelöst, der dazu führt, dass die Pipeline einige Takte benötigt, um alle vorherigen Anweisungen zu löschen. Erst dann kann die korrekte Instruktion ausgeführt werden. Da dies jedoch nur in 50% der Fälle zutrifft, kann praktisch kein Laufzeitgewinn durch die Branch Prediction erzielt werden. Im Gegenteil, durch die Flushes wird sogar die Ausführungsdauer verlangsamt. Bei den 50% spricht man auch von der Selektivität.

Wie kann dieses Verhalten verhindert werden?

Das beste Mittel, um falsche Branch Predictions zu vermeiden, besteht darin, erst gar keine Branches zu verwenden. Dazu kann die boolsche If-Bedingung in einen Integer gecastet werden. Dieser hat entweder den Wert 0 oder 1, der direkt auf die Variable counter addiert werden kann.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
  int counter = 0;
  for (int i = 0; i < 100000; i++)
  {
    counter += (int)(rand() % 101 > 50);
  }
  printf("%d", counter);
  return 0;
}

Auf diese Weise ist die Ausführungsgeschwindigkeit unabhängig von der Selektivität.

Vergleich der Laufzeiten von Branched zu Predicated

Deutlich wird bei einem Vergleich der Laufzeiten ersichtlich, wie sich die Selektivität auf die Performance auswirkt. Bei einer Selektivität von 50% zeigt sich deutlich, dass die Branch Prediction am ineffektivsten ist. Eine Implementierung mit Predication bleibt hingegen gänzlich unberührt von der Selektivität.