Verzweigungsvorhersage in Java

1. Einleitung

Die Branchenvorhersage ist ein interessantes Konzept in der Informatik und kann einen tiefgreifenden Einfluss auf die Leistung unserer Anwendungen haben. Doch es ist in der Regel nicht gut verstanden und die meisten Entwickler zahlen nur sehr wenig Aufmerksamkeit.

In diesem Artikel werden wir genau untersuchen, was es ist, wie es sich auf unsere Software auswirkt und was wir dagegen tun können.

2. Was sind Anweisungspipelines?

Wenn wir ein Computerprogramm schreiben, schreiben wir eine Reihe von Befehlen, die der Computer nacheinander ausführen soll.

Frühe Computer würden diese nacheinander ausführen. Dies bedeutet, dass jeder Befehl in den Speicher geladen und vollständig ausgeführt wird. Erst wenn er abgeschlossen ist, wird der nächste geladen.

Instruction Pipelines sind eine Verbesserung gegenüber dieser. Sie ermöglichen es dem Prozessor, die Arbeit in Teile aufzuteilen und dann verschiedene Teile parallel auszuführen. Dies würde es dem Prozessor dann ermöglichen, einen Befehl auszuführen, während der nächste einsatzbereit geladen wird.

Längere Pipelines im Prozessor ermöglichen nicht nur die Vereinfachung jedes Teils, sondern auch die parallele Ausführung weiterer Teile. Dies kann die Gesamtleistung des Systems verbessern.

Zum Beispiel könnten wir ein einfaches Programm haben:

int a = 0; a += 1; a += 2; a += 3;

Dies kann von einer Pipeline verarbeitet werden, die Segmente zum Abrufen, Dekodieren, Ausführen und Speichern umfasst als:

Wir können hier sehen, wie die Gesamtausführung der vier Befehle parallel ausgeführt wird, wodurch die gesamte Sequenz schneller wird.

3. Was sind die Gefahren?

Bestimmte Befehle, die der Prozessor ausführen muss, verursachen Probleme beim Pipelining . Dies sind alle Befehle, bei denen die Ausführung eines Teils der Pipeline von früheren Teilen abhängt, bei denen diese früheren Teile jedoch möglicherweise noch nicht ausgeführt wurden.

Zweige sind eine besondere Form der Gefahr. Sie bewirken, dass die Ausführung in eine von zwei Richtungen verläuft, und es ist nicht möglich zu wissen, in welche Richtung, bis der Zweig aufgelöst ist. Dies bedeutet, dass jeder Versuch, die Befehle über den Zweig hinaus zu laden, nicht sicher ist, da wir nicht wissen können, woher sie geladen werden sollen.

Lassen Sie uns unser einfaches Programm ändern, um einen Zweig einzuführen:

int a = 0; a += 1; if (a < 10) { a += 2; } a += 3;

Das Ergebnis ist das gleiche wie zuvor, aber wir haben eine if- Anweisung in der Mitte eingefügt. Der Computer sieht dies und kann keine Befehle darüber hinaus laden, bis es behoben wurde . Als solches sieht der Fluss ungefähr so ​​aus:

Wir können sofort sehen, welche Auswirkungen dies auf die Ausführung unseres Programms hat und wie viele Taktschritte erforderlich waren, um dasselbe Ergebnis auszuführen.

4. Was ist eine Verzweigungsvorhersage?

Die Zweigvorhersage ist eine Erweiterung des oben genannten, bei der unser Computer versucht, vorherzusagen, in welche Richtung ein Zweig gehen wird, und dann entsprechend handelt.

In unserem obigen Beispiel könnte der Prozessor vorhersagen, dass wenn (a <10) wahrscheinlich wahr ist , und so wird es so tun, als ob der Befehl a + = 2 der nächste war, der ausgeführt wurde. Dies würde dann dazu führen, dass der Fluss ungefähr so ​​aussieht:

Wir können sofort sehen, dass dies die Leistung unseres Programms verbessert hat - es dauert jetzt neun Ticks und nicht elf, also 19% schneller.

Dies ist jedoch nicht ohne Risiko. Wenn die Verzweigungsvorhersage falsch ist, werden Anweisungen in die Warteschlange gestellt, die nicht ausgeführt werden sollten. In diesem Fall muss der Computer sie wegwerfen und von vorne beginnen.

Lassen Sie uns unsere Bedingung umkehren, damit sie jetzt falsch ist :

int a = 0; a += 1; if (a > 10) { a += 2; } a += 3;

Dies könnte Folgendes ausführen:

Dies ist jetzt langsamer als der frühere Fluss, obwohl wir weniger tun! Der Prozessor sagte fälschlicherweise voraus, dass der Zweig als wahr ausgewertet werden würde , begann, den Befehl a + = 2 in die Warteschlange zu stellen , und musste ihn dann verwerfen und neu beginnen, wenn der Zweig als falsch ausgewertet wurde .

5. Wirkliche Auswirkungen auf den Code

Nun, da wir wissen, was Branchenvorhersage ist und welche Vorteile sie hat, wie kann sie sich auf uns auswirken? Immerhin geht es darum, auf Hochgeschwindigkeitscomputern einige Prozessorzyklen zu verlieren, sodass dies sicherlich nicht auffällt.

Und manchmal stimmt das. Manchmal kann dies jedoch einen überraschenden Unterschied in der Leistung unserer Anwendungen bewirken. Es hängt sehr davon ab, was wir genau tun. Insbesondere hängt es davon ab, wie viel wir in kurzer Zeit tun.

5.1. Listeneinträge zählen

Versuchen wir, Einträge in einer Liste zu zählen. Wir werden eine Liste von Zahlen erstellen und dann zählen, wie viele davon unter einem bestimmten Grenzwert liegen. Das ist den obigen Beispielen sehr ähnlich, aber wir machen es in einer Schleife anstatt nur als einzelne Anweisung:

List numbers = LongStream.range(0, top) .boxed() .collect(Collectors.toList()); if (shuffle) { Collections.shuffle(numbers); } long cutoff = top / 2; long count = 0; long start = System.currentTimeMillis(); for (Long number : numbers) { if (number < cutoff) { ++count; } } long end = System.currentTimeMillis(); LOG.info("Counted {}/{} {} numbers in {}ms", count, top, shuffle ? "shuffled" : "sorted", end - start);

Beachten Sie, dass wir nur die Schleife steuern, die die Zählung durchführt, da wir daran interessiert sind. Wie lange dauert das also?

Wenn wir ausreichend kleine Listen generieren, wird der Code so schnell ausgeführt, dass er nicht zeitgesteuert werden kann. Eine Liste mit einer Größe von 100.000 zeigt immer noch eine Zeit von 0 ms an. Wenn die Liste jedoch so groß wird, dass wir sie zeitlich festlegen können, können wir einen signifikanten Unterschied feststellen, der davon abhängt, ob wir die Liste gemischt haben oder nicht. Für eine Liste von 10.000.000 Nummern:

  • Sortiert - 44ms
  • Gemischt - 221ms

Das heißt, das Zählen der gemischten Liste dauert 5x länger als das Sortieren der Liste, obwohl die tatsächlich gezählten Zahlen gleich sind.

Das Sortieren der Liste ist jedoch erheblich teurer als nur das Zählen. Wir sollten unseren Code immer profilieren und feststellen, ob Leistungssteigerungen von Vorteil sind.

5.2. Reihenfolge der Zweige

Nach dem oben Gesagten erscheint es vernünftig, dass die Reihenfolge der Zweige in einer if / else- Anweisung wichtig sein sollte . Das heißt, wir könnten erwarten, dass Folgendes besser abschneidet, als wenn wir die Filialen nachbestellen würden:

if (mostLikely) { // Do something } else if (lessLikely) { // Do something } else if (leastLikely) { // Do something }

Allerdings können moderne Computer dieses Problem vermeiden , indem die Verzweigungsvorhersage - Cache . In der Tat können wir dies auch testen:

List numbers = LongStream.range(0, top) .boxed() .collect(Collectors.toList()); if (shuffle) { Collections.shuffle(numbers); } long cutoff = (long)(top * cutoffPercentage); long low = 0; long high = 0; long start = System.currentTimeMillis(); for (Long number : numbers) { if (number < cutoff) { ++low; } else { ++high; } } long end = System.currentTimeMillis(); LOG.info("Counted {}/{} numbers in {}ms", low, high, end - start);

Dieser Code wird ungefähr zur gleichen Zeit ausgeführt - ~ 35 ms für sortierte Zahlen, ~ 200 ms für gemischte Zahlen -, wenn 10.000.000 Zahlen gezählt werden, unabhängig vom Wert von cutoffPercentage .

Dies liegt daran, dass der Zweigprädiktor beide Zweige gleich behandelt und richtig errät, welchen Weg wir für sie einschlagen werden.

5.3. Bedingungen kombinieren

What if we have a choice between one or two conditions? It might be possible to re-write our logic in a different way that has the same behavior, but should we do this?

As an example, if we are comparing two numbers to 0, an alternative approach is to multiply them together and compare the result to 0. This is then replacing a condition with a multiplication. But is this worthwhile?

Let's consider an example:

long[] first = LongStream.range(0, TOP) .map(n -> Math.random()  Math.random() < FRACTION ? 0 : n) .toArray(); long count = 0; long start = System.currentTimeMillis(); for (int i = 0; i < TOP; i++) { if (first[i] != 0 && second[i] != 0) { ++count; } } long end = System.currentTimeMillis(); LOG.info("Counted {}/{} numbers using separate mode in {}ms", count, TOP, end - start);

Our condition inside the loop can be replaced, as described above. Doing so actually does affect the runtime:

  • Separate conditions – 40ms
  • Multiple and single condition – 22ms

So the option that uses two different conditions actually takes twice as long to execute.

6. Conclusion

Wir haben gesehen, was Branchenvorhersage ist und wie sie sich auf unsere Programme auswirken kann. Dies kann uns einige zusätzliche Werkzeuge in den Gürtel geben, um sicherzustellen, dass unsere Programme so effizient wie möglich sind.

Wie immer müssen wir jedoch daran denken, unseren Code zu profilieren, bevor wir größere Änderungen vornehmen . Es kann manchmal vorkommen, dass Änderungen zur Unterstützung der Zweigvorhersage auf andere Weise mehr kosten.

Beispiele für die Fälle aus diesem Artikel sind auf GitHub verfügbar.