Pregunta Es

Estoy leyendo un libro donde el autor dice que if( a < 901 ) es más rápido que if( a <= 900 ).

No exactamente como en este ejemplo simple, pero hay ligeros cambios de rendimiento en el código complejo de bucle. Supongo que esto tiene que ver con el código de máquina generado en caso de que sea cierto.


1372
2017-08-27 02:10


origen


Respuestas:


No, no será más rápido en la mayoría de las arquitecturas. No especificó, pero en x86, todas las comparaciones integrales se implementarán típicamente en dos instrucciones de máquina:

  • UN test o cmp instrucción, que establece EFLAGS
  • Y un Jcc (salto) instrucción, según el tipo de comparación (y el diseño del código):
    • jne - Saltar si no es igual -> ZF = 0
    • jz - Saltar si es cero (igual) -> ZF = 1
    • jg - Salta si es mayor -> ZF = 0 and SF = OF
    • (etc ...)

Ejemplo (Editado por brevedad) Compilado con $ gcc -m32 -S -masm=intel test.c

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

Compila para:

    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:

Y

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

Compila para:

    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:

Entonces la única diferencia entre los dos es jg versus un jge instrucción. Los dos tomarán la misma cantidad de tiempo.


Me gustaría comentar el comentario de que nada indica que las diferentes instrucciones de salto tomen la misma cantidad de tiempo. Este es un poco complicado de responder, pero esto es lo que puedo dar: en el Referencia del conjunto de instrucciones de Intel, se agrupan todos bajo una instrucción común, Jcc (Salte si se cumple la condición). La misma agrupación se realiza en conjunto bajo el Manual de referencia de optimización, en el Apéndice C. Latencia y rendimiento.

Estado latente - La cantidad de ciclos de reloj necesarios para el   núcleo de ejecución para completar la ejecución de todos los μops que forman   una instrucción.

Rendimiento - La cantidad de ciclos de reloj necesarios para   espere antes de que los puertos de emisión sean libres de aceptar la misma instrucción   de nuevo. Para muchas instrucciones, el rendimiento de una instrucción puede ser   significativamente menos que su latencia

Los valores para Jcc son:

      Latency   Throughput
Jcc     N/A        0.5

con la siguiente nota al pie Jcc:

7) La selección de instrucciones de salto condicional se debe basar en la recomendación de la sección Sección 3.4.1, "Optimización de predicción de bifurcación", para mejorar la predictibilidad de las bifurcaciones. Cuando las ramas se predicen con éxito, la latencia de jcc es efectivamente cero

Por lo tanto, nada en los documentos de Intel trata alguna vez Jcc instrucción de forma diferente a los demás.

Si uno piensa en los circuitos reales utilizados para implementar las instrucciones, se puede suponer que habría puertas Y / O simples en los diferentes bits en EFLAGS, para determinar si se cumplen las condiciones. Entonces, no hay razón para que una instrucción que prueba dos bits deba tomar más o menos tiempo que una prueba solo una (ignorando el retardo de propagación de la puerta, que es mucho menor que el período del reloj).


Editar: punto flotante

Esto también es válido para el punto flotante x87: (Casi el mismo código que el anterior, pero con double en lugar 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



Históricamente (estamos hablando de la década de 1980 y principios de 1990), hubo algunos arquitecturas en las que esto era cierto. La raíz del problema es que la comparación entera se implementa inherentemente a través de restas enteras. Esto da lugar a los siguientes casos.

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

Ahora, cuando A < B la resta tiene que pedir prestado un bit alto para que la resta sea correcta, tal como lo llevas y pides al agregar y restar a mano. Este bit "prestado" generalmente se conoce como el llevar poco y podría ser probado por una instrucción de rama. Un segundo bit llamado bit cero se establecería si la resta fuera idénticamente cero, lo que implicaba igualdad.

Habitualmente había al menos dos instrucciones de bifurcación condicional, una para bifurcar en el bit de acarreo y otra en el bit cero.

Ahora, para llegar al meollo de la cuestión, expandamos la tabla anterior para incluir los resultados de acarreo y cero bits.

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

Entonces, implementando una rama para A < B se puede hacer en una instrucción, porque el bit de acarreo es claro solamente en este caso, es decir,

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

Pero, si queremos hacer una comparación menor o igual, tenemos que hacer una verificación adicional de la bandera cero para capturar el caso de igualdad.

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

Entonces, en algunas máquinas, usando una comparación "menor que" podría salvar una instrucción de máquina. Esto fue relevante en la era de la velocidad del procesador sub-megahertz y las relaciones de velocidad de la CPU a la memoria de 1: 1, pero hoy es casi totalmente irrelevante.


555
2017-08-27 17:53



Suponiendo que estamos hablando de tipos enteros internos, no hay forma posible de que uno sea más rápido que el otro. Obviamente son semánticamente idénticos. Ambos le piden al compilador que haga exactamente lo mismo. Solo un compilador horriblemente roto generaría un código inferior para uno de estos.

Si hubiera alguna plataforma donde < fue más rápido que <= para tipos enteros simples, el compilador debería siempre convertir <= a < para constantes. Cualquier compilador que no fuera solo sería un compilador incorrecto (para esa plataforma).


85
2017-08-27 02:31



Veo que ninguno es más rápido. El compilador genera el mismo código de máquina en cada condición con un valor diferente.

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

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

Mi ejemplo if es de GCC en la plataforma x86_64 en Linux.

Los escritores de compilación son personas bastante inteligentes, y piensan en estas cosas y en muchas otras que la mayoría de nosotros damos por sentadas.

Noté que si no es una constante, entonces se genera el mismo código de máquina en cualquier caso.

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



Para el código de coma flotante, la comparación <= puede de hecho ser más lenta (con una instrucción) incluso en arquitecturas modernas. Aquí está la primera función:

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

En PowerPC, primero esto realiza una comparación de punto flotante (que actualiza cr, el registro de condición), luego mueve el registro de condición a un GPR, desplaza el bit "comparado menos que" a su lugar, y luego regresa. Toma cuatro instrucciones.

Ahora considere esta función en su lugar:

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

Esto requiere el mismo trabajo que compare_strict arriba, pero ahora hay dos bits de interés: "era menor que" y "era igual a". Esto requiere una instrucción adicional (cror- registro de condición bit a bit O) para combinar estos dos bits en uno. Asi que compare_loose requiere cinco instrucciones, mientras compare_strict requiere cuatro.

Podría pensar que el compilador podría optimizar la segunda función de esta manera:

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

Sin embargo, esto manejará incorrectamente los NaN. NaN1 <= NaN2 y NaN1 > NaN2 necesita ambos evaluar a falso.


48
2017-08-27 18:32



Tal vez el autor de ese libro sin nombre ha leído que a > 0 funciona más rápido que a >= 1 y piensa que eso es verdad universalmente

Pero es porque 0 está involucrado (porque CMP puede, según la arquitectura, reemplazarse, p. con OR) y no a causa de la <.


34
2017-08-27 13:05



Por lo menos, si esto fuera cierto, un compilador podría optimizar trivialmente a <= b to! (A> b), por lo que incluso si la comparación en sí fuera más lenta, con todos menos el compilador más ingenuo, no notaría la diferencia .


29
2017-08-27 09:23



Ellos tienen la misma velocidad. Tal vez en alguna arquitectura especial, lo que él dijo es correcto, pero en la familia x86, al menos, sé que son lo mismo. Porque para hacer esto, la CPU hará una resta (a - b) y luego comprobará los indicadores del registro de banderas. Dos bits de ese registro se llaman ZF (bandera cero) y SF (bandera de señal), y se realiza en un ciclo, porque lo hará con una operación de máscara.


15
2017-08-27 08:25



Esto dependería en gran medida de la arquitectura subyacente a la que se compila el C. Algunos procesadores y arquitecturas pueden tener instrucciones explícitas para igual a, o menor que e igual a, que se ejecutan en diferentes números de ciclos.

Sin embargo, eso sería bastante inusual, ya que el compilador podría evitarlo, haciéndolo irrelevante.


13
2017-08-27 02:15