Question Quel est le plus rapide: while (1) ou while (2)?


C'était une question d'entrevue posée par un cadre supérieur.

Lequel est plus vite?

while(1) {
    // Some code
}

ou

while(2) {
    //Some code
}

J'ai dit que les deux ont la même vitesse d'exécution, comme l'expression à l'intérieur while devrait finalement évaluer true ou false. Dans ce cas, les deux évaluent true et il n'y a pas d'instructions conditionnelles supplémentaires à l'intérieur du while condition. Donc, les deux auront la même vitesse d'exécution et je préfère tout (1).

Mais l'interviewer a dit avec confiance: "Vérifiez vos bases. while(1) est plus rapide que while(2)" (Il ne testait pas ma confiance)

Est-ce vrai?

Voir également: Est-ce que "for (;;)" est plus rapide que "while (TRUE)"? Si non, pourquoi les gens l'utilisent-ils?


552
2017-07-20 07:32


origine


Réponses:


Les deux boucles sont infinies, mais nous pouvons voir laquelle prend plus d'instructions / ressources par itération.

En utilisant gcc, j'ai compilé les deux programmes suivants à assembler à différents niveaux d'optimisation:

int main(void) {
    while(1) {}
    return 0;
}


int main(void) {
    while(2) {}
    return 0;
}

Même sans optimisations (-O0), l'assemblage généré était identique pour les deux programmes. Par conséquent, il n'y a pas de différence de vitesse entre les deux boucles.

Pour référence, voici l'assemblage généré (en utilisant gcc main.c -S -masm=intel avec un drapeau d'optimisation):

Avec -O0:

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .text
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    push    rbp
    .seh_pushreg    rbp
    mov rbp, rsp
    .seh_setframe   rbp, 0
    sub rsp, 32
    .seh_stackalloc 32
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Avec -O1:

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .text
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    sub rsp, 40
    .seh_stackalloc 40
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Avec -O2 et -O3 (même sortie):

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .section    .text.startup,"x"
    .p2align 4,,15
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    sub rsp, 40
    .seh_stackalloc 40
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

En effet, l'assemblage généré pour la boucle est identique pour chaque niveau d'optimisation:

 .L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Les bits importants étant:

.L2:
    jmp .L2

Je ne peux pas lire très bien l'assemblage, mais c'est évidemment une boucle inconditionnelle. le jmp instructions inconditionnellement réinitialise le programme à la .L2 étiqueter sans même comparer une valeur par rapport à vrai, et bien sûr le fait à nouveau jusqu'à ce que le programme soit en quelque sorte terminé. Cela correspond directement au code C / C ++:

L2:
    goto L2;

Modifier:

Assez intéressant, même avec pas d'optimisations, les boucles suivantes ont toutes produit exactement la même sortie (inconditionnelle jmp) dans l'assemblage:

while(42) {}

while(1==1) {}

while(2==2) {}

while(4<7) {}

while(3==3 && 4==4) {}

while(8-9 < 0) {}

while(4.3 * 3e4 >= 2 << 6) {}

while(-0.1 + 02) {}

Et même à ma grande surprise:

#include<math.h>

while(sqrt(7)) {}

while(hypot(3,4)) {}

Les choses deviennent un peu plus intéressantes avec les fonctions définies par l'utilisateur:

int x(void) {
    return 1;
}

while(x()) {}


#include<math.h>

double x(void) {
    return sqrt(7);
}

while(x()) {}

À -O0, ces deux exemples appellent réellement x et effectuez une comparaison pour chaque itération.

Premier exemple (retour 1):

.L4:
    call    x
    testl   %eax, %eax
    jne .L4
    movl    $0, %eax
    addq    $32, %rsp
    popq    %rbp
    ret
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Deuxième exemple (retour sqrt(7)):

.L4:
    call    x
    xorpd   %xmm1, %xmm1
    ucomisd %xmm1, %xmm0
    jp  .L4
    xorpd   %xmm1, %xmm1
    ucomisd %xmm1, %xmm0
    jne .L4
    movl    $0, %eax
    addq    $32, %rsp
    popq    %rbp
    ret
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Cependant, à -O1 et ci-dessus, ils produisent tous les deux le même assemblage que les exemples précédents (une inconditionnelle jmp retour à l'étiquette précédente).

TL; DR

Sous GCC, les différentes boucles sont compilées à l'identique. Le compilateur évalue les valeurs constantes et n'effectue aucune comparaison réelle.

La morale de l'histoire est:

  • Il existe une couche de traduction entre le code source C ++ et les instructions CPU, et cette couche a des implications importantes pour les performances.
  • Par conséquent, les performances ne peuvent pas être évaluées en regardant uniquement le code source.
  • Le compilateur devrait être suffisamment intelligent pour optimiser ces cas triviaux. Programmeurs ne devrait pas perdre leur temps à penser à eux dans la grande majorité des cas.

653
2017-07-20 08:03



Oui, while(1) est beaucoup plus rapide que while(2), pour un humain à lire! Si je vois while(1) dans une base de code inconnue, je sais immédiatement ce que l'auteur a voulu, et mes yeux peuvent continuer à la ligne suivante.

Si je vois while(2), Je vais probablement arrêter dans mes pistes et essayer de comprendre pourquoi l'auteur n'a pas écrit while(1). Le doigt de l'auteur at-il glissé sur le clavier? Est-ce que les mainteneurs de cette base de code utilisent while(n) comme un mécanisme de commentaire obscur pour faire des boucles différentes? Est-ce une solution de contournement brute pour un avertissement erroné dans un outil d'analyse statique cassé? Ou est-ce un indice que je lis code généré? Est-ce un bug résultant d'une mauvaise trouvaille-et-remplacement-tout, ou une mauvaise fusion, ou un rayon cosmique? Peut-être que cette ligne de code est supposée faire quelque chose de radicalement différent. Peut-être était-il censé lire while(w) ou while(x2). Je ferais mieux de trouver l'auteur dans l'histoire du fichier et de leur envoyer un email "WTF" ... et maintenant j'ai brisé mon contexte mental. le while(2) pourrait consommer plusieurs minutes de mon temps, quand while(1) aurait pris une fraction de seconde!

J'exagère, mais seulement un peu. La lisibilité du code est vraiment importante. Et cela vaut la peine d'être mentionné dans une interview!


257
2017-07-22 05:51



Les réponses existantes montrant le code généré par un compilateur particulier pour une cible particulière avec un ensemble particulier d'options ne répondent pas entièrement à la question - sauf si la question a été posée dans ce contexte spécifique ("Qui est plus rapide en utilisant gcc 4.7.2 for x86_64 avec des options par défaut? ", par exemple).

En ce qui concerne la définition du langage, dans le machine abstraite  while (1) évalue la constante entière 1, et while (2) évalue la constante entière 2; dans les deux cas, le résultat est comparé pour l'égalité à zéro. La norme linguistique ne dit absolument rien de la performance relative des deux constructions.

Je peux imaginer qu'un compilateur extrêmement naïf pourrait générer un code machine différent pour les deux formes, au moins lorsqu'il est compilé sans demander d'optimisation.

D'autre part, les compilateurs C doivent absolument évaluer certains expressions constantes au moment de la compilation, lorsqu'elles apparaissent dans des contextes nécessitant une expression constante. Par exemple, ceci:

int n = 4;
switch (n) {
    case 2+2: break;
    case 4:   break;
}

nécessite un diagnostic; un compilateur paresseux n'a pas la possibilité de reporter l'évaluation de 2+2 jusqu'à l'exécution. Comme un compilateur doit avoir la capacité d'évaluer des expressions constantes au moment de la compilation, il n'y a pas de bonne raison pour qu'il ne profite pas de cette capacité même si cela n'est pas nécessaire.

La norme C (N1570 6.8.5p4) dit que

Une instruction d'itération provoque une instruction appelée corps de boucle être   exécuté à plusieurs reprises jusqu'à ce que l'expression de contrôle se compare égale à   0

Donc, les expressions constantes pertinentes sont 1 == 0 et 2 == 0, qui évaluent à la fois int valeur 0. (Ces comparaisons sont implicites dans la sémantique du while boucle; ils n'existent pas en tant qu'expressions C réelles.)

Un compilateur pervers naïf pourrait générer un code différent pour les deux constructions. Par exemple, pour le premier, il pourrait générer une boucle infinie inconditionnelle (traitement 1 comme cas particulier), et pour le second, il pourrait générer une comparaison explicite de l'exécution équivalente à 2 != 0. Mais je n'ai jamais rencontré un compilateur C qui se comporterait de cette façon, et je doute sérieusement qu'un tel compilateur existe.

La plupart des compilateurs (je suis tenté de dire que tous les compilateurs de qualité production) ont des options pour demander des optimisations supplémentaires. Avec une telle option, il est encore moins probable que n'importe quel compilateur génère un code différent pour les deux formes.

Si votre compilateur génère un code différent pour les deux constructions, vérifiez d'abord si les différentes séquences de code ont des performances différentes. Si c'est le cas, essayez de recompiler avec une option d'optimisation (si disponible). Si elles diffèrent encore, envoyez un rapport de bogue au fournisseur du compilateur. Ce n'est pas (forcément) un bug dans le sens d'un défaut de se conformer à la norme C, mais c'est presque certainement un problème qui devrait être corrigé.

Bottom line: while (1) et while(2)  presque certainement avoir la même performance. Ils ont exactement la même sémantique, et il n'y a aucune raison pour que le compilateur ne génère pas de code identique.

Et bien qu'il soit parfaitement légal qu'un compilateur génère un code plus rapide pour while(1) que pour while(2), il est également légal pour un compilateur de générer un code plus rapide pour while(1) que pour une autre occurrence de while(1) dans le même programme.

(Il y a une autre question implicite dans celle que vous avez posée: Comment traitez-vous avec un interviewer qui insiste sur un point technique incorrect? Ce serait probablement une bonne question pour le site du lieu de travail).


149
2017-07-21 00:35



Attends une minute. L'interviewer, ressemblait-il à ce type?

enter image description here

C'est assez mauvais que l'intervieweur lui-même a échoué cette interview, Et si d'autres programmeurs de cette entreprise avaient "passé" ce test?

Évaluer les énoncés 1 == 0 et 2 == 0  devrait être également rapide. nous pourrait imaginer implémentations de compilateur pauvres où l'un pourrait être plus rapide que l'autre. Mais il n'y a pas bien raison pour laquelle on devrait être plus rapide que l'autre.

Même s'il existe une circonstance obscure où la revendication serait vraie, les programmeurs ne devraient pas être évalués sur la base de la connaissance de trivial obscure (et dans ce cas, effrayant). Ne vous inquiétez pas pour cette interview, le mieux est de partir.

Avertissement: Ce n'est pas un dessin animé original de Dilbert. Ceci est simplement un écraser.


129
2017-07-24 18:31



Votre explication est correcte. Cela semble être une question qui teste votre confiance en soi en plus des connaissances techniques.

Au fait, si vous avez répondu

Les deux morceaux de code sont tout aussi rapides, car les deux prennent un temps infini à compléter

l'intervieweur dirait

Mais while (1) peut faire plus d'itérations par seconde; pouvez-vous expliquer pourquoi? (Ceci est un non-sens, tester votre confiance à nouveau)

Donc, en répondant comme vous l'avez fait, vous avez économisé du temps que vous auriez perdu en discutant de cette mauvaise question.


Voici un exemple de code généré par le compilateur sur mon système (MS Visual Studio 2012), avec les optimisations désactivées:

yyy:
    xor eax, eax
    cmp eax, 1     (or 2, depending on your code)
    je xxx
    jmp yyy
xxx:
    ...

Avec les optimisations activées:

xxx:
    jmp xxx

Donc le code généré est exactement le même, au moins avec un compilateur optimisant.


75
2017-07-20 07:59



L'explication la plus probable de la question est que l'intervieweur pense que le processeur vérifie les bits individuels des nombres, un par un, jusqu'à ce qu'il atteigne une valeur non nulle:

1 = 00000001
2 = 00000010

Si le "est zéro?" l'algorithme commence à partir du côté droit du nombre et doit vérifier chaque bit jusqu'à ce qu'il atteigne un bit non nul, le while(1) { } boucle devrait vérifier deux fois plus de bits par itération que le while(2) { } boucle.

Cela nécessite un très mauvais modèle mental du fonctionnement des ordinateurs, mais il a sa propre logique interne. Une façon de vérifier serait de demander si while(-1) { } ou while(3) { } serait aussi rapide, ou si while(32) { } serait encore plus lent.


58
2017-07-21 14:41



Bien sûr, je ne connais pas les intentions réelles de ce manager, mais je propose un point de vue complètement différent: Lors de l'embauche d'un nouveau membre dans une équipe, il est utile de savoir comment il réagit aux situations de conflit.

Ils vous ont conduit dans un conflit. Si cela est vrai, ils sont intelligents et la question était bonne. Pour certaines industries, comme les banques, l'envoi de votre problème à Stack Overflow pourrait être une raison de refus.

Mais bien sûr je ne sais pas, je propose juste une option.


32
2017-07-22 03:17