Dlaczego jeśli (zmienna 1% zmienna 2 == 0) jest nieefektywna?

Jestem nowy w Javie i zeszłej nocy uruchomiłem jakiś kod, co mnie bardzo niepokoiło. Budowałem prosty program do wyświetlania każdego wyjścia X w pętli for i zauważyłem MASYWNY spadek wydajności, kiedy użyłem modułu jako variable % variablevs variable % 5000lub co tam. Czy ktoś może mi wyjaśnić, dlaczego to jest i co go powoduje? Więc mogę być lepszy ...

Oto „wydajny” kod (przepraszam, jeśli mam trochę niepoprawnej składni, nie jestem teraz na komputerze z kodem)

long startNum = 0;
long stopNum = 1000000000L;

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

Oto „nieefektywny kod”

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

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

Pamiętaj, że miałem zmienną daty do pomiaru różnic, a gdy stała się wystarczająco długa, pierwsza zajęła 50 ms, a druga 12 sekund lub coś w tym rodzaju. Być może będziesz musiał zwiększyć stopNumlub zmniejszyć, progressCheckjeśli Twój komputer jest bardziej wydajny niż mój, czy co.

Szukałem tego pytania w Internecie, ale nie mogę znaleźć odpowiedzi, może po prostu nie zadaję tego poprawnie.

EDYCJA: Nie spodziewałem się, że moje pytanie będzie tak popularne, doceniam wszystkie odpowiedzi. Przeprowadziłem test porównawczy w każdej połowie czasu, a nieefektywny kod trwał znacznie dłużej, 1/4 sekundy w porównaniu do 10 sekund. To prawda, że ​​używają println, ale obaj robią to samo, więc nie wyobrażam sobie, że to by to wypaczyło, zwłaszcza że rozbieżność jest powtarzalna. Jeśli chodzi o odpowiedzi, ponieważ jestem nowy w Javie, pozwolę głosom zdecydować, która odpowiedź jest najlepsza. Spróbuję wybrać jeden do środy.

EDYCJA 2: Dziś wieczorem zrobię kolejny test, w którym zamiast modułu, po prostu inkrementuje zmienną, a kiedy osiągnie progressCheck, wykona jedną, a następnie zresetuje tę zmienną do 0. dla trzeciej opcji.

EDYCJA 3.5:

Użyłem tego kodu, a poniżej pokażę moje wyniki. Dziękujemy wszystkim za wspaniałą pomoc! Próbowałem także porównać krótką wartość długiego z 0, więc wszystkie moje nowe kontrole zdarzają się zawsze „65536” razy, co czyni je równymi w powtórzeniach.

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

Wyniki:

• naprawiono = 874 ms (zwykle około 1000 ms, ale szybciej, ponieważ jest to moc 2)
• zmienna = 8590 ms
• zmienna końcowa = 1944 ms (było ~ 1000 ms przy użyciu 50000)
• przyrost = 1904 ms
• Krótka konwersja = 679 ms

Nic dziwnego, ze względu na brak podziału krótka konwersja była o 23% szybsza niż „szybka”. Warto to zauważyć. Jeśli chcesz coś pokazywać lub porównywać co 256 razy (lub mniej więcej tam), możesz to zrobić i użyć

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

JEDNA KOŃCOWA UWAGA: użycie modułu w „Ostatecznej deklarowanej zmiennej” z wartością 65536 (niezbyt ładną liczbą) było o połowę mniejsze (wolniejsze) niż ustalona wartość. Gdzie wcześniej było to porównywanie z tą samą prędkością.

Jesteś pomiaru (wymianę na stosie) OSR niedopałek.

Kod OSR jest specjalną wersją skompilowanej metody przeznaczonej specjalnie do przenoszenia wykonywania z trybu interpretowanego do skompilowanego kodu podczas działania metody.

Kody OSR nie są tak zoptymalizowane jak zwykłe metody, ponieważ wymagają układu zgodnego z interpretowaną ramką. Pokazałem to już w następujących odpowiedziach: 1 , 2 , 3 .

Podobnie dzieje się tutaj. Podczas gdy „niewydajny kod” uruchamia długą pętlę, metoda jest kompilowana specjalnie dla zamiany stosu bezpośrednio w pętli. Stan jest przenoszony z interpretowanej ramki do metody skompilowanej przez OSR, a ten stan obejmuje progressCheckzmienną lokalną. W tym momencie JIT nie może zastąpić zmiennej stałą, a zatem nie może zastosować pewnych optymalizacji, takich jak redukcja siły .

W szczególności środki JIT nie zastępuje całkowitą podział z mnożenia . (Zobacz Dlaczego GCC używa mnożenia przez dziwną liczbę w implementacji dzielenia liczb całkowitych? Dla sztuczki asm z kompilatora z wyprzedzeniem, gdy wartość jest stałą czasu kompilacji po wstawianiu / stałej propagacji, jeśli te optymalizacje są włączone Również dosłownie liczba całkowita w %wyrażeniu jest optymalizowana przez gcc -O0, podobnie jak tutaj, gdzie jest zoptymalizowana przez JITer nawet w odcinku OSR.)

Jeśli jednak uruchomisz tę samą metodę kilka razy, drugie i kolejne uruchomienia spowodują wykonanie zwykłego (nie OSR) kodu, który jest w pełni zoptymalizowany. Oto punkt odniesienia dla udowodnienia teorii ( test porównawczy przy użyciu 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);
            }
        }
    }
}

A wyniki:

# 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

Pierwsza iteracja divVarjest rzeczywiście znacznie wolniejsza z powodu nieefektywnie skompilowanego kodu OSR. Ale gdy tylko metoda uruchomi się od nowa, uruchamiana jest nowa, nieograniczona wersja, która wykorzystuje wszystkie dostępne optymalizacje kompilatora.

W odpowiedzi na komentarz @phuclv sprawdziłem kod wygenerowany przez JIT ¹ , wyniki są następujące:

dla variable % 5000(dzielenie przez stałą):

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

dla 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

Ponieważ dzielenie zawsze trwa dłużej niż mnożenie, ostatni fragment kodu jest mniej wydajny.

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

Jak zauważyli inni, ogólne działanie modułu wymaga podziału. W niektórych przypadkach podział można zastąpić (przez kompilator) mnożeniem. Ale oba mogą być powolne w porównaniu do dodawania / odejmowania. Stąd, najlepszej wydajności można się spodziewać po czymś takim:

long progressCheck = 50000;

long counter = progressCheck;

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

(Jako drobną próbę optymalizacji używamy tutaj licznika wstępnego zmniejszania licznika wstępnego, ponieważ na wielu architekturach porównanie do 0natychmiast po operacji arytmetycznej kosztuje dokładnie 0 instrukcji / cykli procesora, ponieważ flagi ALU są już odpowiednio ustawione przez poprzednią operację. Przyzwoita optymalizacja kompilator wykona tę optymalizację automatycznie, nawet jeśli napiszesz if (counter++ == 50000) { ... counter = 0; }.)

Zauważ, że często tak naprawdę nie chcesz / potrzebujesz modułu, ponieważ wiesz, że twój licznik pętli ( i) lub cokolwiek jest zwiększany tylko o 1, i naprawdę nie przejmujesz się faktyczną pozostałą wartością modułu, po prostu zobacz jeśli licznik rosnący o jeden osiągnie pewną wartość.

Inną „sztuczką” jest użycie potęgi dwóch wartości / limitów, np progressCheck = 1024;. Moduł potęgi dwóch można szybko obliczyć bitowo and, tj if ( (i & (1024-1)) == 0 ) {...}. To również powinno być dość szybkie i może w niektórych architekturach przewyższyć counterpowyższe.

Jestem również zaskoczony, widząc wydajność powyższych kodów. Chodzi o czas potrzebny kompilatorowi na uruchomienie programu zgodnie z zadeklarowaną zmienną. W drugim (nieefektywnym) przykładzie:

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

Wykonujesz operację modułu między dwiema zmiennymi. Tutaj kompilator musi sprawdzać wartość stopNumi progressCheckprzejść do określonego bloku pamięci dla tych zmiennych za każdym razem po każdej iteracji, ponieważ jest to zmienna, a jej wartość może ulec zmianie.

Dlatego po każdym kompilatorze iteracji udaje się do miejsca w pamięci, aby sprawdzić najnowszą wartość zmiennych. Dlatego w czasie kompilacji kompilator nie był w stanie utworzyć wydajnego kodu bajtowego.

W pierwszym przykładzie kodu wykonujesz operator modułu między zmienną a stałą wartością liczbową, która nie ulegnie zmianie w trakcie wykonywania, a kompilator nie musi sprawdzać wartości tej wartości liczbowej z miejsca w pamięci. Dlatego kompilator był w stanie stworzyć wydajny bajtowy kod. Jeśli zadeklarujesz progressCheckpostaci finallub jako final staticzmiennej następnie w czasie run-time / kompilacji kompilator wie, że jest to zmienna, a jej ostateczna wartość nie ulegnie zmianie, a następnie kompilator zastąpi progressCheckz 50000kodem:

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

Teraz możesz zobaczyć, że ten kod również wygląda jak pierwszy (wydajny) przykład kodu. Wydajność pierwszego kodu i, jak wspomniano powyżej, oba kody będą działały wydajnie. W żadnym z przykładów kodu nie będzie dużej różnicy w czasie wykonywania.