Dlaczego 4 miliardy iteracji pętli Java zajmuje tylko 2 ms?

Używam następującego kodu Java na laptopie z procesorem Intel Core i7 2,7 GHz. Zamierzałem pozwolić mu zmierzyć, ile czasu zajmie zakończenie pętli z 2 ^ 32 iteracjami, które, jak spodziewałem się, trwały około 1,48 sekundy (4 / 2,7 = 1,48).

Ale tak naprawdę zajmuje to tylko 2 milisekundy zamiast 1,48 s. Zastanawiam się, czy jest to wynikiem jakiejkolwiek optymalizacji JVM pod spodem?

public static void main(String[] args)
{
    long start = System.nanoTime();

    for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; i++){
    }
    long finish = System.nanoTime();
    long d = (finish - start) / 1000000;

    System.out.println("Used " + d);
}

Zachodzi tutaj jedna z dwóch możliwości:

1. Kompilator zdał sobie sprawę, że pętla jest zbędna i nic nie robi, więc zoptymalizował ją.

2. JIT (kompilator just-in-time) zdał sobie sprawę, że pętla jest nadmiarowa i nic nie robi, więc zoptymalizował ją.

Nowoczesne kompilatory są bardzo inteligentne; mogą zobaczyć, kiedy kod jest bezużyteczny. Spróbuj wstawić pustą pętlę do GodBolt i spójrz na wyjście, a następnie włącz -O2optymalizacje, zobaczysz, że wynik jest podobny do

main():
    xor eax, eax
    ret

Chciałbym coś wyjaśnić, w Javie większość optymalizacji jest wykonywana przez JIT. W niektórych innych językach (np. C / C ++) większość optymalizacji jest wykonywana przez pierwszy kompilator.

Wygląda na to, że został zoptymalizowany przez kompilator JIT. Kiedy go wyłączam ( -Djava.compiler=NONE), kod działa znacznie wolniej:

$ javac MyClass.java
$ java MyClass
Used 4
$ java -Djava.compiler=NONE MyClass
Used 40409

Umieściłem kod OP w class MyClass.

Powiem tylko to, co oczywiste - że jest to optymalizacja JVM, która ma miejsce, pętla zostanie po prostu w ogóle usunięta. Oto mały test, który pokazuje ogromną różnicę JIT, gdy jest włączony / włączony tylko dla C1 Compileriw ogóle wyłączony.

Zastrzeżenie: nie pisz takich testów - to tylko po to, aby udowodnić, że faktyczne „usuwanie” pętli ma miejsce w C2 Compiler:

@Benchmark
@Fork(1)
public void full() {
    long result = 0;
    for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; i++) {
        ++result;
    }
}

@Benchmark
@Fork(1)
public void minusOne() {
    long result = 0;
    for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE - 1; i++) {
        ++result;
    }
}

@Benchmark
@Fork(value = 1, jvmArgsAppend = { "-XX:TieredStopAtLevel=1" })
public void withoutC2() {
    long result = 0;
    for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE - 1; i++) {
        ++result;
    }
}

@Benchmark
@Fork(value = 1, jvmArgsAppend = { "-Xint" })
public void withoutAll() {
    long result = 0;
    for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE - 1; i++) {
        ++result;
    }
}

Wyniki pokazują, że w zależności od tego, która część JITjest włączona, metoda przyspiesza (o wiele szybciej, że wygląda na to, że "nic nie robi" - usuwanie pętli, co wydaje się mieć miejsce w C2 Compiler- co jest maksymalnym poziomem):

 Benchmark                Mode  Cnt      Score   Error  Units
 Loop.full        avgt    2     ≈ 10⁻⁷          ms/op
 Loop.minusOne    avgt    2     ≈ 10⁻⁶          ms/op
 Loop.withoutAll  avgt    2  51782.751          ms/op
 Loop.withoutC2   avgt    2   1699.137          ms/op 

Jak już wspomniano, kompilator JIT (just-in-time) może zoptymalizować pustą pętlę, aby usunąć niepotrzebne iteracje. Ale jak?

W rzeczywistości istnieją dwa kompilatory JIT: C1 i C2 . Najpierw kod jest kompilowany za pomocą C1. C1 zbiera statystyki i pomaga JVM odkryć, że w 100% przypadków nasza pusta pętla niczego nie zmienia i jest bezużyteczna. W tej sytuacji na scenę wkracza C2. Gdy kod jest wywoływany bardzo często, można go zoptymalizować i skompilować za pomocą C2 przy użyciu zebranych statystyk.

Jako przykład przetestuję następny fragment kodu (mój JDK jest ustawiony na wersję 9-wewnętrzną slowdebug ):

public class Demo {
    private static void run() {
        for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; i++) {
        }
        System.out.println("Done!");
    }
}

Z następującymi opcjami wiersza poleceń:

-XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print,*Demo.run

Istnieją różne wersje mojej metody uruchamiania , skompilowane odpowiednio z C1 i C2. U mnie ostateczny wariant (C2) wygląda mniej więcej tak:

...

; B1: # B3 B2 <- BLOCK HEAD IS JUNK  Freq: 1
0x00000000125461b0: mov   dword ptr [rsp+0ffffffffffff7000h], eax
0x00000000125461b7: push  rbp
0x00000000125461b8: sub   rsp, 40h
0x00000000125461bc: mov   ebp, dword ptr [rdx]
0x00000000125461be: mov   rcx, rdx
0x00000000125461c1: mov   r10, 57fbc220h
0x00000000125461cb: call  indirect r10    ; *iload_1

0x00000000125461ce: cmp   ebp, 7fffffffh  ; 7fffffff => 2147483647
0x00000000125461d4: jnl   125461dbh       ; jump if not less

; B2: # B3 <- B1  Freq: 0.999999
0x00000000125461d6: mov   ebp, 7fffffffh  ; *if_icmpge

; B3: # N44 <- B1 B2  Freq: 1       
0x00000000125461db: mov   edx, 0ffffff5dh
0x0000000012837d60: nop
0x0000000012837d61: nop
0x0000000012837d62: nop
0x0000000012837d63: call  0ae86fa0h

...

Jest trochę brudny, ale jeśli przyjrzysz się uważnie, możesz zauważyć, że nie ma tu długiej pętli. Istnieją 3 bloki: B1, B2 i B3, a etapy wykonania mogą być B1 -> B2 -> B3lub B1 -> B3. Gdzie Freq: 1- znormalizowana szacowana częstotliwość wykonywania bloku.

Mierzysz czas potrzebny na wykrycie, że pętla nic nie robi, kompilujesz kod w wątku w tle i eliminujesz kod.

for (int t = 0; t < 5; t++) {
    long start = System.nanoTime();
    for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; i++) {
    }
    long time = System.nanoTime() - start;

    String s = String.format("%d: Took %.6f ms", t, time / 1e6);
    Thread.sleep(50);
    System.out.println(s);
    Thread.sleep(50);
}

Jeśli uruchomisz to z -XX:+PrintCompilation, zobaczysz, że kod został skompilowany w tle do kompilatora poziomu 3 lub C1 i po kilku pętlach do poziomu 4 z C4.

    129   34 %     3       A::main @ 15 (93 bytes)
    130   35       3       A::main (93 bytes)
    130   36 %     4       A::main @ 15 (93 bytes)
    131   34 %     3       A::main @ -2 (93 bytes)   made not entrant
    131   36 %     4       A::main @ -2 (93 bytes)   made not entrant
0: Took 2.510408 ms
    268   75 %     3       A::main @ 15 (93 bytes)
    271   76 %     4       A::main @ 15 (93 bytes)
    274   75 %     3       A::main @ -2 (93 bytes)   made not entrant
1: Took 5.629456 ms
2: Took 0.000000 ms
3: Took 0.000364 ms
4: Took 0.000365 ms

Jeśli zmienisz pętlę, aby używała a long, nie będzie ona tak zoptymalizowana.

    for (long i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; i++) {
    }

zamiast tego dostajesz

0: Took 1579.267321 ms
1: Took 1674.148662 ms
2: Took 1885.692166 ms
3: Took 1709.870567 ms
4: Took 1754.005112 ms

Bierzesz pod uwagę czas rozpoczęcia i zakończenia w nanosekundach i dzielisz przez 10 ^ 6, aby obliczyć opóźnienie

long d = (finish - start) / 1000000

powinno być, 10^9ponieważ 1sekunda = 10^9nanosekunda.