Que es más rápido: x<

Algunos procesadores embebidos solo tienen una instrucción "shift-by-one". En tales procesadores, el compilador cambiaría x << 3 a ((x << 1) << 1) << 1.

Creo que el Motorola MC68HCxx fue una de las familias más populares con esta limitación. Afortunadamente, tales arquitecturas son ahora bastante raras, la mayoría ahora incluyen un cambio de barril con un tamaño de desplazamiento variable.

El Intel 8051, que tiene muchas derivadas modernas, tampoco puede mover un número arbitrario de bits.

Hay muchos casos sobre esto.

1. Muchos MPU de alta velocidad tienen un cambiador de barril, un circuito electrónico tipo multiplexor que hace cualquier cambio en tiempo constante.

2. Si MPU tiene solo 1 bit shift x << 10 normalmente sería más lento, ya que lo hace principalmente por 10 turnos o copiando bytes con 2 turnos.

3. Pero hay un caso común conocido donde x << 10 sería incluso más rápido que x << 1. Si x es 16 bits, solo 6 bits más bajos de él es cuidado (todos los demás serán shifted out), por lo que MPU necesita cargar solo bytes más bajos, por lo tanto hacer un solo ciclo de acceso a la memoria de 8 bits, mientras que x << 10 necesita dos ciclos de acceso. Si el ciclo de acceso es más lento que shift (y borrar byte más bajo), x << 10 será más rápido. Esto puede aplicarse a microcontroladores con una ROM de programa integrada rápida mientras acceden a una RAM de datos externa lenta.

4. Como adición al caso 3, el compilador puede preocuparse por el número de bits significativos en x << 10 y optimizar operaciones adicionales a las de menor ancho, como reemplazar la multiplicación de 16x16 con 16x8 uno (ya que el byte inferior siempre es cero).

Tenga en cuenta que algunos microcontroladores no tienen ninguna instrucción shift-left, usan add x,x en su lugar.

En el BRAZO, esto se puede hacer como un efecto secundario de otra instrucción. Así que potencialmente, no hay latencia en absoluto para ninguno de ellos.

Aquí está mi CPU favorita , en la que x<<2 toma el doble de tiempo que x<<1 :)

Eso depende tanto de la CPU como del compilador. Incluso si la CPU subyacente tiene un cambio de bits arbitrario con un cambio de barril, esto solo sucederá si el compilador aprovecha ese recurso.

Tenga en cuenta que cambiar cualquier cosa fuera del ancho en bits de los datos es un "comportamiento indefinido" en C y C++. El desplazamiento a la derecha de los datos firmados también está "definido por la implementación". En lugar de demasiada preocupación por la velocidad, estar preocupado de que usted está recibiendo la misma respuesta en diferentes aplicación.

Citando la sección 3.3.7 del ANSI C:

3.3.7 Operadores de desplazamiento a bit

Sintaxis

      shift-expression:
              additive-expression
              shift-expression <<  additive-expression
              shift-expression >>  additive-expression

Restricciones

Cada uno de los operandos tendrá tipo integral.

Semántica

Las promociones integrales son realizado en cada uno de los operandos. El tipo de resultado es el de la operando de izquierda promovido. Si el valor del operando derecho es negativo o es mayor o igual a la anchura en bits del operando de izquierda promovido, el el comportamiento es indefinido.

El resultado de E1

El resultado de E1 >> E2 is E1 posiciones de bits E2 desplazadas a la derecha. If E1 tiene un tipo sin signo o si E1 tiene un tipo firmado y valor no negativo, el valor del resultado es el parte integrante del cociente de E1 dividido por la cantidad, 2 elevado a el power E2 . Si E1 tiene una firma tipo y un valor negativo, el el valor resultante es implementación-definida.

Así que:

x = y << z;

"z (undefined si se produce un desbordamiento);

x = y >> z;

">>": implementación-definida para signed (la mayoría de las veces el resultado del desplazamiento aritmético: y / 2 ^z).

Es concebible que, en un procesador de 8 bits, x<<1 podría ser mucho más lento que x<<10 para un valor de 16 bits.

Por ejemplo, una traducción razonable de x<<1 puede ser:

byte1 = (byte1 << 1) | (byte2 >> 7)
byte2 = (byte2 << 1)

Considerando que x<<10 sería más simple:

byte1 = (byte2 << 2)
byte2 = 0

Observe cómo x<<1 cambia más a menudo e incluso más lejos que x<<10. Además, el resultado de x<<10 no depende del contenido del byte 1. Esto podría acelerar la operación adicionalmente.

En algunas generaciones de CPU Intel (P2 o P3? Aunque no AMD, si no recuerdo mal), las operaciones de bitshift son ridículamente lentas. Bitshift por 1 bit siempre debe ser rápido, ya que solo puede usar la adición. Otra pregunta a considerar es si los cambios de bits por un número constante de bits son más rápidos que los cambios de longitud variable. Incluso si los opcodes tienen la misma velocidad, en x86 el operando derecho no constante de un bitshift debe ocupar el registro CL, lo que impone restricciones adicionales en registre la asignación y puede ralentizar el programa de esa manera también.

Como siempre, depende del contexto de código circundante: por ejemplo, ¿está utilizando x<<1 como un índice de matriz? ¿O añadirlo a otra cosa? En cualquier caso, los recuentos de cambios pequeños (1 o 2) a menudo pueden optimizar incluso más que si el compilador termina teniendo que solo cambiar. Por no hablar de todo el rendimiento frente a latencia frente a cuellos de botella front-end. La interpretación de un pequeño fragmento no es unidimensional.

Las instrucciones de cambio de hardware no son las únicas del compilador opción para compilar x<<1, pero las otras respuestas están asumiendo principalmente eso.

x << 1 es exactamente equivalente a x+x para unsigned, y para los enteros firmados del complemento de 2. Los compiladores siempre saben a qué hardware se dirigen mientras compilan, por lo que pueden aprovechar trucos como este.

On Intel Haswell, add tiene un rendimiento de 4 por reloj, pero shl con un recuento inmediato solo tiene un rendimiento de 2 por reloj. (Ver http://agner.org/optimize / para tablas de instrucciones y otros enlaces en el wiki de etiquetas x86). Los cambios de vector SIMD son 1 por reloj (2 en Skylake), pero las adiciones de enteros de vector SIMD son 2 por reloj (3 en Skylake). Sin embargo, la latencia es la misma: 1 ciclo.

También hay una codificación especial shift-by-one de shl donde el recuento está implícito en el opcode. 8086 no tenía cambios de conteo inmediato, solo por uno y por registro cl. Esto es principalmente relevante para los cambios a la derecha, porque sólo se puede añadir para los cambios a la izquierda a menos que esté cambiando un operando de memoria. Pero si el valor se necesita más tarde, es mejor cargar primero en un registro. Pero de todos modos, shl eax,1 o add eax,eax es un byte más corto que shl eax,10, y el tamaño del código puede afectar directamente (descodificación / cuellos de botella front-end) o indirectamente (errores de caché de código L1I) al rendimiento.

Más generalmente, los conteos de cambios pequeños a veces se pueden optimizar en un índice escalado en un modo de direccionamiento en x86. La mayoría de las otras arquitecturas en el uso común en estos días es RISC, y no tienen modos de direccionamiento de índice escalado, pero x86 es una arquitectura lo suficientemente común como para que valga la pena mencionarlo. (por ejemplo, si está indexando una matriz de elementos de 4 bytes, hay espacio para aumentar el factor de escala en 1 para int arr[]; arr[x<<1]).

La necesidad de copiar+shift es común en situaciones donde el valor original de x todavía se necesita. Pero la mayoría de las instrucciones de enteros x86 operan en su lugar. (El destino es una de las fuentes para instrucciones como add o shl.) La convención de llamada del Sistema V x86-64 pasa args en registros, con el primer arg en edi y devuelve el valor en eax, por lo que una función que devuelve x<<10 también hace que el compilador emita código copy+shift.

El LEA la instrucción le permite cambiar y agregar (con un recuento de cambios de 0 a 3, porque utiliza codificación de máquina en modo de direccionamiento). Pone el resultado en un registro separado.

Gcc y clang optimizan estas funciones de la misma manera, como se puede ver en el explorador del compilador Godbolt:

int shl1(int x) { return x<<1; }
    lea     eax, [rdi+rdi]   # 1 cycle latency, 1 uop
    ret

int shl2(int x) { return x<<2; }
    lea     eax, [4*rdi]    # longer encoding: needs a disp32 of 0 because there's no base register, only scaled-index.
    ret

int times5(int x) { return x * 5; }
    lea     eax, [rdi + 4*rdi]
    ret

int shl10(int x) { return x<<10; }
    mov     eax, edi         # 1 uop, 0 or 1 cycle latency
    shl     eax, 10          # 1 uop, 1 cycle latency
    ret

LEA con 2 componentes tiene latencia de 1 ciclo y rendimiento de 2 por reloj en CPU Intel y AMD recientes. (Sandybridge-familia y Bulldozer / Ryzen). En Intel, es solo 1 rendimiento por reloj con latencia 3c para lea eax, [rdi + rsi + 123]. (Related: ¿Por qué este código C++ es más rápido que mi ensamblado escrito a mano para probar la conjetura de Collatz? entra en esto en detalle.)

De todos modos, copy + shift by 10 necesita un instrucción separada mov. Puede ser que sea latencia cero en muchas CPU recientes, pero todavía necesita ancho de banda de front-end y tamaño de código. ( ¿Puede el MOV de x86 ser realmente "libre"? ¿Por qué no puedo reproducir esto en absoluto?)

También relacionado: Cómo multiplicar un registro por 37 usando solo 2 instrucciones leales consecutivas en x86?.

El compilador también es libre de transformar el código circundante para que no haya un cambio real, o se combine con otros operaciones.

Por ejemplo if(x<<1) { } podría usar un and para comprobar todos los bits excepto el bit alto. En x86, usarías una instrucción test, como test eax, 0x7fffffff / jz .false en lugar de shl eax,1 / jz. Esta optimización funciona para cualquier cuenta de cambios, y también funciona en máquinas donde los cambios de gran cuenta son lentos (como Pentium 4), o inexistentes (algunos microcontroladores).

Muchas ISA tienen instrucciones de manipulación de bits más allá del simple cambio. por ejemplo, PowerPC tiene una gran cantidad de extracto / inserto de campo de bits instrucción. O ARM tiene cambios de operandos fuente como parte de cualquier otra instrucción. (Así que las instrucciones shift/rotate son solo una forma especial de move, usando una fuente desplazada.)

Recuerde, C no es lenguaje ensamblador. Siempre mira la salida del compilador optimizado cuando estés ajustando tu código fuente para compilar eficientemente.