Quelle est la technique d’inversion de boucle?

Je parcourais un document qui traite 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 boucle while standard par une boucle do-while while. Et la boucle do-while while est définie dans une clause if . Ce remplacement entraîne deux sauts de moins.

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

NB: Ce serait génial si quelqu’un pouvait expliquer avec un exemple de code Java et comment JIT optimise le code natif et pourquoi il est optimal dans les processeurs modernes.

     while (condition) { ... } 

    Workflow:

    1. condition de vérification;
    2. si faux, sautez en dehors de la boucle;
    3. exécuter une itération;
    4. sauter en haut.

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

    Workflow:

    1. condition de vérification;
    2. si faux, sautez au-delà de la boucle;
    3. exécuter une itération;
    4. condition de vérification;
    5. Si c’est le cas, passez à l’étape 3.

    En comparant ces deux éléments, vous pouvez facilement voir que ce dernier ne fait aucun saut, à condition qu’il y ait exactement une étape dans la boucle, et que le nombre de sauts soit généralement inférieur au nombre d’itérations. Le premier devra revenir en arrière pour vérifier la condition, mais seulement pour sortir de la boucle lorsque la condition est fausse.

    Les sauts sur les architectures de processeurs en pipeline modernes peuvent être assez coûteux: comme le processeur 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 twig échoue. L’exécution ultérieure est retardée pendant la réprimande du pipeline.

    Expliquer la prédiction de twig mentionnée: pour chaque type de saut conditionnel, le CPU a deux instructions, chacune comprenant un pari sur le résultat. Par exemple, vous placeriez une instruction disant ” sauter sinon zéro, misant sur non nul ” à 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 plutôt que celles qui suivent l’instruction de saut elle-même.

    Note importante

    Veuillez ne pas prendre cela comme exemple pour optimiser au niveau du code source. Cela serait totalement erroné car, comme cela a déjà été dit dans votre question, le compilateur JIT effectue automatiquement la transformation de la première forme en la seconde.

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

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

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

    En revanche, une boucle à faire est nécessaire pour sauter 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); } 

    Parcourons-les:

    La version while :

     void foo(int n) { while (n < 10) { use(n); ++n; } done(); } 
    1. D'abord, nous testons 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 que nous ne faisons pas 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. D'abord, nous testons 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 passons (pas sautons) à done() .

    Ainsi, par exemple, si n commence par 9 , nous ne sautons jamais du tout dans la version do-while , alors que dans la version temporaire, nous devons retourner au début, faire le test et revenir à la fin lorsque nous vois 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 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 en tant que jeu d’instructions unique, il est logique de convertir une boucle for avec un décrément et une opération 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 par la performance? Lorsque la valeur de i est 99, le processeur n'a pas besoin d'exécuter un GOTO (requirejs dans le premier cas). Cela améliore les performances.