Alternativa al uso del operador% y/operador en C++

Question

Se dice que el operador de módulo "%" y el operador de división "/" son muy ineficientes en C++ incorporado.

¿Cómo puedo alternativamente lograr el siguiente expresión:

a = b % c; 

entiendo que esto se puede lograr mediante la siguiente lógica:

a = b - c; 
while (a >= c) { 
    a = a - c; 
} 

Pero mi pregunta es, es el código que implica que los bucles while lo suficientemente eficiente, en comparación con% operador?

Gracias, Kirti

Answer 1

nada va a ser mucho más eficiente que el operador %. Si hubiera una mejor manera de hacerlo, cualquier compilador razonable lo convertiría automáticamente. Cuando le dicen que % y / son ineficaces, eso se debe a que son operaciones difíciles; si necesita realizar un módulo, hágalo.

Puede haber casos especiales cuando hay formas mejores, por ejemplo, mod una potencia de dos se puede escribir como un binario o - pero probablemente se hayan optimizado por su compilador.

Answer 2

La división y el módulo son costosas operaciones de hardware, hagas lo que hagas (esto está más relacionado con la arquitectura de hardware que con los lenguajes o compiladores), tal vez diez veces más lento que la suma.

^{Sin embargo, en los equipos portátiles o servidores actuales, y en los microcontroladores de gama alta, los errores cache suelen ser mucho más lentos que las divisiones.}

El compilador GCC a menudo puede optimizarlos, cuando el divisor es una constante.

Su circuito ingenuo suele ser mucho más lento que el uso de las instrucciones de división de hardware (o la rutina de la biblioteca que lo hace, si no lo proporciona el hardware). Creo que te equivocas al evitar la división & reemplazándola por tu lazo.

Puede ajustar sus algoritmos, por ejemplo, al tener el poder de dos, pero no recomiendo usar tu código. Recuerde que optimización prematura es malo así que primero intente hacer que su programa sea correcto, luego perfilelo para encontrar los puntos problemáticos.

Answer 3

Es casi seguro que el código será más lento que el procesador/compilador que decida realizar la división/modificación. En general, los atajos son bastante difíciles de conseguir para los operadores aritméticos básicos, ya que los diseñadores de mcu/cpu y los programadores de compiladores son bastante buenos para optimizar esto en casi todas las aplicaciones.

Un atajo común en dispositivos integrados (donde cada ciclo/byte puede marcar la diferencia) es mantener todo en términos de base-2 para usar los operadores de desplazamiento de bit para realizar multiplicación y división, y bitwise y (&) para realizar modulo.

Ejemplos:

unsigned int x = 100; 
unsigned int y1 = x << 4; // same as x * 2^4 = x*16 
unsigned int y2 = x >> 6; // same as x/2^6 = x/64 
unsigned int y3 = x & 0x07; // same as x % 8 

Answer 4

Si el divisor es conocido en tiempo de compilación, la operación se puede transformar en una multiplicación por un recíproco, con algunos cambios, adiciones y otras operaciones rápidas.Esto será más rápido en cualquier procesador moderno, incluso si implementa división en hardware. Los objetivos incrustados suelen tener rutinas altamente optimizadas para dividir/módulo, ya que estas operaciones son requeridas por el estándar.

Answer 5

La división por constante se puede lograr mediante un cambio si una potencia de 2 o una mul agregan la combinación de cambio para otros.

http: // masm32.com/board/index.php?topic=9937.0 tiene la versión de ensamblaje x86 y la fuente C en la descarga desde la primera publicación. que genera este código para ti.

Answer 6

Si ha perfilado su código con cuidado y encontró que un operador de módulo es el mayor costo en un bucle interno, entonces hay una optimización que podría ayudar. Es posible que ya están familiarizados con el truco para determinar el signo de un entero usando desplazamientos aritméticos izquierda (para los valores de 32 bits):

sign = (x >> 31) | 1; 

esto se extiende el bit de signo a través de la palabra, por lo que los valores negativos producen -1 y positivo valores 0. a continuación, el bit 0 se establece de modo que los valores positivos representan 1.

Si solo estamos incrementando los valores por una cantidad que es menor que el módulo entonces este mismo truco puede ser utilizado para envolver el resultado:

val += inc; 
val -= modulo & (static_cast<int32_t>(((modulo - 1) - val)) >> 31); 

Alternativamente, si está disminuyendo por valores menores que el módulo a continuación, el código en cuestión es:

int32_t signedVal = static_cast<int32_t>(val - dec); 
val = signedVal + (modulo & (signedVal >> 31)); 

He añadido los operadores static_cast porque yo estaba pasando en uint32_t, pero puede que no sea necesario encontrarlos.

¿Esto ayuda mucho a diferencia de un simple operador%? Eso depende de su compilador y arquitectura de CPU. Descubrí que un bucle simple funcionaba un 60% más rápido en mi procesador i3 cuando se compilaba con VS2012; sin embargo, en el chip ARM11 de Raspberry Pi y compilando con GCC solo obtuve una mejora del 20%.