En C++, ¿qué es más rápido? (2 * i + 1) o (i << 1 | 1)?

Question

Me doy cuenta de que la respuesta probablemente sea específica del hardware, pero tengo curiosidad por saber si me faltaba una intuición más general.

me preguntó this pregunta & dado la respuesta, ahora me pregunto si debería cambiar mi enfoque en general a utilizar "(i < < 1 | 1)" en lugar de "(2 * i + 1)"? ?

Answer 1

Solo un experimento con respuestas dadas sobre "...que va a utilizar LEA ":
El siguiente código:

int main(int argc, char **argv) 
{ 
#ifdef USE_SHIFTOR 
return (argc << 1 | 1); 
#else 
return (2 * argc + 1); 
#endif 
} 

voluntad, con gcc -fomit-frame-pointer -O8 -m{32|64} (para 32 o 64 bits) compilar en el siguiente código de montaje:

1. x86, de 32 bits:

   080483a0 <main>: 
   80483a0: 8b 44 24 04    mov 0x4(%esp),%eax 
   80483a4: 8d 44 00 01    lea 0x1(%eax,%eax,1),%eax 
   80483a8: c3      ret

2. x86, de 64 bits:

   00000000004004c0 <main>: 
   4004c0: 8d 44 3f 01    lea 0x1(%rdi,%rdi,1),%eax 
   4004c4: c3      retq

3. x86 de 64 bits en -DUSE_SHIFTOR:

   080483a0 <main>: 
   80483a0: 8b 44 24 04    mov 0x4(%esp),%eax 
   80483a4: 01 c0     add %eax,%eax 
   80483a6: 83 c8 01    or  $0x1,%eax 
   80483a9: c3      ret

4. x86, de 32 bits, -DUSE_SHIFTOR:

   00000000004004c0 <main>: 
   4004c0: 8d 04 3f    lea (%rdi,%rdi,1),%eax 
   4004c3: 83 c8 01    or  $0x1,%eax 
   4004c6: c3      retq

De hecho, es cierto que la mayoría de los casos usarán LEA. Sin embargo, el código es no lo mismo para los dos casos. Hay dos razones para ello:

1. Además puede desbordarse y se envuelven alrededor, mientras que las operaciones de bits como << o | no puede
2. (x + 1) == (x | 1) sólo es cierto si !(x & 1) demás la adición se traslada a la siguiente bit. En general, agregar uno solo hace que el bit más bajo se establezca en la mitad de los casos.

Si bien nosotros (y el compilador, probablemente) sepamos que el segundo es necesariamente aplicable, el primero sigue siendo una posibilidad. Por lo tanto, el compilador crea código diferente, ya que la "o la versión" requiere forzar bit cero a 1.

Answer 2

Cualquier pero el compilador más con muerte cerebral verán esas expresiones como equivalentes y compilarlos con el mismo código ejecutable.

lo general no es realmente vale la pena preocuparse demasiado acerca de la optimización de expresiones aritméticas simples como estos, ya que es el tipo de cosas que los compiladores son los mejores en la optimización. (A diferencia de muchos otros casos en los que un "compilador inteligente" podría hacer lo correcto, pero un compilador real se cae).

Esto funcionará con el mismo par de instrucciones en PPC, Sparc y MIPS, por el camino: un cambio seguido de un complemento. En el ARM, se reducirá a una sola instrucción fusionada de desplazamiento-cambio, y en x86 probablemente sea un solo LEA op.

Answer 3

Dado que la norma ISO realidad no exigir requisitos de desempeño, esto dependerá de la aplicación, las opciones del compilador elegido, la CPU de destino y, posiblemente, la fase de la luna.

Este tipo de optimizaciones (ahorro de un par de ciclos) casi siempre se vuelven insignificantes en términos de retorno de la inversión, en contra de optimizaciones a nivel macro como la selección de algoritmo.

Objetivo para facilitar la lectura del código en primer lugar. Si su intención es cambiar los bits y OR, use la versión de desplazamiento de bit. Si tu intención es multiplicar, usa la versión *. Solo preocúpate por el rendimiento una vez que hayas establecido que hay un problema.

Cualquier compilador decente optimizará mucho mejor que se puede de todos modos :-)

Answer 4

salida de gcc con la opción -S (no hay opciones del compilador dado):

.LCFI3: 
     movl 8(%ebp), %eax 
     addl %eax, %eax 
     orl  $1, %eax 
     popl %ebp 
     ret 

.LCFI1: 
     movl 8(%ebp), %eax 
     addl %eax, %eax 
     addl $1, %eax 
     popl %ebp 
     ret 

No estoy seguro cuál es cuál, pero no creo que importe.

Si el compilador no hay optimizaciones en absoluto, entonces el segundo probablemente a traducir las instrucciones de montaje más rápidos. El tiempo que toma cada instrucción depende completamente de la arquitectura. La mayoría de los compiladores los optimizarán para que sean las mismas instrucciones de nivel de ensamblaje.

Answer 5

A nadie le importa. Tampoco deberían ellos.
Deje de preocuparse por eso y obtenga su código correcto, simple y listo.

Answer 6

i + i + 1 puede ser más rápido que otros dos, porque la adición es más rápida que la multiplicación y puede ser más rápida que el cambio.

Answer 7

Cuanto más rápido es la primera forma (la que tiene el desplazamiento a la derecha), de hecho, la instrucción shr toma 4 ciclos de reloj para completar en el peor de los casos, mientras que mul 10 en el mejor de los casos. Sin embargo, la mejor forma la debe decidir el compilador, ya que tiene una vista completa de las demás instrucciones (ensamblaje).

Answer 8

Acabo de probar esto con gcc-4.7.1 usando la fuente de Frankh, el código generado es

lea 0x1(%rdi,%rdi,1),%eax 
retq 

sin importar si se usa la versión de cambio o multiplicación.