Por que se (variável1% variável2 == 0) é ineficiente?

Eu sou novo em java, e estava executando algum código ontem à noite, e isso realmente me incomodou. Eu estava construindo um programa simples para exibir todas as saídas X em um loop for, e notei uma enorme queda no desempenho quando usei o módulo como variable % variablevs variable % 5000ou outros enfeites. Alguém pode me explicar por que isso é e o que está causando isso? Para que eu possa ser melhor ...

Aqui está o código "eficiente" (desculpe se entendi um pouco de sintaxe, não estou no computador com o código no momento)

long startNum = 0;
long stopNum = 1000000000L;

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

Aqui está o "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);
    }
}

Lembre-se de que eu tinha uma variável de data para medir as diferenças e, uma vez que ficou longa o suficiente, a primeira levou 50ms enquanto a outra levou 12 segundos ou algo assim. Você pode ter que aumentar stopNumou diminuir progressCheckse o seu PC for mais eficiente que o meu ou não.

Procurei essa pergunta na Web, mas não consigo encontrar uma resposta, talvez não esteja fazendo a pergunta certa.

EDIT: Eu não esperava que minha pergunta fosse tão popular, agradeço todas as respostas. Realizei uma referência em cada metade do tempo gasto, e o código ineficiente demorou consideravelmente mais, 1/4 de segundo versus 10 segundos mais ou menos. É verdade que eles estão usando println, mas ambos estão fazendo a mesma quantidade, então eu não imaginaria que isso distorceria muito, especialmente porque a discrepância é repetível. Quanto às respostas, como sou novo em Java, deixarei os votos decidirem por enquanto qual é a melhor. Vou tentar escolher um até quarta-feira.

EDIT2: Vou fazer outro teste hoje à noite, onde, em vez de módulo, ele apenas incrementa uma variável e, quando atinge progressCheck, ele executa uma e, em seguida, redefine a variável para 0. para uma terceira opção.

EDIT3.5:

Eu usei esse código e abaixo mostrarei meus resultados .. Obrigado a todos pela maravilhosa ajuda! Eu também tentei comparar o valor curto do longo com 0, então todas as minhas novas verificações acontecem sempre "65536" vezes, tornando-o igual em repetições.

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:

• fixo = 874 ms (normalmente em torno de 1000ms, mas mais rápido devido a uma potência de 2)
• variável = 8590 ms
• variável final = 1944 ms (era ~ 1000ms ao usar 50000)
• incremento = 1904 ms
• Conversão curta = 679 ms

Não surpreende o suficiente, devido à falta de divisão, a conversão curta foi 23% mais rápida que a maneira "rápida". Isso é interessante notar. Se você precisar mostrar ou comparar algo a cada 256 vezes (ou por aí), faça isso e use

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

UMA NOTA INTERESSANTE FINAL, o uso do módulo na "Variável declarada final" com 65536 (número não muito bonito) foi metade da velocidade (mais lenta) do que o valor fixo. Onde antes estava comparando com a mesma velocidade.

Você está medindo o stub OSR (substituição na pilha) .

O OSR stub é uma versão especial do método compilado, projetado especificamente para transferir a execução do modo interpretado para o código compilado enquanto o método está em execução.

Os stubs OSR não são tão otimizados quanto os métodos regulares, porque precisam de um layout de quadro compatível com o quadro interpretado. Eu já mostrei isso nas seguintes respostas: 1 , 2 , 3 .

Uma coisa semelhante acontece aqui também. Enquanto o "código ineficiente" está executando um loop longo, o método é compilado especialmente para a substituição na pilha dentro do loop. O estado é transferido do quadro interpretado para o método compilado por OSR e esse estado inclui progressChecka variável local. Nesse ponto, o JIT não pode substituir a variável pela constante e, portanto, não pode aplicar certas otimizações, como redução de força .

Em particular, isso significa que o JIT não substitui a divisão inteira pela multiplicação . (Veja Por que o uso GCC multiplicação por um número estranho na implementação divisão inteira? Para o truque asm de um compilador antes-do-tempo, quando o valor é uma constante de tempo de compilação após inlining / constant-propagação, se essas otimizações são habilitados Um literal inteiro inteiro na %expressão também é otimizado gcc -O0, semelhante a aqui onde é otimizado pelo JITer, mesmo em um stub OSR.)

No entanto, se você executar o mesmo método várias vezes, a segunda e a subsequente executarão o código regular (não OSR), que é totalmente otimizado. Aqui está uma referência para provar a teoria ( comparada usando 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);
            }
        }
    }
}

E os 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

A primeira iteração de divVaré realmente muito mais lenta, devido ao stub OSR ineficientemente compilado. Porém, assim que o método é executado novamente desde o início, a nova versão irrestrita é executada, o que aproveita todas as otimizações disponíveis do compilador.

No seguimento do comentário @phuclv , verifiquei o código gerado pelo JIT ¹ , os resultados são os seguintes:

para variable % 5000(divisão 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

Como a divisão sempre leva mais tempo que a multiplicação, o último trecho de código tem menos desempenho.

Versão 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 - Opções de VM usadas: -XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print,src/java/Main.main}

Como outros observaram, a operação geral do módulo exige que uma divisão seja feita. Em alguns casos, a divisão pode ser substituída (pelo compilador) por uma multiplicação. Mas ambos podem ser lentos em comparação com adição / subtração. Portanto, o melhor desempenho pode ser esperado por algo nesse sentido:

long progressCheck = 50000;

long counter = progressCheck;

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

(Como uma pequena tentativa de otimização, usamos um contador de pré-decréscimo aqui, porque em muitas arquiteturas, comparando 0imediatamente após uma operação aritmética, custa exatamente 0 instruções / ciclos de CPU, porque os sinalizadores da ALU já estão configurados adequadamente pela operação anterior. O compilador, no entanto, fará essa otimização automaticamente, mesmo se você escrever if (counter++ == 50000) { ... counter = 0; }.)

Observe que muitas vezes você realmente não quer / precisa de módulo, porque você sabe que seu contador de loop ( i) ou o que quer que seja apenas incrementado em 1, e você realmente não se importa com o restante do módulo, basta ver se o contador de incremento por um atingir algum valor.

Outro 'truque' é usar dois valores / limites de potência, por exemplo progressCheck = 1024;. O módulo de potência de dois pode ser calculado rapidamente via bit a bit and, ou seja if ( (i & (1024-1)) == 0 ) {...}. Isso também deve ser muito rápido e, em algumas arquiteturas, pode superar o explícito counteracima.

Também estou surpreso ao ver o desempenho dos códigos acima. É tudo sobre o tempo gasto pelo compilador para executar o programa de acordo com a variável declarada. No segundo exemplo (ineficiente):

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

Você está executando a operação do módulo entre duas variáveis. Aqui, o compilador deve verificar o valor stopNume progressCheckacessar o bloco de memória específico localizado para essas variáveis ​​todas as vezes após cada iteração, porque é uma variável e seu valor pode ser alterado.

É por isso que após cada compilador de iteração foi para o local da memória para verificar o valor mais recente das variáveis. Portanto, no momento da compilação, o compilador não conseguiu criar um código de bytes eficiente.

No primeiro exemplo de código, você está executando um operador de módulo entre uma variável e um valor numérico constante que não será alterado na execução e no compilador, não sendo necessário verificar o valor desse valor numérico a partir da localização da memória. É por isso que o compilador conseguiu criar código de bytes eficiente. Se você declarar progressCheckcomo uma variável finalou como final staticvariável, no momento do compilador em tempo de execução / tempo de compilação saiba que é uma variável final e seu valor não será alterado, substitua-o progressCheckpor 50000no código:

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

Agora você pode ver que esse código também se parece com o primeiro exemplo de código (eficiente). O desempenho do primeiro código e, como mencionamos acima, ambos os códigos funcionarão eficientemente. Não haverá muita diferença no tempo de execução dos dois exemplos de código.