Czy kompilator Java kompilator JIT lub optymalizuje podziały lub multiplikacje przez stałą moc dwóch do przesunięcia bitowego?Czy Java optymalizuje dzielenie przez moce dwóch do przenoszenia bitu?
Czy na przykład poniższe dwie instrukcje zostały zoptymalizowane tak, aby były takie same?
int median = start + (end - start) >>> 1;
int median = start + (end - start)/2;
(w zasadzie this question ale dla Java)
Nie, kompilator Javy nie robi, ponieważ nie może być pewny tego, co znak (end - start) będzie. Dlaczego to ma znaczenie? Przesunięcia bitów na liczbach całkowitych ujemnych dają inny wynik niż zwykły podział. Tutaj można zobaczyć demo: this simple test:
System.out.println((-10) >> 1); // prints -5
System.out.println((-11) >> 1); // prints -6
System.out.println((-11)/2); // prints -5
Należy również zauważyć, że użyłem >> zamiast >>>. A >>> to unsigned bitshift, a podpis >>.
System.out.println((-10) >>> 1); // prints 2147483643
@Mystical: Napisałem punkt odniesienia, który pokazuje, że kompilator/JVM nie robi optymalizacja: https://ideone.com/aKDShA
Chociaż nie są one takie same, nie ma nic, co mogłoby powstrzymać kompilator przed obejściem. Na przykład 'x/2' jest równe' (x - (x >> 31)) >> 1'. – Mysticial
To są 3 instrukcje ASM w stosunku do 1. Nie sądzę, że jest to optymalizacja. Może się mylić. –
Podział jest zdecydowanie wolniejszy niż 3 podstawowe instrukcje. W zależności od tego, przez co dzielisz, mają one od 10 do 70 cykli. Podczas gdy większość podstawowych instrukcji to tylko 1 cykl. (nie licząc przepustowości) – Mysticial
Choć przyjął odpowiedź ma rację w tym sensie, że podział może zamiast prostej zmiany, benchmark jest bardzo źle. Każdy test Java działający krócej niż jedną sekundę prawdopodobnie mierzy wydajność interpretera - nie jest to coś, na czym zwykle zależy.
Nie mogłem się oprzeć i napisałem własny kod benchmark, który pokazuje przede wszystkim, że jest bardziej skomplikowany. Nie chcę, aby w pełni wyjaśnić results, ale mogę powiedzieć, że
Dzięki. To przydatne informacje i dobre dane. – wchargin
Twoja odpowiedź brzmi: "podział według potęgi dwóch zostaje zastąpiony przez przesunięcie w prawo i korekta liczb ujemnych", podczas gdy zaakceptowana odpowiedź mówi, że tak nie jest, która z nich jest? – vach
@vach Mój benchmark wyraźnie pokazuje, że optymalizacja rzeczywiście jest wykonywana (jednak w zależności od VM i procesora). Benchmark z zaakceptowanej odpowiedzi jest całkowicie zepsuty z powodu eliminacji martwego kodu, więc możemy go zapomnieć (przeczytaj o blackhole JMH, jeśli nie masz pewności, komu zaufać). – maaartinus
Jeśli JVM tego nie robi, możesz to zrobić samodzielnie.
Jak wspomniano, prawe przesunięcia na liczbach ujemnych nie zachowują się tak samo jak podział, ponieważ wynik jest zaokrąglany w niewłaściwym kierunku. Jeśli wiesz, że dywidenda jest nieujemna, możesz bezpiecznie zastąpić dywizję zmianą. Jeśli może być ujemna, możesz skorzystać z poniższej techniki.
Jeśli można wyrazić swój oryginalny kod w tej formie:
int result = x/(1 << shift);
można zastąpić go z tego kodu zoptymalizowanego:
int result = (x + (x >> 31 >>> (32 - shift))) >> shift;
Lub alternatywnie:
int result = (x + ((x >> 31) & ((1 << shift) - 1))) >> shift;
These formuły kompensują niepoprawne zaokrąglenia, dodając małą liczbę obliczoną z bitu znaku z dywidendy. Działa to na każdym x z wszystkich wartości przesunięcia od 1 do 30.
Jeśli przesunięcie to 1 (to znaczy, to jest dzielenie przez 2), a następnie >> 31 można usuwać w pierwszej formuły, aby ten bardzo czyste fragmentu:
int result = (x + (x >>> 31)) >> 1;
Zauważyłem, że te techniki są szybsze, nawet jeśli przesunięcie nie jest stałe, ale oczywiście przynoszą one najwięcej korzyści, jeśli przesunięcie jest stałe. Uwaga: W przypadku longx zamiast int, zmiany 31 i 32 odpowiednio do 63 i 64.
Examining the generated machine code pokazuje, że (nic dziwnego) HotSpot VM Server może zrobić optymalizacji automatycznie, gdy zmiana jest stała, ale (również zaskoczeniem) Maszyna wirtualna klienta HotSpot jest zbyt głupia.
Czy spojrzałeś na kod bajtowy wygenerowany przez te dwie instrukcje? – Julien
Zauważ, że istnieje kilka kompilatorów. E.g javac i ten w czasie zaćmienia. –
@Julien Rozważam także JIT. – wchargin