¿Qué es más rápido: x << 1 ox << 10?

No quiero optimizar nada, lo juro, solo quiero hacer esta pregunta por curiosidad. Sé que en la mayoría del hardware hay un comando de ensamblaje de bit-shift (por ejemplo shl, shr), que es un solo comando. Pero, ¿importa (nanosegundos o CPU) cuántos bits desplaza? En otras palabras, ¿alguno de los siguientes es más rápido en cualquier CPU?

x << 1;

y

x << 10;

Y por favor no me odies por esta pregunta. :)

Depende potencialmente de la CPU.

Sin embargo, todas las CPU modernas (x86, ARM) utilizan un "cambiador de barril", un módulo de hardware diseñado específicamente para realizar cambios arbitrarios en tiempo constante.

Así que la conclusión es ... no. Ninguna diferencia.

Algunos procesadores integrados solo tienen una instrucción de "cambio en uno". En tales procesadores, el compilador cambiaría x << 3a ((x << 1) << 1) << 1.

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

El Intel 8051, que tiene muchos derivados modernos, tampoco puede cambiar un número arbitrario de bits.

Hay muchos casos sobre esto.

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

2. Si MPU tiene solo 1 bit de desplazamiento x << 10, normalmente sería más lento, ya que se hace principalmente con 10 turnos o copia de bytes con 2 turnos.

3. Pero hay un caso común conocido en el x << 10que sería incluso más rápido que x << 1. Si x es de 16 bits, solo hay que tener cuidado con los 6 bits inferiores (todos los demás se desplazarán), por lo que MPU solo debe cargar un byte inferior, por lo que solo debe realizar un ciclo de acceso a la memoria de 8 bits, mientras que x << 10necesita dos ciclos de acceso. Si el ciclo de acceso es más lento que el cambio (y borra el byte inferior), x << 10será más rápido. Esto puede aplicarse a microcontroladores con ROM de programa integrada rápida mientras se accede a una RAM de datos externa lenta.

4. Además del caso 3, el compilador puede preocuparse por el número de bits significativos x << 10y optimizar las operaciones adicionales para las de menor ancho, como reemplazar la multiplicación 16x16 por 16x8 uno (ya que el byte más bajo es siempre cero).

Tenga en cuenta que algunos microcontroladores no tienen ninguna instrucción de desplazamiento a la izquierda, sino que utilizan add x,x.

En ARM, esto se puede hacer como efecto secundario de otra instrucción. Entonces, potencialmente, no hay latencia en absoluto para ninguno de ellos.

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

Eso depende tanto de la CPU como del compilador. Incluso si la CPU subyacente tiene un desplazamiento de bits arbitrario con un desplazador 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 se "define por implementación". En lugar de preocuparse demasiado por la velocidad, preocúpese de obtener la misma respuesta en diferentes implementaciones.

Citando de la sección 3.3.7 de ANSI C:

3.3.7 Operadores de desplazamiento bit a bit

Sintaxis

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

Restricciones

Cada uno de los operandos tendrá un tipo integral.

Semántica

Las promociones integrales se realizan en cada uno de los operandos. El tipo de resultado es el del operando izquierdo promovido. Si el valor del operando derecho es negativo o es mayor o igual que el ancho en bits del operando izquierdo promovido, el comportamiento no está definido.

El resultado de E1 << E2 es E1 posiciones de bit E2 desplazadas a la izquierda; los bits vacíos se rellenan con ceros. Si E1 tiene un tipo unsigned, el valor del resultado es E1 multiplicado por la cantidad, 2 elevado a la potencia E2, módulo reducido ULONG_MAX + 1 si E1 tiene un tipo unsigned long, UINT_MAX + 1 en caso contrario. (Las constantes ULONG_MAX y UINT_MAX se definen en el encabezado).

El resultado de E1 >> E2 es E1 posiciones de bit E2 desplazadas a la derecha. Si E1 tiene un tipo sin signo o si E1 tiene un tipo con signo y un valor no negativo, el valor del resultado es la parte integral del cociente de E1 dividido por la cantidad, 2 elevado a la potencia E2. Si E1 tiene un tipo con signo y un valor negativo, el valor resultante está definido por la implementación.

Entonces:

x = y << z;

"<<": y × 2 ^z ( indefinido si se produce un desbordamiento);

x = y >> z;

">>": definido por la implementación para firmado (la mayoría de las veces, el resultado del cambio aritmético: y / 2 ^z ).

Es concebible que, en un procesador de 8 bits, en x<<1realidad sea mucho más lento que x<<10para un valor de 16 bits.

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

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

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

byte1 = (byte2 << 2)
byte2 = 0

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

En algunas generaciones de CPU Intel (¿P2 o P3? Aunque no AMD, si mal no recuerdo), las operaciones de cambio de bits son ridículamente lentas. Sin embargo, el cambio de bits de 1 bit siempre debería ser rápido, ya que solo puede usar la suma. Otra cuestión a considerar es si los desplazamientos de bits en un número constante de bits son más rápidos que los desplazamientos de longitud variable. Incluso si los códigos de operación tienen la misma velocidad, en x86 el operando no constante de la mano derecha de un desplazamiento de bits debe ocupar el registro CL, lo que impone restricciones adicionales en la asignación de registros y puede ralentizar el programa de esa manera también.

Como siempre, depende del contexto del código circundante : por ejemplo, ¿está utilizando x<<1como índice de matriz? ¿O agregarlo 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 acabara teniendo que cambiar. Sin mencionar el intercambio total de rendimiento vs. latencia vs. cuellos de botella de front-end. El rendimiento de un pequeño fragmento no es unidimensional.

Las instrucciones de cambio de hardware no son la única opción de un compilador para compilar x<<1, pero las otras respuestas suponen principalmente eso.

x << 1es exactamente equivalente ax+x para enteros sin signo y complemento a 2 con signo. Los compiladores siempre saben a qué hardware se dirigen mientras compilan, por lo que pueden aprovechar trucos como este.

En Intel Haswell , addtiene un rendimiento de 4 por reloj, pero shlcon un recuento inmediato tiene solo 2 por rendimiento de reloj. (Consulte http://agner.org/optimize/ para obtener tablas de instrucciones y otros enlaces en elx86etiqueta wiki). Los cambios de vector SIMD son 1 por reloj (2 en Skylake), pero las adiciones de enteros vectoriales 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 shldónde está implícita la cuenta en el código de operación. 8086 no tenía turnos de conteo inmediato, solo por uno y por clregistro. Esto es sobre todo relevante para los desplazamientos a la derecha, porque solo puede agregar para desplazamientos a la izquierda a menos que esté desplazando 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,1o add eax,eaxes un byte más corto que shl eax,10, y el tamaño del código puede afectar directamente (decodificar / cuellos de botella de front-end) o indirectamente (fallas de caché de código L1I) afectar el rendimiento.

De manera más general, los recuentos 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 de uso común en estos días son 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. (huevo 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 + desplazamiento es común en situaciones en las que xaún se necesita el valor original de . Pero la mayoría de las instrucciones de enteros x86 funcionan in situ. (El destino es una de las fuentes para instrucciones como addo shl). La convención de llamadas de System V x86-64 pasa args en registros, con el primer argumento ediy el valor de retorno eax, por lo que una función que devuelve x<<10también hace que el compilador emita copy + shift código.

La LEAinstrucció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 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 1 ciclo de latencia y 2 por reloj en CPU recientes de Intel y AMD. (Familia Sandybridge y Bulldozer / Ryzen). En Intel, es solo 1 rendimiento por reloj con latencia de 3c para lea eax, [rdi + rsi + 123]. (Relacionado: ¿Por qué este código C ++ es más rápido que mi ensamblaje escrito a mano para probar la conjetura de Collatz? Entra en esto en detalle).

De todos modos, copiar + desplazar por 10 necesita una movinstrucción separada . Puede ser una latencia cero en muchas CPU recientes, pero aún requiere ancho de banda de front-end y tamaño de código. ( ¿Puede el MOV de x86 ser realmente "gratuito"? ¿Por qué no puedo reproducirlo? )

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 otras operaciones .

Por ejemplo, if(x<<1) { }podría usar an andpara verificar todos los bits excepto el bit alto. En x86, usaría una testinstrucción, como test eax, 0x7fffffff/ en jz .falselugar de shl eax,1 / jz. Esta optimización funciona para cualquier recuento de turnos, y también funciona en máquinas donde los turnos de recuento grande 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 muchas instrucciones de extracción / inserción de campos de bits. O ARM tiene cambios de operandos fuente como parte de cualquier otra instrucción. (Por lo tanto, las instrucciones de cambio / rotación son solo una forma especial de moveusar una fuente desplazada).

Recuerde, C no es lenguaje ensamblador . Siempre observe la salida optimizada del compilador cuando esté ajustando su código fuente para compilar de manera eficiente.