Est <plus rapide que <=?

1574

Est if( a < 901 )plus rapide que if( a <= 900 ).

Pas exactement comme dans cet exemple simple, mais il y a de légères modifications des performances sur le code complexe de boucle. Je suppose que cela doit faire quelque chose avec le code machine généré au cas où c'est même vrai.

snoopy
la source
153
Je ne vois aucune raison de clore cette question (et surtout de ne pas la supprimer, comme les votes le montrent actuellement) compte tenu de son importance historique, de la qualité de la réponse et du fait que les autres principales questions relatives aux performances restent ouvertes. Il doit tout au plus être verrouillé. De plus, même si la question elle-même est mal informée / naïve, le fait qu'elle soit apparue dans un livre signifie que la désinformation originale existe quelque part dans des sources "crédibles", et cette question est donc constructive en ce qu'elle permet de clarifier cela.
Jason C
32
Vous ne nous avez jamais dit de quel livre vous parlez.
Jonathon Reinhart
160
La <saisie est deux fois plus rapide que la saisie <=.
Deqing
6
C'était vrai sur le 8086.
Joshua
7
Le nombre de votes positifs montre clairement qu'il y a des centaines de personnes qui suroptimisent fortement.
m93a

Réponses:

1704

Non, ce ne sera pas plus rapide sur la plupart des architectures. Vous n'avez pas spécifié, mais sur x86, toutes les comparaisons intégrales seront généralement implémentées dans deux instructions machine:

  • Une instruction testou cmp, qui définitEFLAGS
  • Et une Jccinstruction (jump) , selon le type de comparaison (et la disposition du code):
    • jne - Saut si différent -> ZF = 0
    • jz - Saut si zéro (égal) -> ZF = 1
    • jg - Saut si plus grand -> ZF = 0 and SF = OF
    • (etc...)

Exemple (édité par souci de concision) Compilé avec$ gcc -m32 -S -masm=intel test.c

    if (a < b) {
        // Do something 1
    }

Compile vers:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jge     .L2                          ; jump if a is >= b
    ; Do something 1
.L2:

Et

    if (a <= b) {
        // Do something 2
    }

Compile vers:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jg      .L5                          ; jump if a is > b
    ; Do something 2
.L5:

La seule différence entre les deux est donc jgune jgeinstruction par rapport à une instruction. Les deux prendront le même temps.


Je voudrais répondre au commentaire que rien n'indique que les différentes instructions de saut prennent le même temps. Celui-ci est un peu difficile à répondre, mais voici ce que je peux donner: dans la référence du jeu d'instructions Intel , ils sont tous regroupés sous une instruction commune, Jcc(sauter si la condition est remplie). Le même regroupement est effectué dans le Manuel de référence de l' optimisation , à l'annexe C. Latence et débit.

Latence - Le nombre de cycles d'horloge requis pour que le noyau d'exécution termine l'exécution de tous les μops qui forment une instruction.

Débit - Le nombre de cycles d'horloge requis pour attendre avant que les ports d'émission ne soient libres d'accepter à nouveau la même instruction. Pour de nombreuses instructions, le débit d'une instruction peut être nettement inférieur à sa latence

Les valeurs de Jccsont:

      Latency   Throughput
Jcc     N/A        0.5

avec la note de bas de page suivante Jcc:

7) La sélection des instructions de saut conditionnel doit être basée sur la recommandation de la section Section 3.4.1, «Optimisation de la prédiction des branches», pour améliorer la prévisibilité des branches. Lorsque les branches sont prédites avec succès, la latence de jccest effectivement nulle.

Ainsi, rien dans les documents Intel ne traite jamais une Jccinstruction différemment des autres.

Si l'on pense aux circuits réels utilisés pour mettre en œuvre les instructions, on peut supposer qu'il y aurait de simples portes ET / OU sur les différents bits EFLAGSpour déterminer si les conditions sont remplies. Il n'y a donc aucune raison pour qu'une instruction testant deux bits prenne plus ou moins de temps qu'une seule testant un (Ignorer le délai de propagation de la porte, qui est bien inférieur à la période d'horloge).


Modifier: virgule flottante

Cela vaut également pour la virgule flottante x87: (à peu près le même code que ci-dessus, mais avec doubleau lieu de int.)

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; Compare ST(0) and ST(1), and set CF, PF, ZF in EFLAGS
        fstp    st(0)
        seta    al                     ; Set al if above (CF=0 and ZF=0).
        test    al, al
        je      .L2
        ; Do something 1
.L2:

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; (same thing as above)
        fstp    st(0)
        setae   al                     ; Set al if above or equal (CF=0).
        test    al, al
        je      .L5
        ; Do something 2
.L5:
        leave
        ret
Jonathon Reinhart
la source
239
@Dyppl en fait jget jnlesont la même instruction, 7F:-)
Jonathon Reinhart
17
Sans oublier que l'optimiseur peut modifier le code si en effet une option est plus rapide que l'autre.
Elazar Leibovich
3
ce n'est pas parce que quelque chose aboutit à la même quantité d'instructions que la durée totale de l'exécution de toutes ces instructions sera la même. En fait, plus d'instructions pourraient être exécutées plus rapidement. Les instructions par cycle ne sont pas un nombre fixe, elles varient en fonction des instructions.
jontejj
22
@jontejj J'en suis très conscient. Avez-vous même lu ma réponse? Je n'ai rien dit sur le même nombre d'instructions, j'ai déclaré qu'elles sont compilées essentiellement pour exactement les mêmes instructions , sauf qu'une instruction de saut regarde un drapeau, et l'autre instruction de saut regarde deux drapeaux. Je pense avoir fourni des preuves plus qu'adéquates pour montrer qu'elles sont sémantiquement identiques.
Jonathon Reinhart
2
@jontejj Vous soulevez un très bon point. Pour autant de visibilité que cette réponse, je devrais probablement lui donner un peu de nettoyage. Merci pour les commentaires.
Jonathon Reinhart
593

Historiquement (nous parlons des années 1980 et du début des années 1990), il y avait certaines architectures dans lesquelles cela était vrai. Le problème racine est que la comparaison d'entiers est implémentée de manière inhérente via des soustractions d'entiers. Cela donne lieu aux cas suivants.

Comparison     Subtraction
----------     -----------
A < B      --> A - B < 0
A = B      --> A - B = 0
A > B      --> A - B > 0

Maintenant, lorsque A < Bla soustraction doit emprunter un bit élevé pour que la soustraction soit correcte, tout comme vous effectuez et empruntez en ajoutant et en soustrayant à la main. Ce bit "emprunté" était généralement appelé bit de retenue et pouvait être testé par une instruction de branchement. Un deuxième bit appelé bit zéro serait défini si la soustraction était identique à zéro, ce qui impliquait l'égalité.

Il y avait généralement au moins deux instructions de branchement conditionnel, une à branchement sur le bit de retenue et une sur le bit zéro.

Maintenant, pour aller au cœur du problème, développons le tableau précédent pour inclure les résultats de report et de bit zéro.

Comparison     Subtraction  Carry Bit  Zero Bit
----------     -----------  ---------  --------
A < B      --> A - B < 0    0          0
A = B      --> A - B = 0    1          1
A > B      --> A - B > 0    1          0

Ainsi, l'implémentation d'une branche pour A < Bpeut être effectuée dans une instruction, car le bit de report est clair uniquement dans ce cas, c'est-à-dire,

;; Implementation of "if (A < B) goto address;"
cmp  A, B          ;; compare A to B
bcz  address       ;; Branch if Carry is Zero to the new address

Mais, si nous voulons faire une comparaison inférieure ou égale, nous devons effectuer une vérification supplémentaire de l'indicateur zéro pour attraper le cas de l'égalité.

;; Implementation of "if (A <= B) goto address;"
cmp A, B           ;; compare A to B
bcz address        ;; branch if A < B
bzs address        ;; also, Branch if the Zero bit is Set

Ainsi, sur certaines machines, l'utilisation d'une comparaison "inférieure à" peut enregistrer une instruction machine . C'était pertinent à l'ère de la vitesse du processeur sous-mégahertz et des rapports de vitesse 1: 1 CPU-mémoire, mais c'est presque totalement hors de propos aujourd'hui.

Lucas
la source
10
De plus, des architectures comme x86 implémentent des instructions comme jge, qui testent à la fois les drapeaux zéro et signe / report.
greyfade
3
Même si c'est vrai pour une architecture donnée. Quelles sont les chances qu'aucun des rédacteurs du compilateur n'ait jamais remarqué et ajouté une optimisation pour remplacer le plus lent par le plus rapide?
Jon Hanna
8
Cela est vrai sur le 8080. Il a des instructions pour sauter sur zéro et sauter sur moins, mais aucun qui peut tester les deux simultanément.
4
C'est également le cas sur la famille de processeurs 6502 et 65816, qui s'étend également au Motorola 68HC11 / 12.
Lucas
31
Même sur le 8080 un <=test peut être mis en œuvre dans une instruction avec permutation des opérandes et de test pour not <(équivalent à >=) Ceci est le désiré <=avec opérandes troqué: cmp B,A; bcs addr. C'est la raison pour laquelle ce test a été omis par Intel, ils l'ont considéré comme redondant et vous ne pouviez pas vous permettre des instructions redondantes à ces moments :-)
Gunther Piez
92

En supposant que nous parlons de types d'entiers internes, il n'y a aucun moyen possible que l'un soit plus rapide que l'autre. Ils sont évidemment sémantiquement identiques. Ils demandent tous deux au compilateur de faire exactement la même chose. Seul un compilateur horriblement cassé générerait un code inférieur pour l'un d'entre eux.

S'il y avait une plate-forme où <était plus rapide que <=pour les types entiers simples, le compilateur devrait toujours se convertir <=en <constantes. Tout compilateur qui ne le serait pas serait juste un mauvais compilateur (pour cette plate-forme).

David Schwartz
la source
6
+1 Je suis d'accord. Ni <ni <=avoir de vitesse jusqu'à ce que le compilateur décide quelle vitesse ils auront. Ceci est une optimisation très simple pour les compilateurs quand on considère qu'ils effectuent généralement déjà l' optimisation de code mort, l' optimisation d'appel queue, levage en boucle (et le déroulement, à l' occasion), parallélisation automatique des différentes boucles, etc ... Pourquoi perdre du temps méditée Optimisations prématurés ? Lancez un prototype, profilez-le pour déterminer où se trouvent les optimisations les plus significatives, effectuez ces optimisations par ordre d'importance et profilez à nouveau le long du chemin pour mesurer les progrès ...
autistique
Il y a encore des cas limites où une comparaison ayant une valeur constante pourrait être plus lente sous <=, par exemple, lorsque la transformation de (a < C)à (a <= C-1)(pour certaines constantes C) Cest plus difficile à coder dans le jeu d'instructions. Par exemple, un jeu d'instructions peut représenter des constantes signées de -127 à 128 sous une forme compacte dans les comparaisons, mais les constantes en dehors de cette plage doivent être chargées en utilisant soit un encodage plus long, plus lent, soit une autre instruction entièrement. Ainsi, une comparaison comme celle-ci (a < -127)peut ne pas avoir une transformation simple.
BeeOnRope
@BeeOnRope Le problème n'était pas de savoir si l'exécution d'opérations différentes en raison de la présence de constantes différentes pouvait affecter les performances, mais si l' expression de la même opération à l'aide de constantes différentes pouvait affecter les performances. Nous ne comparons donc a > 127pas a > 128parce que vous n'avez pas le choix, vous utilisez celui dont vous avez besoin. Nous comparons a > 127à a >= 128, qui ne peuvent pas nécessiter un encodage différent ou des instructions différentes car ils ont la même table de vérité. Tout encodage de l'un est également un encodage de l'autre.
David Schwartz
Je répondais de manière générale à votre déclaration selon laquelle "S'il y avait une plate-forme où [<= était plus lent], le compilateur devrait toujours se convertir <=en <for constants". Pour autant que je sache, cette transformation implique de changer la constante. Par exemple, a <= 42est compilé car a < 43parce qu'il <est plus rapide. Dans certains cas extrêmes, une telle transformation ne serait pas fructueuse car la nouvelle constante peut nécessiter des instructions plus ou plus lentes. Bien sûr a > 127, ils a >= 128sont équivalents et un compilateur devrait coder les deux formes de la (même) manière la plus rapide, mais ce n'est pas incompatible avec ce que j'ai dit.
BeeOnRope
67

Je vois que ni l'un ni l'autre n'est plus rapide. Le compilateur génère le même code machine dans chaque condition avec une valeur différente.

if(a < 901)
cmpl  $900, -4(%rbp)
jg .L2

if(a <=901)
cmpl  $901, -4(%rbp)
jg .L3

Mon exemple ifvient de GCC sur la plate-forme x86_64 sous Linux.

Les auteurs de compilateurs sont des gens assez intelligents, et ils pensent à ces choses et à beaucoup d'autres que la plupart d'entre nous tiennent pour acquises.

J'ai remarqué que si ce n'est pas une constante, le même code machine est généré dans les deux cas.

int b;
if(a < b)
cmpl  -4(%rbp), %eax
jge   .L2

if(a <=b)
cmpl  -4(%rbp), %eax
jg .L3
Adrian Cornish
la source
9
Notez que cela est spécifique à x86.
Michael Petrotta
10
Je pense que vous devriez utiliser cela if(a <=900)pour démontrer qu'il génère exactement le même asm :)
Lipis
2
@AdrianCornish Désolé .. Je l'ai édité .. c'est plus ou moins pareil .. mais si vous changez le second if en <= 900 alors le code asm sera exactement le même :) C'est à peu près le même maintenant .. mais vous savoir .. pour le TOC :)
Lipis
3
@Boann Cela pourrait être réduit à if (vrai) et éliminé complètement.
Qsario
5
Personne n'a souligné que cette optimisation ne s'applique qu'aux comparaisons constantes . Je peux garantir que cela ne se fera pas comme ceci pour comparer deux variables.
Jonathon Reinhart
51

Pour le code à virgule flottante, la comparaison <= peut en effet être plus lente (d'une instruction) même sur les architectures modernes. Voici la première fonction:

int compare_strict(double a, double b) { return a < b; }

Sur PowerPC, cela effectue d'abord une comparaison à virgule flottante (qui met à jour crle registre de conditions), puis déplace le registre de conditions vers un GPR, déplace le bit «comparé moins de» en place, puis revient. Il faut quatre instructions.

Considérez maintenant cette fonction à la place:

int compare_loose(double a, double b) { return a <= b; }

Cela nécessite le même travail que compare_strictci-dessus, mais maintenant il y a deux bits d'intérêt: "était inférieur à" et "était égal à". Cela nécessite une instruction supplémentaire ( cror- registre de condition OR au niveau du bit) pour combiner ces deux bits en un seul. Nécessite donc compare_loosecinq instructions, tandis quecompare_strict que quatre.

Vous pourriez penser que le compilateur pourrait optimiser la deuxième fonction comme ceci:

int compare_loose(double a, double b) { return ! (a > b); }

Cependant, cela ne traitera pas correctement les NaN. NaN1 <= NaN2et NaN1 > NaN2doivent à la fois évaluer faux.

ridicule_fish
la source
Heureusement, cela ne fonctionne pas comme ça sur x86 (x87). fucomipdéfinit ZF et CF.
Jonathon Reinhart
3
@JonathonReinhart: Je pense que vous vous méprenez sur ce que fait le PowerPC - le registre de condition cr est l'équivalent de drapeaux comme ZFet CFsur le x86. (Bien que le CR soit plus flexible.) Ce dont l'affiche parle, c'est de déplacer le résultat vers un GPR: qui prend deux instructions sur PowerPC, mais x86 a une instruction de déplacement conditionnel.
Dietrich Epp
@DietrichEpp Ce que je voulais ajouter après ma déclaration était: que vous pouvez ensuite immédiatement sauter en fonction de la valeur d'EFLAGS. Excusez-moi de ne pas avoir été clair.
Jonathon Reinhart
1
@JonathonReinhart: Oui, et vous pouvez également sauter immédiatement en fonction de la valeur du CR. La réponse ne parle pas de sauter, d'où proviennent les instructions supplémentaires.
Dietrich Epp
34

Peut-être que l'auteur de ce livre sans nom a lu a > 0plus rapidement a >= 1et pense que cela est vrai universellement.

Mais c'est parce qu'un 0est impliqué (car CMPpeut, selon l'architecture, remplacé par exemple par OR) et non à cause du <.

glglgl
la source
1
Bien sûr, dans une version "debug", mais cela prendrait un mauvais compilateur pour (a >= 1)fonctionner plus lentement que (a > 0), car le premier peut être trivialement transformé en ce dernier par l'optimiseur ..
BeeOnRope
2
@BeeOnRope Parfois, je suis surpris des choses compliquées qu'un optimiseur peut optimiser et des choses faciles qu'il ne parvient pas à faire.
glglgl
1
En effet, et cela vaut toujours la peine de vérifier la sortie asm pour les très rares fonctions où cela importerait. Cela dit, la transformation ci-dessus est très basique et a été effectuée même dans des compilateurs simples pendant des décennies.
BeeOnRope
32

À tout le moins, si cela était vrai, un compilateur pourrait optimiser trivialement un <= b à! (A> b), et donc même si la comparaison elle-même était en fait plus lente, avec tout sauf le compilateur le plus naïf, vous ne remarqueriez pas de différence .

Eliot Ball
la source
Pourquoi! (A> b) est une version optimisée de a <= b. N'est-ce pas! (A> b) 2 opérations en une?
Abhishek Singh
6
@AbhishekSingh NOTvient d'être créé par une autre instruction ( jevs. jne)
Pavel Gatnar
15

Ils ont la même vitesse. Peut-être que dans une architecture spéciale, ce qu'il a dit est juste, mais dans la famille x86 au moins, je sais que ce sont les mêmes. Parce que pour ce faire, le CPU fera une soustraction (a - b) puis vérifiera les drapeaux du registre des drapeaux. Deux bits de ce registre sont appelés ZF (drapeau zéro) et SF (drapeau de signe), et cela se fait en un cycle, car il le fera avec une opération de masque.

Masoud
la source
14

Cela dépendrait fortement de l'architecture sous-jacente à laquelle le C est compilé. Certains processeurs et architectures peuvent avoir des instructions explicites égales ou inférieures et égales à, qui s'exécutent en différents nombres de cycles.

Ce serait assez inhabituel cependant, car le compilateur pourrait contourner cela, le rendant non pertinent.

Telgin
la source
1
SI il y avait une différence dans les cyles. 1) il ne serait pas détectable. 2) Tout compilateur digne de ce nom ferait déjà la transformation de la forme lente en forme plus rapide sans changer la signification du code. Donc, l'instruction résultante plantée serait identique.
Martin York
D'accord, ce serait une différence assez banale et idiote en tout cas. Certainement rien à mentionner dans un livre qui devrait être indépendant de la plateforme.
Telgin
@lttlrck: Je comprends. Ça m'a pris du temps (idiot). Non, ils ne sont pas détectables car il se passe tellement d'autres choses qui rendent leur mesure impossible. Le processeur cale / cache manque / signaux / échange de processus. Ainsi, dans une situation de système d'exploitation normal, les choses au niveau d'un cycle unique ne peuvent pas être physiquement mesurables. Si vous pouvez éliminer toutes ces interférences de vos mesures (exécutez-le sur une puce avec mémoire intégrée et sans système d'exploitation), vous avez toujours une granularité de vos minuteries à vous inquiéter, mais théoriquement, si vous l'exécutez assez longtemps, vous pouvez voir quelque chose.
Martin York
12

Réponse TL; DR

Pour la plupart des combinaisons d'architecture, de compilateur et de langage, ce ne sera pas plus rapide.

Réponse complète

D'autres réponses se sont concentrées sur l' architecture x86 , et je ne connais pas l' architecture ARM (que votre exemple d'assembleur semble être) assez bien pour commenter spécifiquement le code généré, mais ceci est un exemple de micro-optimisation qui est très architecture spécifique, et est aussi susceptible d’être une anti-optimisation qu’une optimisation .

En tant que tel, je dirais que ce type de micro-optimisation est un exemple de programmation culte du fret plutôt que de meilleures pratiques d'ingénierie logicielle.

Il y a probablement des architectures où c'est une optimisation, mais je connais au moins une architecture où le contraire peut être vrai. L' architecture vénérable de Transputer ne comportait que des instructions de code machine égales et supérieures ou égales à , donc toutes les comparaisons devaient être construites à partir de ces primitives.

Même alors, dans presque tous les cas, le compilateur pouvait ordonner les instructions d'évaluation de telle manière qu'en pratique, aucune comparaison n'avait aucun avantage sur aucune autre. Dans le pire des cas cependant, il peut être nécessaire d'ajouter une instruction inverse (REV) pour échanger les deux premiers éléments de la pile d'opérandes . Il s'agissait d'une instruction à un seul octet qui prenait un seul cycle à exécuter, donc avait le plus petit temps système possible.

Qu'une micro-optimisation comme celle-ci soit une optimisation ou une anti-optimisation dépend de l'architecture spécifique que vous utilisez, il est donc généralement une mauvaise idée de prendre l'habitude d'utiliser des micro-optimisations spécifiques à l'architecture, sinon vous pourriez instinctivement utilisez-en un quand il est inapproprié de le faire, et il semble que c'est exactement ce que préconise le livre que vous lisez.

Mark Booth
la source
6

Vous ne devriez pas être en mesure de remarquer la différence même s'il y en a. De plus, dans la pratique, vous devrez faire une condition supplémentaire a + 1ou a - 1faire tenir la condition à moins que vous n'utilisiez des constantes magiques, ce qui est une très mauvaise pratique par tous les moyens.

shinkou
la source
1
Quelle est la mauvaise pratique? Incrémenter ou décrémenter un compteur? Comment stockez-vous alors la notation d'index?
jcolebrand
5
Il signifie que si vous faites une comparaison de 2 types de variables. Bien sûr, c'est trivial si vous définissez la valeur d'une boucle ou quelque chose. Mais si vous avez x <= y, et y est inconnu, il serait plus lent de «l'optimiser» à x <y + 1
JustinDanielson
@JustinDanielson a accepté. Sans parler de laid, déroutant, etc.
Jonathon Reinhart
4

Vous pourriez dire que la ligne est correcte dans la plupart des langages de script, car le caractère supplémentaire entraîne un traitement de code légèrement plus lent. Cependant, comme la première réponse l'a souligné, cela ne devrait pas avoir d'effet en C ++, et tout ce qui est fait avec un langage de script n'est probablement pas préoccupé par l'optimisation.

Ecksters
la source
Je suis un peu en désaccord. Dans la programmation compétitive, les langages de script offrent souvent la solution la plus rapide à un problème, mais des techniques correctes (lire: optimisation) doivent être appliquées pour obtenir une solution correcte.
Tyler Crompton
3

Quand j'ai écrit cette réponse, je ne regardais que la question du titre sur <vs <= en général, pas l'exemple spécifique d'une constante a < 901 par rapport a <= 900. De nombreux compilateurs réduisent toujours l'amplitude des constantes en convertissant entre <et <=, par exemple parce que l'opérande immédiat x86 a un codage à 1 octet plus court pour -128..127.

Pour ARM et en particulier AArch64, le fait de pouvoir encoder en tant qu'immédiat dépend de pouvoir faire pivoter un champ étroit dans n'importe quelle position dans un mot. Donccmp w0, #0x00f000 serait donc encodable, alors que cmp w0, #0x00effffce ne l'est peut-être pas. Ainsi, la règle de comparaison plus petite par rapport à une constante de temps de compilation ne s'applique pas toujours à AArch64.


<vs. <= en général, y compris pour les conditions à variable d'exécution

En langage d'assemblage sur la plupart des machines, une comparaison pour <= a le même coût qu'une comparaison pour <. Cela s'applique que vous le branchiez, le booléeniez pour créer un entier 0/1 ou l'utilisiez comme prédicat pour une opération de sélection sans branche (comme x86 CMOV). Les autres réponses n'ont abordé que cette partie de la question.

Mais cette question concerne les opérateurs C ++, l' entrée de l'optimiseur. Normalement, ils sont tous deux aussi efficaces; les conseils du livre semblent totalement faux car les compilateurs peuvent toujours transformer la comparaison qu'ils implémentent en asm. Mais il y a au moins une exception où l'utilisation <=peut créer accidentellement quelque chose que le compilateur ne peut pas optimiser.

En tant que condition de boucle, il existe des cas où <=est qualitativement différent de <, lorsqu'il empêche le compilateur de prouver qu'une boucle n'est pas infinie. Cela peut faire une grande différence en désactivant la vectorisation automatique.

Le débordement non signé est bien défini comme un bouclage en base 2, contrairement au débordement signé (UB). Les compteurs de boucles signées sont généralement à l'abri de cela avec des compilateurs qui optimisent en fonction de l'UB de débordement signé qui ne se ++i <= sizeproduira pas toujours. ( Ce que tout programmeur C devrait savoir sur le comportement indéfini )

void foo(unsigned size) {
    unsigned upper_bound = size - 1;  // or any calculation that could produce UINT_MAX
    for(unsigned i=0 ; i <= upper_bound ; i++)
        ...

Les compilateurs ne peuvent optimiser que de manière à préserver le comportement (défini et légalement observable) de la source C ++ pour toutes les valeurs d'entrée possibles , à l'exception de celles qui conduisent à un comportement non défini.

(Un simple i <= size créerait également le problème, mais je pensais que calculer une limite supérieure était un exemple plus réaliste d'introduire accidentellement la possibilité d'une boucle infinie pour une entrée qui ne vous intéressait pas mais que le compilateur devait considérer.)

Dans ce cas, size=0conduit à upper_bound=UINT_MAX, et i <= UINT_MAXest toujours vrai. Cette boucle est donc infinie pour size=0, et le compilateur doit respecter cela même si vous, en tant que programmeur, n'avez probablement jamais l'intention de passer size = 0. Si le compilateur peut incorporer cette fonction dans un appelant où il peut prouver que size = 0 est impossible, alors grand, il peut optimiser comme il le pourrait pour i < size.

Asm like if(!size) skip the loop; do{...}while(--size);est un moyen normalement efficace d'optimiser une for( i<size )boucle, si la valeur réelle de in'est pas nécessaire à l'intérieur de la boucle ( pourquoi les boucles sont-elles toujours compilées dans le style "do ... while" (tail jump)? ).

Mais cela ne {} tout en ne peut pas être infini: si entré avec size==0, nous obtenons 2 ^ n itérations. (L' itération sur tous les entiers non signés dans une boucle for C permet d'exprimer une boucle sur tous les entiers non signés, y compris zéro, mais ce n'est pas facile sans un indicateur de report tel qu'il est dans asm.)

Le bouclage du compteur de boucles étant une possibilité, les compilateurs modernes «abandonnent» souvent et n'optimisent pas de manière aussi agressive.

Exemple: somme d'entiers de 1 à n

L' i <= nutilisation de la reconnaissance des idiomes de clang défait non signé qui optimise les sum(1 .. n)boucles avec une forme fermée basée sur la n * (n+1) / 2formule de Gauss .

unsigned sum_1_to_n_finite(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i < n+1 ; ++i)
        total += i;
    return total;
}

x86-64 asm de clang7.0 et gcc8.2 sur l'explorateur du compilateur Godbolt

 # clang7.0 -O3 closed-form
    cmp     edi, -1       # n passed in EDI: x86-64 System V calling convention
    je      .LBB1_1       # if (n == UINT_MAX) return 0;  // C++ loop runs 0 times
          # else fall through into the closed-form calc
    mov     ecx, edi         # zero-extend n into RCX
    lea     eax, [rdi - 1]   # n-1
    imul    rax, rcx         # n * (n-1)             # 64-bit
    shr     rax              # n * (n-1) / 2
    add     eax, edi         # n + (stuff / 2) = n * (n+1) / 2   # truncated to 32-bit
    ret          # computed without possible overflow of the product before right shifting
.LBB1_1:
    xor     eax, eax
    ret

Mais pour la version naïve, nous obtenons juste une boucle stupide de clang.

unsigned sum_1_to_n_naive(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i<=n ; ++i)
        total += i;
    return total;
}
# clang7.0 -O3
sum_1_to_n(unsigned int):
    xor     ecx, ecx           # i = 0
    xor     eax, eax           # retval = 0
.LBB0_1:                       # do {
    add     eax, ecx             # retval += i
    add     ecx, 1               # ++1
    cmp     ecx, edi
    jbe     .LBB0_1            # } while( i<n );
    ret

GCC n'utilise pas de forme fermée dans les deux cas, donc le choix de la condition de boucle ne lui fait pas vraiment de mal ; il vectorise automatiquement avec l'addition d'entiers SIMD, exécutant 4 ivaleurs en parallèle dans les éléments d'un registre XMM.

# "naive" inner loop
.L3:
    add     eax, 1       # do {
    paddd   xmm0, xmm1    # vect_total_4.6, vect_vec_iv_.5
    paddd   xmm1, xmm2    # vect_vec_iv_.5, tmp114
    cmp     edx, eax      # bnd.1, ivtmp.14     # bound and induction-variable tmp, I think.
    ja      .L3 #,       # }while( n > i )

 "finite" inner loop
  # before the loop:
  # xmm0 = 0 = totals
  # xmm1 = {0,1,2,3} = i
  # xmm2 = set1_epi32(4)
 .L13:                # do {
    add     eax, 1       # i++
    paddd   xmm0, xmm1    # total[0..3] += i[0..3]
    paddd   xmm1, xmm2    # i[0..3] += 4
    cmp     eax, edx
    jne     .L13      # }while( i != upper_limit );

     then horizontal sum xmm0
     and peeled cleanup for the last n%3 iterations, or something.

Il a également une boucle scalaire simple que je pense qu'il utilise pour les très petites net / ou pour le cas de la boucle infinie.

BTW, ces deux boucles gaspillent une instruction (et un uop sur les processeurs de la famille Sandybridge) sur la surcharge de boucle. sub eax,1/ jnzau lieu de add eax,1/ cmp / jcc serait plus efficace. 1 uop au lieu de 2 (après macro-fusion de sub / jcc ou cmp / jcc). Le code après les deux boucles écrit EAX sans condition, il n'utilise donc pas la valeur finale du compteur de boucles.

Peter Cordes
la source
Bel exemple artificiel. Qu'en est-il de votre autre commentaire sur un effet potentiel sur l'exécution hors service due à l'utilisation d'EFLAGS? Est-ce purement théorique ou peut-il arriver qu'un JB mène à un meilleur pipeline qu'un JBE?
rustyx
@rustyx: ai-je commenté quelque part sous une autre réponse? Les compilateurs n'émettront pas de code qui provoque des blocages de drapeau partiel, et certainement pas pour un C <ou <=. Mais bien sûr, test ecx,ecx/ bt eax, 3/ jbesautera si ZF est défini (ecx == 0), ou si CF est défini (bit 3 de EAX == 1), provoquant un blocage partiel des drapeaux sur la plupart des CPU parce que les drapeaux qu'il lit ne sont pas tous proviennent de la dernière instruction pour écrire des drapeaux. Sur la famille Sandybridge, il ne bloque pas, il suffit d'insérer un uop fusionnant. cmp/ testécrire tous les drapeaux, mais btlaisse ZF non modifié. felixcloutier.com/x86/bt
Peter Cordes
2

Seulement si les gens qui ont créé les ordinateurs sont mauvais avec la logique booléenne. Ce qu'ils ne devraient pas être.

Chaque comparaison (>= <= > < ) peut être effectuée à la même vitesse.

Ce que chaque comparaison est, c'est juste une soustraction (la différence) et voir si c'est positif / négatif.
(Si msbest défini, le nombre est négatif)

Comment vérifier a >= b? Sous a-b >= 0Vérifier si a-best positif.
Comment vérifier a <= b? Sous 0 <= b-aVérifier si b-aest positif.
Comment vérifier a < b? Sous a-b < 0Vérifier si a-best négatif.
Comment vérifier a > b? Sous 0 > b-aVérifier si b-aest négatif.

Autrement dit, l'ordinateur peut simplement faire cela sous le capot pour l'opération donnée:

a >= b== msb(a-b)==0
a <= b==msb(b-a)==0
a > b == msb(b-a)==1
a < b==msb(a-b)==1

et bien sûr l'ordinateur n'aurait pas vraiment besoin de faire le ==0ou==1 autre.
car ==0il pourrait simplement inverser msble circuit.

Quoi qu'il en soit, ils n'auraient certainement pas pu a >= bêtre calculés comme a>b || a==blol

Flaque
la source