Question Est-ce

Je lis un livre où l'auteur dit que if( a < 901 ) est plus rapide que if( a <= 900 ).

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


1372
2017-08-27 02:10


origine


Réponses:


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

Exemple (Publié pour la brièveté) Compilé avec $ gcc -m32 -S -masm=intel test.c

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

Compile pour:

    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 pour:

    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 instruction. Les deux prendront le même temps.


Je voudrais répondre au commentaire selon lequel 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 le 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é sous la Manuel de référence d'optimisation, à l'annexe C. Latence et débit.

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

Débit - Le nombre de cycles d'horloge requis pour   attendre avant que les ports d'émission sont libres d'accepter la même instruction   encore. Pour de nombreuses instructions, le débit d'une instruction peut être   significativement moins que sa latence

Les valeurs pour Jcc sont:

      Latency   Throughput
Jcc     N/A        0.5

avec la note de bas de page suivante Jcc:

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

Donc, rien dans les docs Intel traite jamais un Jcc instruction différente des autres.

Si l'on pense à la circuiterie réelle utilisée pour mettre en œuvre les instructions, on peut supposer qu'il y aurait des portes ET / OU simples sur les différents bits dans EFLAGS, pour déterminer si les conditions sont remplies. Il n'y a donc pas de raison pour qu'une instruction testant deux bits prenne plus ou moins de temps qu'une épreuve n'en testant qu'une seule (Ignorer le délai de propagation de la porte, ce qui est beaucoup moins que la période de l'horloge).


Edit: Floating Point

Cela vaut également pour le point flottant 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

1570
2017-08-27 02:13



Historiquement (nous parlons les années 1980 et début des années 1990), il y avait certains architectures dans lesquelles cela était vrai. Le problème fondamental est que la comparaison d'entiers est intrinsèquement mise en œuvre via des soustractions entières. 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 haut pour que la soustraction soit correcte, tout comme vous le faites et l'empruntez en ajoutant et en soustrayant manuellement. Ce bit «emprunté» était généralement appelé porter un peu et serait testable par une instruction de branchement. Un deuxième bit appelé le zéro bit serait défini si la soustraction était identiquement nulle, ce qui impliquait l'égalité.

Il y avait habituellement au moins deux instructions de branchement conditionnel, l'une sur le bit de report et l'autre 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 carry et zero bit.

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

Donc, mettre en œuvre une branche pour A < B peut être fait dans une instruction, parce que le bit de transport est clair seulement 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 moins-ou-égale, nous devons faire 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, en utilisant une comparaison "inférieure à" pourrait enregistrer une instruction machine. Cela était pertinent à l'ère de la vitesse du processeur sous-mégahertz et des rapports de vitesse CPU-mémoire 1: 1, mais il est presque totalement hors de propos aujourd'hui.


555
2017-08-27 17:53



En supposant que nous parlons de types entiers internes, il n'y a pas de possibilité 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 doit toujours convertir <= à < pour les constantes. Tout compilateur qui ne le ferait pas serait juste un mauvais compilateur (pour cette plate-forme).


85
2017-08-27 02:31



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 if est de GCC sur la plate-forme x86_64 sous Linux.

Les rédacteurs de compilateurs sont des gens très intelligents, et ils pensent à ces choses et à beaucoup d'autres que la plupart d'entre nous considèrent comme allant de soi.

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

67
2017-08-27 02:16



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, d'abord cela effectue une comparaison à virgule flottante (qui met à jour cr, le registre de condition), déplace ensuite le registre de condition vers un GPR, décale le bit "comparé inférieur à" et le renvoie. Il faut quatre instructions.

Considérons maintenant cette fonction à la place:

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

Cela nécessite le même travail que compare_strict ci-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 bit à bit OU) pour combiner ces deux bits en un seul. Alors compare_loose nécessite cinq instructions, tandis que compare_strict nécessite 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 gèrera incorrectement les NaN. NaN1 <= NaN2 et NaN1 > NaN2 besoin d'évaluer à la fois faux.


48
2017-08-27 18:32



Peut-être que l'auteur de ce livre anonyme a lu a > 0 fonctionne plus vite que a >= 1 et pense que c'est vrai universellement.

Mais c'est parce qu'un 0 est impliqué (parce que CMP peut, en fonction de l'architecture, être remplacé par ex. avec OR) et non à cause de <.


34
2017-08-27 13:05



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


29
2017-08-27 09:23



Ils ont la même vitesse. Peut-être dans une architecture spéciale ce qu'il a dit est juste, mais dans la famille x86 au moins, je sais qu'ils 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 il est fait en un cycle, parce qu'il le fera avec une opération de masque.


15
2017-08-27 08:25



Cela dépend 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 plutôt inhabituel, car le compilateur pourrait contourner ce problème, le rendant non pertinent.


13
2017-08-27 02:15