Sentencia if vs sentencia if-else, ¿cuál es más rápida? [cerrado]

83

Discutí con un amigo el otro día sobre esos dos fragmentos. ¿Cuál es más rápido y por qué?

value = 5;
if (condition) {
    value = 6;
}

y:

if (condition) {
    value = 6;
} else {
    value = 5;
}

¿Y si valuees una matriz?

Nota: Sé que value = condition ? 6 : 5;existe y espero que sea más rápido, pero no era una opción.

Editar (solicitado por el personal ya que la pregunta está en espera en este momento):

  • responda considerando el ensamblado x86 generado por los compiladores convencionales (por ejemplo, g ++, clang ++, vc, mingw ) en versiones optimizadas y no optimizadas o ensamblado MIPS .
  • cuando el ensamblaje es diferente, explique por qué una versión es más rápida y cuándo ( por ejemplo, "mejor porque no hay ramificaciones y las ramificaciones tienen el siguiente problema blahblah" )
Julien__
fuente
173
La optimización acabará con todo eso ... no importa ...
The Quantum Physicist
21
Podrías perfilarlo, personalmente dudo que veas alguna diferencia usando un compilador moderno.
George
25
Usar en value = condition ? 6 : 5;lugar de if/elseprobablemente resultará en la generación del mismo código. Mire el resultado del ensamblaje si desea saber más.
Jabberwocky
8
lo más importante en este caso es evitar la rama, que es lo más caro aquí. (recarga de tubería, descarte instrucciones precargadas, etc.)
Tommylee2k
11
La única vez que tiene sentido micro-optimizar para una velocidad como esta es dentro de un bucle que se ejecutará muchas, muchas veces, y el optimizador puede optimizar todas las instrucciones de la rama, como puede hacerlo gcc para este ejemplo trivial, o en el mundo real el rendimiento dependerá en gran medida de la predicción correcta de la rama (enlace obligatorio a stackoverflow.com/questions/11227809/… ). Si inevitablemente se ramificará dentro de un bucle, puede ayudar al predictor de ramificaciones generando un perfil y compilando con él.
Davislor

Respuestas:

282

TL; DR: En código no optimizado, ifsin elseparece irrelevantemente más eficiente, pero incluso con el nivel más básico de optimización habilitado, el código básicamente se reescribe value = condition + 5.


Lo intenté y generé el ensamblado para el siguiente código:

int ifonly(bool condition, int value)
{
    value = 5;
    if (condition) {
        value = 6;
    }
    return value;
}

int ifelse(bool condition, int value)
{
    if (condition) {
        value = 6;
    } else {
        value = 5;
    }
    return value;
}

En gcc 6.3 con optimizaciones deshabilitadas ( -O0), la diferencia relevante es:

 mov     DWORD PTR [rbp-8], 5
 cmp     BYTE PTR [rbp-4], 0
 je      .L2
 mov     DWORD PTR [rbp-8], 6
.L2:
 mov     eax, DWORD PTR [rbp-8]

porque ifonly, mientras ifelsetiene

 cmp     BYTE PTR [rbp-4], 0
 je      .L5
 mov     DWORD PTR [rbp-8], 6
 jmp     .L6
.L5:
 mov     DWORD PTR [rbp-8], 5
.L6:
 mov     eax, DWORD PTR [rbp-8]

Este último parece un poco menos eficiente porque tiene un salto adicional, pero ambos tienen al menos dos y como máximo tres asignaciones, así que a menos que realmente necesites exprimir hasta la última gota de rendimiento (pista: a menos que estés trabajando en un transbordador espacial, no , e incluso entonces probablemente no lo haga) la diferencia no se notará.

Sin embargo, incluso con el nivel de optimización más bajo ( -O1), ambas funciones se reducen a lo mismo:

test    dil, dil
setne   al
movzx   eax, al
add     eax, 5

que es básicamente el equivalente de

return 5 + condition;

asumiendo que conditiones cero o uno. Los niveles de optimización más altos no cambian realmente la salida, excepto que logran evitarlos movzxponiendo a cero eficientemente el EAXregistro al principio.


Descargo de responsabilidad: probablemente no debería escribir 5 + conditionusted mismo (a pesar de que el estándar garantiza que la conversión truea un tipo entero da 1) porque su intención podría no ser inmediatamente obvia para las personas que leen su código (que puede incluir su yo futuro). El objetivo de este código es mostrar que lo que produce el compilador en ambos casos es (prácticamente) idéntico. Ciprian Tomoiaga lo dice bastante bien en los comentarios:

El trabajo de un humano es escribir código para humanos y dejar que el compilador escriba código para la máquina .

CompuChip
fuente
50
Esta es una gran respuesta y debería aceptarse.
dtell
10
Nunca hubiera pensado en usar la adición (<- lo que Python te hace.)
Ciprian Tomoiagă
26
@CiprianTomoiaga y, a menos que esté escribiendo un optimizador, ¡no debería hacerlo! En casi todos los casos, debe dejar que el compilador realice optimizaciones como esta, especialmente cuando reducen drásticamente la legibilidad del código. Solo si las pruebas de rendimiento muestran problemas con un cierto fragmento de código, debería comenzar a intentar optimizarlo, e incluso entonces mantenerlo limpio y bien comentado, y solo realizar optimizaciones que marcan una diferencia medible.
Muzer
22
Quería responderle a Muzer, pero no habría agregado nada al hilo. Sin embargo, solo quiero reafirmar que el trabajo de un humano es escribir código para humanos y dejar que el compilador escriba código para la máquina . Dije eso de un desarrollador de compiladores PoV (que no soy, pero aprendí un poco sobre ellos)
Ciprian Tomoiagă
10
El valor trueconvertido a intsiempre produce 1, punto. Por supuesto, si su condición es simplemente "veraz" y no el boolvalor true, entonces ese es un asunto completamente diferente.
TC
44

La respuesta de CompuChip muestra que intambos están optimizados para el mismo ensamblaje, por lo que no importa.

¿Y si el valor es una matriz?

Interpretaré esto de una manera más general, es decir, ¿qué pasaría si fuera valuede un tipo cuyas construcciones y asignaciones son caras (y los movimientos son baratos)?

entonces

T value = init1;
if (condition)
   value = init2;

es subóptimo porque, en caso de que conditionsea ​​cierto, haces la inicialización innecesaria ay init1luego haces la asignación de copia.

T value;
if (condition)
   value = init2;
else
   value = init3;

Esta es mejor. Pero sigue siendo subóptimo si la construcción predeterminada es cara y si la construcción de la copia es más cara que la inicialización.

Tienes la solución de operador condicional que es buena:

T value = condition ? init1 : init2;

O, si no le gusta el operador condicional, puede crear una función auxiliar como esta:

T create(bool condition)
{
  if (condition)
     return {init1};
  else
     return {init2};
}

T value = create(condition);

Dependiendo de qué init1y qué init2es, también puede considerar esto:

auto final_init = condition ? init1 : init2;
T value = final_init;

Pero nuevamente debo enfatizar que esto es relevante solo cuando la construcción y las asignaciones son realmente costosas para el tipo dado. E incluso entonces, solo mediante la elaboración de perfiles se sabe con certeza.

bolov
fuente
3
Caro y no optimizado. Por ejemplo, si el constructor predeterminado pone a cero la matriz, el compilador podría darse cuenta de que la asignación consiste simplemente en sobrescribir esos ceros, por lo que no los pone a cero y escribe directamente en esta memoria. Por supuesto, los optimizadores son bestias quisquillosas, por lo que es difícil predecir cuándo se activan o no ...
Matthieu M.
@MatthieuM. por supuesto. Lo que quise decir con "caro" es "caro de ejecutar (por una métrica, ya sea relojes de CPU, utilización de recursos, etc.) incluso después de las optimizaciones del compilador.
bolov
Me parece poco probable que la construcción predeterminada sea costosa pero se mueva barata.
Plugwash
6
@plugwash Considere una clase con una matriz asignada muy grande. El constructor predeterminado asigna e inicializa la matriz, lo cual es costoso. El constructor mover (¡no copiar!) Puede simplemente intercambiar punteros con el objeto fuente y no necesita asignar o inicializar la matriz grande.
TrentP
1
Siempre que las partes sean simples, definitivamente preferiría usar el ?:operador en lugar de introducir una nueva función. Después de todo, es probable que no solo pase la condición a la función, sino también algunos argumentos del constructor. Algunos de los cuales ni siquiera pueden usarse create()dependiendo de la condición.
cmaster - reinstalar a monica
12

En lenguaje pseudo-ensamblador,

    li    #0, r0
    test  r1
    beq   L1
    li    #1, r0
L1:

puede o no puede ser más rápido que

    test  r1
    beq   L1
    li    #1, r0
    bra   L2
L1:
    li    #0, r0
L2:

dependiendo de qué tan sofisticada sea la CPU real. Pasando de lo más simple a lo más elegante:

  • Con cualquier CPU fabricada después de aproximadamente 1990, el buen rendimiento depende de que el código encaje en la caché de instrucciones . En caso de duda, por lo tanto, minimice el tamaño del código. Esto pesa a favor del primer ejemplo.

  • Con una CPU básica " en orden, canalización de cinco etapas ", que sigue siendo aproximadamente lo que se obtiene en muchos microcontroladores, hay una burbuja de canalización cada vez que se toma una rama, condicional o incondicional, por lo que también es importante minimizar el número de instrucciones de bifurcación. Esto también pesa a favor del primer ejemplo.

  • Las CPU algo más sofisticadas, lo suficientemente elegantes como para realizar una " ejecución fuera de orden ", pero no lo suficientemente elegantes como para usar las implementaciones más conocidas de ese concepto, pueden generar burbujas de canalización siempre que encuentren peligros de escritura tras escritura . Esto pesa a favor del segundo ejemplo, donde r0se escribe solo una vez, pase lo que pase. Estas CPU suelen ser lo suficientemente elegantes como para procesar ramas incondicionales en el buscador de instrucciones, por lo que no solo está intercambiando la penalización de escritura después de escritura por una penalización de rama.

    No sé si alguien todavía fabrica este tipo de CPU. Sin embargo, las CPUs que no utilizan los "mejores implementaciones conocidas" de ejecución fuera de orden es probable que cortar las esquinas en las instrucciones de uso menos frecuente, por lo que deberá tener en cuenta que este tipo de cosas puede suceder. Un ejemplo real son las dependencias de datos falsas en los registros de destino en popcnty lzcntsobre las CPU de Sandy Bridge .

  • En el extremo más alto, el motor OOO terminará emitiendo exactamente la misma secuencia de operaciones internas para ambos fragmentos de código; esta es la versión de hardware de "no se preocupe, el compilador generará el mismo código de máquina de cualquier manera". Sin embargo, el tamaño del código sigue siendo importante y ahora también debería preocuparse por la previsibilidad de la rama condicional. Las fallas en la predicción de rama potencialmente causan una descarga completa de la tubería , lo cual es catastrófico para el rendimiento; consulte ¿Por qué es más rápido procesar una matriz ordenada que una matriz no ordenada? para comprender cuánta diferencia puede hacer esto.

    Si la rama es muy impredecible y su CPU tiene instrucciones de movimiento condicional o de conjunto condicional, este es el momento de usarlas:

        li    #0, r0
        test  r1
        setne r0
    

    o

        li    #0, r0
        li    #1, r2
        test  r1
        movne r2, r0
    

    La versión de conjunto condicional también es más compacta que cualquier otra alternativa; si esa instrucción está disponible, prácticamente se garantiza que será lo correcto para este escenario, incluso si la rama era predecible. La versión de movimiento condicional requiere un registro temporal adicional y siempre desperdicia liel valor de una instrucción de recursos de despacho y ejecución; si la rama era de hecho predecible, la versión ramificada bien podría ser más rápida.

zwol
fuente
Volvería a redactar su segundo punto sobre si la CPU tiene un motor fuera de servicio que se retrasa por los peligros de escritura tras escritura. Si una CPU tiene un motor fuera de servicio que puede manejar tales peligros sin demora, no hay problema, pero tampoco hay problema si la CPU no tiene un motor fuera de servicio .
supercat
@supercat El párrafo al final está destinado a cubrir ese caso, pero pensaré en cómo aclararlo.
zwol
No sé qué CPU actuales tienen un caché que haría que el código ejecutado secuencialmente se ejecutara más rápido la segunda vez que la primera vez (algunas partes ARM basadas en flash tienen una interfaz que puede almacenar en búfer algunas filas de datos flash, pero pueden obtener código secuencialmente tan rápido como lo ejecutan, pero la clave para hacer que el código con muchas ramas se ejecute rápidamente en ellos es copiarlo a la RAM) Las CPU sin ninguna ejecución fuera de orden son mucho más comunes que aquellas que se retrasarían por los peligros de escritura tras escritura.
supercat
Esto es muy revelador
Julien__
9

En código no optimizado, el primer ejemplo asigna una variable siempre una vez y, a veces, dos veces. El segundo ejemplo solo asigna una variable una vez. El condicional es el mismo en ambas rutas de código, por lo que no debería importar. En código optimizado, depende del compilador.

Como siempre, si está tan preocupado, genere el ensamblado y vea qué está haciendo realmente el compilador.

Neil
fuente
1
Si le preocupa el rendimiento, no se compilarán sin optimizar. Pero ciertamente lo "bueno" que sea el optimizador depende del compilador / versión.
old_timer
AFAIK, no hay comentarios sobre qué compilador / arquitectura de CPU, etc., por lo que potencialmente, su compilador no optimiza. Podrían estar compilando en cualquier cosa, desde un PIC de 8 bits hasta un Xeon de 64 bits.
Neil
8

¿Qué te haría pensar que alguno de ellos, incluso el delineador, es más rápido o más lento?

unsigned int fun0 ( unsigned int condition, unsigned int value )
{
    value = 5;
    if (condition) {
        value = 6;
    }
    return(value);
}
unsigned int fun1 ( unsigned int condition, unsigned int value )
{

    if (condition) {
        value = 6;
    } else {
        value = 5;
    }
    return(value);
}
unsigned int fun2 ( unsigned int condition, unsigned int value )
{
    value = condition ? 6 : 5;
    return(value);
}

Más líneas de código de un lenguaje de alto nivel le dan al compilador más con qué trabajar, así que si desea establecer una regla general al respecto, dé al compilador más código para trabajar. Si el algoritmo es el mismo que en los casos anteriores, se esperaría que el compilador con una optimización mínima lo averiguara.

00000000 <fun0>:
   0:   e3500000    cmp r0, #0
   4:   03a00005    moveq   r0, #5
   8:   13a00006    movne   r0, #6
   c:   e12fff1e    bx  lr

00000010 <fun1>:
  10:   e3500000    cmp r0, #0
  14:   13a00006    movne   r0, #6
  18:   03a00005    moveq   r0, #5
  1c:   e12fff1e    bx  lr

00000020 <fun2>:
  20:   e3500000    cmp r0, #0
  24:   13a00006    movne   r0, #6
  28:   03a00005    moveq   r0, #5
  2c:   e12fff1e    bx  lr

no es una gran sorpresa que hizo la primera función en un orden diferente, aunque el mismo tiempo de ejecución.

0000000000000000 <fun0>:
   0:   7100001f    cmp w0, #0x0
   4:   1a9f07e0    cset    w0, ne
   8:   11001400    add w0, w0, #0x5
   c:   d65f03c0    ret

0000000000000010 <fun1>:
  10:   7100001f    cmp w0, #0x0
  14:   1a9f07e0    cset    w0, ne
  18:   11001400    add w0, w0, #0x5
  1c:   d65f03c0    ret

0000000000000020 <fun2>:
  20:   7100001f    cmp w0, #0x0
  24:   1a9f07e0    cset    w0, ne
  28:   11001400    add w0, w0, #0x5
  2c:   d65f03c0    ret

Es de esperar que tenga la idea de que podría haber intentado esto si no fuera obvio que las diferentes implementaciones no eran realmente diferentes.

En lo que respecta a una matriz, no estoy seguro de cómo eso importa,

if(condition)
{
 big blob of code a
}
else
{
 big blob of code b
}

simplemente voy a poner el mismo envoltorio if-then-else alrededor de las grandes manchas de código, ya sean de valor = 5 o algo más complicado. Del mismo modo, la comparación, incluso si es una gran cantidad de código, aún debe calcularse, e igual o no igual a algo a menudo se compila con el negativo, si (condición) hacer algo a menudo se compila como si no fuera condición goto.

00000000 <fun0>:
   0:   0f 93           tst r15     
   2:   03 24           jz  $+8         ;abs 0xa
   4:   3f 40 06 00     mov #6, r15 ;#0x0006
   8:   30 41           ret         
   a:   3f 40 05 00     mov #5, r15 ;#0x0005
   e:   30 41           ret         

00000010 <fun1>:
  10:   0f 93           tst r15     
  12:   03 20           jnz $+8         ;abs 0x1a
  14:   3f 40 05 00     mov #5, r15 ;#0x0005
  18:   30 41           ret         
  1a:   3f 40 06 00     mov #6, r15 ;#0x0006
  1e:   30 41           ret         

00000020 <fun2>:
  20:   0f 93           tst r15     
  22:   03 20           jnz $+8         ;abs 0x2a
  24:   3f 40 05 00     mov #5, r15 ;#0x0005
  28:   30 41           ret         
  2a:   3f 40 06 00     mov #6, r15 ;#0x0006
  2e:   30 41

Acabamos de realizar este ejercicio con alguien más recientemente en stackoverflow. Este compilador mips curiosamente en ese caso no solo se dio cuenta de que las funciones eran las mismas, sino que una función simplemente saltaba a la otra para ahorrar espacio en el código. Aunque no hice eso aquí

00000000 <fun0>:
   0:   0004102b    sltu    $2,$0,$4
   4:   03e00008    jr  $31
   8:   24420005    addiu   $2,$2,5

0000000c <fun1>:
   c:   0004102b    sltu    $2,$0,$4
  10:   03e00008    jr  $31
  14:   24420005    addiu   $2,$2,5

00000018 <fun2>:
  18:   0004102b    sltu    $2,$0,$4
  1c:   03e00008    jr  $31
  20:   24420005    addiu   $2,$2,5

algunos objetivos más.

00000000 <_fun0>:
   0:   1166            mov r5, -(sp)
   2:   1185            mov sp, r5
   4:   0bf5 0004       tst 4(r5)
   8:   0304            beq 12 <_fun0+0x12>
   a:   15c0 0006       mov $6, r0
   e:   1585            mov (sp)+, r5
  10:   0087            rts pc
  12:   15c0 0005       mov $5, r0
  16:   1585            mov (sp)+, r5
  18:   0087            rts pc

0000001a <_fun1>:
  1a:   1166            mov r5, -(sp)
  1c:   1185            mov sp, r5
  1e:   0bf5 0004       tst 4(r5)
  22:   0204            bne 2c <_fun1+0x12>
  24:   15c0 0005       mov $5, r0
  28:   1585            mov (sp)+, r5
  2a:   0087            rts pc
  2c:   15c0 0006       mov $6, r0
  30:   1585            mov (sp)+, r5
  32:   0087            rts pc

00000034 <_fun2>:
  34:   1166            mov r5, -(sp)
  36:   1185            mov sp, r5
  38:   0bf5 0004       tst 4(r5)
  3c:   0204            bne 46 <_fun2+0x12>
  3e:   15c0 0005       mov $5, r0
  42:   1585            mov (sp)+, r5
  44:   0087            rts pc
  46:   15c0 0006       mov $6, r0
  4a:   1585            mov (sp)+, r5
  4c:   0087            rts pc

00000000 <fun0>:
   0:   00a03533            snez    x10,x10
   4:   0515                    addi    x10,x10,5
   6:   8082                    ret

00000008 <fun1>:
   8:   00a03533            snez    x10,x10
   c:   0515                    addi    x10,x10,5
   e:   8082                    ret

00000010 <fun2>:
  10:   00a03533            snez    x10,x10
  14:   0515                    addi    x10,x10,5
  16:   8082                    ret

y compiladores

con este código uno esperaría que los diferentes objetivos también coincidan

define i32 @fun0(i32 %condition, i32 %value) #0 {
  %1 = icmp ne i32 %condition, 0
  %. = select i1 %1, i32 6, i32 5
  ret i32 %.
}

; Function Attrs: norecurse nounwind readnone
define i32 @fun1(i32 %condition, i32 %value) #0 {
  %1 = icmp eq i32 %condition, 0
  %. = select i1 %1, i32 5, i32 6
  ret i32 %.
}

; Function Attrs: norecurse nounwind readnone
define i32 @fun2(i32 %condition, i32 %value) #0 {
  %1 = icmp ne i32 %condition, 0
  %2 = select i1 %1, i32 6, i32 5
  ret i32 %2
}


00000000 <fun0>:
   0:   e3a01005    mov r1, #5
   4:   e3500000    cmp r0, #0
   8:   13a01006    movne   r1, #6
   c:   e1a00001    mov r0, r1
  10:   e12fff1e    bx  lr

00000014 <fun1>:
  14:   e3a01006    mov r1, #6
  18:   e3500000    cmp r0, #0
  1c:   03a01005    moveq   r1, #5
  20:   e1a00001    mov r0, r1
  24:   e12fff1e    bx  lr

00000028 <fun2>:
  28:   e3a01005    mov r1, #5
  2c:   e3500000    cmp r0, #0
  30:   13a01006    movne   r1, #6
  34:   e1a00001    mov r0, r1
  38:   e12fff1e    bx  lr


fun0:
    push.w  r4
    mov.w   r1, r4
    mov.w   r15, r12
    mov.w   #6, r15
    cmp.w   #0, r12
    jne .LBB0_2
    mov.w   #5, r15
.LBB0_2:
    pop.w   r4
    ret

fun1:
    push.w  r4
    mov.w   r1, r4
    mov.w   r15, r12
    mov.w   #5, r15
    cmp.w   #0, r12
    jeq .LBB1_2
    mov.w   #6, r15
.LBB1_2:
    pop.w   r4
    ret


fun2:
    push.w  r4
    mov.w   r1, r4
    mov.w   r15, r12
    mov.w   #6, r15
    cmp.w   #0, r12
    jne .LBB2_2
    mov.w   #5, r15
.LBB2_2:
    pop.w   r4
    ret

Ahora, técnicamente, hay una diferencia de rendimiento en algunas de estas soluciones, a veces el resultado es 5 casos tiene un salto sobre el resultado es 6 códigos, y viceversa, ¿es una rama más rápida que la ejecución? se podría argumentar, pero la ejecución debería variar. Pero eso es más una condición if que una condición if not en el código, lo que hace que el compilador ejecute el if this jump over else. pero esto no se debe necesariamente al estilo de codificación, sino a la comparación y los casos if y else en cualquier sintaxis.

viejo contador de tiempo
fuente
0

Ok, dado que el ensamblaje es una de las etiquetas, simplemente asumiré que su código es pseudocódigo (y no necesariamente c) y lo traduciré por un humano al ensamblaje 6502.

1ra opción (sin más)

        ldy #$00
        lda #$05
        dey
        bmi false
        lda #$06
false   brk

2da opción (con más)

        ldy #$00
        dey
        bmi else
        lda #$06
        sec
        bcs end
else    lda #$05
end     brk

Supuestos: La condición está en el registro Y, establezca esto en 0 o 1 en la primera línea de cualquier opción, el resultado estará en el acumulador.

Entonces, después de contar los ciclos para ambas posibilidades de cada caso, vemos que la primera construcción es generalmente más rápida; 9 ciclos cuando la condición es 0 y 10 ciclos cuando la condición es 1, mientras que la opción dos también es 9 ciclos cuando la condición es 0, pero 13 ciclos cuando la condición es 1. (los recuentos de ciclos no incluyen el BRKal final ).

Conclusión: If onlyes más rápido que If-Elseconstruir.

Y para completar, aquí hay una value = condition + 5solución optimizada :

ldy #$00
lda #$00
tya
adc #$05
brk

Esto reduce nuestro tiempo a 8 ciclos ( nuevamente sin incluir el BRKal final ).

Glen Yates
fuente
6
Desafortunadamente para esta respuesta, introducir el mismo código fuente en un compilador de C (o en un compilador de C ++) produce una salida muy diferente a la de alimentarlo en el cerebro de Glen. No hay diferencia, ni potencial de "optimización", entre ninguna de las alternativas a nivel de código fuente. Simplemente use el que sea más legible (presumiblemente el if / else one).
Quuxplusone
1
@Sí. Es probable que el compilador optimice ambas variantes para obtener la versión más rápida o que agregue una sobrecarga adicional que supere con creces la diferencia entre las dos. O ambos.
jpaugh
1
Asumir que " no es necesariamente C " parece una opción sensata, dado que la pregunta está etiquetada como C ++ (desafortunadamente, no logra declarar los tipos de variables involucradas).
Toby Speight