tuning - programacion java

¿Por qué es ineficaz(variable1% variable2== 0)?

Question

Soy nuevo en Java, y estaba ejecutando algunos códigos anoche, y esto realmente me molestó. Estaba creando un programa simple para mostrar todas las salidas X en un bucle for, y noté una disminución MASIVA en el rendimiento, cuando usé el módulo como variable % variable frente a variable % 5000 o lo que sea. ¿Puede alguien explicarme por qué esto es y qué lo está causando? Para que pueda ser mejor ...

Aquí está el código "eficiente" (perdón si me equivoco un poco de sintaxis, no estoy usando el código en este momento)

long startNum = 0;
long stopNum = 1000000000L;
for (long i = startNum; i <= stopNum; i++){
if (i % 50000 == 0) {
System.out.println(i);
}
}

Aquí está el "código ineficiente"

long startNum = 0;
long stopNum = 1000000000L;
long progressCheck = 50000;
for (long i = startNum; i <= stopNum; i++){
if (i % progressCheck == 0) {
System.out.println(i);
}
}

Ten en cuenta que tenía una variable de fecha para medir las diferencias, y una vez que se hizo lo suficientemente larga, la primera tomó 50 ms, mientras que la otra tomó 12 segundos o algo así. Es posible que tenga que aumentar el stopNum o disminuir el progressCheck stopNum si su PC es más eficiente que la mía o no.

Busqué esta pregunta en la web, pero no puedo encontrar una respuesta, tal vez no esté haciendo la pregunta correctamente.

EDIT: No esperaba que mi pregunta fuera tan popular, agradezco todas las respuestas. Realicé un punto de referencia en cada mitad del tiempo empleado, y el código ineficiente tardó considerablemente más tiempo, 1/4 de segundo frente a 10 segundos de dar o recibir. Es cierto que están usando println, pero los dos están haciendo la misma cantidad, así que no me imagino que eso lo alteraría mucho, especialmente porque la discrepancia es repetible. En cuanto a las respuestas, ya que soy nuevo en Java, dejaré que los votos decidan por el momento cuál es la mejor respuesta. Intentaré elegir uno para el miércoles.

EDIT2: Voy a hacer otra prueba esta noche, donde en lugar de módulo, solo incrementa una variable, y cuando llega a progressCheck, realizará una, y luego restablecerá esa variable a 0. para una tercera opción.

EDIT3.5:

Utilicé este código, y a continuación mostraré mis resultados. ¡Gracias a todos por la maravillosa ayuda! También traté de comparar el valor corto del valor largo a 0, por lo que todas mis nuevas comprobaciones se producen "65536" cada vez, haciéndolo igual en repeticiones.

public class Main {
public static void main(String[] args) {
long startNum = 0;
long stopNum = 1000000000L;
long progressCheck = 65536;
final long finalProgressCheck = 50000;
long date;
// using a fixed value
date = System.currentTimeMillis();
for (long i = startNum; i <= stopNum; i++) {
if (i % 65536 == 0) {
System.out.println(i);
}
}
long final1 = System.currentTimeMillis() - date;
date = System.currentTimeMillis();
//using a variable
for (long i = startNum; i <= stopNum; i++) {
if (i % progressCheck == 0) {
System.out.println(i);
}
}
long final2 = System.currentTimeMillis() - date;
date = System.currentTimeMillis();
// using a final declared variable
for (long i = startNum; i <= stopNum; i++) {
if (i % finalProgressCheck == 0) {
System.out.println(i);
}
}
long final3 = System.currentTimeMillis() - date;
date = System.currentTimeMillis();
// using increments to determine progressCheck
int increment = 0;
for (long i = startNum; i <= stopNum; i++) {
if (increment == 65536) {
System.out.println(i);
increment = 0;
}
increment++;
}
//using a short conversion
long final4 = System.currentTimeMillis() - date;
date = System.currentTimeMillis();
for (long i = startNum; i <= stopNum; i++) {
if ((short)i == 0) {
System.out.println(i);
}
}
long final5 = System.currentTimeMillis() - date;
System.out.println(
"/nfixed = " + final1 + " ms " + "/nvariable = " + final2 + " ms " + "/nfinal variable = " + final3 + " ms " + "/nincrement = " + final4 + " ms" + "/nShort Conversion = " + final5 + " ms");
}
}

Resultados:

• fijo = 874 ms (normalmente alrededor de 1000 ms, pero más rápido debido a que tiene una potencia de 2)
• variable = 8590 ms
• variable final = 1944 ms (fue ~ 1000ms cuando se usaron 50000)
• incremento = 1904 ms
• Conversión corta = 679 ms

No es sorprendente, debido a la falta de división, la Conversión Corta fue un 23% más rápida que la forma "rápida". Esto es interesante para tener en cuenta. Si necesita mostrar o comparar algo cada 256 veces (o aproximadamente) puede hacer esto y usar

if ((byte)integer == 0) {''Perform progress check code here''}

UNA NOTA FINAL DE INTERÉS, el uso de módulo en la "Variable declarada final" con 65536 (no es un número bonito) fue la mitad de la velocidad (más lenta) que el valor fijo. Donde antes estaba el benchmarking cerca de la misma velocidad.

Answer 1

Como otros han señalado, la operación de módulo general requiere una división para hacerse. En algunos casos, la división puede ser reemplazada (por el compilador) por una multiplicación. Pero ambos pueden ser lentos en comparación con la suma / resta. Por lo tanto, el mejor rendimiento puede esperarse por algo en estas líneas:

long progressCheck = 50000;
long counter = progressCheck;
for (long i = startNum; i <= stopNum; i++){
if (--counter == 0) {
System.out.println(i);
counter = progressCheck;
}
}

(Como un pequeño intento de aprovechamiento, usamos un contador descendente de decremento aquí porque en muchas arquitecturas que se comparan con 0 inmediatamente después de una operación aritmética cuesta exactamente 0 instrucciones / ciclos de CPU porque los indicadores de ALU ya están establecidos correctamente por la operación anterior. sin embargo, la optimización del compilador hará esa optimización automáticamente incluso si escribe if (counter++ == 50000) { ... counter = 0; } .)

Tenga en cuenta que a menudo realmente no quiere / necesita módulo, porque sabe que su contador de bucles ( i ) o lo que sea solo se incrementa en 1, y realmente no le importa el resto real que le dará el módulo, solo ver si el contador de incremento por uno alcanza algún valor.

Otro ''truco'' es usar valores / límites de potencia de dos, por ejemplo, progressCheck = 1024; . El módulo de una potencia de dos puede calcularse rápidamente a través de bits and , es decir, if ( (i & (1024-1)) == 0 ) {...} . Esto también debería ser bastante rápido, y en algunas arquitecturas puede superar al counter explícito anterior.

Answer 2

En el seguimiento de @phuclv comment , verifiqué el código generado por JIT ¹ , los resultados son los siguientes:

para la variable % 5000 (división por constante):

mov rax,29f16b11c6d1e109h
imul rbx
mov r10,rbx
sar r10,3fh
sar rdx,0dh
sub rdx,r10
imul r10,rdx,0c350h ; <-- imul
mov r11,rbx
sub r11,r10
test r11,r11
jne 1d707ad14a0h

para variable % variable :

mov rax,r14
mov rdx,8000000000000000h
cmp rax,rdx
jne 22ccce218edh
xor edx,edx
cmp rbx,0ffffffffffffffffh
je 22ccce218f2h
cqo
idiv rax,rbx ; <-- idiv
test rdx,rdx
jne 22ccce218c0h

Debido a que la división siempre lleva más tiempo que la multiplicación, el último fragmento de código tiene menos rendimiento.

Versión de Java:

java version "11" 2018-09-25
Java(TM) SE Runtime Environment 18.9 (build 11+28)
Java HotSpot(TM) 64-Bit Server VM 18.9 (build 11+28, mixed mode)

^{1 - Opciones de VM utilizadas: -XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print,src/java/Main.main}

Answer 3

También me sorprende ver el rendimiento de los códigos anteriores. Se trata del tiempo que toma el compilador para ejecutar el programa según la variable declarada. En el segundo ejemplo (ineficiente):

for (long i = startNum; i <= stopNum; i++) {
if (i % progressCheck == 0) {
System.out.println(i)
}
}

Está realizando la operación de módulo entre dos variables. Aquí, el compilador debe verificar el valor de stopNum y progressCheck para ir al bloque de memoria específico ubicado para estas variables cada vez después de cada iteración, ya que es una variable y su valor puede cambiar.

Es por eso que, después de cada compilación de iteraciones, fue a la ubicación de la memoria para verificar el último valor de las variables. Por lo tanto, en el momento de la compilación, el compilador no pudo crear un código de bytes eficiente.

En el primer ejemplo de código, está realizando un operador de módulo entre una variable y un valor numérico constante que no cambiará dentro de la ejecución y el compilador no necesita verificar el valor de ese valor numérico desde la ubicación de la memoria. Es por eso que el compilador fue capaz de crear un código de bytes eficiente. Si declara progressCheck como una variable final o como una variable final static , en el momento del compilador en tiempo de ejecución sabrá que es una variable final y su valor no va a cambiar, entonces el compilador reemplaza el progressCheck con el código:

for (long i = startNum; i <= stopNum; i++) {
if (i % 50000== 0) {
System.out.println(i)
}
}

Ahora puede ver que este código también se parece al primer ejemplo de código (eficiente). El rendimiento del primer código y como mencionamos anteriormente, ambos códigos funcionarán de manera eficiente. No habrá mucha diferencia en el tiempo de ejecución de ninguno de los dos ejemplos de código.

Answer 4

Usted está midiendo el trozo de OSR (reemplazo en la pila) .

El código auxiliar OSR es una versión especial del método compilado diseñado específicamente para transferir la ejecución del modo interpretado al código compilado mientras se ejecuta el método.

Los apéndices OSR no están tan optimizados como los métodos regulares, ya que necesitan un diseño de marco compatible con el marco interpretado. Ya mostré esto en las siguientes respuestas: 1 , 2 , 3 .

Algo similar sucede aquí también. Mientras que el "código ineficiente" está ejecutando un bucle largo, el método se compila especialmente para el reemplazo en la pila dentro del bucle. El estado se transfiere desde el marco interpretado al método compilado por OSR, y este estado incluye la variable local progressCheck . En este punto, JIT no puede reemplazar la variable con la constante y, por lo tanto, no puede aplicar ciertas optimizaciones como la reducción de la fuerza .

En particular, esto significa que JIT no reemplaza la división entera con la multiplicación . (Consulte ¿Por qué GCC usa la multiplicación por un número extraño en la implementación de la división de enteros? Para el truco asm de un compilador de tiempo adelantado, cuando el valor es una constante de tiempo de compilación después de la alineación / propagación de constantes, si esas optimizaciones están habilitadas . Un derecho literal entero en la expresión % también se optimiza por gcc -O0 , similar a aquí donde está optimizado por el JITer incluso en un stub OSR).

Sin embargo, si ejecuta el mismo método varias veces, la segunda ejecución y las posteriores ejecutarán el código regular (no OSR), que está totalmente optimizado. Aquí hay una referencia para probar la teoría ( comparada con JMH ):

@State(Scope.Benchmark)
public class Div {
@Benchmark
public void divConst(Blackhole blackhole) {
long startNum = 0;
long stopNum = 100000000L;
for (long i = startNum; i <= stopNum; i++) {
if (i % 50000 == 0) {
blackhole.consume(i);
}
}
}
@Benchmark
public void divVar(Blackhole blackhole) {
long startNum = 0;
long stopNum = 100000000L;
long progressCheck = 50000;
for (long i = startNum; i <= stopNum; i++) {
if (i % progressCheck == 0) {
blackhole.consume(i);
}
}
}
}

Y los resultados:

# Benchmark: bench.Div.divConst
# Run progress: 0,00% complete, ETA 00:00:16
# Fork: 1 of 1
# Warmup Iteration 1: 126,967 ms/op
# Warmup Iteration 2: 105,660 ms/op
# Warmup Iteration 3: 106,205 ms/op
Iteration 1: 105,620 ms/op
Iteration 2: 105,789 ms/op
Iteration 3: 105,915 ms/op
Iteration 4: 105,629 ms/op
Iteration 5: 105,632 ms/op
# Benchmark: bench.Div.divVar
# Run progress: 50,00% complete, ETA 00:00:09
# Fork: 1 of 1
# Warmup Iteration 1: 844,708 ms/op <-- much slower!
# Warmup Iteration 2: 105,893 ms/op <-- as fast as divConst
# Warmup Iteration 3: 105,601 ms/op
Iteration 1: 105,570 ms/op
Iteration 2: 105,475 ms/op
Iteration 3: 105,702 ms/op
Iteration 4: 105,535 ms/op
Iteration 5: 105,766 ms/op

La primera iteración de divVar es mucho más lenta, debido a un stub OSR ineficientemente compilado. Pero tan pronto como el método se vuelve a ejecutar desde el principio, se ejecuta la nueva versión sin restricciones que aprovecha todas las optimizaciones del compilador disponibles.