Warum ist if (variable1% variable2 == 0) ineffizient?

Ich bin neu in Java und habe letzte Nacht Code ausgeführt, und das hat mich wirklich gestört. Ich habe ein einfaches Programm erstellt, um alle X-Ausgänge in einer for-Schleife anzuzeigen, und ich habe einen massiven Leistungsabfall festgestellt, als ich den Modul als variable % variablevs variable % 5000oder so weiter verwendet habe. Kann mir jemand erklären, warum das so ist und was es verursacht? Also kann ich besser sein ...

Hier ist der "effiziente" Code (Entschuldigung, wenn ich ein bisschen falsche Syntax habe, bin ich gerade nicht mit dem Code auf dem Computer)

long startNum = 0;
long stopNum = 1000000000L;

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

Hier ist der "ineffiziente Code"

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

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

Wohlgemerkt, ich hatte eine Datumsvariable, um die Unterschiede zu messen, und sobald sie lang genug war, dauerte die erste 50 ms, während die andere 12 Sekunden oder so etwas dauerte. Möglicherweise müssen Sie die erhöhen stopNumoder verringern, progressCheckwenn Ihr PC effizienter als meiner ist oder was nicht.

Ich habe im Internet nach dieser Frage gesucht, aber ich kann keine Antwort finden. Vielleicht stelle ich sie einfach nicht richtig.

EDIT: Ich hatte nicht erwartet, dass meine Frage so beliebt ist, ich schätze alle Antworten. Ich habe für jede Hälfte der Zeit einen Benchmark durchgeführt, und der ineffiziente Code dauerte erheblich länger, 1/4 Sekunde gegenüber 10 Sekunden Geben oder Nehmen. Zugegeben, sie verwenden println, aber beide machen die gleiche Menge, daher würde ich mir nicht vorstellen, dass dies zu einer starken Verzerrung führen würde, zumal die Diskrepanz wiederholbar ist. Da ich neu in Java bin, werde ich die Stimmen vorerst entscheiden lassen, welche Antwort die beste ist. Ich werde versuchen, bis Mittwoch einen auszuwählen.

EDIT2: Ich werde heute Abend einen weiteren Test durchführen, bei dem anstelle des Moduls nur eine Variable inkrementiert wird. Wenn progressCheck erreicht ist, wird eine durchgeführt und diese Variable für eine dritte Option auf 0 zurückgesetzt.

EDIT3.5:

Ich habe diesen Code verwendet und unten zeige ich meine Ergebnisse. Vielen Dank an ALLE für die wunderbare Hilfe! Ich habe auch versucht, den kurzen Wert des langen mit dem Wert 0 zu vergleichen, sodass alle meine neuen Überprüfungen immer "65536" Mal durchgeführt werden, sodass sie in Wiederholungen gleich sind.

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

Ergebnisse:

• fest = 874 ms (normalerweise um 1000 ms, aber schneller, da es eine Potenz von 2 ist)
• variabel = 8590 ms
• letzte Variable = 1944 ms (war ~ 1000 ms bei Verwendung von 50000)
• Inkrement = 1904 ms
• Kurzumwandlung = 679 ms

Kein Wunder, dass die Short Conversion aufgrund mangelnder Teilung 23% schneller war als der "schnelle" Weg. Das ist interessant zu bemerken. Wenn Sie alle 256 Mal (oder ungefähr dort) etwas zeigen oder vergleichen müssen, können Sie dies tun und verwenden

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

EIN ENDGÜLTIGER INTERESSANTER HINWEIS: Die Verwendung des Moduls für die "endgültig deklarierte Variable" mit 65536 (keine hübsche Zahl) war halb so schnell (langsamer) als der feste Wert. Wo vorher war es Benchmarking in der Nähe der gleichen Geschwindigkeit.

Sie messen den OSR- Stub (On-Stack-Ersatz) .

OSR-Stub ist eine spezielle Version der kompilierten Methode, die speziell zum Übertragen der Ausführung vom interpretierten Modus in kompilierten Code während der Ausführung der Methode vorgesehen ist.

OSR-Stubs sind nicht so optimiert wie normale Methoden, da sie ein Frame-Layout benötigen, das mit dem interpretierten Frame kompatibel ist. Ich habe dies bereits in den folgenden Antworten gezeigt: 1 , 2 , 3 .

Ähnliches passiert auch hier. Während "ineffizienter Code" eine lange Schleife ausführt, wird die Methode speziell für den On-Stack-Austausch direkt innerhalb der Schleife kompiliert. Der Status wird vom interpretierten Frame an die OSR-kompilierte Methode übertragen, und dieser Status enthält eine progressChecklokale Variable. Zu diesem Zeitpunkt kann JIT die Variable nicht durch die Konstante ersetzen und daher bestimmte Optimierungen wie die Festigkeitsreduzierung nicht anwenden .

Insbesondere ist diese Mittel JIT ersetzen nicht ganzzahlige Division mit Multiplikation . (Siehe Warum verwendet GCC bei der Implementierung der Ganzzahldivision die Multiplikation mit einer seltsamen Zahl? Für den asm-Trick eines Compilers vor der Zeit, wenn der Wert nach Inlining / Konstanten-Propagation eine Konstante zur Kompilierungszeit ist, wenn diese Optimierungen aktiviert sind Ein ganzzahliges Literalrecht im %Ausdruck wird ebenfalls von optimiert gcc -O0, ähnlich wie hier, wo es vom JITer selbst in einem OSR-Stub optimiert wird.)

Wenn Sie dieselbe Methode jedoch mehrmals ausführen, führen der zweite und der nachfolgende Lauf den regulären Code (ohne OSR) aus, der vollständig optimiert ist. Hier ist ein Benchmark zum Nachweis der Theorie ( Benchmarking mit 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);
            }
        }
    }
}

Und die Ergebnisse:

# 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

Die allererste Iteration von divVarist in der Tat viel langsamer, da der OSR-Stub ineffizient kompiliert wurde. Sobald die Methode jedoch von Anfang an erneut ausgeführt wird, wird die neue, nicht eingeschränkte Version ausgeführt, die alle verfügbaren Compiler-Optimierungen nutzt.

Im Anschluss an den @ phuclv- Kommentar habe ich den von JIT ¹ generierten Code überprüft. Die Ergebnisse lauten wie folgt:

für variable % 5000(Division durch Konstante):

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

für 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

Da die Division immer länger dauert als die Multiplikation, ist das letzte Code-Snippet weniger performant.

Java-Version:

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 - Verwendete VM-Optionen: -XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print,src/java/Main.main}

Wie andere angemerkt haben, erfordert die allgemeine Moduloperation eine Division. In einigen Fällen kann die Division (durch den Compiler) durch eine Multiplikation ersetzt werden. Beide können jedoch im Vergleich zur Addition / Subtraktion langsam sein. Daher kann die beste Leistung von etwas in dieser Richtung erwartet werden:

long progressCheck = 50000;

long counter = progressCheck;

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

(Als kleinen Optimierungsversuch verwenden wir hier einen Abwärtszähler vor der Dekrementierung, da bei vielen Architekturen im Vergleich zu 0unmittelbar nach einer arithmetischen Operation genau 0 Befehle / CPU-Zyklen kosten, da die Flags der ALU durch die vorhergehende Operation bereits entsprechend gesetzt sind. Eine anständige Optimierung Der Compiler führt diese Optimierung jedoch automatisch durch, selbst wenn Sie schreiben if (counter++ == 50000) { ... counter = 0; }.)

Beachten Sie, dass Sie den Modul oft nicht wirklich wollen / brauchen, weil Sie wissen, dass Ihr Schleifenzähler ( i) oder was auch immer immer nur um 1 erhöht wird, und Sie sich wirklich nicht um den tatsächlichen Rest kümmern, den der Modul Ihnen gibt, sehen Sie einfach wenn der um eins erhöhte Zähler einen Wert erreicht.

Ein weiterer "Trick" besteht darin, Zweierpotenzwerte / -grenzen zu verwenden, z progressCheck = 1024;. Der Modul einer Zweierpotenz kann schnell bitweise berechnet werden and, d if ( (i & (1024-1)) == 0 ) {...}. H. Dies sollte auch ziemlich schnell sein und kann bei einigen Architekturen die counteroben genannten Anforderungen übertreffen .

Ich bin auch überrascht, wie gut die oben genannten Codes funktionieren. Es geht um die Zeit, die der Compiler für die Ausführung des Programms gemäß der deklarierten Variablen benötigt. Im zweiten (ineffizienten) Beispiel:

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

Sie führen die Moduloperation zwischen zwei Variablen aus. Hier muss der Compiler jedes Mal nach jeder Iteration den Wert von überprüfen stopNumund progressCheckzu dem spezifischen Speicherblock gehen, der sich für diese Variablen befindet, da es sich um eine Variable handelt und sich ihr Wert möglicherweise ändert.

Aus diesem Grund ging der Compiler nach jeder Iteration zum Speicherort, um den neuesten Wert der Variablen zu überprüfen. Daher konnte der Compiler zum Zeitpunkt der Kompilierung keinen effizienten Bytecode erstellen.

Im ersten Codebeispiel führen Sie einen Moduloperator zwischen einer Variablen und einem konstanten numerischen Wert aus, der sich innerhalb der Ausführung nicht ändert, und der Compiler muss den Wert dieses numerischen Werts nicht vom Speicherort aus überprüfen. Aus diesem Grund konnte der Compiler effizienten Bytecode erstellen. Wenn Sie erklären progressCheckals eine finaloder als final staticVariable dann zum Zeitpunkt der Laufzeit / Kompilierung-Compiler weiß , dass es eine letzte Variable ist und sein Wert wird nicht dann den Compiler ersetzen ändern progressCheckmit 50000in Code:

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

Jetzt können Sie sehen, dass dieser Code auch wie das erste (effiziente) Codebeispiel aussieht. Die Leistung des ersten Codes und wie oben erwähnt, funktioniert effizient. Es wird keinen großen Unterschied in der Ausführungszeit eines der beiden Codebeispiele geben.