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

No quiero optimizar nada, lo juro, solo quiero hacer esta pregunta por curiosidad. Sé que en la mayoría de los hardware hay un comando de ensamblado de cambio de bits (por ejemplo, shl , shr ), que es un solo comando. Pero, ¿importa (en nanosegundos o en cuanto al tacto de la CPU) cuántos bits cambia? 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 una “palanca de cambio”, 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 por uno”. En tales procesadores, el comstackdor 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 architectures 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 en esto.

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

  2. Si las MPU tienen 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.

  3. Pero se conoce un caso común en el que x << 10 sería incluso más rápido que x << 1 . Si x es de 16 bits, solo le importan 6 bits inferiores (todos los demás se desplazarán), por lo que las MPU solo necesitan cargar un byte inferior, por lo que solo deben realizar un ciclo de acceso único a la memoria de 8 bits, mientras que x << 10 necesitan 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 ROM de progtwig a bordo rápido mientras se accede a una RAM de datos externa lenta.

  4. Además del caso 3, el comstackdor puede preocuparse por la cantidad de bits significativos en x << 10 y optimizar las operaciones posteriores a las de menor ancho, como reemplazar la multiplicación 16x16 por una 16x8 (ya que el byte inferior siempre es cero).

Tenga en cuenta que algunos microcontroladores no tienen ninguna instrucción de desplazamiento hacia la izquierda, en su lugar usan add x,x .

En ARM, 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 comstackdor. Incluso si la CPU subyacente tiene un cambio de bit arbitrario con una palanca de cambios de barril, esto solo sucederá si el comstackdor se aprovecha de 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 es “implementación definida”. En lugar de preocuparse demasiado por la velocidad, tenga en cuenta que está obteniendo la misma respuesta en diferentes implementaciones.

Citando de la sección 3.3.7 de ANSI C:

3.3.7 Operadores de cambio bitwise

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 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; bits vacíos están llenos de ceros. Si E1 tiene un tipo sin signo, el valor del resultado es E1 multiplicado por la cantidad, 2 aumentados a la potencia E2, módulo reducido ULONG_MAX + 1 si E1 tiene el tipo sin signo largo, UINT_MAX + 1 de lo 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 se define por la implementación.

Asi que:

 x = y << z; 

"<<": y × 2 z ( no definido si se produce un desbordamiento);

 x = y >> z; 

">>": implementación definida para firmado (lo más frecuente es el resultado del cambio 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) 

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

 byte1 = (byte2 << 2) byte2 = 0 

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

En algunas generaciones de CPU Intel (¿P2 o P3? Sin embargo, no es AMD, si recuerdo bien), las operaciones de desplazamiento de bits son ridículamente lentas. Bitshift por 1 bit siempre debería ser rápido ya que solo puede usar la sum. Otra pregunta a considerar es si los desplazamientos de bits por 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 son de la misma velocidad, en x86, el operando derecho no constante de un cambio de bits debe ocupar el registro CL, que impone restricciones adicionales en la asignación de registros y puede ralentizar el progtwig de esa manera también.

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

Las instrucciones de un cambio de hardware no son la única opción de un comstackdor para comstackr x<<1 , pero las otras respuestas en su mayoría suponen eso.


x << 1 es exactamente equivalente a x+x para los enteros con signo complementado y sin signo de 2. Los comstackdores siempre saben qué hardware están dirigiendo mientras comstackn, por lo que pueden aprovechar trucos como este.

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

También hay una encoding especial de cambio de uno a uno donde el recuento está implícito en el código de operación. 8086 no tenía turnos de recuento inmediato, solo por uno y por registro cl . Esto es mayormente relevante para los turnos a la derecha, porque puede agregarlos para los turnos a la izquierda a menos que esté cambiando un operando de memoria. Pero si el valor se necesita más adelante, 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 (desencoding / cuellos de botella front-end) o indirectamente (falta de caché de código L1I) el rendimiento.

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


La necesidad de copiar + desplazar es común en situaciones en las que el valor original de x todavía es necesario. Pero la mayoría de las instrucciones de enteros x86 operan in situ. (El destino es una de las fonts para instrucciones como add o shl ). La convención de llamadas del sistema V del sistema x86-64 pasa argumentos en los registros, con el primer argumento en edi y el valor de retorno en eax , por lo que una función que devuelve x<<10 También hace que el comstackdor emita copia + código de desplazamiento.

La instrucción LEA le permite cambiar y agregar (con un número de turnos de 0 a 3, porque utiliza la encoding de la máquina en modo 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 comstackdor 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 reloj en las recientes CPU Intel y AMD. (Sandybridge-familia y Bulldozer / Ryzen). En Intel, es solo 1 por reloj con 3c de latencia para lea eax, [rdi + rsi + 123] . (Relacionado: ¿Por qué este código C ++ es más rápido que mi conjunto escrito a mano para probar la conjetura de Collatz? Entra en esto en detalle).

De todos modos, copy + shift by 10 necesita una instrucción de mov separado. Puede ser una latencia cero en muchas CPU recientes, pero aún así toma ancho de banda y tamaño de código de front-end. ( ¿Puede el MOV de x86 realmente ser "gratuito"? ¿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 comstackdor 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 and para verificar todos los bits excepto el bit alto. En x86, test eax, 0x7fffffff una instrucción de test , como test eax, 0x7fffffff / jz .false lugar de shl eax,1 / jz . Esta optimización funciona para cualquier conteo de turnos, y también funciona en máquinas donde los turnos de grandes conteos 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 turnos de operandos de origen como parte de cualquier otra instrucción. (Por lo tanto, las instrucciones de cambio / rotación son solo una forma especial de move , usando una fuente desplazada).

Recuerda, C no es lenguaje ensamblador . Siempre mire la salida del comstackdor optimizada cuando ajuste su código fuente para comstackr de manera eficiente.