Qu'est-ce que la technique d'inversion de boucle ?

Question

Je parcourais un document qui parle de compilateur juste-à-temps (JIT) pour Java. L'une d'entre elles était "l'inversion de boucle". Et le document dit :

Vous remplacez un while boucle avec un do-while boucle. Et le do-while est placé dans une if clause. Ce remplacement conduit à deux sauts de moins.

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

N.B. : Ce serait formidable si quelqu'un pouvait expliquer avec un exemple de code Java et comment le JIT l'optimise par rapport au code natif et pourquoi c'est optimal dans les processeurs modernes.

Answer 1

while (condition) { 
  ... 
}

Flux de travail :

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

---

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

Flux de travail :

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

---

En comparant les deux, vous pouvez facilement voir que la seconde peut ne pas faire de saut du tout, à condition qu'il y ait exactement une étape dans la boucle, et généralement le nombre de sauts sera inférieur d'une unité au nombre d'itérations. La première devra sauter en arrière pour vérifier la condition, pour ensuite sauter hors de la boucle lorsque la condition est fausse.

Les sauts sur les architectures modernes de CPU en pipeline peuvent être assez coûteux : alors que le CPU termine l'exécution des contrôles avant le saut, les instructions au-delà de ce saut sont déjà au milieu du pipeline. Tout ce traitement doit être abandonné si la prédiction de branchement échoue. L'exécution ultérieure est retardée pendant que le pipeline est réamorcé.

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

Remarque importante

Faites-le, s'il vous plaît. no Prenez cela comme un exemple de la façon d'optimiser au niveau du code source. Ce serait une erreur puisque, comme le montre clairement votre question, la transformation de la première forme en la seconde est une opération de routine que le compilateur JIT effectue de manière totalement autonome.

Answer 2

Cela permet d'optimiser une boucle qui est toujours exécutée au moins une fois.

Un régulier while La boucle reviendra alors toujours au début au moins une fois et sautera à la fin une fois à la fin. Exemple d'une boucle simple fonctionnant une fois :

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

A do-while loop, en revanche, sautera le premier et le dernier saut. Voici une boucle équivalente à celle ci-dessus, qui s'exécutera sans sauts :

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

Answer 3

Parcourons-les :

El while version :

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

1. Nous testons d'abord n et passer à done(); si la condition n'est pas vraie.
2. Ensuite, nous utilisons et incrémentons n .
3. Maintenant, nous revenons à la condition.
4. Rincer, répéter.
5. Lorsque la condition n'est plus vraie, nous passons à l'étape suivante. done() .

El do-while version :

(Rappelez-vous, nous ne faisons pas réellement cela dans le code source [cela 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. Nous testons d'abord n et passer à 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. Rincer, répéter.
5. Lorsque la condition n'est plus vraie, nous passons (et non pas sautons) à l'étape suivante. done() .

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

Answer 4

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

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

Wikipedia propose un très bon exemple et je l'explique à nouveau 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 en termes de performances ? Lorsque la valeur de i est 99, le processeur n'a pas besoin d'effectuer un GOTO (qui est nécessaire dans le premier cas). Cela améliore les performances.