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

Soy nuevo en Java, y estaba ejecutando algo de código anoche, y esto realmente me molestó. Estaba creando un programa simple para mostrar cada X salidas en un bucle for, y noté una disminución MASIVA en el rendimiento, cuando usé el módulo como variable % variablevs variable % 5000o no. ¿Puede alguien explicarme por qué es esto y qué lo está causando? Entonces puedo ser mejor ...

Aquí está el código "eficiente" (perdón si tengo un poco de sintaxis incorrecta, no estoy en la computadora con 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);
    }
}

Eso sí, tenía una variable de fecha para medir las diferencias, y una vez que se hizo lo suficientemente larga, la primera tardó 50 ms, mientras que la otra tardó 12 segundos o algo así. Es posible que tenga que aumentar stopNumo disminuir progressChecksi 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 simplemente no la estoy preguntando correctamente.

EDITAR: 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 tomó mucho más tiempo, 1/4 de segundo frente a 10 segundos más o menos. De acuerdo, están usando println, pero ambos están haciendo la misma cantidad, por lo que no me imagino que eso lo distorsione mucho, especialmente porque la discrepancia es repetible. En cuanto a las respuestas, dado que soy nuevo en Java, dejaré que los votos decidan por ahora qué respuesta es la mejor. 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 alcanza el Progreso de comprobación, realizará una, y luego restablecerá esa variable a 0. para una tercera opción.

EDITAR 3.5:

Usé este código, y a continuación mostraré mis resultados. ¡Gracias a TODOS por la maravillosa ayuda! También intenté comparar el valor corto del largo con 0, por lo que todas mis nuevas comprobaciones suceden "65536" veces, 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 es una potencia de 2)
• variable = 8590 ms
• variable final = 1944 ms (Fue ~ 1000ms cuando se usa 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 de notar. Si necesita mostrar o comparar algo cada 256 veces (o más allá), puede hacer esto y usar

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

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

Está midiendo el código auxiliar OSR (reemplazo en la pila) .

El código auxiliar de OSR es una versión especial del método compilado destinado específicamente a 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 normales, porque 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 "código ineficiente" ejecuta un ciclo largo, el método se compila especialmente para el reemplazo en la pila dentro del ciclo. El estado se transfiere del marco interpretado al método compilado por OSR, y este estado incluye progressCheckla variable local. 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 de enteros 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 adelantado, cuando el valor es una constante de tiempo de compilación después de la línea / propagación constante, si esas optimizaciones están habilitadas %También se optimiza un literal entero en la expresión gcc -O0, similar a aquí donde JITer lo optimiza incluso en un código auxiliar OSR).

Sin embargo, si ejecuta el mismo método varias veces, la segunda y las ejecuciones posteriores ejecutarán el código regular (no OSR), que está completamente optimizado. Aquí hay un punto de 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 divVares de hecho mucho más lenta, debido al código auxiliar OSR compilado de manera ineficiente. 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 de compilador disponibles.

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

para 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}

Como otros han señalado, la operación de módulo general requiere que se realice una división. 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, se puede esperar el mejor rendimiento por algo en este sentido:

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 optimización, usamos un contador descendente de pre-decremento aquí porque en muchas arquitecturas en comparación con 0inmediatamente después de una operación aritmética cuesta exactamente 0 instrucciones / ciclos de CPU porque los indicadores de la ALU ya están configurados adecuadamente por la operación anterior. Una optimización decente sin embargo, el compilador hará esa optimización automáticamente incluso si escribe if (counter++ == 50000) { ... counter = 0; }).

Tenga en cuenta que a menudo no desea / necesita un módulo, porque sabe que su contador de bucle ( 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 vea si el contador incremental por uno alcanza algún valor.

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

También me sorprende ver el rendimiento de los códigos anteriores. Se trata del tiempo que tarda el compilador en 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 tiene que verificar el valor de stopNumy progressCheckpara ir al bloque de memoria específico ubicado para estas variables cada vez después de cada iteración porque es una variable y su valor puede cambiar.

Es por eso que después de cada compilador de iteración 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 va a 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 pudo crear un código de bytes eficiente. Si se declara progressCheckcomo una finalo como una final staticvariable de entonces en el momento de tiempo de ejecución / know compilador de tiempo de compilación que se trata de una variable final y su valor no va a cambiar a continuación, reemplazar el compilador progressCheckcon 50000en 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 ejemplos de código.