Quelle est la technique d'inversion de boucle?

J'étais en train de parcourir un document qui parle des techniques d'optimisation du compilateur juste à temps (JIT) pour Java. L'un d'eux était "l'inversion de boucle". Et le document dit:

Vous remplacez une whileboucle régulière par une do-whileboucle. Et la do-whileboucle est définie dans une ifclause. Ce remplacement entraîne deux sauts de moins.

Comment fonctionne l'inversion de boucle et comment optimise-t-elle notre chemin de code?

NB: Ce serait formidable si quelqu'un pouvait expliquer avec un exemple de code Java et comment JIT l'optimise en code natif et pourquoi est-il optimal dans les processeurs modernes.

while (condition) { 
  ... 
}

Flux de travail:

1. vérifier l'état;
2. si faux, sauter à l'extérieur de la boucle;
3. exécuter une itération;
4. sauter en haut.

if (condition) do {
  ...
} while (condition);

Flux de travail:

1. vérifier l'état;
2. si faux, passez au-delà de la boucle;
3. exécuter une itération;
4. vérifier l'état;
5. si vrai, passez à l'étape 3.

En comparant ces deux, vous pouvez facilement voir que ce dernier peut ne pas faire de sauts du tout, à condition qu'il y ait exactement un pas dans la boucle, et généralement le nombre de sauts sera inférieur d'un au nombre d'itérations. Le premier devra revenir en arrière pour vérifier la condition, seulement pour sauter hors de la boucle lorsque la condition est fausse.

Les sauts sur des architectures CPU modernes en pipeline peuvent être assez coûteux: comme le CPU termine l'exécution des vérifications avant le saut, les instructions au-delà de ce saut sont déjà au milieu du pipeline. Tout ce traitement doit être ignoré si la prédiction de branchement échoue. La poursuite de l'exécution est retardée pendant le réamorçage du pipeline.

Explication de la prédiction de branche mentionnée : pour chaque type de saut conditionnel, le CPU a deux instructions, chacune comprenant un pari sur le résultat. Par exemple, vous mettriez une instruction disant " sauter sinon zéro, parier sur pas zéro " à la fin d'une boucle car le saut devra être fait sur toutes les itérations sauf la dernière. De cette façon, le CPU commence à pomper son pipeline avec les instructions suivant la cible de saut au lieu de celles suivant l'instruction de saut elle-même.

Note importante

Veuillez ne pas prendre cela comme un exemple d'optimisation au niveau du code source. Ce serait totalement erroné car, comme cela ressort de votre question, la transformation de la première forme en la seconde est quelque chose que le compilateur JIT fait de façon routinière, complètement de lui-même.

Cela peut optimiser une boucle qui est toujours exécutée au moins une fois.

Une whileboucle régulière retournera alors toujours au début au moins une fois et sautera à la fin une fois à la fin. Un exemple de boucle simple exécutée une fois:

int i = 0;
while (i++ < 1) {
    //do something
}  

Une do-whileboucle en revanche sautera le premier et le dernier saut. Voici une boucle équivalente à celle ci-dessus, qui se déroulera sans sauts:

int i = 0;
if (i++ < 1) {
    do {
        //do something
    } while (i++ < 1); 
}

Parcourons-les:

La whileversion:

void foo(int n) {
    while (n < 10) {
       use(n);
       ++n;
    }
    done();
}

1. Tout d'abord, nous testons net passons à done();si la condition n'est pas vraie.
2. Ensuite, nous utilisons et incrémentons n.
3. Maintenant, nous revenons à la condition.
4. Rincez, répétez.
5. Lorsque la condition n'est plus vraie, nous passons à done().

La do-whileversion:

(Rappelez-vous que nous ne faisons pas cela dans le code source [qui introduirait des problèmes de maintenance], le compilateur / JIT le fait pour nous.)

void foo(int n) {
    if (n < 10) {
        do {
            use(n);
            ++n;
        }
        while (n < 10);
    }
    done();
}

1. Tout d'abord, nous testons net passons à done();si la condition n'est pas vraie.
2. Ensuite, nous utilisons et incrémentons n.
3. Maintenant, nous testons la condition et sautons en arrière si elle est vraie.
4. Rincez, répétez.
5. Lorsque la condition n'est plus vraie, nous passons (pas sautons) à done().

Ainsi, par exemple, si au ndébut 9, nous ne sautons jamais du tout dans la do-whileversion, alors que dans la whileversion, nous devons revenir au début, faire le test, puis revenir à la fin quand nous voyons que ce n'est pas vrai .

L'inversion de boucle est une technique d'optimisation des performances qui améliore les performances car le processeur peut obtenir le même résultat avec moins d'instructions. Cela devrait surtout améliorer les performances dans des conditions aux limites.

Ce lien fournit un autre exemple d'inversion de boucle. Dans quelques architectures où décrémenter et comparer est implémenté comme un jeu d'instructions unique, il est logique de convertir une boucle for en un moment avec une opération de décrémentation et de comparaison.

Wikipedia a un très bon exemple et je l'explique encore ici.

 int i, a[100];
  i = 0;
  while (i < 100) {
    a[i] = 0;
    i++;
  }

sera converti par le compilateur en

  int i, a[100];
  i = 0;
  if (i < 100) {
    do {
      a[i] = 0;
      i++;
    } while (i < 100);
  }

Comment cela se traduit-il par la performance? Lorsque la valeur de i est 99, le processeur n'a pas besoin d'effectuer un GOTO (ce qui est requis dans le premier cas). Cela améliore les performances.