Les compilateurs produisent-ils un meilleur code pour les boucles do-while par rapport aux autres types de boucles?

Il y a un commentaire dans la bibliothèque de compression zlib (qui est utilisée dans le projet Chromium parmi beaucoup d'autres) qui implique qu'une boucle do-while en C génère du «meilleur» code sur la plupart des compilateurs. Voici l'extrait de code où il apparaît.

do {
} while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
         scan < strend);
/* The funny "do {}" generates better code on most compilers */

https://code.google.com/p/chromium/codesearch#chromium/src/third_party/zlib/deflate.c&l=1225

Existe-t-il des preuves que la plupart (ou certains) des compilateurs généreraient un meilleur code (par exemple plus efficace)?

Mise à jour: Mark Adler , l'un des auteurs originaux, a donné un peu de contexte dans les commentaires.

Tout d'abord:

Une do-whileboucle n'est pas la même chose qu'une while-loop ou une for-loop.

• whileet les forboucles peuvent ne pas exécuter du tout le corps de la boucle.
• Une do-whileboucle exécute toujours le corps de la boucle au moins une fois - elle ignore la vérification de la condition initiale.

Voilà donc la différence logique. Cela dit, tout le monde n'y adhère pas strictement. Il est assez courant d' utiliser des boucles whileou des forboucles même s'il est garanti qu'elles boucleront toujours au moins une fois. (Surtout dans les langues avec des boucles foreach .)

Donc, pour éviter de comparer des pommes et des oranges, je vais continuer en supposant que la boucle s'exécutera toujours au moins une fois. De plus, je ne mentionnerai plus les forboucles car ce sont essentiellement des whileboucles avec un peu de sucre de syntaxe pour un compteur de boucles.

Je vais donc répondre à la question:

Si une whileboucle est garantie de boucler au moins une fois, y a-t-il un gain de performance en utilisant une do-whileboucle à la place?

A do-whileignore le premier contrôle de condition. Il y a donc une branche de moins et une condition de moins à évaluer.

Si la condition est coûteuse à vérifier et que vous savez que vous êtes assuré de faire une boucle au moins une fois, une do-whileboucle pourrait être plus rapide.

Et bien que cela soit considéré comme une micro-optimisation au mieux, c'est une que le compilateur ne peut pas toujours faire: en particulier lorsque le compilateur est incapable de prouver que la boucle entrera toujours au moins une fois.

En d'autres termes, une boucle while:

while (condition){
    body
}

Est effectivement le même que celui-ci:

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

Si vous savez que vous bouclerez toujours au moins une fois, cette instruction if est étrangère.

De même, au niveau de l'assemblage, c'est à peu près comment les différentes boucles se compilent pour:

boucle do-while:

start:
    body
    test
    conditional jump to start

boucle while:

    test
    conditional jump to end
start:
    body
    test
    conditional jump to start
end:

Notez que la condition a été dupliquée. Une autre approche est:

    unconditional jump to end
start:
    body
end:
    test
    conditional jump to start

... qui échange le code en double contre un saut supplémentaire.

Quoi qu'il en soit, c'est encore pire qu'une do-whileboucle normale .

Cela dit, les compilateurs peuvent faire ce qu'ils veulent. Et s'ils peuvent prouver que la boucle entre toujours une fois, alors il a fait le travail pour vous.

Mais les choses sont un peu bizarres pour l'exemple particulier de la question car il a un corps de boucle vide. Puisqu'il n'y a pas de corps, il n'y a pas de différence logique entre whileet do-while.

FWIW, j'ai testé ceci dans Visual Studio 2012:

• Avec le corps vide, il génère en fait le même code pour whileet do-while. Donc, cette partie est probablement un vestige de l'ancien temps où les compilateurs n'étaient pas aussi bons.

• Mais avec un corps non vide, VS2012 parvient à éviter la duplication du code de condition, mais génère toujours un saut conditionnel supplémentaire.

Il est donc ironique que, bien que l'exemple de la question montre pourquoi une do-whileboucle pourrait être plus rapide dans le cas général, l'exemple lui-même ne semble pas apporter d'avantages sur un compilateur moderne.

Compte tenu de l'âge du commentaire, nous ne pouvons que deviner pourquoi il serait important. Il est très possible que les compilateurs de l'époque n'aient pas été capables de reconnaître que le corps était vide. (Ou s'ils l'ont fait, ils n'ont pas utilisé les informations.)

Existe-t-il des preuves que la plupart (ou certains) des compilateurs généreraient un meilleur code (par exemple plus efficace)?

Pas grand-chose, à moins que vous ne regardiez l' assemblage réellement généré d'un compilateur réel et spécifique sur une plate-forme spécifique avec des paramètres d'optimisation spécifiques.

Cela valait probablement la peine de s'inquiéter il y a des décennies (lorsque ZLib a été écrit), mais certainement pas de nos jours, à moins que vous ne trouviez, par un vrai profilage, que cela supprime un goulot d'étranglement de votre code.

En un mot (tl; dr):

J'interprète le commentaire dans le code des OP un peu différemment, je pense que le "meilleur code" qu'ils prétendent avoir observé était dû au déplacement du travail réel dans la "condition" de la boucle. Je suis tout à fait d'accord cependant que c'est très spécifique au compilateur et que la comparaison qu'ils ont faite, tout en étant capable de produire un code légèrement différent, est pour la plupart inutile et probablement obsolète, comme je le montre ci-dessous.

Détails:

Il est difficile de dire ce que l'auteur original voulait dire par son commentaire sur cette do {} whileproduction de meilleur code, mais j'aimerais spéculer dans une autre direction que ce qui a été soulevé ici - nous pensons que la différence entre do {} whileet les while {}boucles est assez mince (une branche de moins comme Mystical a dit), mais il y a quelque chose d'encore plus "drôle" dans ce code et qui met tout le travail dans cette folle condition, et garde la partie interne vide ( do {}).

J'ai essayé le code suivant sur gcc 4.8.1 (-O3), et cela donne une différence intéressante -

#include "stdio.h" 
int main (){
    char buf[10];
    char *str = "hello";
    char *src = str, *dst = buf;

    char res;
    do {                            // loop 1
        res = (*dst++ = *src++);
    } while (res);
    printf ("%s\n", buf);

    src = str;
    dst = buf;
    do {                            // loop 2
    } while (*dst++ = *src++);
    printf ("%s\n", buf);

    return 0; 
}

Après la compilation -

00000000004003f0 <main>:
  ... 
; loop 1  
  400400:       48 89 ce                mov    %rcx,%rsi
  400403:       48 83 c0 01             add    $0x1,%rax
  400407:       0f b6 50 ff             movzbl 0xffffffffffffffff(%rax),%edx
  40040b:       48 8d 4e 01             lea    0x1(%rsi),%rcx
  40040f:       84 d2                   test   %dl,%dl
  400411:       88 16                   mov    %dl,(%rsi)
  400413:       75 eb                   jne    400400 <main+0x10>
  ...
;loop 2
  400430:       48 83 c0 01             add    $0x1,%rax
  400434:       0f b6 48 ff             movzbl 0xffffffffffffffff(%rax),%ecx
  400438:       48 83 c2 01             add    $0x1,%rdx
  40043c:       84 c9                   test   %cl,%cl
  40043e:       88 4a ff                mov    %cl,0xffffffffffffffff(%rdx)
  400441:       75 ed                   jne    400430 <main+0x40>
  ...

Ainsi, la première boucle fait 7 instructions tandis que la seconde en fait 6, même si elles sont censées faire le même travail. Maintenant, je ne peux pas vraiment dire s'il y a une certaine intelligence du compilateur derrière cela, probablement pas et c'est juste une coïncidence, mais je n'ai pas vérifié comment cela interagit avec les autres options du compilateur que ce projet pourrait utiliser.

Sur clang 3.3 (-O3) par contre, les deux boucles génèrent ce code de 5 instructions:

  400520:       8a 88 a0 06 40 00       mov    0x4006a0(%rax),%cl
  400526:       88 4c 04 10             mov    %cl,0x10(%rsp,%rax,1)
  40052a:       48 ff c0                inc    %rax
  40052d:       48 83 f8 05             cmp    $0x5,%rax
  400531:       75 ed                   jne    400520 <main+0x20>

Ce qui montre simplement que les compilateurs sont assez différents et progressent à un rythme beaucoup plus rapide que ce que certains programmeurs auraient pu prévoir il y a plusieurs années. Cela signifie également que ce commentaire est assez dénué de sens et probablement là parce que personne n'avait jamais vérifié s'il avait encore du sens.

En bout de ligne - si vous voulez optimiser le meilleur code possible (et que vous savez à quoi cela devrait ressembler), faites-le directement dans l'assemblage et coupez le "middle-man" (compilateur) de l'équation, mais prenez en compte ce plus récent les compilateurs et les nouveaux matériels peuvent rendre cette optimisation obsolète. Dans la plupart des cas, il est préférable de laisser simplement le compilateur faire ce niveau de travail pour vous et de se concentrer sur l'optimisation des gros travaux.

Un autre point à souligner - le nombre d'instructions (en supposant que c'est ce que le code des OP d'origine recherchait), n'est en aucun cas une bonne mesure de l'efficacité du code. Toutes les instructions n'ont pas été créées égales, et certaines d'entre elles (de simples mouvements de reg-to-reg par exemple) sont vraiment bon marché car elles sont optimisées par le CPU. Une autre optimisation pourrait en fait nuire aux optimisations internes du processeur, de sorte que seule une analyse comparative appropriée compte.

Une whileboucle est souvent compilée comme une do-whileboucle avec une branche initiale vers la condition, c'est-à-dire

    bra $1    ; unconditional branch to the condition
$2:
    ; loop body
$1:
    tst <condition> ; the condition
    brt $2    ; branch if condition true

alors que la compilation d'une do-whileboucle est la même sans la branche initiale. Vous pouvez voir que cela while()est intrinsèquement moins efficace par le coût de la succursale initiale, qui n'est cependant payée qu'une seule fois. [Comparez avec la manière naïve d'implémentation while,qui nécessite à la fois une branche conditionnelle et une branche inconditionnelle par itération.]

Cela dit, ce ne sont pas des alternatives vraiment comparables. Il est pénible de transformer une whileboucle en do-whileboucle et vice versa. Ils font des choses différentes. Et dans ce cas, les divers appels de méthode domineraient totalement tout ce que le compilateur a fait par whilerapport àdo-while.

La remarque ne concerne pas le choix de l'instruction de contrôle (do vs. while), il s'agit du déroulement de la boucle !!!

Comme vous pouvez le voir, il s'agit d'une fonction de comparaison de chaînes (les éléments de chaîne mesurant probablement 2 octets de long), qui auraient pu être écrits avec une seule comparaison plutôt que quatre dans un raccourci et une expression.

Cette dernière implémentation est bien sûr plus rapide, car elle effectue une seule vérification de la condition de fin de chaîne après toutes les comparaisons de quatre éléments, alors que le codage standard impliquerait une vérification par comparaison. Dit différemment, 5 tests par 4 éléments contre 8 tests par 4 éléments.

Quoi qu'il en soit, cela ne fonctionnera que si la longueur de la chaîne est un multiple de quatre ou a un élément sentinelle (de sorte que les deux chaînes sont garanties de différer au-delà de la strendfrontière). Assez risqué!

Cette discussion de l'efficacité while vs do est complètement inutile dans ce cas, car il n'y a pas de corps.

while (Condition)
{
}

et

do
{
}
while (Condition);

sont absolument équivalents.