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, car l'expression à l'intérieur whiledevrait finalement être évaluée à trueou false. Dans ce cas, les deux évaluent trueet il n'y a pas d'instructions conditionnelles supplémentaires dans la whilecondition. Ainsi, les deux auront la même vitesse d'exécution et je préfère while (1).

Mais l'intervieweur 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 aussi: "for (;;)" est-il plus rapide que "while (TRUE)"? Sinon, pourquoi les gens l'utilisent-ils?

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 pour l'assemblage à 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'assembly 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'assembly généré (à l'aide gcc main.c -S -masm=inteld'un indicateur 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 -O2et -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'assembly 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 très bien lire l'assemblage, mais c'est évidemment une boucle inconditionnelle. L' jmpinstruction réinitialise inconditionnellement le programme sur l' .L2étiquette sans même comparer une valeur par rapport à true, et bien sûr le fait immédiatement à nouveau jusqu'à ce que le programme soit en quelque sorte terminé. Cela correspond directement au code C / C ++:

L2:
    goto L2;

Éditer:

Chose intéressante, même sans optimisation , 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 à mon grand étonnement:

#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 xet effectuent 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, au niveau -O1et au -dessus, ils produisent tous les deux le même assemblage que les exemples précédents (un jmpretour inconditionnel à l'étiquette précédente).

TL; DR

Sous GCC, les différentes boucles sont compilées en assemblage identique. Le compilateur évalue les valeurs constantes et ne prend pas la peine d'effectuer une 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 doit être suffisamment intelligent pour optimiser ces cas triviaux. Les programmeurs ne devraient pas perdre leur temps à y penser dans la grande majorité des cas.

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

Si je vois while(2), je vais probablement m'arrêter sur mes traces et essayer de comprendre pourquoi l'auteur n'a pas écrit while(1). Le doigt de l'auteur a-t-il glissé sur le clavier? Les responsables de cette base de code utilisent-ils while(n)comme un mécanisme de commentaire obscur pour rendre les boucles différentes? Est-ce une solution de contournement grossière pour un avertissement fallacieux dans un outil d'analyse statique cassé? Ou est-ce un indice que je lis le code généré? S'agit-il d'un bogue résultant d'une recherche et d'un remplacement non judicieux, d'une mauvaise fusion ou d'un rayon cosmique? Peut-être que cette ligne de code est censée faire quelque chose de radicalement différent. Peut-être que c'était censé lire while(w)ou while(x2). Je ferais mieux de trouver l'auteur dans l'historique du fichier et de leur envoyer un e-mail "WTF" ... et maintenant j'ai rompu mon contexte mental.while(2)while(1) aurait pris une fraction de seconde!

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

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

En ce qui concerne la définition du langage, la machine abstraite while (1) évalue la constante entière 1et while (2)évalue la constante entière 2; dans les deux cas, le résultat est comparé à zéro. La norme de langage ne dit absolument rien sur les performances relatives 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 formulaires, au moins lorsqu'il est compilé sans demander d'optimisation.

En revanche, les compilateurs C doivent absolument évaluer certaines expressions constantes au moment de la compilation, lorsqu'elles apparaissent dans des contextes qui nécessitent 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 2+2jusqu'au moment de l'exécution. Puisqu'un compilateur doit avoir la capacité d'évaluer des expressions constantes au moment de la compilation, il n'y a aucune bonne raison pour qu'il ne profite pas de cette capacité même si elle n'est pas requise.

La norme C ( N1570 6.8.5p4) dit que

Une instruction d'itération provoque l' exécution répétée d' une instruction appelée corps de boucle jusqu'à ce que l'expression de contrôle soit égale à 0.

Ainsi, les expressions constantes pertinentes sont 1 == 0et 2 == 0, toutes deux évaluées à la intvaleur 0. (Ces comparaisons sont implicites dans la sémantique de la whileboucle; elles n'existent pas en tant qu'expressions C réelles.)

Un compilateur perversement 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 (traitée 1comme un cas spécial), et pour le second, il pourrait générer une comparaison d'exécution explicite équivalente à 2 != 0. Mais je n'ai jamais rencontré de compilateur C qui se comporterait réellement 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 qu'un compilateur génère du code différent pour les deux formulaires.

Si votre compilateur génère un code différent pour les deux constructions, vérifiez d'abord si les séquences de code différentes ont réellement des performances différentes. Si tel est le cas, essayez à nouveau de compiler avec une option d'optimisation (si disponible). S'ils diffèrent toujours, soumettez un rapport de bogue au fournisseur du compilateur. Ce n'est pas (nécessairement) un bug dans le sens d'une non-conformité à la norme C, mais c'est presque certainement un problème qui devrait être corrigé.

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

Et bien qu'il soit parfaitement légal pour un compilateur de générer du code plus rapide pour while(1)que pour while(2), il est tout aussi légal pour un compilateur de générer du code plus rapide 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 gérez-vous un enquêteur qui insiste sur un point technique incorrect. Ce serait probablement une bonne question pour le site Workplace ).

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

Il est déjà assez grave que l'intervieweur lui-même n'ait pas réussi cette interview, et si d'autres programmeurs de cette entreprise ont "réussi" ce test?

Non. Évaluer les déclarations 1 == 0et 2 == 0 devrait être tout aussi rapide. Nous pourrions imaginer de mauvaises implémentations de compilateur où l'une pourrait être plus rapide que l'autre. Mais il n'y a aucune bonne raison pour que l'un soit plus rapide que l'autre.

Même s'il y a une circonstance obscure où l'affirmation serait vraie, les programmeurs ne devraient pas être évalués sur la base de la connaissance de futilités obscures (et dans ce cas, effrayantes). Ne vous inquiétez pas de cette interview, la meilleure chose à faire ici est de vous éloigner.

Avertissement: Ce n'est PAS une bande dessinée originale de Dilbert. Ce n'est qu'un mashup .

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

Au fait, si vous avez répondu

Les deux morceaux de code sont également rapides, car les deux prennent un temps infini pour terminer

l'intervieweur dirait

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

Donc, en répondant comme vous l'avez fait, vous avez gagné du temps que vous perdriez autrement à discuter 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

Le code généré est donc exactement le même, au moins avec un compilateur d'optimisation.

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 à droite du nombre et doit vérifier chaque bit jusqu'à ce qu'il atteigne un bit différent de zéro, la while(1) { }boucle devrait vérifier deux fois plus de bits par itération que la while(2) { }boucle.

Cela nécessite un modèle mental très erroné 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 tout aussi rapide, ou si ce while(32) { }serait encore plus lent .

Bien sûr, je ne connais pas les véritables intentions de ce manager, mais je propose une vision complètement différente: 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 au conflit. Si c'est vrai, ils sont intelligents et la question était bonne. Pour certaines industries, comme la banque, la publication de votre problème dans Stack Overflow peut être une raison de rejet.

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

Je pense que l'indice se trouve dans "demandé par un cadre supérieur". Il est évident que cette personne a cessé de programmer lorsqu'elle est devenue gestionnaire, puis il lui a fallu plusieurs années pour devenir cadre supérieur. Je n'ai jamais perdu d'intérêt pour la programmation, mais je n'ai jamais écrit de ligne depuis ces jours. Donc, sa référence n'est pas "n'importe quel compilateur décent", comme le mentionnent certaines réponses, mais "le compilateur avec lequel cette personne a travaillé il y a 20-30 ans".

À cette époque, les programmeurs passaient un pourcentage considérable de leur temps à essayer diverses méthodes pour rendre leur code plus rapide et plus efficace, car le temps CPU du «mini-ordinateur central» était si précieux. Tout comme les gens qui écrivent des compilateurs. Je suppose que le seul et unique compilateur que sa société a rendu disponible à ce moment-là a été optimisé sur la base des `` déclarations fréquemment rencontrées qui peuvent être optimisées '' et a pris un peu de raccourci lors de la rencontre (1) et a tout évalué sinon, y compris un certain temps (2). Une telle expérience pourrait expliquer sa position et sa confiance en elle.

La meilleure approche pour vous embaucher est probablement celle qui permet au cadre supérieur de s'emballer et de vous faire une conférence de 2 à 3 minutes sur "le bon vieux temps de la programmation" avant de le conduire en douceur vers le sujet de l'entretien suivant. (Un bon timing est important ici - trop rapide et vous interrompez l'histoire - trop lent et vous êtes étiqueté comme quelqu'un avec une concentration insuffisante). Dites-lui à la fin de l'entretien que vous seriez très intéressé à en savoir plus sur ce sujet.

Vous auriez dû lui demander comment il en est arrivé à cette conclusion. Sous n'importe quel compilateur décent, les deux compilent les mêmes instructions asm. Donc, il aurait aussi dû vous dire le compilateur pour commencer. Et même ainsi, vous devriez très bien connaître le compilateur et la plate-forme pour faire une supposition théorique. Et au final, cela n'a pas vraiment d'importance dans la pratique, car il existe d'autres facteurs externes comme la fragmentation de la mémoire ou la charge du système qui influenceront la boucle plus que ce détail.

Pour cette question, je dois ajouter que je me souviens que Doug Gwyn du comité C avait écrit que certains des premiers compilateurs C sans la passe de l'optimiseur génèreraient un test en assemblage pour le while(1)(comparé à celui for(;;)qui ne l'aurait pas).

Je répondrais à l'intervieweur en donnant cette note historique et en disant ensuite que même si je serais très surpris qu'un compilateur fasse cela, un compilateur pourrait avoir:

• sans optimiseur passer le compilateur générer un test pour les deux while(1)etwhile(2)
• avec l'optimizer pass, le compilateur est chargé d'optimiser (avec un saut inconditionnel) tout cela while(1)parce qu'ils sont considérés comme idiomatiques. Cela laisserait le while(2)test et ferait donc une différence de performances entre les deux.

J'ajouterais bien sûr à l'intervieweur que le fait de ne pas considérer while(1)et while(2)la même construction est un signe d'optimisation de faible qualité car ce sont des constructions équivalentes.

Une autre prise sur une telle question serait de voir si vous avez le courage de dire à votre manager qu'il a tort! Et avec quelle douceur vous pouvez le communiquer.

Mon premier réflexe aurait été de générer une sortie d'assembly pour montrer au gestionnaire que tout compilateur décent devrait s'en occuper, et si ce n'est pas le cas, vous soumettrez le prochain patch pour cela :)

Voir autant de personnes se plonger dans ce problème montre exactement pourquoi cela pourrait très bien être un test pour voir à quelle vitesse vous voulez micro-optimiser les choses.

Ma réponse serait; cela n'a pas beaucoup d'importance, je me concentre plutôt sur le problème commercial que nous résolvons. Après tout, c'est pour ça que je vais être payé.

De plus, j'opterais pour while(1) {}car c'est plus courant et les autres coéquipiers n'auraient pas besoin de passer du temps pour comprendre pourquoi quelqu'un irait pour un nombre supérieur à 1.

Maintenant, écrivez du code. ;-)

Si vous êtes préoccupé par l'optimisation, vous devez utiliser

for (;;)

car cela n'a pas de tests. (mode cynique)

Il me semble que c'est l'une de ces questions d'entrevue comportementale masquée comme une question technique. Certaines entreprises le font - elles poseront une question technique qui devrait être assez facile à répondre pour tout programmeur compétent, mais lorsque l'enquêté donne la bonne réponse, l'intervieweur leur dira qu'ils ont tort.

L'entreprise souhaite savoir comment vous allez réagir dans cette situation. Vous asseyez-vous tranquillement et n'insistez pas pour que votre réponse soit correcte, à cause du doute de soi ou de la peur de déranger l'intervieweur? Ou êtes-vous prêt à défier une personne en autorité dont vous savez qu'elle a tort? Ils veulent voir si vous êtes prêt à défendre vos convictions et si vous pouvez le faire avec tact et respect.

J'avais l'habitude de programmer le code C et l'assembly lorsque ce genre de non-sens aurait pu faire une différence. Quand cela a fait une différence, nous l'avons écrit à l'Assemblée.

Si on m'avait posé cette question, j'aurais répété la célèbre citation de Donald Knuth de 1974 sur l'optimisation prématurée et je me serais promené si l'intervieweur ne riait pas et ne continuait pas.

Peut-être que l'intervieweur a posé intentionnellement une question aussi stupide et voulait que vous fassiez trois remarques:

1. Raisonnement de base. Les deux boucles sont infinies, il est difficile de parler de performances.
2. Connaissance des niveaux d'optimisation. Il voulait vous entendre si vous laissez le compilateur faire une optimisation pour vous, cela optimiserait la condition, surtout si le bloc n'était pas vide.
3. Connaissance de l'architecture des microprocesseurs. La plupart des architectures ont une instruction CPU spéciale pour la comparaison avec 0 (bien que pas nécessairement plus rapide).

Voici un problème: si vous écrivez réellement un programme et mesurez sa vitesse, la vitesse des deux boucles pourrait être différente! Pour une comparaison raisonnable:

unsigned long i = 0;
while (1) { if (++i == 1000000000) break; }

unsigned long i = 0;
while (2) { if (++i == 1000000000) break; }

avec du code ajouté qui imprime l'heure, un effet aléatoire comme la position de la boucle dans une ou deux lignes de cache pourrait faire la différence. Une boucle peut, par pur hasard, se trouver entièrement dans une ligne de cache, ou au début d'une ligne de cache, ou elle peut chevaucher deux lignes de cache. Et par conséquent, tout ce que l'enquêteur prétend être le plus rapide pourrait être le plus rapide - par coïncidence.

Pire scénario: un compilateur d'optimisation ne comprend pas ce que fait la boucle, mais détermine que les valeurs produites lorsque la deuxième boucle est exécutée sont les mêmes que celles produites par la première. Et générez du code complet pour la première boucle, mais pas pour la seconde.

Ils sont tous deux égaux - les mêmes.

Selon les spécifications, tout ce qui n'est pas 0 est considéré comme vrai, donc même sans aucune optimisation, et un bon compilateur ne générera aucun code pour while (1) ou while (2). Le compilateur générerait une simple vérification != 0.

À en juger par la quantité de temps et d'efforts que les gens ont passé à tester, prouver et répondre à cette question très simple, je dirais que les deux ont été très lents en posant la question.

Et donc pour y consacrer encore plus de temps ...

"while (2)" est ridicule, car,

"while (1)" et "while (true)" sont historiquement utilisés pour créer une boucle infinie qui s'attend à ce que "break" soit appelé à un certain stade à l'intérieur de la boucle en fonction d'une condition qui se produira certainement.

Le "1" est simplement là pour toujours être évalué comme vrai et donc, dire "while (2)" est à peu près aussi idiot que dire "while (1 + 1 == 2)" qui sera également évalué comme vrai.

Et si vous voulez être complètement idiot, utilisez simplement: -

while (1 + 5 - 2 - (1 * 3) == 0.5 - 4 + ((9 * 2) / 4)) {
    if (succeed())
        break;
}

J'aimerais penser que votre codeur a fait une faute de frappe qui n'a pas affecté le fonctionnement du code, mais s'il a intentionnellement utilisé le "2" juste pour être bizarre, limogez-le avant qu'il ne mette bizarre tout le long de votre code, ce qui le rend difficile à lire et travailler avec.

Cela dépend du compilateur.

S'il optimise le code ou s'il évalue 1 et 2 à vrai avec le même nombre d'instructions pour un ensemble d'instructions particulier, la vitesse d'exécution sera la même.

Dans des cas réels, il sera toujours aussi rapide, mais il serait possible d'imaginer un compilateur particulier et un système particulier lorsque cela serait évalué différemment.

Je veux dire: ce n'est pas vraiment une question liée à la langue (C).

Étant donné que les personnes cherchant à répondre à cette question souhaitent la boucle la plus rapide, j'aurais répondu que les deux se compilent également dans le même code d'assemblage, comme indiqué dans les autres réponses. Néanmoins, vous pouvez suggérer à l'intervieweur d'utiliser le «déroulement de boucle»; une boucle do {} while au lieu de la boucle while.

Attention: vous devez vous assurer que la boucle s'exécute au moins toujours une fois .

La boucle doit avoir une condition de rupture à l'intérieur.

Aussi pour ce type de boucle, je préférerais personnellement l'utilisation de do {} while (42) car n'importe quel entier, sauf 0, ferait le travail.

La réponse évidente est: comme publié, les deux fragments exécuteraient une boucle infinie également occupée, ce qui rend le programme infiniment lent .

Bien que la redéfinition des mots clés C en tant que macros aurait techniquement un comportement indéfini, c'est la seule façon dont je puisse penser pour rendre l'un des fragments de code rapide: vous pouvez ajouter cette ligne au-dessus des 2 fragments:

#define while(x) sleep(x);

il sera en effet while(1)deux fois plus rapide (ou moitié moins lent) que while(2).

La seule raison pour laquelle je peux penser que le while(2)serait plus lent est:

1. Le code optimise la boucle pour

   cmp eax, 2

2. Lorsque la soustraction se produit, vous soustrayez essentiellement

   une. 00000000 - 00000010 cmp eax, 2

   au lieu de

   b. 00000000 - 00000001 cmp eax, 1

cmpdéfinit uniquement des indicateurs et ne définit pas de résultat. Donc, sur les bits les moins significatifs, nous savons si nous devons emprunter ou non avec b . Alors qu'avec un, vous devez effectuer deux soustractions avant d'obtenir un emprunt.