c++ - ¿Cuál es más rápido: x<< 1 o x<< 10?

performance cpu (9)

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

x << 1;

x << 10;

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

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

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

El Intel 8051, que tiene muchos derivados modernos, tampoco puede desplazar una cantidad arbitraria de bits.

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

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

En algunas generaciones de CPUs de Intel (P2 o P3, aunque no AMD, si mal no recuerdo), las operaciones de cambio de bits son ridículamente lentas. Bitshift por 1 bit siempre debe 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 cambios de longitud variable. Incluso si los códigos de operación son de la misma velocidad, en x86 el operando no constante de la derecha de un cambio de bits debe ocupar el registro CL, lo que impone restricciones adicionales en la asignación del registro y también puede ralentizar el programa de esa manera.

Es concebible que, en un procesador de 8 bits, x<<1 realidad 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)

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

byte1 = (byte2 << 2) byte2 = 0

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

Eso depende tanto de la CPU como del compilador. Incluso si la CPU subyacente tiene un desplazamiento de bit arbitrario con una palanca de cambio de barril, esto solo ocurrirá si el compilador aprovecha ese recurso.

Tenga en cuenta que desplazar 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 es "implementación definida". En lugar de preocuparse demasiado por la velocidad, preocúpese de obtener la misma respuesta en diferentes implementaciones.

Citando de ANSI C sección 3.3.7:

3.3.7 Operadores de desplazamiento a nivel de bit
Sintaxis
shift-expression: additive-expression shift-expression << additive-expression shift-expression >> additive-expression
Restricciones
Cada uno de los operandos debe tener 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 sin signo, 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 el tipo sin signo largo, 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 firmado y un valor negativo, el valor resultante está definido por la implementación.

Asi que:

x = y << z;

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

x = y >> z;

">>": implementación definida para firmado (más a menudo el resultado del cambio aritmético: y / 2 ^z ).

Hay muchos casos sobre esto.

Muchas MPU de alta velocidad tienen una palanca de cambio de barril, un circuito electrónico similar a un multiplexor que realiza cualquier cambio en un tiempo constante.
Si MPU tiene solo un desplazamiento de 1 bit x << 10 normalmente sería más lento, ya que en su mayoría se realiza mediante 10 turnos o copia de bytes con 2 turnos.
Pero se conoce un caso común donde x << 10 sería incluso más rápido que x << 1 . Si x es 16 bit, solo 6 bits más bajos son cuidados (todos los demás se desplazarán), por lo que MPU solo necesita cargar un byte más bajo, por lo tanto, hacer solo un ciclo de acceso único 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 el cambio (y borra el byte inferior), x << 10 será más rápido. Esto puede aplicarse a los microcontroladores con una ROM de programa incorporada rápida mientras se accede a la RAM de datos externos lentos.
Como adición al caso 3, al compilador puede importarle el número de bits significativos en x << 10 y optimizar otras operaciones a los de menor ancho, como reemplazar la multiplicación de 16x16 por 16x8 (ya que el byte inferior siempre es cero).

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

Potencialmente depende de la CPU.

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

Entonces, el resultado final es ... no. Ninguna diferencia.

Como siempre, depende del contexto del código circundante : por ejemplo, ¿está utilizando x<<1 como un índice de matriz? ¿O agregarlo a algo más? En cualquier caso, los recuentos de turnos pequeños (1 o 2) a menudo se pueden optimizar incluso más que si el compilador acaba teniendo que cambiar. Por no mencionar el rendimiento total frente a la latencia frente a la compensación de los cuellos de botella. El rendimiento de un pequeño fragmento no es unidimensional.

Las instrucciones de cambio de hardware no son la única opción del compilador para compilar x<<1 , pero las demás respuestas lo asumen en su mayoría.

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

En Intel Haswell , add tiene un rendimiento de 4 por reloj, pero shl con un recuento inmediato tiene solo 2 por rendimiento de reloj. (Consulte http://agner.org/optimize/ para ver las tablas de instrucciones y otros enlaces en la wiki de la etiqueta x86 ). Los desplazamientos de vectores SIMD son 1 por reloj (2 en Skylake), pero los números enteros del vector SIMD son 2 por reloj (3 en Skylake). Latencia es la misma, sin embargo: 1 ciclo.

También hay una codificación especial shift-by-one de shl donde el conteo está implícito en el código de operación. 8086 no tuvo cambios de recuento inmediato, solo by-one y por cl register. Esto es principalmente relevante para los cambios a la derecha, ya que solo puede agregar 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 code-size puede directamente (descodificación / cuellos de botella del front-end) o indirectamente (falta de caché del código L1I) afectar el rendimiento.

En general, los recuentos de turnos 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 actualmente son RISC, y no tienen modos de direccionamiento de índice escalado, pero x86 es una arquitectura bastante común para que esto sea digno de mención. (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] ).

Necesitar copiar + cambio es común en situaciones donde el valor original de x todavía se necesita. Pero la mayoría de las instrucciones enteras x86 funcionan en el lugar. (El destino es una de las fuentes de instrucciones como add o shl .) La convención de llamadas System86 x86 pasa args en registros, con la primera arg en edi y el valor de retorno en eax , por lo que una función que devuelve x<<10 también hace que el compilador emita código copy + shift.

La instrucción LEA le permite cambiar-y-agregar (con un recuento de cambios de 0 a 3, porque usa codificación de máquina de 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 una latencia de 1 ciclo y un rendimiento de 2 por ciclo en las recientes CPU Intel y AMD. (Sandybridge-family y Bulldozer / Ryzen). En Intel, es solo 1 por procesamiento de reloj con latencia 3c para lea eax, [rdi + rsi + 123] . (Relacionado: .com/questions/40354978/… Entra en esto en detalle).

De todos modos, copiar + desplazar por 10 necesita una instrucción mov separado. Puede que tenga cero latencia en muchas CPU recientes, pero aún requiere el ancho de banda de entrada y el tamaño del 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 utilizando solo 2 instrucciones leales consecutivas en x86? .

El compilador también puede transformar el código que lo rodea para que no haya un cambio real, o se combina con otras operaciones .

Por ejemplo, if(x<<1) { } podría usar an and para verificar todos los bits excepto el bit alto. En x86, utilizaría una instrucción de test , como test eax, 0x7fffffff / jz .false lugar 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 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 muchas instrucciones para extraer / insertar campos de bits. O ARM tiene cambios de operandos fuente como parte de cualquier otra instrucción. (Entonces las instrucciones de cambio / rotación son solo una forma especial de move , usando una fuente desplazada).

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