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

Question

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

Piszę kod w Javie, gdzie 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 i nigdy nie mieszczą się 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ż spodziewam się, że ten fragment kodu będzie działał miliony razy na run, zastanawiałem się, który z nich będzie szybszy. Zrobiłem eksperyment porównując je na ogromnej losowo generowana tablica, i byłem również ciekaw, jak sparsity tablicy (ułamek 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 więcej niż ~3% czasu, a*b != 0 jest szybsze niż a!=0 && b!=0:

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

Edytuj: z ciekawości... now that I dowiedziałem się o przewidywaniu gałęzi, zastanawiałem się, co porównanie analogowe pokaże dla lub b jest niezerowe:

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

Update

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

2 - i również włączone a != 0 || b != 0, (a+b) != 0 i (a|b) != 0 z ciekawości, po zapoznaniu się z prognozowaniem gałęzi. Ale nie są one logicznie równoważne innym wyrażeniom, ponieważ tylko a lub b musi być niezerowe, aby zwrócić true, więc nie należy ich porównywać pod względem wydajności przetwarzania.

3-dodałem również rzeczywisty benchmark, którego użyłem do analizy, która jest po prostu iteracją arbitralnej zmiennej int.

4-niektórzy sugerowali, aby włączyć a != 0 & b != 0 w przeciwieństwie do a != 0 && b != 0, z przewidywaniem, że będzie zachowywać się bliżej a*b != 0, ponieważ usuniemy efekt przewidywania gałęzi. Nie wiedziałem, że & może być używany ze zmiennymi logicznymi, myślałem, że jest używany tylko do operacji binarnych z liczbami całkowitymi.

Uwaga: w kontekście, w którym rozważałem to wszystko, przepełnienie int nie jest problemem, ale jest to zdecydowanie ważna kwestia w ogólnych kontekstach.

Procesor: Intel Core i7-3610QM @ 2.3 GHz

Wersja Javy: 1.8.0_45
Java (TM) SE Runtime Environment (build 1.8.0_45-b14)
Java HotSpot (TM) 64-Bit Serwer VM (build 25.45-B02, mixed mode)

355

java performance branch-prediction microbenchmark processing-efficiency

Author: Maljam, 2016-02-21

Source

5 answers

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

(a*b)!=0 (a+b)!=0 zrobi złą rzecz dla wartości, które się przepełniają, a (a+b)!=0 dodatkowo zrobi złą rzecz dla wartości dodatnich i ujemnych, które sumują się do zera, więc nie można użyć żadnego z tych wyrażeń w ogólnym przypadku, nawet jeśli działają tutaj.
(a|b)!=0 and (a+b)!=0 are testing if either value is non-zero, while (a*b)!=0 i a != 0 && b != 0 sprawdzają, czy oba są niezerowe. Te dwa typy warunków nie będą prawdziwe dla tego samego odsetka danych.
Maszyna wirtualna zoptymalizuje wyrażenie podczas kilku pierwszych uruchomień zewnętrznej pętli (fraction), Gdy fraction jest równe 0, gdy gałęzie prawie nigdy nie są brane. Optymalizator może robić różne rzeczy, jeśli zaczniesz fraction od 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 czynnik komplikujący, gdy próbuje dowiedzieć się, co dzieje się na niskim poziomie. Możesz uzyskać różne wyniki, jeśli podzielisz tablicę dwuwymiarową na dwie tablice płaskie, zmieniając nums[0][i] i nums[1][i] na nums0[i] i nums1[i].
Predyktory gałęzi CPU próbują wykryć krótkie wzorce w danych lub przebieg wszystkich branych gałęzi lub nie branych. Twoje losowo generowane dane porównawcze to najgorsza rzecz dla oddziału / align = "left" / Jeśli twoje rzeczywiste dane mają przewidywalny wzorzec lub mają długie przebiegi wszystkich wartości zerowych i wszystkich niezerowych, gałęzie mogą kosztować znacznie mniej.
Konkretny kod, który jest wykonywany po spełnieniu warunku, może mieć wpływ na wydajność samego warunku, ponieważ wpływa na rzeczy takie jak to, czy pętla może być rozwinięta, które rejestry CPU są dostępne, i jeśli którakolwiek z pobranych wartości nums musi być ponownie użyta po tym, jak ocena stanu. Samo zwiększenie licznika w benchmarku nie jest idealnym elementem zastępczym dla tego, co zrobiłby prawdziwy kod.
System.currentTimeMillis() w większości systemów nie jest dokładniejsza niż +/- 10 ms. {[15] } jest zwykle dokładniejsza.

Jak widać jest wiele niepewności i zawsze trudno powiedzieć coś konkretnego w przypadku tego rodzaju mikro-optymalizacji, ponieważ sztuczka, która jest szybsza na jednej maszynie wirtualnej lub procesorze, może być wolniejsza na innej. Jeśli twoja maszyna wirtualna jest hotspotem, należy pamiętać, że istnieją dwie dalsze odmiany maszyny wirtualnej " klienckiej "o różnych (słabszych) optymalizacjach w porównaniu do maszyny wirtualnej" serwerowej".

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

63

Author: Boann,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-02-22 16:16:42

Odpowiedzi tutaj są dobre, chociaż miałem pomysł, który może poprawić rzeczy.

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

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

Może też działać

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

Z tego powodu, zgodnie z regułami zwarcia, jeśli pierwszy boolean jest fałszywy, drugi nie powinien być oceniany. Musi wykonać dodatkową gałąź, aby uniknąć oceny nums[1][i] if nums[0][i] was false. Możesz nie dbać o to, że nums[1][i] zostanie oceniony, ale kompilator nie może być pewien, że nie wyrzuci poza zakres lub null ref kiedy to zrobisz. Redukując blok if do prostych boolów, kompilator może być na tyle inteligentny, aby zdać sobie sprawę, że niepotrzebna ocena drugiej boolowskiej nie będzie miała negatywnych skutków ubocznych.

21

Author: Pagefault,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-02-23 07:11:12

Jeśli weźmiemy mnożenie, nawet jeśli jedna liczba jest równa 0, to iloczyn jest równy 0. Podczas pisania

    (a*b != 0)

Ocenia wynik produktu eliminując tym samym kilka pierwszych wystąpień iteracji począwszy 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. Stąd wymagany czas jest mniejszy. Ale wierzę, że drugi warunek może dać ci dokładniejsze rozwiązanie.

10

Author: Sanket Gupte,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-02-21 02:30:11

Używasz randomizowanych danych wejściowych, które sprawiają, że gałęzie są nieprzewidywalne. W praktyce gałęzie są często (~90%) przewidywalne, więc w kodzie rzeczywistym kod rozgałęzienia prawdopodobnie będzie szybszy.

To powiedziane. Nie wiem jak a*b != 0 może być szybszy niż (a|b) != 0. Generalnie mnożenie liczb całkowitych jest droższe niż bitowe OR. Ale takie rzeczy czasami stają się dziwne. Zobacz na przykład" przykład 7: złożoność sprzętowa " przykład z galerii efektów pamięci podręcznej procesora .

6

Author: StackedCrooked,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-02-24 16:44:55

score 216 · Accepted Answer

Ignoruję problem, że Twój benchmarking może być wadliwy i biorąc wynik za wartość nominalną.

Czy jest to kompilator czy na poziomie sprzętowym?

To ostatnie, chyba:

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

Skompiluje do 2 obciążeń pamięci i dwóch gałęzi warunkowych

  if (a * b != 0)

Skompiluje do 2 obciążeń pamięci, mnożenia i jednej gałęzi warunkowej.

Mnożenie jest prawdopodobnie szybsze niż druga gałąź warunkowa, jeśli przewidywanie gałęzi na poziomie sprzętowym jest nieskuteczne. Jak zwiększyć stosunek ... przewidywanie gałęzi staje się coraz mniej skuteczne.

Powodem, dla którego gałęzie warunkowe są wolniejsze, jest to, że powodują zatrzymanie potoku wykonywania instrukcji. Przewidywanie gałęzi polega na unikaniu przeciągnięcia, przewidując, w którą stronę pójdzie gałąź i spekulacyjnie wybierając na tej podstawie następną instrukcję. Jeśli przewidywanie nie powiedzie się, następuje opóźnienie, podczas gdy instrukcja dla drugiego kierunek załadowany.

(uwaga: powyższe Wyjaśnienie jest uproszczone. Aby uzyskać dokładniejsze wyjaśnienie, musisz spojrzeć na literaturę dostarczoną przez producenta procesora dla koderów języka asemblera i kompilatorów. Strona Wikipedii na Branch Predictors jest dobrym tłem.)

Jest jednak jedna rzecz, na którą należy uważać przy tej optymalizacji. Czy są jakieś wartości, w których a * b != 0 da złą odpowiedź? Rozważ przypadki, w których obliczanie produktu powoduje całkowite przepełnienie.

UPDATE

Twoje wykresy potwierdzają to, co powiedziałem.

Istnieje również efekt "przewidywania gałęzi" w przypadku gałęzi warunkowej a * b != 0, który pojawia się na wykresach.
Jeśli wyświetlasz krzywe poza 0,9 na osi X, wygląda na to, że 1) spotkają się na około 1,0 i 2) punkt spotkania będzie miał mniej więcej taką samą wartość Y, jak dla X = 0.0.

UPDATE 2

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

(zauważ, że tego rodzaju rzeczy mogą być specyficzne dla konkretnego numeru modelu układu, a nawet wersji. Wyniki testów mogą być różne w innych systemach.)

Jednak obie mają tę zaletę, że praca dla wszystkich nieujemnych wartości a i b.