descargar - java vs c++ diferencias

¿Es<más rápido que<=?

Question

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 cambios leves en el rendimiento del 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.

Answer 1

TL;DR respuesta TL;DR

Para la mayoría de las combinaciones de arquitectura, compilador y lenguaje no será más rápido.

Respuesta completa

Otras respuestas se han concentrado en la arquitectura x86 , y no conozco la arquitectura ARM (que su ensamblador de ejemplo parece ser) lo suficientemente bien como para comentar específicamente el código generado, pero este es un ejemplo de una micro-optimisation que es muy arquitectura específico, y es tan probable que sea una anti-optimización como una optimización .

Como tal, sugeriría que este tipo de micro-optimisation es un ejemplo de la programación del culto de la carga en lugar de la mejor práctica de ingeniería de software.

Probablemente hay algunas arquitecturas en las que se trata de una optimización, pero conozco al menos una arquitectura donde lo contrario puede ser cierto. La venerable arquitectura Transputer solo tenía instrucciones de código de máquina igual o mayor que o igual , por lo que todas las comparaciones tenían que construirse a partir de estas primitivas.

Incluso entonces, en casi todos los casos, el compilador podría ordenar las instrucciones de evaluación de tal manera que, en la práctica, ninguna comparación tuviera ninguna ventaja sobre ninguna otra. Sin embargo, en el peor de los casos, podría ser necesario agregar una instrucción inversa (REV) para intercambiar los dos elementos superiores en la pila de operandos . Esta fue una instrucción de un solo byte que tomó un solo ciclo para ejecutarse, por lo que tenía la menor sobrecarga posible.

Si una microoptimización como esta es o no una optimización o una anti-optimización depende de la arquitectura específica que esté utilizando, por lo que generalmente es una mala idea adquirir el hábito de usar micro optimizaciones específicas de la arquitectura, de lo contrario, podría instintivamente use uno cuando sea inapropiado para hacerlo, y parece que esto es exactamente lo que el libro que está leyendo está defendiendo.

Answer 2

En realidad, serán exactamente la misma velocidad, porque en el nivel de ensamblaje ambos toman una línea. Como:

• jl ax,dx (salta si AX es menor que DX)
• jle ax,dx (salta si AX es menor o igual que DX)

Así que no, tampoco es más rápido. Pero si quiere ser realmente técnico, creo que si lo verificara en un nivel de corriente de electrones, sería un poco más rápido pero no en una velocidad cercana a la que notaría.

Answer 3

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

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

Answer 4

Históricamente (estamos hablando de los años 80 y principios de los 90), hubo algunas arquitecturas en las que esto era cierto. El problema raíz es que la comparación de enteros se implementa de forma inherente a través de restas de enteros. 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, al igual que usted lleva y pide prestado al sumar y restar a mano. Este bit "prestado" solía denominarse bit de acarreo y se podía probar mediante una instrucción de bifurcación. Un segundo bit llamado bit cero se establecería si la resta fuera idénticamente cero, lo que implicaba igualdad.

Normalmente había al menos dos instrucciones de bifurcación condicionales, una para bifurcarse 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, la implementación de una rama para A < B se puede hacer en una instrucción, porque el bit de acarreo es claro solo 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, necesitamos hacer una verificación adicional de la bandera cero para detectar 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

Por lo tanto, en algunas máquinas, el uso de una comparación "menor que" puede ahorrar una instrucción de la máquina . Esto fue relevante en la era de la velocidad del procesador sub-megahertz y las relaciones de velocidad 1: 1 de la CPU a la memoria, pero hoy en día es casi totalmente irrelevante.

Answer 5

No debería ser capaz de notar la diferencia incluso si hay alguna. Además, en la práctica, tendrás que hacer un a + 1 o a - 1 adicional para que la condición se mantenga a menos que vayas a usar algunas constantes mágicas, lo cual es una práctica muy mala por todos los medios.

Answer 6

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 normalmente en dos instrucciones de máquina:

• Una instrucción de test o cmp , que establece EFLAGS
• Y una Jcc (salto) , 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 - Saltar 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 a:

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

    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:

Así que la única diferencia entre los dos es una instrucción jg versus una instrucción jge . Los dos tomarán la misma cantidad de tiempo.

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

Latencia : la cantidad de ciclos de reloj que se requieren para que el núcleo de ejecución complete la ejecución de todos los μops que forman una instrucción.

Rendimiento : la cantidad de ciclos de reloj necesarios para esperar antes de que los puertos de emisión tengan la libertad de aceptar la misma instrucción nuevamente. Para muchas instrucciones, el rendimiento de una instrucción puede ser significativamente menor que su latencia

Los valores para Jcc son:

      Latency   Throughput
Jcc     N/A        0.5

Con la siguiente nota en Jcc :

7) La selección de instrucciones de salto condicional debe basarse en la recomendación de la sección 3.4.1, “Optimización de la predicción de sucursales”, para mejorar la previsibilidad de las sucursales. Cuando las ramas se pronostican con éxito, la latencia de jcc es efectivamente cero.

Por lo tanto, nada en los documentos de Intel trata una instrucción Jcc diferente a las otras.

Si se piensa en el circuito real utilizado 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 pruebe dos bits tome más o menos tiempo que una prueba solo uno (ignorando el retardo de propagación de la puerta, que es mucho menor que el período de 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 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

Answer 7

Para el código de punto flotante, la comparación <= puede ser más lenta (por 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 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 con menos de" y luego regresa. Lleva 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 condición de cror OR en modo bit) para combinar estos dos bits en uno. Así que compare_loose requiere cinco instrucciones, mientras que compare_strict requiere cuatro.

Podría pensar que el compilador podría optimizar la segunda función así:

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

Sin embargo esto manejará incorrectamente NaNs. NaN1 <= NaN2 y NaN1 > NaN2 necesitan ambos evaluar en falso.

Answer 8

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

Answer 9

Se podría decir que la línea es correcta en la mayoría de los lenguajes de script, ya que el carácter adicional resulta en un procesamiento de código ligeramente más lento. Sin embargo, como lo señaló la respuesta principal, no debería tener ningún efecto en C ++, y cualquier cosa que se haga con un lenguaje de scripting probablemente no sea tan preocupada por la optimización.

Answer 10

Suponiendo que estamos hablando de tipos de 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. Sólo un compilador horriblemente roto generaría un código inferior para uno de estos.

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

Answer 11

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

Pero es porque está involucrado un 0 (porque CMP puede, dependiendo de la arquitectura, reemplazarse, por ejemplo, con OR ) y no debido a la < .

Answer 12

Tienen la misma velocidad. Tal vez en alguna arquitectura especial lo que él / ella 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 verificará las banderas del registro de bandera. Dos bits de ese registro se denominan ZF (indicador cero) y SF (indicador de signo), y se realiza en un ciclo, porque lo hará con una operación de máscara.

Answer 13

Veo que tampoco 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 compiladores son personas bastante inteligentes, y piensan en estas cosas y en muchas otras que la mayoría de nosotros damos por sentado.

Noté que si no es una constante, en ambos casos se generará el mismo código de máquina.

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

if(a <=b)
cmpl  -4(%rbp), %eax
jg .L3