Pourquoi est if (variable1% variable2 == 0) inefficace?

Je suis nouveau sur Java, et j'utilisais du code hier soir, et cela m'a vraiment dérangé. Je construisais un programme simple pour afficher toutes les sorties X dans une boucle for, et j'ai remarqué une diminution MASSIVE des performances, lorsque j'ai utilisé le module comme variable % variablevs variable % 5000ou autre chose. Quelqu'un peut-il m'expliquer pourquoi et quelle en est la cause? Alors je peux être meilleur ...

Voici le code "efficace" (désolé si je me trompe un peu de syntaxe, je ne suis pas sur l'ordinateur avec le code en ce moment)

long startNum = 0;
long stopNum = 1000000000L;

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

Voici le "code inefficace"

long startNum = 0;
long stopNum = 1000000000L;
long progressCheck = 50000;

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

Remarquez que j'avais une variable de date pour mesurer les différences, et une fois qu'elle est devenue assez longue, la première a pris 50 ms tandis que l'autre a pris 12 secondes ou quelque chose comme ça. Vous devrez peut-être augmenter lestopNum ou diminuer le progressChecksi votre PC est plus efficace que le mien ou autre.

J'ai cherché cette question sur le Web, mais je ne trouve pas de réponse, peut-être que je ne la pose pas correctement.

EDIT: Je ne m'attendais pas à ce que ma question soit si populaire, j'apprécie toutes les réponses. J'ai effectué un benchmark sur chaque mi-temps, et le code inefficace a pris beaucoup plus de temps, 1/4 de seconde contre 10 secondes à peu près. Certes, ils utilisent println, mais ils font tous les deux le même montant, donc je n'imagine pas que cela fausserait beaucoup, d'autant plus que l'écart est répétable. En ce qui concerne les réponses, comme je suis nouveau sur Java, je vais laisser les votes décider pour l'instant quelle réponse est la meilleure. J'essaierai d'en choisir un d'ici mercredi.

EDIT2: Je vais faire un autre test ce soir, où au lieu de module, il incrémente simplement une variable, et quand il atteindra progressCheck, il en effectuera un, puis remettra cette variable à 0. pour une troisième option.

EDIT3.5:

J'ai utilisé ce code, et ci-dessous je vais montrer mes résultats .. Merci à TOUS pour la merveilleuse aide! J'ai également essayé de comparer la valeur courte du long à 0, de sorte que tous mes nouveaux contrôles se produisent jamais "65536" fois, ce qui le rend égal en répétitions.

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");
    }
}

Résultats:

• fixe = 874 ms (normalement autour de 1000 ms, mais plus rapide car il s'agit d'une puissance de 2)
• variable = 8590 ms
• variable finale = 1944 ms (était ~ 1000 ms lors de l'utilisation de 50000)
• incrément = 1904 ms
• Conversion courte = 679 ms

Pas assez surprenant, faute de division, la conversion courte était 23% plus rapide que la méthode «rapide». Ceci est intéressant à noter. Si vous avez besoin de montrer ou de comparer quelque chose toutes les 256 fois (ou environ), vous pouvez le faire et utiliser

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

UNE FINALE NOTE INTÉRESSANTE, en utilisant le module sur la «Variable déclarée finale» avec 65536 (pas un joli nombre) était la moitié de la vitesse de (plus lente) que la valeur fixe. Là où auparavant, il était comparé à la même vitesse.

Vous mesurez le stub OSR (remplacement sur pile) .

Le stub OSR est une version spéciale de la méthode compilée destinée spécifiquement au transfert de l'exécution du mode interprété au code compilé pendant l'exécution de la méthode.

Les stubs OSR ne sont pas aussi optimisés que les méthodes classiques, car ils ont besoin d'une disposition de cadre compatible avec le cadre interprété. Je l'ai déjà montré dans les réponses suivantes: 1 , 2 , 3 .

Une chose similaire se produit ici aussi. Alors que "code inefficace" exécute une longue boucle, la méthode est compilée spécialement pour le remplacement sur pile juste à l'intérieur de la boucle. L'état est transféré de la trame interprétée à la méthode compilée OSR, et cet état inclut progressCheckune variable locale. À ce stade, JIT ne peut pas remplacer la variable par la constante et ne peut donc pas appliquer certaines optimisations comme la réduction de la force .

En particulier, cela signifie que JIT ne remplace pas la division entière par la multiplication . (Voir Pourquoi GCC utilise-t-il la multiplication par un nombre étrange dans l'implémentation de la division entière? Pour l'astuce asm d'un compilateur en avance, lorsque la valeur est une constante au moment de la compilation après l'inlining / constante-propagation, si ces optimisations sont activées . Un entier littéral directement dans l' %expression est également optimisé par gcc -O0, comme ici où il est optimisé par le JITer même dans un stub OSR.)

Cependant, si vous exécutez la même méthode plusieurs fois, la deuxième exécution et les suivantes exécuteront le code normal (non OSR), qui est entièrement optimisé. Voici un benchmark pour prouver la théorie ( benchmarké en utilisant 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);
            }
        }
    }
}

Et les résultats:

# 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 toute première itération de divVarest en effet beaucoup plus lente, en raison d'un stub OSR compilé de manière inefficace. Mais dès que la méthode est réexécutée depuis le début, la nouvelle version sans contrainte est exécutée, ce qui exploite toutes les optimisations de compilateur disponibles.

Dans le prolongement du commentaire @phuclv , j'ai vérifié le code généré par JIT ¹ , les résultats sont les suivants:

pour variable % 5000(division par 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

pour 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

Étant donné que la division prend toujours plus de temps que la multiplication, le dernier extrait de code est moins performant.

Version 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 - Options VM utilisées: -XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print,src/java/Main.main}

Comme d'autres l'ont noté, le fonctionnement du module général nécessite une division. Dans certains cas, la division peut être remplacée (par le compilateur) par une multiplication. Mais les deux peuvent être lents par rapport à l'addition / soustraction. Par conséquent, les meilleures performances peuvent être attendues par quelque chose du genre:

long progressCheck = 50000;

long counter = progressCheck;

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

(En tant que tentative mineure d'optimisation, nous utilisons ici un décompteur avant décrémentation car, sur de nombreuses architectures, la comparaison avec 0immédiatement après une opération arithmétique coûte exactement 0 instructions / cycles de processeur car les indicateurs de l'ALU sont déjà définis de manière appropriée par l'opération précédente. Une optimisation décente Cependant, le compilateur effectuera cette optimisation automatiquement même si vous écrivez if (counter++ == 50000) { ... counter = 0; }.)

Remarquez que souvent vous ne voulez pas vraiment / avez besoin de module, car vous savez que votre compteur de boucle (i ) ou quoi que ce soit n'est jamais incrémenté de 1, et vous ne vous souciez vraiment pas du reste réel que le module vous donnera, voyez juste si le compteur incrémentiel atteint une valeur.

Une autre «astuce» consiste à utiliser des valeurs / limites de puissance de deux, par exemple progressCheck = 1024;. Module une puissance de deux peut être rapidement calculé via bitwise and, ie if ( (i & (1024-1)) == 0 ) {...}. Cela devrait également être assez rapide et peut sur certaines architectures surpasser les performances explicites counterci-dessus.

Je suis également surpris de voir les performances des codes ci-dessus. Tout dépend du temps pris par le compilateur pour exécuter le programme selon la variable déclarée. Dans le deuxième exemple (inefficace):

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

Vous effectuez l'opération de module entre deux variables. Ici, le compilateur doit vérifier la valeur de stopNumetprogressCheck accéder au bloc de mémoire spécifique situé pour ces variables à chaque fois après chaque itération car il s'agit d'une variable et sa valeur peut être modifiée.

C'est pourquoi, après chaque itération, le compilateur est allé à l'emplacement mémoire pour vérifier la dernière valeur des variables. Par conséquent, au moment de la compilation, le compilateur n'était pas en mesure de créer un code d'octet efficace.

Dans le premier exemple de code, vous effectuez un opérateur de module entre une variable et une valeur numérique constante qui ne changera pas pendant l'exécution et le compilateur n'a pas besoin de vérifier la valeur de cette valeur numérique à partir de l'emplacement mémoire. C'est pourquoi le compilateur a pu créer un code d'octet efficace. Si vous déclarez en progressChecktant finalque final staticvariable ou en tant que variable, alors au moment du compilateur au moment de l'exécution / de la compilation, sachez qu'il s'agit d'une variable finale et que sa valeur ne changera pas, alors le compilateur remplace le progressCheckpar 50000dans le code:

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

Vous pouvez maintenant voir que ce code ressemble également au premier exemple de code (efficace). Les performances du premier code et, comme nous l'avons mentionné ci-dessus, les deux codes fonctionneront efficacement. Il n'y aura pas beaucoup de différence dans le temps d'exécution des deux exemples de code.