Est-ce que <= est plus rapide que <= ?

Question

Est if (a < 901) plus vite que if (a <= 900) ?

Pas exactement comme dans cet exemple simple, mais il y a de légers changements de performance sur le code complexe de la boucle. Je suppose que cela a quelque chose à voir avec le code machine généré, au cas où ce serait vrai.

Answer 1

Non, il ne sera pas plus rapide sur la plupart des architectures. Vous ne l'avez pas précisé, mais sur x86, toutes les comparaisons intégrales seront typiquement implémentées en deux instructions machine :

• A test ou cmp qui définit EFLAGS
• Et un Jcc instruction (saut) en fonction du type de comparaison (et de la disposition du code) :
  • jne - Sauter si non égal --> ZF = 0
  • jz - Saut si zéro (égal) --> ZF = 1
  • jg - Sauter si plus grand --> ZF = 0 and SF = OF
  • (etc...)

---

Exemple (édité pour la brièveté) 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:

Donc la seule différence entre les deux est un jg par rapport à un jge l'instruction. Les deux prendront le même temps.

---

J'aimerais répondre au commentaire selon lequel rien n'indique que les différentes instructions de saut prennent le même temps. Il est un peu difficile de répondre à cette question, mais voici ce que je peux dire : Dans le Référence du jeu d'instructions Intel ils sont tous regroupés sous une instruction commune, Jcc (Saut si la condition est remplie). Le même regroupement est effectué sous le Manuel de référence sur l'optimisation dans l'annexe C. Latence et débit.

Latence - Le nombre de cycles d'horloge qui sont nécessaires pour que le noyau d'exécution pour achever l'exécution de toutes les opérations qui constituent une instruction.

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

Les valeurs pour Jcc sont :

      Latency   Throughput
Jcc     N/A        0.5

avec la note de bas de page suivante sur Jcc :

7) La sélection des instructions de saut conditionnel doit être basée sur la recommandation de la section 3.4.1, " Optimisation de la prédiction des branches ", afin d'améliorer la prévisibilité des branches. Lorsque les branchements sont prédits avec succès, la latence de jcc est effectivement nulle.

Donc, rien dans la documentation d'Intel ne traite jamais d'un Jcc d'instructions différentes 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 de l'instruction. EFLAGS pour 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 instruction n'en testant qu'un seul (sans tenir compte du délai de propagation de la porte, qui est bien inférieur à la période d'horloge).

---

Edit : Floating Point

Cela s'applique également à la virgule flottante x87 : (à peu près le même code que ci-dessus, mais avec double au 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

Answer 2

Historiquement (nous parlons des années 1980 et du début des années 1990), il y avait un peu de architectures dans lesquelles cela était vrai. Le problème de base est que la comparaison de nombres entiers est intrinsèquement mise en œuvre via des soustractions de nombres 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, quand A < B la soustraction doit emprunter un bit de poids fort pour que la soustraction soit correcte, tout comme vous portez et empruntez lorsque vous additionnez et soustrayez à la main. Ce bit "emprunté" est généralement appelé le bit de poids fort. bit de report et serait testable par une instruction de branchement. Un deuxième bit appelé zéro bit serait défini si la soustraction était identique à zéro, ce qui implique l'égalité.

Il y avait généralement au moins deux instructions de branchement conditionnel, une pour se brancher sur le bit de report et une sur le bit de zéro.

Maintenant, pour entrer dans le vif du sujet, élargissons le tableau précédent pour inclure les résultats de la retenue et du 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, la mise en œuvre d'une branche pour A < B peut être réalisée en une seule instruction, car le bit de report est effacé. 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 du drapeau zéro pour attraper le cas d'é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 "moins que" pourrait sauver instruction d'une machine . C'était pertinent à l'époque des processeurs sub-mégahertz et des rapports de vitesse CPU/mémoire de 1:1, mais c'est presque totalement inutile aujourd'hui.

Answer 3

En supposant que nous parlions de types d'entiers internes, il est impossible que l'un soit plus rapide que l'autre. Ils sont évidemment sémantiquement identiques. Ils demandent tous deux au compilateur de faire précisément la même chose. Seul un compilateur horriblement défectueux pourrait générer un code inférieur pour l'un d'entre eux.

S'il y avait une plateforme où < était plus rapide que <= pour les types entiers simples, le compilateur devrait toujours convertir <= à < pour les constantes. Tout compilateur qui ne le ferait pas serait simplement un mauvais compilateur (pour cette plateforme).

Answer 4

Je constate qu'aucun des deux 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 if est de GCC sur la plateforme x86_64 sous Linux.

Les auteurs de compilateurs sont des personnes plutôt intelligentes, qui pensent à ces choses et à bien d'autres que la plupart d'entre nous considèrent comme 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

Answer 5

Pour le code à virgule flottante, la comparaison <= peut effectivement ê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, il effectue d'abord une comparaison en virgule flottante (qui met à jour les données de l'ordinateur). cr le registre des conditions), puis déplace le registre des conditions vers un GPR, met en place le bit "comparé moins que", puis revient. Cela prend quatre instructions.

Maintenant, considérez plutôt cette fonction :

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

Cela nécessite le même travail que compare_strict ci-dessus, mais il y a maintenant deux éléments intéressants : "était inférieur à" et "était égal à". Cela nécessite une instruction supplémentaire ( cror - condition de registre bitwise OR) pour combiner ces deux bits en un seul. Ainsi, compare_loose nécessite cinq instructions, tandis que compare_strict en nécessite quatre.

On pourrait penser que le compilateur pourrait optimiser la deuxième fonction de la manière suivante :

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

Cependant, cela ne permettra pas de gérer correctement les NaN. NaN1 <= NaN2 et NaN1 > NaN2 doivent tous deux être évalués à faux.