c# - sumar - ¿Cambiar los bits más rápido que multiplicar y dividir en Java?.¿RED?
suma resta multiplicacion y division en java netbeans (13)
Casi cualquier entorno que valga la pena optimizará esto para usted. Y si no es así, tienes peces más grandes para freír. En serio, no pierdas ni un segundo más pensando en esto. Sabrá cuándo tiene problemas de rendimiento. Y después de ejecutar un generador de perfiles, sabrá qué lo está causando, y debería estar bastante claro cómo solucionarlo.
Nunca escuchará a nadie decir "mi aplicación fue demasiado lenta, entonces comencé a reemplazar aleatoriamente x * 2 con x << 1 y todo se solucionó". Los problemas de rendimiento generalmente se resuelven al encontrar una manera de hacer un orden de magnitud menos de trabajo, no al encontrar la manera de hacer el mismo trabajo un 1% más rápido.
El desplazamiento de bits hacia la izquierda y hacia la derecha es aparentemente más rápido que las operaciones de multiplicación y división en la mayoría de las CPU, tal vez incluso en todas, si usa una potencia de 2. Sin embargo, puede reducir la claridad del código para algunos lectores y algunos algoritmos. ¿El cambio de bit es realmente necesario para el rendimiento, o puedo esperar que el compilador o VM detecte el caso y lo optimice (en particular, cuando el poder de 2 es un literal)? Estoy interesado principalmente en el comportamiento de Java y .NET, pero también me gustan las implementaciones de otros lenguajes.
De acuerdo con los resultados de este microbenchmark , el desplazamiento es dos veces más rápido que la división (Oracle Java 1.7.0_72).
En las computadoras que probé, las divisiones enteras son de 4 a 10 veces más lentas que otras operaciones.
Cuando los compiladores pueden reemplazar las divisiones por múltiplos de 2 y no ver ninguna diferencia, las divisiones por múltiplos de 2 no son significativamente más lentas.
Por ejemplo, tengo un programa (gráfico) con muchas divisiones muchas por 255. En realidad, mi cálculo es:
r = (((top.R - bottom.R) * alpha + (bottom.R * 255)) * 0x8081) >> 23;
Puedo asegurarme de que es mucho más rápido que mi cálculo anterior:
r = ((top.R - bottom.R) * alpha + (bottom.R * 255)) / 255;
entonces no, los compiladores no pueden hacer todos los trucos de optimización.
Es casi seguro que dependa de la optimización de la multiplicación de la potencia literal de dos para una operación de cambio. Esta es una de las primeras optimizaciones que aprenderán los estudiantes de construcción de compiladores. :)
Sin embargo, no creo que haya ninguna garantía para esto. Su código fuente debe reflejar su intención , en lugar de tratar de decirle al optimizador qué hacer. Si está haciendo una cantidad más grande, use la multiplicación. Si está moviendo un campo de bit de un lugar a otro (piense en la manipulación del color RGB), use una operación de desplazamiento. De cualquier manera, su código fuente reflejará lo que realmente está haciendo.
Es dependiente del hardware. Si hablamos de microcontrolador o i386, el cambio puede ser más rápido, pero, como indican varias respuestas, el compilador generalmente hará la optimización por usted.
En el hardware moderno (Pentium Pro y más allá), la canalización hace que esto sea totalmente irrelevante y alejarse de los caminos trillados generalmente significa que perderá muchas más optimizaciones de las que puede obtener.
Las micro optimizaciones no solo son una pérdida de tiempo, sino que también son extremadamente difíciles de corregir.
Este es un análisis del punto de referencia hecho por Savvas Dalkitsis. Aunque esta prueba verifica la velocidad de multiplicación sobre el cambio de bit, los valores utilizados no son los mismos, verifique el código a continuación en C # que muestra los valores)
for (int i = 0, j = 1, k = 1; i < 10; i++)
{
j = j * 2;
k <<= 2;
Console.WriteLine("{0} {1}", j, k);
}
El código equivalente del ejemplo de Savvas Dalkitsis con los valores mostrados en C # será
public static void Main(String[] args)
{
for (int i = 0, j = 1, k = 1; i < 10; i++)
{
j = j * 2; k <<= 2;
Console.WriteLine("{0} {1}", j, k);
}
Console.WriteLine("-----------------------------------------------");
DateTime before = DateTime.Now;
for (int j = 1; j < 500000000; j++)
{
int a = 1;
for (int i = 0; i < 10; i++) a *= 2;
}
DateTime after = DateTime.Now;
Console.WriteLine("Multiplying " + (after - before).ToString() + " milliseconds");
before = DateTime.Now;
for (int j = 1; j < 500000000; j++)
{
int a = 1;
for (int i = 0; i < 10; i++) a = a << 1;
}
after = DateTime.Now;
Console.WriteLine("Shifting " + (after - before).ToString() + " milliseconds");
Console.ReadKey();
}
Estoy asombrado ya que acabo de escribir este código y me di cuenta de que cambiar por uno es en realidad más lento que multiplicar por 2.
(EDIT: cambió el código para dejar de desbordarse después de la sugerencia de Michael Myers, pero los resultados son los mismos! ¿Qué pasa aquí?)
import java.util.Date;
public class Test {
public static void main(String[] args) {
Date before = new Date();
for (int j = 1; j < 50000000; j++) {
int a = 1 ;
for (int i = 0; i< 10; i++){
a *=2;
}
}
Date after = new Date();
System.out.println("Multiplying " + (after.getTime()-before.getTime()) + " milliseconds");
before = new Date();
for (int j = 1; j < 50000000; j++) {
int a = 1 ;
for (int i = 0; i< 10; i++){
a = a << 1;
}
}
after = new Date();
System.out.println("Shifting " + (after.getTime()-before.getTime()) + " milliseconds");
}
}
Los resultados son:
Multiplicando 639 milisegundos
Cambiando 718 milisegundos
La mayoría de los compiladores convertirán la multiplicación y la división en cambios de bits cuando corresponda. Es una de las optimizaciones más fáciles de hacer. Entonces, debes hacer lo que sea más fácil de leer y apropiado para la tarea dada.
Los humanos están equivocados en estos casos.
99% cuando tratan de adivinar un compilador moderno (y todos los futuros).
99.9% cuando tratan de adivinar los JIT modernos (y todos los futuros) al mismo tiempo.
99.999% cuando intentan adivinar las optimizaciones de CPU modernas (y todas las futuras).
Programe de una manera que describa con precisión lo que quiere lograr, no cómo hacerlo. Las futuras versiones de JIT, VM, compilador y CPU se pueden mejorar y optimizar de forma independiente. Si especifica algo tan pequeño y específico, perderá el beneficio de todas las optimizaciones futuras.
Preguntaría "¿qué estás haciendo que importaría?". Primero diseñe su código para legibilidad y facilidad de mantenimiento. La probabilidad de que hacer un cambio de bit en la multiplicación estándar hará que la diferencia en el rendimiento sea EXTREMADAMENTE pequeña.
Si el compilador (constante de tiempo de compilación) o JIT (constante de tiempo de ejecución) sabe que el divisor o el multiplicando es una potencia de dos y se está realizando una aritmética entera, la convertirá en un cambio para usted.
Tenga en cuenta que desplazar hacia abajo y dividir la división (en Java, por supuesto) dará resultados diferentes para los números negativos e impares.
int a = -7;
System.out.println("Shift: "+(a >> 1));
System.out.println("Div: "+(a / 2));
Huellas dactilares:
Shift: -4
Div: -3
Como Java no tiene ningún número sin signo, no es realmente posible que un compilador de Java lo optimice.
La mayoría de los compiladores de hoy harán más que convertir multiplicar o dividir por una potencia de dos para cambiar las operaciones. Al optimizar, muchos compiladores pueden optimizar una multiplicación o división con una constante de tiempo de compilación incluso si no es una potencia de 2. A menudo una multiplicación o división se puede descomponer en una serie de cambios y agregaciones, y si esa serie de operaciones será más rápida que multiplicar o dividir, el compilador lo usará.
Para la división por una constante, el compilador a menudo puede convertir la operación en una multiplicación por un "número mágico" seguido de un cambio. Este puede ser un gran ahorro de tiempo en el ciclo del reloj ya que la multiplicación es a menudo mucho más rápida que una operación de división.
El libro de Henry Warren, Hacker''s Delight, tiene una gran cantidad de información sobre este tema, que también se cubre bastante bien en el sitio web complementario:
Ver también una discusión (con un enlace o dos) en:
De todos modos, todo esto se reduce a permitir que el compilador se ocupe de los detalles tediosos de las micro-optimizaciones. Han pasado años desde que hacer sus propios turnos fue más astuto que el compilador.