Quelle est la technique d'inversion de boucle?

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

Vous remplacez une boucle while régulière par une boucle do-while. Et la La boucle do-while est définie dans une clause if. 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 peut expliquer avec un exemple de code Java et comment JIT l'optimise en code natif et pourquoi est-il optimal dans les processeurs modernes.

87
demandé sur Trying 2013-12-29 19:26:15

4 réponses 

while (condition) { 
  ... 
}

Flux de travail:

  1. vérifier l'état;
  2. si false, passez à l'extérieur de la boucle;
  3. exécuter une itération;
  4. aller en haut.
if (condition) do {
  ...
} while (condition);

Flux de travail:

  1. vérifier l'état;
  2. si false, passez à au-delà de la boucle;
  3. exécuter une itération;
  4. vérifier l'état;
  5. si true, 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 une étape dans la boucle, et en général le nombre de sauts sera un de moins que le 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 les architectures CPU pipelined modernes peuvent être assez coûteux: comme 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 jeté si la prédiction de branche échoue. La poursuite de l'exécution est retardée pendant que le pipeline est réprimandé.

Expliquant mentionnés direction de la prévision: pour chaque type de saut conditionnel de l'UC deux instructions, chacune comprenant un pari sur le résultat. Par exemple, vous mettriez une instruction disant "jump if not zero, pariant sur not zero" à 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 processeur commence à pomper son pipeline avec les instructions suivant la cible de saut au lieu de celles qui suivent l'instruction de saut elle-même.

Remarque Importante

Veuillez faire Pas prenez ceci comme un exemple de la façon d'optimiser au niveau du code source. Ce serait tout à fait erroné puisque, comme déjà clair à partir de votre question, la transformation de la première forme dans la seconde est quelque chose que le compilateur JIT fait comme une question de routine, complètement seul.

106
répondu Marko Topolnik 2013-12-29 22:12:05

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

Une boucle while régulière va alors toujours revenir au début au moins une fois et sauter à la fin une fois à la fin. Un exemple de boucle simple s'exécutant une fois: 

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

Une boucle do-while d'autre part sautera le premier et le dernier saut. Voici une boucle équivalente à celle ci-dessus, qui fonctionnera sans sauts: 

int i = 0;
if (i++ < 1) {
    do {
        //do something
    } while (i++ < 1); 
}
23
répondu Keppil 2013-12-29 15:45:10

Marchons à travers eux:

La version while: 

void foo(int n) {
    while (n < 10) {
       use(n);
       ++n;
    }
    done();
}
  1. nous testons d'abord n et passons à 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 à done().

La version do-while:

(rappelez-vous, nous ne le faisons pas réellement dans le code source [qui introduirait la maintenance problèmes], 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 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 c'est vrai.
  4. rincer, répéter.
  5. lorsque la condition n'est plus vraie, nous coulons (pas sautons) à done().

Par exemple, si n commence par être 9, nous ne sautons jamais du tout dans la version 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.

3
répondu T.J. Crowder 2013-12-29 15:38:28

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 principalement améliorer les performances dans des conditions aux limites.

Ce lien fournit un autre exemple d'inversion de boucle. Dans quelques architectures où decrement and compare est implémenté comme un seul jeu d'instructions, il est logique de convertir une boucle for en un while avec decrement and compare opération.

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 par des performances? 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.

3
répondu Anirudhan J 2013-12-29 15:44:28