Dlaczego (a * b! = 0) jest szybszy niż (a! = 0 && b! = 0) w Javie?

Piszę trochę kodu w Javie, w którym w pewnym momencie przepływ programu zależy od tego, czy dwie zmienne int, „a” i „b”, są niezerowe (uwaga: a i b nigdy nie są ujemne, a nigdy w zakresie przepełnienia liczb całkowitych).

Mogę to ocenić za pomocą

if (a != 0 && b != 0) { /* Some code */ }

Lub alternatywnie

if (a*b != 0) { /* Some code */ }

Ponieważ oczekuję, że ten fragment kodu będzie uruchamiany miliony razy na uruchomienie, zastanawiałem się, który z nich będzie szybszy. Zrobiłem eksperyment, porównując je na ogromnej losowo wygenerowanej tablicy, i byłem również ciekawy, jak rzadkość tablicy (część danych = 0) wpłynie na wyniki:

long time;
final int len = 50000000;
int arbitrary = 0;
int[][] nums = new int[2][len];

for (double fraction = 0 ; fraction <= 0.9 ; fraction += 0.0078125) {
    for(int i = 0 ; i < 2 ; i++) {
        for(int j = 0 ; j < len ; j++) {
            double random = Math.random();

            if(random < fraction) nums[i][j] = 0;
            else nums[i][j] = (int) (random*15 + 1);
        }
    }

    time = System.currentTimeMillis();

    for(int i = 0 ; i < len ; i++) {
        if( /*insert nums[0][i]*nums[1][i]!=0 or nums[0][i]!=0 && nums[1][i]!=0*/ ) arbitrary++;
    }
    System.out.println(System.currentTimeMillis() - time);
}

A wyniki pokazują, że jeśli spodziewasz się, że „a” lub „b” będzie równe 0 przez więcej niż ~ 3% czasu, a*b != 0jest to szybsze niż a!=0 && b!=0:

Jestem ciekawy, dlaczego. Czy ktoś mógłby rzucić trochę światła? Czy to jest kompilator, czy jest na poziomie sprzętowym?

Edycja: Z ciekawości ... teraz, gdy dowiedziałem się o przewidywaniu gałęzi, zastanawiałem się, co pokaże porównanie analogowe dla OR b jest niezerowe:

Widzimy taki sam efekt przewidywania gałęzi, jak oczekiwano, co ciekawe, wykres jest nieco odwrócony wzdłuż osi X.

Aktualizacja

1- Dodałem !(a==0 || b==0)do analizy, aby zobaczyć, co się stanie.

2- ja również a != 0 || b != 0, (a+b) != 0i (a|b) != 0z ciekawości, gdy dowiedział się o przewidywania rozgałęzień. Ale nie są one logicznie równoważne z innymi wyrażeniami, ponieważ tylko OR b musi być niezerowe, aby zwrócić true, więc nie należy ich porównywać pod kątem wydajności przetwarzania.

3- Dodałem również rzeczywisty test porównawczy, którego użyłem do analizy, która jest po prostu iteracją dowolnej zmiennej int.

4 - Niektóre osoby sugerowały włączenie a != 0 & b != 0w przeciwieństwie do a != 0 && b != 0prognozy, że będzie się ona zachowywać ściślej, a*b != 0ponieważ usuniemy efekt przewidywania gałęzi. Nie wiedziałem, że &można go używać ze zmiennymi boolowskimi, myślałem, że był on używany tylko do operacji binarnych z liczbami całkowitymi.

Uwaga: W kontekście, który rozważałem, przepełnienie int nie jest problemem, ale jest to zdecydowanie ważna uwaga w kontekście ogólnym.

Procesor: Intel Core i7-3610QM @ 2,3 GHz

Wersja Java: 1.8.0_45
Środowisko wykonawcze Java (TM) SE (kompilacja 1.8.0_45-b14
) 64-bitowa maszyna wirtualna serwera Java HotSpot (TM) (kompilacja 25.45-b02, tryb mieszany)

Ignoruję problem, że twoje testy porównawcze mogą być wadliwe, i oceniam wynik na pierwszy rzut oka.

Czy to jest kompilator, czy jest na poziomie sprzętowym?

Myślę, że ten ostatni:

  if (a != 0 && b != 0)

skompiluje się do 2 ładowań pamięci i dwóch gałęzi warunkowych

  if (a * b != 0)

skompiluje do 2 ładowań pamięci, wielokrotności i jednej gałęzi warunkowej.

Mnożenie będzie prawdopodobnie szybsze niż druga gałąź warunkowa, jeśli przewidywanie gałęzi na poziomie sprzętu jest nieskuteczne. W miarę zwiększania współczynnika przewidywanie gałęzi staje się coraz mniej skuteczne.

Powodem, dla którego gałęzie warunkowe są wolniejsze, jest to, że powodują one zatrzymanie potoku wykonywania instrukcji. Prognozowanie gałęzi polega na unikaniu przeciągnięcia poprzez przewidywanie, w którą stronę pójdzie gałąź i spekulatywne wybieranie następnej instrukcji na tej podstawie. Jeśli przewidywanie się nie powiedzie, nastąpi opóźnienie podczas ładowania instrukcji dla drugiego kierunku.

(Uwaga: powyższe wyjaśnienie jest nadmiernie uproszczone. Aby uzyskać dokładniejsze wyjaśnienie, należy zapoznać się z literaturą dostarczoną przez producenta procesora dla koderów języka asemblera i autorów kompilatorów. Strona Wikipedii na temat Predictors oddziałów jest dobrym tłem).

Jednak przy tej optymalizacji należy zachować ostrożność. Czy są jakieś wartości, a * b != 0które dadzą złą odpowiedź? Rozważ przypadki, w których obliczenie produktu powoduje przepełnienie liczb całkowitych.

AKTUALIZACJA

Twoje wykresy zwykle potwierdzają to, co powiedziałem.

• W warunkowym a * b != 0przypadku rozgałęzienia występuje również efekt „przewidywania rozgałęzień” , który pojawia się na wykresach.

• Jeśli rzutujesz krzywe powyżej 0,9 na oś X, wygląda na to, że 1) spotkają się na około 1,0 i 2) punkt spotkania będzie miał mniej więcej tę samą wartość Y jak dla X = 0,0.

AKTUALIZACJA 2

Nie rozumiem, dlaczego krzywe są różne dla przypadków a + b != 0i a | b != 0. W logice predyktorów gałęzi może być coś sprytnego. Lub może wskazywać na coś innego.

(Pamiętaj, że tego rodzaju rzeczy mogą być specyficzne dla konkretnego numeru modelu chipa lub nawet wersji. Wyniki twoich testów mogą być inne w innych systemach).

Oba mają jednak tę zaletę, że działają dla wszystkich nieujemnych wartości ai b.

Myślę, że twój test porównawczy ma pewne wady i może nie być przydatny do wnioskowania o prawdziwych programach. Oto moje przemyślenia:

• (a|b)!=0i (a+b)!=0sprawdź, czy którakolwiek wartość jest różna od zera, a != 0 && b != 0i (a*b)!=0sprawdź, czy obie są niezerowe. Więc nie porównujesz taktowania samej arytmetyki: jeśli warunek jest spełniony częściej, powoduje to więcej wykonań ifciała, co również zajmuje więcej czasu.

• (a+b)!=0 zrobi coś złego dla wartości dodatnich i ujemnych, które sumują się do zera, więc nie można jej użyć w ogólnym przypadku, nawet jeśli tutaj działa.

• Podobnie (a*b)!=0zrobi coś złego w przypadku przepełnienia wartości. (Przypadkowy przykład: 196608 * 327680 ma wartość 0, ponieważ prawdziwy wynik może być podzielny przez 2 ³² , więc jego niskie 32 bity to 0, a te bity są wszystkim, co otrzymasz, jeśli jest to intoperacja.)

• Maszyna wirtualna zoptymalizuje wyrażenie podczas pierwszych kilku uruchomień fractionpętli zewnętrznej ( ), gdy fractionwynosi 0, gdy gałęzie prawie nigdy nie są brane. Optymalizator może robić różne rzeczy, jeśli zaczniesz fractionod 0,5.

• O ile maszyna wirtualna nie jest w stanie wyeliminować niektórych kontroli granic tablicy, istnieją cztery inne gałęzie w wyrażeniu tylko ze względu na kontrole granic, a to jest komplikujący czynnik przy próbie ustalenia, co dzieje się na niskim poziomie. Możesz uzyskać różne wyniki, jeśli podzielisz tablicę dwuwymiarową na dwie płaskie tablice, zmieniając nums[0][i]i nums[1][i]na nums0[i]i nums1[i].

• Predyktory gałęzi procesora wykrywają krótkie wzorce w danych lub przebiegi wszystkich branych branych lub nie branych. Losowo generowane dane porównawcze są najgorszym scenariuszem dla predyktora gałęzi . Jeśli rzeczywiste dane mają przewidywalny wzorzec lub mają długie serie wartości zerowych i zerowych, gałęzie mogą kosztować znacznie mniej.

• Konkretny kod, który jest wykonywany po spełnieniu warunku, może wpływać na wydajność oceny samego warunku, ponieważ wpływa na takie rzeczy, jak to, czy pętla może zostać rozwinięta, które rejestry procesora są dostępne i czy któraś z pobranych numswartości musi być ponownie użyte po ocenie stanu. Zwykłe zwiększanie licznika w teście porównawczym nie jest idealnym symbolem zastępczym dla tego, co zrobiłby prawdziwy kod.

• System.currentTimeMillis()jest w większości systemów nie dokładniejszy niż +/- 10 ms. System.nanoTime()jest zwykle dokładniejszy.

Istnieje wiele niepewności i zawsze trudno jest powiedzieć coś konkretnego z tego rodzaju mikrooptymalizacjami, ponieważ sztuczka, która jest szybsza na jednej maszynie wirtualnej lub procesorze, może być wolniejsza na innej. Jeśli korzystasz z 32-bitowej maszyny JVM HotSpot, a nie w wersji 64-bitowej, pamiętaj, że występuje ona w dwóch wersjach: z maszyną wirtualną „Klient” z różnymi (słabszymi) optymalizacjami w porównaniu z maszyną wirtualną „Serwer”.

Jeśli możesz zdemontować kod maszynowy wygenerowany przez maszynę wirtualną , zrób to, zamiast zgadywać, co robi!

Odpowiedzi tutaj są dobre, chociaż wpadłem na pomysł, który może poprawić sytuację.

Ponieważ dwie gałęzie i związane z nimi przewidywanie gałęzi są prawdopodobnymi winowajcami, możemy być w stanie zredukować rozgałęzienie do jednej gałęzi bez zmiany logiki.

bool aNotZero = (nums[0][i] != 0);
bool bNotZero = (nums[1][i] != 0);
if (aNotZero && bNotZero) { /* Some code */ }

Może to również działać

int a = nums[0][i];
int b = nums[1][i];
if (a != 0 && b != 0) { /* Some code */ }

Powodem jest to, że zgodnie z regułami zwarcia, jeśli pierwszy boolean jest fałszywy, drugiego nie należy oceniać. Musi wykonać dodatkową gałąź, aby uniknąć oceny, nums[1][i]czy nums[0][i]to fałsz. Teraz możesz nie przejmować nums[1][i]się oceną, ale kompilator nie może być pewien, że nie wyrzuci poza zakresu lub wartości zerowej. Zmniejszając blok if do prostych boolów, kompilator może być wystarczająco inteligentny, aby zdać sobie sprawę, że niepotrzebna ocena drugiego boolean nie będzie miała negatywnych skutków ubocznych.

Gdy weźmiemy mnożenie, nawet jeśli jedna liczba wynosi 0, to iloczyn to 0. Podczas pisania

    (a*b != 0)

Ocenia wynik produktu, eliminując w ten sposób kilka pierwszych wystąpień iteracji, zaczynając od 0. W rezultacie porównania są mniejsze niż w przypadku warunku

   (a != 0 && b != 0)

Gdzie każdy element jest porównywany z 0 i oceniany. Dlatego wymagany czas jest krótszy. Ale wierzę, że drugi warunek może dać ci dokładniejsze rozwiązanie.

Używasz losowych danych wejściowych, co powoduje, że oddziały są nieprzewidywalne. W praktyce rozgałęzienia są często (~ 90%) przewidywalne, więc w prawdziwym kodzie rozgałęziony kod będzie prawdopodobnie szybszy.

To mówi. Nie rozumiem, jak a*b != 0może być szybciej niż (a|b) != 0. Zasadniczo mnożenie liczb całkowitych jest droższe niż bitowe OR. Ale takie rzeczy czasami stają się dziwne. Zobacz na przykład przykład „Przykład 7: Złożoność sprzętu” z galerii efektów pamięci podręcznej procesora .