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.

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

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.

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).

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

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.

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 <.

À 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 .

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.

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.

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.

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.

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.

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.

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