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

179

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.

Robert Cotterman
la source
29
J'ai eu le même résultat en fait. Sur ma machine, la première boucle dure environ 1,5 seconde et la seconde dure environ 9 secondes. Si j'ajoute finaldevant la progressCheckvariable, les deux fonctionnent à nouveau à la même vitesse. Cela me porte à croire que le compilateur ou le JIT parvient à optimiser la boucle lorsqu'il sait que progressCheckc'est constant.
marstran
24
La division par une constante peut être facilement convertie en une multiplication par l'inverse multiplicatif . La division par une variable ne peut pas. Et une division 32 bits est plus rapide qu'une division 64 bits sur x86
phuclv
2
@phuclv note La division 32 bits n'est pas un problème ici, c'est une opération de reste 64 bits dans les deux cas
user85421
4
@RobertCotterman si vous déclarez la variable comme finale, le compilateur crée le même bytecode que l'utilisation de la constante (eclipse / Java 11) ((malgré l'utilisation d'un emplacement mémoire supplémentaire pour la variable))
user85421

Réponses:

139

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.

apangin
la source
5
J'hésite à voter là-dessus. D'une part, cela ressemble à une manière élaborée de dire "Vous avez raté votre benchmark, lisez quelque chose sur JIT". D'un autre côté, je me demande pourquoi vous semblez si sûr que l'OSR était le principal point pertinent ici. Je veux dire, faire un (micro) benchmark qui implique System.out.printlnproduira presque nécessairement des résultats inutiles, et le fait que les deux versions soient également rapides n'a rien à faire avec OSR en particulier , pour autant que je
sache
2
(Je suis curieux et j'aime comprendre cela. J'espère que les commentaires ne sont pas dérangeants, je pourrais les supprimer plus tard, mais:) Le lien 1est un peu douteux - la boucle vide pourrait également être optimisée complètement. Le second est plus similaire à celui-là. Mais encore une fois, on ne sait pas pourquoi vous attribuez la différence au DSO spécifiquement . Je dirais simplement: à un moment donné, la méthode est JITed et devient plus rapide. À ma connaissance, l'OSR fait que l'utilisation du code optimisé final soit (approximativement) ~ "reportée à la prochaine passe d'optimisation". (suite ...)
Marco13
1
(suite :) À moins que vous n'analysiez spécifiquement les journaux des hotspots, vous ne pouvez pas dire si la différence est causée en comparant le code JITed et non-JITed, ou en comparant le code JITed et OSR-stub-code. Et vous ne pouvez certainement pas dire cela avec certitude lorsque la question ne contient pas le vrai code ou un benchmark JMH complet. Donc, faire valoir que la différence est causée par OSR semble, pour moi, d'une spécificité inappropriée (et "injustifiée") par rapport à dire qu'elle est causée par le JIT en général. (Aucune infraction - je me demande juste ...)
Marco13
4
@ Marco13 il y a une heuristique simple: sans l'activité du JIT, chaque %opération aurait le même poids, car une exécution optimisée n'est possible, enfin, que si un optimiseur faisait un travail réel. Ainsi, le fait qu'une variante de boucle soit significativement plus rapide que l'autre prouve la présence d'un optimiseur et prouve en outre qu'il n'a pas réussi à optimiser l'une des boucles au même degré que l'autre (dans la même méthode!). Comme cette réponse prouve la capacité d'optimiser les deux boucles au même degré, il doit y avoir quelque chose qui a gêné l'optimisation. Et c'est OSR dans 99,9% de tous les cas
Holger
4
@ Marco13 C'était une "supposition éclairée" basée sur la connaissance de HotSpot Runtime et l'expérience de l'analyse de problèmes similaires auparavant. Une boucle aussi longue pourrait difficilement être compilée d'une manière autre que OSR, en particulier dans un simple benchmark fait à la main. Maintenant, quand OP a posté le code complet, je ne peux que confirmer à nouveau le raisonnement en exécutant le code avec -XX:+PrintCompilation -XX:+TraceNMethodInstalls.
apangin le
42

Dans le prolongement du commentaire @phuclv , j'ai vérifié le code généré par JIT 1 , 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

Oleksandr Pyrohov
la source
14
Donner un ordre de grandeur sur "plus lent", pour x86_64: imulsoit 3 cycles, idivsoit entre 30 et 90 cycles. La division entière est donc entre 10x et 30x plus lente que la multiplication entière.
Matthieu M.
2
Pourriez-vous expliquer ce que tout cela signifie pour les lecteurs intéressés, mais ne parlant pas assembleur?
Nico Haase le
7
@NicoHaase Les deux lignes commentées sont les seules importantes. Dans la première section, le code effectue une multiplication d'entiers, tandis que dans la deuxième section, le code effectue une division entière. Si vous pensez faire des multiplications et des divisions à la main, lorsque vous multipliez, vous faites généralement un tas de petites multiplications, puis un grand ensemble d'additions, mais la division est une petite division, une petite multiplication, une soustraction et une répétition. La division est lente parce que vous faites essentiellement un tas de multiplications.
MBraedley
4
@MBraedley merci pour votre contribution, mais une telle explication devrait être ajoutée à la réponse elle-même et ne pas être cachée dans la section des commentaires
Nico Haase
6
@MBraedley: Plus précisément, la multiplication dans un CPU moderne est rapide car les produits partiels sont indépendants et peuvent donc être calculés séparément, tandis que chaque étape d'une division dépend des étapes précédentes.
supercat
26

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.

JimmyB
la source
3
Un compilateur intelligent inverserait les boucles ici. Ou vous pouvez le faire dans la source. Le if()corps devient un corps de boucle externe et les éléments extérieurs if()deviennent un corps de boucle interne qui s'exécute pendant des min(progressCheck, stopNum-i)itérations. Donc, au début, et à chaque fois qu'il counteratteint 0, vous devez long next_stop = i + min(progressCheck, stopNum-i);configurer une for(; i< next_stop; i++) {}boucle. Dans ce cas, cette boucle interne est vide et devrait, espérons-le, être entièrement optimisée, vous pouvez le faire dans la source et le rendre facile pour le JITer, en réduisant votre boucle à i + = 50k.
Peter Cordes
2
Mais oui, en général, un compteur décroissant est une bonne technique efficace pour les trucs de type fizzbuzz / progresscheck.
Peter Cordes
J'ai ajouté à ma question, et fait une augmentation, l' --counterest tout aussi rapide que ma version d'incrément, mais moins code.also était de 1 inférieur à ce qu'il devrait être, je suis curieux de savoir s'il devrait être counter--d'obtenir le nombre exact que vous voulez , pas que ce soit une grande différence
Robert Cotterman
@PeterCordes Un compilateur intelligent afficherait simplement les nombres, pas de boucle du tout. (Je pense que certains repères un peu plus triviaux ont commencé à échouer de cette façon il y a peut-être 10 ans.)
Peter - Réintégrer Monica le
2
@RobertCotterman Oui, --counterest désactivé par un. counter--vous donnera exactement le progressChecknombre d'itérations (ou vous pouvez définir progressCheck = 50001;bien sûr).
JimmyB
4

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.

Bishal Dubey
la source
1
Il y a une énorme différence, même si je faisais l'opération un billion de fois, donc plus de 1 billion d'opérations, cela a permis de gagner 89% de temps pour faire le code «efficace». faites attention si vous ne le faites que quelques milliers de fois, que vous parliez d'une si petite différence, ce n'est probablement pas un gros problème. Je veux dire que plus de 1000 opérations vous feraient gagner 1 millionième de 7 secondes.
Robert Cotterman
1
@Bishal Dubey "Il n'y aura pas beaucoup de différence dans le temps d'exécution des deux codes." Avez-vous lu la question?
Grant Foster
"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" - À moins que la variable n'ait été déclarée, volatilele 'compilateur' ne lira pas sa valeur à partir de la RAM encore et encore.
JimmyB