¿La multiplicación y división utilizando operadores de cambio en C es realmente más rápida?

La multiplicación y la división se pueden lograr utilizando operadores de bits, por ejemplo

i*2 = i<<1 i*3 = (i<<1) + i; i*10 = (i<<3) + (i<<1) 

y así.

¿Es realmente más rápido usar decir (i<<3)+(i<<1) multiplicar con 10 que usar i*10 directamente? ¿Hay algún tipo de entrada que no se pueda multiplicar o dividir de esta manera?

Respuesta corta: no es probable.

Respuesta larga: su comstackdor tiene un optimizador que sabe cómo multiplicar tan rápido como la architecture de su procesador de destino es capaz. Su mejor apuesta es decirle claramente al comstackdor su intención (es decir, i * 2 en lugar de i << 1) y dejar que decida cuál es la secuencia de ensamblaje / código de máquina más rápida. Incluso es posible que el propio procesador haya implementado la instrucción de multiplicar como una secuencia de cambios y agrega microcódigos.

En resumen, no pases mucho tiempo preocupándote por esto. Si quieres cambiar, cambia. Si quieres multiplicar, multiplicar. Haz lo que es semánticamente claro: tus compañeros de trabajo te lo agradecerán más tarde. O, más probablemente, te maldiga más tarde si lo haces de otra manera.

Solo un punto de medida concreto: hace muchos años, comparé dos versiones de mi algoritmo hash:

 unsigned hash( char const* s ) { unsigned h = 0; while ( *s != '\0' ) { h = 127 * h + (unsigned char)*s; ++ s; } return h; } 

y

 unsigned hash( char const* s ) { unsigned h = 0; while ( *s != '\0' ) { h = (h << 7) - h + (unsigned char)*s; ++ s; } return h; } 

En cada máquina en la que lo comparé, la primera fue al menos tan rápida como la segunda. Sorprendentemente, a veces era más rápido (por ejemplo, en un Sun Sparc). Cuando el hardware no era compatible con la multiplicación rápida (y la mayoría no lo hacía en aquel entonces), el comstackdor convertía la multiplicación en las combinaciones apropiadas de turnos y agregaba / sub. Y como conocía el objective final, a veces podía hacerlo con menos instrucciones que cuando escribía explícitamente los cambios y los add / subs.

Tenga en cuenta que esto fue algo así como hace 15 años. Afortunadamente, los comstackdores solo han mejorado desde entonces, así que puedes contar con que el comstackdor hará lo correcto, probablemente mejor que tú. (Además, la razón por la que el código se ve tan C'ish es porque fue hace más de 15 años. Obviamente usaría std::string e iteradores hoy).

Además de todas las otras buenas respuestas aquí, permítanme señalar otra razón para no usar cambio cuando se refiere a dividir o multiplicar. Nunca he visto a alguien presentar un error al olvidar la relativa precedencia de la multiplicación y la sum. He visto errores introducidos cuando los progtwigdores de mantenimiento olvidaron que “multiplicar” a través de un cambio es lógicamente una multiplicación pero no sintácticamente de la misma precedencia que la multiplicación. x * 2 + z y x << 1 + z son muy diferentes!

Si está trabajando en números , utilice operadores aritméticos como + - * / % . Si está trabajando en matrices de bits, utilice operadores de giros de bits como & ^ | >> & ^ | >> . No los mezcles; una expresión que tiene ambos movimientos de bits y aritmética es un error que está por ocurrir.

Esto depende del procesador y el comstackdor. Algunos comstackdores ya optimizan el código de esta manera, otros no. Por lo tanto, debe verificar cada vez que su código debe optimizarse de esta manera.

A menos que necesite optimizar desesperadamente, no codificaría mi código fuente solo para guardar una instrucción de ensamblaje o un ciclo de procesador.

¿Es realmente más rápido usar decir (i << 3) + (i << 1) multiplicar con 10 que usar i * 10 directamente?

Puede que esté o no en su máquina; si le importa, mida su uso en el mundo real.

Un caso de estudio: de 486 a Core i7

El benchmarking es muy difícil de hacer de manera significativa, pero podemos ver algunos hechos. Desde http://www.penguin.cz/~literakl/intel/s.html#SAL y http://www.penguin.cz/~literakl/intel/i.html#IMUL obtenemos una idea de los ciclos de reloj x86 necesario para el cambio aritmético y la multiplicación. Digamos que nos atenemos a “486” (el más nuevo en la lista), 32 bit registra e instántanea, IMUL toma 13-42 ciclos e IDIV 44. Cada SAL toma 2 y agrega 1, por lo que incluso con algunos de ellos juntos se desplaza superficialmente como un ganador

En estos días, con el núcleo i7:

(desde http://software.intel.com/en-us/forums/showthread.php?t=61481 )

La latencia es 1 ciclo para una sum entera y 3 ciclos para una multiplicación entera . Puede encontrar las latencias y la producción en el Apéndice C del “Manual de referencia de optimización de architectures Intel® 64 e IA-32”, que se encuentra en http://www.intel.com/products/processor/manuals/ .

(de algún anuncio de Intel)

Usando SSE, el Core i7 puede emitir instrucciones simultáneas de agregar y multiplicar, lo que resulta en una tasa máxima de 8 operaciones de punto flotante (FLOP) por ciclo de reloj

Eso te da una idea de cuán lejos han llegado las cosas. La trivia de optimización, como el cambio de bit frente a * , que se tomó en serio incluso en los años 90, ahora es obsoleta. El cambio de bit es aún más rápido, pero para mul-div sin potencia de dos para cada uno de los turnos y para agregar los resultados, es más lento nuevamente. Luego, más instrucciones significan más fallas de caché, más problemas potenciales en la canalización, más uso de registros temporales puede significar más ahorro y restauración del contenido de registro de la stack … rápidamente se vuelve demasiado complicado para cuantificar definitivamente todos los impactos, pero son predominantemente negativo.

funcionalidad en código fuente vs implementación

De manera más general, su pregunta está etiquetada C y C ++. Como lenguajes de 3ª generación, están diseñados específicamente para ocultar los detalles del conjunto de instrucciones de la CPU subyacente. Para satisfacer sus estándares de idioma, deben soportar operaciones de multiplicación y desplazamiento (y muchas otras) incluso si el hardware subyacente no lo hace . En tales casos, deben sintetizar el resultado requerido usando muchas otras instrucciones. Del mismo modo, deben proporcionar soporte de software para operaciones de punto flotante si la CPU no tiene y no hay FPU. Las CPU modernas son compatibles con * y << , por lo que esto puede parecer absurdamente teórico e histórico, pero lo importante es que la libertad de elegir la implementación va en ambos sentidos: incluso si la CPU tiene una instrucción que implementa la operación solicitada en el código fuente En el caso general, el comstackdor puede elegir libremente otra cosa que prefiera porque es mejor para el caso específico al que se enfrenta el comstackdor.

Ejemplos (con un lenguaje ensamblador hipotético)

 source literal approach optimised approach #define N 0 int x; .word x xor registerA, registerA x *= N; move x -> registerA move x -> registerB A = B * immediate(0) store registerA -> x ...............do something more with x............... 

Las instrucciones como exclusivo o ( xor ) no tienen relación con el código fuente, pero xor -ing cualquier cosa con sí mismo borra todos los bits, por lo que se puede usar para establecer algo en 0. El código fuente que implica direcciones de memoria puede no implicar ningún uso .

Este tipo de hacks se han utilizado durante el tiempo que las computadoras han existido. En los primeros días de 3GL, para garantizar la aceptación del desarrollador, la salida del comstackdor tenía que satisfacer el desarrollo de lenguaje de ensamblaje de optimización de mano hardcore existente. comunidad que el código producido no fue más lento, más detallado o de otro modo peor. Los comstackdores rápidamente adoptaron muchas optimizaciones excelentes: se convirtieron en una mejor tienda centralizada de lo que podría ser cualquier progtwigdor de lenguaje ensamblador individual, aunque siempre existe la posibilidad de que pierdan una optimización específica que resulta crucial en un caso específico: los humanos a veces pueden agrégalo y busca algo mejor mientras los comstackdores solo hacen lo que les han dicho hasta que alguien les devuelva esa experiencia.

Entonces, incluso si cambiar y agregar es aún más rápido en algún hardware en particular, entonces es probable que el comstackdor haya resuelto exactamente cuando es seguro y beneficioso.

Mantenibilidad

Si su hardware cambia, puede volver a comstackrlo y verá la CPU objective y tomará otra mejor decisión, mientras que es poco probable que quiera volver a visitar sus "optimizaciones" o enumerar qué entornos de comstackción deberían usar multiplicación y cuál debería cambiar. ¡Piensa en todas las "optimizaciones" sin potencia de dos bits modificadas escritas hace más de 10 años que ahora están ralentizando el código en el que se encuentran, ya que se ejecuta en procesadores modernos ...!

Afortunadamente, buenos comstackdores como GCC pueden reemplazar una serie de cambios de bits y aritmética con una multiplicación directa cuando se habilita cualquier optimización (es decir ...main(...) { return (argc << 4) + (argc << 2) + argc; } -> imull $21, 8(%ebp), %eax ) por lo que una recomstackción puede ayudar incluso sin corregir el código, pero eso no está garantizado.

El extraño código de cambio de bits implementando multiplicación o división es mucho menos expresivo de lo que intentabas lograr conceptualmente, por lo que otros desarrolladores se confundirán por eso, y un progtwigdor confuso es más propenso a introducir errores o eliminar algo esencial en un esfuerzo por restaurar la cordura aparente. Si solo hace cosas no obvias cuando son realmente tangiblemente beneficiosas, y luego las documenta bien (pero de todos modos no documenta otras cosas que sean intuitivas), todos estarán más felices.

Soluciones generales versus soluciones parciales

Si tiene algún conocimiento adicional, como que su int realmente solo almacenará los valores x , y y z , entonces podrá descifrar algunas instrucciones que funcionen para esos valores y obtener su resultado más rápidamente que cuando el comstackdor no tiene esa idea y necesita una implementación que funcione para todos los valores int . Por ejemplo, considere su pregunta:

La multiplicación y la división se pueden lograr utilizando operadores de bits ...

Usted ilustra la multiplicación, pero ¿qué hay de la división?

 int x; x >> 1; // divide by 2? 

De acuerdo con el estándar C ++ 5.8:

-3- El valor 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 firmado y un valor no negativo, el valor del resultado es la parte integral del cociente de E1 dividido entre la cantidad 2 elevada a la potencia E2. Si E1 tiene un tipo firmado y un valor negativo, el valor resultante está definido por la implementación.

Por lo tanto, su cambio de bit tiene un resultado definido de implementación cuando x es negativo: puede no funcionar de la misma manera en máquinas diferentes. Pero, / funciona mucho más predeciblemente. (Puede que tampoco sea perfectamente consistente, ya que diferentes máquinas pueden tener diferentes representaciones de números negativos, y por lo tanto diferentes rangos incluso cuando hay la misma cantidad de bits que componen la representación).

Puede decir "No me importa ... que int esté almacenando la edad del empleado, nunca puede ser negativo". Si tiene ese tipo de conocimiento especial, entonces sí, su comstackción puede pasar por alto su optimización segura a menos que lo haga explícitamente en su código. Pero, es arriesgado y rara vez útil, la mayor parte del tiempo no tendrá este tipo de información, y otros progtwigdores que trabajen en el mismo código no sabrán que ha apostado a la casa sobre algunas expectativas inusuales de la información que usted ' ll estar manejando ... lo que parece un cambio totalmente seguro para ellos podría ser contraproducente debido a su "optimización".

¿Hay algún tipo de entrada que no se pueda multiplicar o dividir de esta manera?

Sí ... como se mencionó anteriormente, los números negativos tienen un comportamiento definido de implementación cuando se "divide" mediante un cambio de bit.

Acabo de probar mi máquina comstackndo esto:

 int a = ...; int b = a * 10; 

Cuando se desarma produce salida:

 MOV EAX,DWORD PTR SS:[ESP+1C] ; Move a into EAX LEA EAX,DWORD PTR DS:[EAX+EAX*4] ; Multiply by 5 without shift ! SHL EAX, 1 ; Multiply by 2 using shift 

Esta versión es más rápida que su código optimizado a mano con cambio y adición puros.

Realmente nunca sabes lo que el comstackdor va a producir, así que es mejor simplemente escribir una multiplicación normal y dejar que optimice la forma en que lo desea, excepto en casos muy precisos donde sabes que el comstackdor no puede optimizar.

El cambio es generalmente mucho más rápido que la multiplicación en un nivel de instrucción, pero es posible que esté perdiendo el tiempo haciendo optimizaciones prematuras. El comstackdor puede realizar estas optimizaciones en tiempo de comstackción. Hacerlo usted mismo afectará la legibilidad y posiblemente no tenga ningún efecto en el rendimiento. Probablemente solo valga la pena hacer cosas como esta si tiene un perfil y encontró que esto es un cuello de botella.

En realidad, el truco de división, conocido como “división mágica” en realidad puede rendir enormes recompensas. Nuevamente debe hacer un perfil primero para ver si es necesario. Pero si lo usa hay progtwigs útiles para ayudarlo a descubrir qué instrucciones son necesarias para la misma semántica de división. Aquí hay un ejemplo: http://www.masm32.com/board/index.php?topic=12421.0

Un ejemplo que he levantado del hilo OP en MASM32:

 include ConstDiv.inc ... mov eax,9999999 ; divide eax by 100000 cdiv 100000 ; edx = quotient 

Generaría:

 mov eax,9999999 mov edx,0A7C5AC47h add eax,1 .if !CARRY? mul edx .endif shr edx,16 

Las instrucciones de multiplicar Shift e Integer tienen un rendimiento similar en la mayoría de las CPU modernas: las instrucciones de multiplicar enteros fueron relativamente lentas en la década de 1980, pero en general esto ya no es cierto. Las instrucciones de multiplicar enteros pueden tener una latencia más alta, por lo que puede haber casos en los que sea preferible un cambio. Lo mismo ocurre con los casos en los que puede mantener ocupadas más unidades de ejecución (aunque esto puede cortar en ambos sentidos).

La división de enteros sigue siendo relativamente lenta, por lo que usar un cambio en lugar de división con una potencia de 2 sigue siendo una victoria, y la mayoría de los comstackdores implementarán esto como una optimización. Sin embargo, tenga en cuenta que para que esta optimización sea válida, el dividendo debe ser sin signo o debe ser positivo. ¡Por un dividendo negativo, el cambio y la división no son equivalentes!

 #include  int main(void) { int i; for (i = 5; i >= -5; --i) { printf("%d / 2 = %d, %d >> 1 = %d\n", i, i / 2, i, i >> 1); } return 0; } 

Salida:

 5 / 2 = 2, 5 >> 1 = 2 4 / 2 = 2, 4 >> 1 = 2 3 / 2 = 1, 3 >> 1 = 1 2 / 2 = 1, 2 >> 1 = 1 1 / 2 = 0, 1 >> 1 = 0 0 / 2 = 0, 0 >> 1 = 0 -1 / 2 = 0, -1 >> 1 = -1 -2 / 2 = -1, -2 >> 1 = -1 -3 / 2 = -1, -3 >> 1 = -2 -4 / 2 = -2, -4 >> 1 = -2 -5 / 2 = -2, -5 >> 1 = -3 

Entonces, si quiere ayudar al comstackdor, asegúrese de que la variable o expresión en el dividendo esté explícitamente sin firmar.

Depende completamente del dispositivo de destino, el idioma, el propósito, etc.

Pixel crujiendo en un controlador de tarjeta de video? Muy probablemente, si!

Aplicación empresarial .NET para su departamento? Absolutamente ninguna razón para mirarlo.

Para un juego de alto rendimiento para un dispositivo móvil, vale la pena investigarlo, pero solo después de que se hayan realizado optimizaciones más sencillas.

No lo haga a menos que sea absolutamente necesario y la intención de su código requiere cambio en lugar de multiplicación / división.

En un día normal, usted podría ahorrar potentiamente algunos ciclos de la máquina (o perder, ya que el comstackdor sabe mejor qué optimizar), pero el costo no vale la pena: usted gasta tiempo en detalles menores en lugar del trabajo real, mantener el código se vuelve más difícil y tus compañeros de trabajo te maldecirán.

Es posible que deba hacerlo para cálculos de carga alta, donde cada ciclo guardado significa minutos de tiempo de ejecución. Sin embargo, debe optimizar un lugar a la vez y realizar pruebas de rendimiento cada vez para ver si realmente lo hizo más rápido o rompió la lógica de los comstackdores.

Hasta donde yo sé, en algunas máquinas la multiplicación puede necesitar hasta 16 a 32 ciclos de máquina. Entonces , dependiendo del tipo de máquina, los operadores de desplazamiento de bits son más rápidos que la multiplicación / división.

Sin embargo, ciertas máquinas tienen su procesador matemático, que contiene instrucciones especiales para la multiplicación / división.

Estoy de acuerdo con la respuesta marcada de Drew Hall. La respuesta podría usar algunas notas adicionales.

Para la gran mayoría de los desarrolladores de software, el procesador y el comstackdor ya no son relevantes para la pregunta. La mayoría de nosotros está mucho más allá del 8088 y MS-DOS. Tal vez solo sea relevante para aquellos que todavía están desarrollando procesadores integrados …

En mi compañía de software, Math (add / sub / mul / div) debe usarse para todas las matemáticas. Mientras Shift se debe utilizar al convertir entre tipos de datos, p. Ej. ushort a byte como n >> 8 y no n / 256.

En el caso de los enteros con signo y el cambio a la derecha frente a la división, puede marcar la diferencia. Para los números negativos, las rondas de cambio se redondean hacia el infinito negativo mientras que la división se redondea hacia cero. Por supuesto, el comstackdor cambiará la división a algo más económico, pero por lo general lo cambiará a algo que tenga el mismo comportamiento de redondeo que la división, porque no puede demostrar que la variable no será negativa o simplemente no lo hace. cuidado. Entonces, si puede probar que un número no será negativo o si no le importa de qué manera lo hará, puede hacer esa optimización de una manera que sea más probable que haga la diferencia.

Prueba de Python que realiza la misma multiplicación 100 millones de veces contra los mismos números aleatorios.

 >>> from timeit import timeit >>> setup_str = 'import scipy; from scipy import random; scipy.random.seed(0)' >>> N = 10*1000*1000 >>> timeit('x=random.randint(65536);', setup=setup_str, number=N) 1.894096851348877 # Time from generating the random #s and no opperati >>> timeit('x=random.randint(65536); x*2', setup=setup_str, number=N) 2.2799630165100098 >>> timeit('x=random.randint(65536); x << 1', setup=setup_str, number=N) 2.2616429328918457 >>> timeit('x=random.randint(65536); x*10', setup=setup_str, number=N) 2.2799630165100098 >>> timeit('x=random.randint(65536); (x << 3) + (x<<1)', setup=setup_str, number=N) 2.9485139846801758 >>> timeit('x=random.randint(65536); x // 2', setup=setup_str, number=N) 2.490908145904541 >>> timeit('x=random.randint(65536); x / 2', setup=setup_str, number=N) 2.4757170677185059 >>> timeit('x=random.randint(65536); x >> 1', setup=setup_str, number=N) 2.2316000461578369 

Entonces al hacer un cambio en lugar de la multiplicación / división por un poder de dos en python, hay una ligera mejoría (~ 10% para la división, ~ 1% para la multiplicación). Si no es potencia de dos, es probable que haya una desaceleración considerable.

De nuevo, estos #s cambiarán dependiendo de su procesador, su comstackdor (o intérprete, lo hizo en python para simplificar).

Como con todos los demás, no optimice prematuramente. Escriba un código muy legible, si el perfil no es lo suficientemente rápido, y luego intente optimizar las partes lentas. Recuerde, su comstackdor es mucho mejor en optimización que usted.

Hay optimizaciones que el comstackdor no puede hacer porque solo funcionan para un conjunto reducido de entradas.

Debajo hay un código de muestra de C ++ que puede hacer una división más rápida haciendo una “multiplicación por el recíproco” de 64bits. Tanto el numerador como el denominador deben estar debajo de cierto umbral. Tenga en cuenta que debe comstackrse para usar instrucciones de 64 bits para ser realmente más rápido que la división normal.

 #include  #include  static const unsigned s_bc = 32; static const unsigned long long s_p = 1ULL << s_bc; static const unsigned long long s_hp = s_p / 2; static unsigned long long s_f; static unsigned long long s_fr; static void fastDivInitialize(const unsigned d) { s_f = s_p / d; s_fr = s_f * (s_p - (s_f * d)); } static unsigned fastDiv(const unsigned n) { return (s_f * n + ((s_fr * n + s_hp) >> s_bc)) >> s_bc; } static bool fastDivCheck(const unsigned n, const unsigned d) { // 32 to 64 cycles latency on modern cpus const unsigned expected = n / d; // At least 10 cycles latency on modern cpus const unsigned result = fastDiv(n); if (result != expected) { printf("Failed for: %u/%u != %u\n", n, d, expected); return false; } return true; } int main() { unsigned result = 0; // Make sure to verify it works for your expected set of inputs const unsigned MAX_N = 65535; const unsigned MAX_D = 40000; const double ONE_SECOND_COUNT = 1000000000.0; auto t0 = std::chrono::steady_clock::now(); unsigned count = 0; printf("Verifying...\n"); for (unsigned d = 1; d <= MAX_D; ++d) { fastDivInitialize(d); for (unsigned n = 0; n <= MAX_N; ++n) { count += !fastDivCheck(n, d); } } auto t1 = std::chrono::steady_clock::now(); printf("Errors: %u / %u (%.4fs)\n", count, MAX_D * (MAX_N + 1), (t1 - t0).count() / ONE_SECOND_COUNT); t0 = t1; for (unsigned d = 1; d <= MAX_D; ++d) { fastDivInitialize(d); for (unsigned n = 0; n <= MAX_N; ++n) { result += fastDiv(n); } } t1 = std::chrono::steady_clock::now(); printf("Fast division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT); t0 = t1; count = 0; for (unsigned d = 1; d <= MAX_D; ++d) { for (unsigned n = 0; n <= MAX_N; ++n) { result += n / d; } } t1 = std::chrono::steady_clock::now(); printf("Normal division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT); getchar(); return result; } 

Creo que en el primer caso que quiera multiplicar o dividir por una potencia de dos, no se puede equivocar al usar los operadores de bitshift, incluso si el comstackdor los convierte en un MUL / DIV, porque algunos microcodificadores de procesadores (realmente, un macro) de todos modos, entonces para esos casos logrará una mejora, especialmente si el cambio es más de 1. O más explícitamente, si la CPU no tiene operadores de cambio de bits, será un MUL / DIV de todos modos, pero si la CPU tiene operadores bitshift, se evita una twig de microcódigo y estas son algunas instrucciones menos.

Estoy escribiendo un código ahora que requiere muchas operaciones de doblar / reducir a la mitad porque está trabajando en un árbol binario denso, y hay una operación más que sospecho que podría ser más óptima que una adición: una izquierda (poder de dos multiplicar) ) cambiar con una adición. Esto se puede reemplazar con un desplazamiento a la izquierda y un xor si el cambio es más ancho que el número de bits que desea agregar, ejemplo fácil es (i << 1) ^ 1, que agrega uno a un valor duplicado. This does not of course apply to a right shift (power of two divide) because only a left (little endian) shift fills the gap with zeros.

In my code, these multiply/divide by two and powers of two operations are very intensively used and because the formulae are quite short already, each instruction that can be eliminated can be a substantial gain. If the processor does not support these bitshift operators, no gain will happen but neither will there be a loss.

Also, in the algorithms I am writing, they visually represent the movements that occur so in that sense they are in fact more clear. The left hand side of a binary tree is bigger, and the right is smaller. As well as that, in my code, odd and even numbers have a special significance, and all left-hand children in the tree are odd and all right hand children, and the root, are even. In some cases, which I haven’t encountered yet, but may, oh, actually, I didn’t even think of this, x&1 may be a more optimal operation compared to x%2. x&1 on an even number will produce zero, but will produce 1 for an odd number.

Going a bit further than just odd/even identification, if I get zero for x&3 I know that 4 is a factor of our number, and same for x%7 for 8, and so on. I know that these cases have probably got limited utility but it’s nice to know that you can avoid a modulus operation and use a bitwise logic operation instead, because bitwise operations are almost always the fastest, and least likely to be ambiguous to the compiler.

I am pretty much inventing the field of dense binary trees so I expect that people may not grasp the value of this comment, as very rarely do people want to only perform factorisations on only powers of two, or only multiply/divide powers of two.