Prédiction de branche en Java

1. Introduction

La prédiction de branche est un concept intéressant en informatique et peut avoir un impact profond sur les performances de nos applications. Pourtant, ce n'est généralement pas bien compris et la plupart des développeurs y prêtent très peu d'attention.

Dans cet article, nous allons explorer exactement ce que c'est, comment cela affecte notre logiciel et ce que nous pouvons faire à ce sujet.

2. Que sont les pipelines d'instructions?

Lorsque nous écrivons un programme informatique, nous écrivons un ensemble de commandes que nous attendons de l'ordinateur qu'il exécute en séquence.

Les premiers ordinateurs les exécutaient un par un. Cela signifie que chaque commande est chargée en mémoire, exécutée dans son intégralité, et ce n'est que lorsqu'elle est terminée que la suivante sera chargée.

Les pipelines d'instructions constituent une amélioration par rapport à cela. Ils permettent au processeur de diviser le travail en morceaux, puis d'exécuter différentes parties en parallèle. Cela permettrait alors au processeur d'exécuter une commande tout en chargeant la suivante, prête à l'emploi.

Des pipelines plus longs à l'intérieur du processeur permettent non seulement de simplifier chaque partie, mais également d'exécuter davantage de parties en parallèle. Cela peut améliorer les performances globales du système.

Par exemple, nous pourrions avoir un programme simple:

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

Cela peut être traité par un pipeline comprenant des segments Fetch, Decode, Execute, Store comme:

Nous pouvons voir ici comment l'exécution globale des quatre commandes est exécutée en parallèle, rendant ainsi toute la séquence plus rapide.

3. Quels sont les dangers?

Certaines commandes que le processeur doit exécuter entraîneront des problèmes pour le pipelining . Il s'agit de toutes les commandes où l'exécution d'une partie du pipeline dépend des parties précédentes, mais où ces parties précédentes n'ont peut-être pas encore été exécutées.

Les succursales sont une forme particulière de danger. Ils entraînent l'exécution dans l'une des deux directions, et il n'est pas possible de savoir dans quelle direction tant que la branche n'est pas résolue. Cela signifie que toute tentative de charger les commandes au-delà de la branche n'est pas sûre car nous n'avons aucun moyen de savoir d'où les charger.

Modifions notre programme simple pour introduire une branche:

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

Le résultat est le même que précédemment, mais nous avons introduit une instruction if au milieu. L'ordinateur verra cela et ne pourra pas charger les commandes après cela tant que cela n'aura pas été résolu . En tant que tel, le flux ressemblera à quelque chose comme:

Nous pouvons voir immédiatement l'impact que cela a sur l'exécution de notre programme, et combien de pas d'horloge il a fallu pour exécuter le même résultat.

4. Qu'est-ce que la prédiction de branche?

La prédiction de branche est une amélioration de ce qui précède, où notre ordinateur tentera de prédire la direction dans laquelle une branche va aller et agira en conséquence.

Dans notre exemple ci-dessus, le processeur peut prédire que if (a <10) est susceptible d'être vrai , et donc il agira comme si l'instruction a + = 2 était la suivante à exécuter. Cela ferait alors ressembler le flux à quelque chose comme:

Nous pouvons voir tout de suite que cela a amélioré les performances de notre programme - il prend maintenant neuf ticks et non 11, donc c'est 19% plus rapide.

Ce n’est pas sans risque, cependant. Si la prédiction de branche se trompe, elle commencera à mettre en file d'attente les instructions qui ne devraient pas être exécutées. Si cela se produit, l'ordinateur devra les jeter et recommencer.

Tournons notre conditionnel pour qu'il soit maintenant faux :

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

Cela pourrait exécuter quelque chose comme:

This is now slower than the earlier flow, even though we're doing less! The processor incorrectly predicted that the branch would evaluate to true, started queueing up the a += 2 instruction, and then had to discard it and start over when the branch evaluated to false.

5. Real Impact on Code

Now that we know what branch prediction is and what the benefits are, how can it affect us? After all, we're talking about losing a few processor cycles on high-speed computers, so surely it won't be noticeable.

And sometimes that's true. But sometimes it can make a surprising difference to the performance of our applications. It depends a lot on exactly what we're doing. Specifically, it depends on how much we're doing in a short time.

5.1. Counting List Entries

Let's try counting entries in a list. We're going to generate a list of numbers, then count how many of them are less than a certain cutoff. That's very similar to the above examples, but we're doing it in a loop instead of just as a single instruction:

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

Note that we're only timing the loop that does the counting because this is what we're interested in. So, how long does this take?

If we're generating sufficiently small lists, then the code runs so fast that it can't be timed — a list of size 100,000 still shows a time of 0ms. However, when the list gets large enough that we can time it, we can see a significant difference based on whether we have shuffled the list or not. For a list of 10,000,000 numbers:

  • Sorted – 44ms
  • Shuffled – 221ms

That is, the shuffled list takes 5x longer to count than the sorted list, even though the actual numbers being counted are the same.

However, the act of sorting the list is significantly more expensive than just performing the counting. We should always profile our code and determine if any performance gains are beneficial.

5.2. Order of Branches

Following the above, it seems reasonable that the order of branches in an if/else statement should be important. That is, we could expect the following to perform better than if we re-ordered the branches:

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

However, modern computers can avoid this issue by using the branch prediction cache. Indeed, we can test this as well:

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

This code executes in around the same time – ~35ms for sorted numbers, ~200ms for shuffled numbers – when counting 10,000,000 numbers, irrespective of the value of cutoffPercentage.

This is because the branch predictor is handling both branches equally and correctly guessing which way we're going to go for them.

5.3. Combining Conditions

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

Nous avons vu ce qu'est la prédiction de branche et comment elle peut avoir un impact sur nos programmes. Cela peut nous donner des outils supplémentaires dans notre ceinture pour nous assurer que nos programmes sont aussi efficaces que possible.

Cependant, comme c'est toujours le cas, nous devons nous rappeler de profiler notre code avant d'apporter des modifications majeures . Il arrive parfois que des modifications pour aider à la prédiction des branches coûtent plus cher d'autres manières.

Des exemples de cas de cet article sont disponibles à l'adresse over sur GitHub.