¿Son If Thes más rápidos que la multiplicación y la asignación?

Question

Tengo una pregunta rápida, supongo que tengo el siguiente código y se repite de manera similar 10 veces, por ejemplo.

if blah then 
    number = number + 2^n 
end if 

¿Sería más rápido para evaluar:

number = number + blah*2^n? 

Lo que también trae la pregunta, ¿puede multiplicar un valor multiplicado por booleanos un número entero (Aunque no estoy seguro del tipo que se devuelve desde 2^n, es un número entero o sin signo ... etc)? (Estoy trabajando en Ada, pero vamos a tratar de generalizar esto tal vez?)

EDIT: Perdón, debo aclarar Estoy buscando en 2 a la potencia de n, y puse c allí porque estaba interesado en mi propio aprendizaje en el futuro si alguna vez me encuentro con este problema en c y creo que hay más c programadores en estos foros, entonces Ada (estoy asumiendo y tú sabes lo que eso significa), sin embargo mi problema actual está en Ada idioma, pero la pregunta debería ser bastante independiente del lenguaje (espero).

Answer 1

si estamos hablando de C y bla no está bajo su control, a continuación, sólo hacer esto:

 
if(blah) number += (1<<n); 

no hay realmente un valor lógico en C y no tiene que ser, falso es cero y verdadera no es cero, por lo que no se puede asumir que no es cero es 1, que es lo que se necesita para su solución, ni se puede asumir que cualquier bit particular en bla se establece, por ejemplo:

 
number += (blah&1)<<n; 

no necesariamente trabajar ya sea porque 0x2 o 0x4 o cualquier cosa que no sea cero con el bit cero claro es considerado d un verdadero. Normalmente encontrará que 0xFFF ... FFFF (menos uno, o todos) se usan como verdaderos, pero no puede confiar en los típicos.

Ahora, si usted tiene el control completo sobre el valor en bla, y mantenerlo estrictamente a un 0 para falso y 1 para la verdadera entonces se podría hacer lo que preguntabas:

 
number += blah<<n; 

y evitar el potencial de una rama, relleno de línea de caché adicional, etc.

Volver al caso genérico, sin embargo, tomar esta solución genérica:

 
unsigned int fun (int blah, unsigned int n, unsigned int number) 
{ 
    if(blah) number += (1<<n); 
    return(number); 
} 

y compilación de los dos más popu lar/plataformas usadas:

 
    testl %edi, %edi 
    movl %edx, %eax 
    je .L2 
    movl $1, %edx 
    movl %esi, %ecx 
    sall %cl, %edx 
    addl %edx, %eax 
.L2: 

Lo anterior usa una rama condicional.

El que se muestra a continuación utiliza la ejecución condicional, sin ramificación, sin alineación de tubería, es determinista.

 
    cmp r0,#0 
    movne r3,#1 
    addne r2,r2,r3,asl r1 
    mov r0,r2 
    bx lr 

podría haber salvado la r0 mov, instrucción r2 reorganizando los argumentos en la llamada de función, pero que es académica, te podría quemar una llamada de función en esta normalmente.

EDIT:

Como se sugiere:

 
unsigned int fun (int blah, unsigned int n, unsigned int number) 
{ 
    number += ((blah!=0)&1)<<n; 
    return(number); 
} 

 
    subs r0, r0, #0 
    movne r0, #1 
    add r0, r2, r0, asl r1 
    bx lr 

sin duda más barato, y el código se ve bien, pero me molestaría hacer suposiciones de que el resultado de bla = 0, que es cero o todo lo que el compilador ha definido como verdadero siempre tiene el conjunto lsbit. No tiene que tener ese bit configurado para que el compilador genere código de trabajo. Tal vez las normas dictan el valor específico para verdadero. al volver a organizar los parámetros de la función, el número if (blah) + = ... también dará como resultado tres instrucciones de reloj individuales y no tendrá suposiciones.

Edit2:

En cuanto a lo que yo entiendo que es el estándar C99:

El == (igual a) y = (no iguales a) Los operadores son análogas a la relacional operadores a excepción de su menor precedencia. Cada uno de los operadores produce 1 si la relación especificada es verdadera y 0 si es falsa.

Lo que explica por qué la edición anterior funciona y por qué obtienes la movne r0, # 1 y no otro número aleatorio. El cartel hacía la pregunta con respecto a C pero también señalaba que ADA era el idioma actual, desde una perspectiva independiente del lenguaje no debe asumir "características" como la característica C anterior y usar un número if (blah) = número + (1 < < n). Pero esto se solicitó con una etiqueta C, por lo que el resultado más genérico (independiente del procesador) para C es, creo, el número + = (blah! = 0) < < n; Así que el comentario de Steven Wright tenía razón y debería obtener crédito por esto.

La suposición de los carteles también es básicamente correcta, si puede obtener bla en una forma 0 o 1, entonces usarlo en las matemáticas es más rápido en el sentido de que no hay ramificación. Conseguirlo en esa forma sin que sea más caro que una sucursal es el truco.

Answer 2

Si su idioma permite la multiplicación entre un booleano y un número, entonces sí, eso es más rápido que un condicional. Los condicionales requieren ramificación, lo que puede invalidar la tubería de la CPU. Además, si la rama es lo suficientemente grande, incluso puede causar un error en la caché en las instrucciones, aunque es poco probable en su pequeño ejemplo.

Answer 3

No existe una respuesta general a esta pregunta, esto depende mucho de su compilador y CPU. La CPU moderna tiene instrucciones de movimiento condicional, por lo que todo es posible.

Las únicas formas de saberlo aquí son inspeccionar el ensamblador que se produce (generalmente -S como opción de compilación) y medir.

Answer 4

Lo mantendría con el condicional. No debe preocuparse por los detalles de optimización de bajo nivel en este punto. Escriba el código que mejor describa su algoritmo y confíe en su compilador. En algunas CPU, la multiplicación es más lenta (por ejemplo, procesadores ARM que tienen condicionales en cada instrucción). También podría usar la expresión?: Que optimiza mejor bajo algunos compiladores. Por ejemplo:

number += (blah ? 2^n : 0); 

Si por alguna razón este pequeño cálculo es el cuello de botella de la aplicación después de perfilar luego preocuparse por la optimización de bajo nivel.

Answer 5

En C, con respecto a bla * 2^n: ¿Tiene alguna razón para creer que bla toma los valores 0 y 1? El lenguaje solo promete que 0 < -> FALSO y (todo lo demás) < -> VERDADERO. C le permite multiplicar un temporal "booleano" con otro número, pero el resultado no está definido, excepto en la medida en que result = 0 < => el bool era falso o el número era cero.

En Ada, con respecto a bla * 2^n: El lenguaje no define un operador de multiplicación en tipo Booleano. Por lo tanto, bla no puede ser un bool y multiplicarse.

Answer 6

En cualquier caso, no puede evitar una derivación (internamente), ¡así que no intente!

En

number = number + blah*2^n 

la plena expresión siempre tendrá que ser evaluado, a menos que el compilador es suficientemente inteligente como para detenerse cuando bla es 0. Si lo es, usted obtendrá una rama si bla es 0. Si no es así, siempre obtienes un caro multiplicar. En caso de que blah sea falso, también obtendrá el complemento y la asignación innecesarios.

En la instrucción "if then", la instrucción solo hará el agregado y la asignación cuando blah sea verdadero.

En resumen, la respuesta a su pregunta en este caso es "sí".

Answer 7

En Ada ...

La formulación original:

if Blah then 
    Number := Number + (2 ** N); 
end if; 

La formulación general alternativa, suponiendo Blah es de tipo booleano y Número y N son de tipos adecuados:

Number := Number + (Boolean'pos(Blah) * (2 ** N)); 

(Para N y Number de tipos de coma flotante o entero definidos por el usuario, es posible que se requieran definiciones adecuadas y conversiones de tipo ., El punto clave aquí es la construcción Boolean'pos(), que Ada garantías le dará un 0 o 1 para el tipo booleano predefinido)

En cuanto a si esto es más rápido o no, estoy de acuerdo con @Cthutu:

Lo mantendría con el condicional. No debería preocuparse por los detalles de optimización de bajo nivel en este punto. Escriba el código que mejor describe su algoritmo y confíe en su compilador .

Answer 8

Generaly, y particularmente cuando se trabaja con Ada, no debe preocuparse por problemas de micro-optimización como este. Escriba su código para que esté claro para el lector, y solo preocúpese por el rendimiento cuando tenga un problema con el rendimiento, y haga que se rastree hasta esa parte del código.

Diferentes CPU tienen diferentes necesidades, y pueden ser increíblemente complejas. Por ejemplo, en este caso, que es más rápido, depende mucho de la configuración de la tubería de su CPU, qué hay en la memoria caché en ese momento y cómo funciona la unidad de predicción de sucursal. Parte del trabajo de tu compilador es ser un experto en esas cosas, y hará un mejor trabajo que todos excepto los mejores programadores de ensamblaje. Certianly mejor que usted (o yo).

Así que solo preocúpate por escribir un buen código y deja que el compilador se preocupe por hacer un código de máquina eficiente.

Answer 9

Este código muestra que funcionan de manera similar, pero la multiplicación suele ser un poco más rápida.

@Test 
public void manual_time_trial() 
{ 
    Date beforeIfElse = new Date(); 
    if_else_test(); 
    Date afterIfElse = new Date(); 
    long ifElseDifference = afterIfElse.getTime() - beforeIfElse.getTime(); 
    System.out.println("If-Else Diff: " + ifElseDifference); 

    Date beforeMultiplication = new Date(); 
    multiplication_test(); 
    Date afterMultiplication = new Date(); 
    long multiplicationDifference = afterMultiplication.getTime() - beforeMultiplication.getTime(); 
    System.out.println("Mult Diff : " + multiplicationDifference); 

} 

private static long loopFor = 100000000000L; 
private static short x = 200; 
private static short y = 195; 
private static int z; 

private static void if_else_test() 
{ 
    short diff = (short) (y - x); 
    for(long i = 0; i < loopFor; i++) 
    { 
     if (diff < 0) 
     { 
      z = -diff; 
     } 
     else 
     { 
      z = diff; 
     } 
    } 
} 

private static void multiplication_test() 
{ 
    for(long i = 0; i < loopFor; i++) 
    { 
     short diff = (short) (y - x); 
     z = diff * diff; 
    } 
} 

Answer 10

Para el problema indicado, de hecho hay expresiones simples en C que pueden producir un código eficiente.

El n ésima potencia de 2 se puede calcular con el operador << como 1 << n, siempre n es menor que el número de bits de valor en una int.

Si blah es una boolean, a saber, un int con un valor de 0 o 1, su fragmento de código puede escribirse:

number += blah << n; 

Si blah es cualquier tipo escalar que puede ser probado para su verdad valor como if (blah), la expresión es ligeramente más elaborado:

number += !!blah << n; 

que es equivalente a number += (blah != 0) << n;

La prueba sigue presente pero, para las arquitecturas modernas, el código generado no tendrá saltos, como se puede verificar en línea usando Godbolt's compiler explorer.