Uruchomienie następującego programu Java zajmuje średnio od 0,50 sekundy do 0,55 sekundy:
public static void main(String[] args) {
long startTime = System.nanoTime();
int n = 0;
for (int i = 0; i < 1000000000; i++) {
n += 2 * (i * i);
}
System.out.println((double) (System.nanoTime() - startTime) / 1000000000 + " s");
System.out.println("n = " + n);
}
Jeśli mogę wymienić 2 * (i * i)
z 2 * i * i
, trwa między 0,60 i 0,65 sek do uruchomienia. Dlaczego?
Uruchomiłem każdą wersję programu 15 razy, naprzemiennie między nimi. Oto wyniki:
2*(i*i) | 2*i*i
----------+----------
0.5183738 | 0.6246434
0.5298337 | 0.6049722
0.5308647 | 0.6603363
0.5133458 | 0.6243328
0.5003011 | 0.6541802
0.5366181 | 0.6312638
0.515149 | 0.6241105
0.5237389 | 0.627815
0.5249942 | 0.6114252
0.5641624 | 0.6781033
0.538412 | 0.6393969
0.5466744 | 0.6608845
0.531159 | 0.6201077
0.5048032 | 0.6511559
0.5232789 | 0.6544526
Najszybsza seria 2 * i * i
trwała dłużej niż najwolniejsza seria 2 * (i * i)
. Gdyby mieli taką samą wydajność, prawdopodobieństwo takiego zdarzenia byłoby mniejsze niż 1/2^15 * 100% = 0.00305%
.
java
performance
benchmarking
bytecode
jit
Stefan
źródło
źródło
2 * i * i
jest on wolniejszy. Spróbuję również biegać z Graalem.i * i * 2
szybszy niż2 * i * i
? ”, Aby zwiększyć jasność, że problem występuje w kolejności operacji.Odpowiedzi:
Istnieje niewielka różnica w kolejności kodu bajtowego.
2 * (i * i)
:vs
2 * i * i
:Na pierwszy rzut oka nie powinno to mieć znaczenia; jeśli cokolwiek, druga wersja jest bardziej optymalna, ponieważ wykorzystuje o jedno miejsce mniej.
Musimy więc zagłębić się w niższy poziom (JIT) 1 .
Pamiętaj, że JIT bardzo agresywnie rozwija małe pętle. Rzeczywiście obserwujemy 16-krotne rozwijanie się
2 * (i * i)
przypadku:Widzimy, że na stosie znajduje się 1 rejestr „rozlany”.
A dla
2 * i * i
wersji:Tutaj obserwujemy znacznie więcej „rozlewania” i więcej dostępu do stosu
[RSP + ...]
, ze względu na więcej pośrednich wyników, które należy zachować.Zatem odpowiedź na pytanie jest prosta:
2 * (i * i)
jest szybsza niż2 * i * i
ponieważ JIT generuje bardziej optymalny kod asemblera dla pierwszego przypadku.Ale oczywiście jest oczywiste, że ani pierwsza, ani druga wersja nie jest dobra; pętla może naprawdę skorzystać z wektoryzacji, ponieważ każdy procesor x86-64 ma co najmniej obsługę SSE2.
Jest to więc kwestia optymalizatora; jak to często bywa, rozwija się zbyt agresywnie i strzela sobie w stopę, tracąc jednocześnie różne inne możliwości.
W rzeczywistości nowoczesne procesory x86-64 dzielą instrukcje na mikrooperacje (µops), a dzięki takim funkcjom, jak zmiana nazw rejestrów, pamięci podręczne µop i bufory pętli, optymalizacja pętli wymaga o wiele bardziej finezji niż zwykłe rozwijanie dla uzyskania optymalnej wydajności. Według przewodnika optymalizacji Agner Fog :
Jeśli chodzi o czasy ładowania - nawet najszybsze trafienie L1D kosztuje 4 cykle , dodatkowy rejestr i µop, więc tak, nawet kilka dostępów do pamięci pogorszy wydajność w ciasnych pętlach.
Wróćmy jednak do możliwości wektoryzacji - aby przekonać się, jak szybko może być, możemy skompilować podobną aplikację C za pomocą GCC , która całkowicie ją wektoryzuje (pokazano AVX2, SSE2 jest podobny) 2 :
Z czasem pracy:
1 Aby uzyskać dane wyjściowe zestawu wygenerowane przez JIT, pobierz JVM do debugowania i uruchom
-XX:+PrintOptoAssembly
2 Wersja C jest kompilowana z
-fwrapv
flagą, która pozwala GCC traktować przepełnienie liczby całkowitej ze znakiem jako uzupełnienie do dwóch.źródło
ret
instrukcję, lub wyślij etykietę, a nie instrukcję ret, więc wykonanie po prostu się kończy. GCC faktycznie zachowuje się tak, że czasami napotyka UB. Na przykład: dlaczego ret znikają z optymalizacją? . Na pewno chcesz skompilować dobrze sformułowany kod, aby mieć pewność, że asm jest rozsądny.mov
/add-immediate
. np.movl RBX, R9
/addl RBX, #8
powinno byćleal ebx, [r9 + 8]
, 1 uop, aby skopiować i dodać. Lubleal ebx, [r9 + r9 + 16]
zrobićebx = 2*(r9+8)
. Więc tak, rozwijanie się do punktu rozlewania jest głupie, podobnie jak naiwny kodegen Braindead, który nie korzysta z tożsamości liczb całkowitych i matematycznych liczb całkowitych asocjacyjnych.Gdy mnożenie jest możliwe
2 * (i * i)
, JVM jest w stanie wyliczyć mnożenie przez2
z pętli, co daje ten równoważny, ale bardziej wydajny kod:ale gdy mnożenie jest
(2 * i) * i
, JVM nie optymalizuje go, ponieważ mnożenie przez stałą nie jest już tuż przed dodaniem.Oto kilka powodów, dla których myślę, że tak jest:
if (n == 0) n = 1
instrukcji na początku pętli powoduje, że obie wersje są tak samo wydajne, ponieważ uwzględnienie mnożenia nie gwarantuje już, że wynik będzie taki sam2 * (i * i)
wersjaOto kod testowy, którego użyłem do wyciągnięcia następujących wniosków:
A oto wyniki:
źródło
n *= 2000000000;
2*1*1 + 2*2*2 + 2*3*3
. Oczywiste jest, że obliczanie1*1 + 2*2 + 3*3
i mnożenie przez 2 jest poprawne, podczas gdy mnożenie przez 8 nie byłoby.2(1²) + 2(2²) + 2(3²) = 2(1² + 2² + 3²)
. To było bardzo proste i po prostu zapomniałem, ponieważ przyrost pętli.2 * (i * i)
ale nie od(2 * i) * i
? Myślę, że są one równoważne (może to być moje złe założenie). Jeśli tak, to czy JVM nie kanonizuje wyrażenia przed optymalizacją?Kody bajtów: https://cs.nyu.edu/courses/fall00/V22.0201-001/jvm2.html Przeglądarka kodów bajtów: https://github.com/Konloch/bytecode-viewer
W moim JDK (Windows 10 64 bit, 1.8.0_65-b17) mogę odtworzyć i wyjaśnić:
Wynik:
Więc dlaczego? Kod bajtu jest następujący:
Różnica polega na: W nawiasach (
2 * (i * i)
):Bez nawiasów (
2 * i * i
):Ładowanie wszystkich na stos, a następnie powrót do pracy jest szybsze niż przełączanie między nakładaniem na stos i działaniem na nim.
źródło
Kasperd zapytał w komentarzu do zaakceptowanej odpowiedzi:
Nie mam wystarczającej reputacji, aby odpowiedzieć na to w komentarzach, ale są to te same ISA. Warto zauważyć, że wersja GCC używa 32-bitowej logiki liczb całkowitych, a wersja skompilowana w JVM używa 64-bitowej logiki liczb wewnętrznych.
R8 do R15 to tylko nowe rejestry X86_64 . EAX do EDX to dolne części rejestrów ogólnego przeznaczenia RAX do RDX. Ważną częścią odpowiedzi jest to, że wersja GCC nie jest rozwinięta. Po prostu wykonuje jedną rundę pętli na rzeczywistą pętlę kodu maszynowego. Podczas gdy wersja JVM ma 16 rund pętli w jednej pętli fizycznej (na podstawie odpowiedzi Rustyxa, nie zinterpretowałem zestawu). Jest to jeden z powodów, dla których używanych jest więcej rejestrów, ponieważ korpus pętli jest w rzeczywistości 16 razy dłuższy.
źródło
*2
w pętli. Chociaż w tym przypadku nie jest to nawet wygrana, ponieważ robi to za darmo z LEA. Na procesorach Intellea eax, [rax+rcx*2]
ma takie samo opóźnienie 1c jakadd eax,ecx
. Jednak w procesorach AMD każdy skalowany indeks zwiększa opóźnienie LEA do 2 cykli. Tak więc łańcuch zależności przenoszony przez pętlę wydłuża się do 2 cykli, stając się wąskim gardłem na Ryzen. (imul ecx,edx
przepustowość wynosi 1 na zegar na Ryzen i na Intel).Chociaż nie jest to bezpośrednio związane ze środowiskiem pytania, tylko dla ciekawości, zrobiłem ten sam test na .NET Core 2.1, x64, tryb wydania.
Oto interesujący wynik, potwierdzający podobne zjawiska (odwrotnie) zachodzące nad ciemną stroną siły. Kod:
Wynik:
2 * (i * i)
2 * i * i
źródło
Mam podobne wyniki:
Otrzymałem SAME wyniki, jeśli obie pętle były w tym samym programie lub każda z nich była w osobnym pliku .java / .class, wykonanym przy oddzielnym uruchomieniu.
Wreszcie, oto
javap -c -v <.java>
dekompilacja każdego z nich:vs.
FYI -
źródło
-XX:+PrintOptoAssembly
. Lub po prostu użyj vtune lub podobnego.Ciekawa obserwacja za pomocą Java 11 i wyłączanie rozwijania pętli za pomocą następującej opcji maszyny wirtualnej:
Pętla z
2 * (i * i)
wyrażeniem powoduje zwarty kod natywny 1 :w porównaniu z
2 * i * i
wersją:Wersja Java:
Wyniki testu porównawczego:
Kod źródłowy testu porównawczego:
1 - Zastosowane opcje VM:
-XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:LoopUnrollLimit=0
źródło
i
przed skopiowaniem go do obliczenia2*i
, robi to po, więc potrzebuje dodatkowejadd r11d,2
instrukcji. (Plus brakujeadd same,same
wizjera zamiast oshl
1 (dodaj działa na większej liczbie portów). Brakuje również wizjera LEA dlax*2 + 2
(lea r11d, [r8*2 + 2]
), jeśli naprawdę chce robić rzeczy w tej kolejności z jakiegoś szalonego powodu planowania instrukcji. Widzieliśmy już z wersja rozwijana, w której brakowało LEA, kosztowała ją wiele ulepszeń, tak samo jak tutaj obie pętlelea eax, [rax + r11 * 2]
zastąpiłby 2 instrukcje (w obu pętlach), gdyby kompilator JIT miał czas na poszukiwanie tej optymalizacji w długo działających pętlach. Dowolny kompilator z wyprzedzeniem by go znalazł. (Chyba że strojenie tylko dla AMD, gdzie LEA ze skalowanym indeksem ma opóźnienie 2 cykli, więc może nie jest tego warte.)Wypróbowałem JMH przy użyciu domyślnego archetypu: dodałem również zoptymalizowaną wersję opartą na wyjaśnieniu Runemoro .
Rezultaty są tutaj:
Na moim komputerze ( Core i7 860 - nie robi nic poza czytaniem na moim smartfonie):
n += i*i
następnien*2
jest pierwszy2 * (i * i)
jest drugi.JVM najwyraźniej nie optymalizuje w taki sam sposób jak człowiek (na podstawie odpowiedzi Runemoro).
Teraz czytając kod bajtowy:
javap -c -v ./target/classes/org/sample/MyBenchmark.class
Nie jestem ekspertem w dziedzinie kodu bajtowego, ale my
iload_2
przedtemimul
: pewnie na tym polega różnica: mogę założyć, że JVM optymalizuje odczyti
dwa razy (i
jest już tutaj i nie ma potrzeby ładowania go ponownie), podczas2*i*i
gdy może t.źródło
Więcej aneksu. Powtórzyłem eksperyment przy użyciu najnowszej JVM Java 8 firmy IBM:
I to pokazuje bardzo podobne wyniki:
(drugie wyniki przy użyciu 2 * i * i).
Co ciekawe, podczas uruchamiania na tym samym komputerze, ale przy użyciu Oracle Java:
wyniki są średnio nieco wolniejsze:
Krótko mówiąc: nawet niewielki numer wersji HotSpot ma tutaj znaczenie, ponieważ subtelne różnice w implementacji JIT mogą mieć znaczące efekty.
źródło
Dwie metody dodawania generują nieco inny kod bajtowy:
Dla
2 * (i * i)
vs:Dla
2 * i * i
.Podczas korzystania z testu porównawczego JMH takiego:
Różnica jest wyraźna:
To, co obserwujesz, jest poprawne, a nie tylko anomalią Twojego stylu testu porównawczego (tj. Bez rozgrzewki, zobacz Jak napisać poprawny mikroprocesor w Javie? )
Ponowne uruchamianie z Graal:
Widzisz, że wyniki są znacznie bliższe, co ma sens, ponieważ Graal jest ogólnie lepiej działającym, bardziej nowoczesnym kompilatorem.
Tak więc tak naprawdę zależy to od tego, jak dobrze kompilator JIT jest w stanie zoptymalizować określony fragment kodu i niekoniecznie ma logiczny powód.
źródło