Co jest szybsze? Warunek, czy dodawanie 0

Witam
załóżmy, że mam tablicę 200 elementową, 100 elementów jest o wartości 0, a drugie 100 ma wartość dodatnią, albo ujemną. Czy szybciej będzie jeżeli dodam każdy element nawet ten zerowy:

 
for (int i = 0;i<200;i++)
{
    suma+=tab[i];
}

Czy lepiej jeżeli wstawię warunek sprawdzający, czy dany element równa się 0:

for (int i = 0;i<200;i++)
{
    if (tab[i]!=0)
    {
        suma+=tab[i];
    }
}
 

Teoretycznie wykonam mniej dodawań, ale nie wiem jak warunki wpływają na szybkość działania, bo wtedy wykonam jednak więcej operacji. Jak wyszukać literaturę, która mogłaby mi rozjaśnić co nieco na temat jakie operacje działają szybciej, a które wolniej?

Jeśli tablica będzie posortowana, to wersja z warunkiem będzie szybsza. Będzie szybsza ponieważ procesor wykryje że przez odpowiednią ilość iteracji warunek nie jest spełniany i zacznie go po prostu pomijać. W sytuacji gdy się pomyli to będzie musiał jeszcze raz pewne operacje wykonać i ponownie przejsc przez tą konkretną iterację, ale i tak będzie to sie opłacało. Jeśli tabela posortowana nie jest, to może być nawet wolniejsza. Poczytaj o branch prediction.

a co, dziala ci za wolno? uzywaj pierwszej wersji bo jest duzo czytelniejsza a potencjalny zysk jest tak czy siak pomijalny.

http://ideone.com/wOEHI7

Właściwie to było do przewidzenia - każdy if przekłada się w skoki do odpowiednich instrukcji programu, takie troche goto w asm. Dodawanie jest natomiast bardzo szybkie. Spora różnica jest na każdym poziomie optymalizacji (O0- Ofast) jednak przy 200 elementach różnicy nie ma.

premature optimization is the root of all evil
Zajmij się optymalizacją algorytmu w większej skali, a nie czymś takim - najlepiej zacznij od odpalenia profilera.

Nic, robię zadanie ze spoja i przypomniał mi się wykład profesora Krzysztofa Diksa (na youtube gdzieś jest) i to jak mówił o mnożeniu macierzy przez wektor, on wspominał tam, że jeżeli tych niezerowych elementów byłoby mało to jest to szybsze, ale nie bardzo rozumiem dlaczego, bo dla każdej liczby trzeba także sprawdzić warunek co zdawało mi się, że jednak zwiększa ilość operacji, gdy tych niezerowych elementów jest więcej i wydłuża czas obliczania tego, więc nie zawsze powinno być to dobre, ale założyłem, że tak jest. Teraz pomyślałem o czymś podobnym tylko, że tutaj wykonuje i tak jedną operację, a nie dodatkowe 2 przy true, a dodatkowo 0 przy false (o ile się nie mylę). Ciekaw byłem, czy to po prostu te 2 operacje mniej przyśpiesza program, czy sprawdzanie warunku.

Cyfra to nie jest liczba.

Ciekaw byłem, czy to po prostu te 2 operacje mniej przyśpiesza program, czy sprawdzanie warunku.

Jeśli branch predictor nawali i nie odgadnie, która część ifa zaraz się wykona (a nie ma prawa wiedzieć bez wykonania tego porównania), nastąpi bardzo bolesny branch misprediction, cały pipeline będzie musiał zostać wyczyszczony i, cóż, to jest znacznie dłuższe niż po prostu wykonanie dodawania.

Dodawanie jest niewątpliwie szybsze od warunku. W wersji pierwszej masz jedno dodawanie. W wersji drugiej masz warunek + 0.5 dodawania (statystycznie). Teraz sam pomyśl co musi być szybsze.

Już rozumiem, dziękuję. Przekombinowałem trochę, sądziłem na początku, że jeżeli jest warunek jako false to po jakimś czasie kompilator będzie to jakoś ignorować, albo przeliczać szybciej i wróci do tego dopiero jak wartość będzie inna od false i dzięki temu przy dużej ilości zer zadziała to szybciej...

Dokładnie tak (no prawie dokładnie) działa branch prediction. Procesor musi być jednak w stanie przewidzieć, kiedy warunek jest false. Pomaga mu w tym na przykład sortowanie tablicy:
http://ideone.com/qVD1YO

Po sortowaniu na początku jest mnóstwo zer - po jakimś czasie procesor to zauważy i będzie strzelał, że w kolejnej komórce tablicy jest też zero. To sporo przyśpiesza. Jeśli natomiast liczby są randomowo rozrzucone po tablicy, to branch prediction nic nie zdziała.
Świetne wytłumaczenie tutaj: http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array

Jak już koledzy napisali, warunek zależny od danych jest bardzo kosztowny jeśli te dane są losowe, ze względu na branch prediction.
Jeżeli rzeczywiście pierwsze 100 elementów jest zerowych, a potem same niezerowe, albo na przemian - zero, niezero, to predyktor skoków sobie z tym poradzi.
Ale jeśli te zera są rozrzucone chaotycznie, to cpu nie jest jasnowidzem, i przy 50% pudłowaniu predyktora skoków pętla będzie działać bardzo wolno.

Zgodnie z Glodbotem to GCC 5.2 w przypadku braku optymalizacji spowoduje, że kod z ifem będzie o znacznie dłuższy: https://goo.gl/5ZzxUe
W przypadku optymalizacji, podstawowych optymalizacji kod wyjściowy jest identyczny: https://goo.gl/YPUAqF

Fajnie gcc rozwij... masakruje tę pętlę jak się da -O3.

Co do tematu wątku, to pozwolę sobie trochę rozwinąć:

• Operacje arytmetyczno-logiczne na intach są bardzo szybkie. Na większości nowoczesnych procesorów dodawanie, odejmowanie, przesunięcia bitowe, and/or/xor, porównania to wszystko 1 cykl, mnożenie intów to na ogół 3. Wyjątkiem jest dzielenie, które potrafi być powolniejsze niż pierwiastkowanie floatów (ostatnio jak robiłem testy na Sandy Bridge, to zajmowało ok. 60 cykli, a pierwiastkowanie mieściło się w 50). Szybkość dzielenie jest też zależne od wielkości dzielonych liczb.
• Dodawanie, odejmowanie, mnożenie floatów i doubli jest niemal tak samo szybkie jak na intach. Kiedyś było inaczej (i na pewnych procesorach np. ARM, nadal tak jest), jednak na intelach mamy typowo ok. 2-4 cykli.
• Arytmetyka ma jeszcze tę miłą cechę, że CPU mają po kilka ALU. Np. Intele mają 3. W efekcie oznacza to, że można zrealizować 3 dodawania lub trzy mnożenia w jednym cyklu równolegle, o ile zależności między danymi na to pozwalają. Wyjątkiem jest dzielenie - jest tylko jedna jednostka realizująca DIV/FDIV.
• Skoki bezwarunkowe pod stały adres - bardzo szybkie, 1 cykl
• Skoki warunkowe / skoki pod adres zależny od danych - samo wykonanie porównania i skoku jest bardzo szybkie (1 cykl), pod warunkiem że skok zostanie prawidłowo przewidziany. Jeśli skok nie zostanie prawidłowo przewidziany to mamy problem, bo trzeba wycofać wszystko co już weszło do potoku za skokiem. W praktyce średnio wychodzi ok. 8-15 cykli w plecy; oczywiście jest to zależne od konkretnego CPU i zależne też od tego, co sprzed instrukcji skoku udało się schedulerowi instrukcji wcisnąć za skok. Czasami nie trzeba wycofywać wszystkiego.
• Jest tylko jedna jednostka wykonywania skoków. Dopiero od Haswella są dwie. Nadal to mniej niż ALU/FPU.
• Żeby było jeszcze trudniej, nowoczesne procesory potrafią wykonywać gałęzie spekulatywnie, tj. wstępnie olać wynik warunku i wykonywać obie ścieżki jednocześnie do czasu gdy warunek zostanie obliczony i następnie wycofać wyniki jednej ścieżki. Kosztuje to więcej energii niż przy klasycznym przewidywaniu skoku, ale cena za złe przewidzenie skoku jest mniejsza. Przez tę technikę jak próbowaliśmy zmierzyć efekt źle przewidzianych skoków na Haswellu, to nic nie chciało wyjść.
• Niektóre procesory mają więcej instrukcji warunkowych - np. warunkowe przesłania, albo warunkową arytmetykę. Intel na razie się doczekał chyba tylko warunkowego mov. Pozwala to wprost na etapie komplacji wyeliminować niektóre skoki warunkowe, zwłaszcza takie, które służą tylko do warunkowego przeskoczenia np. jednej, dwóch instrukcji (np. if (costam) ++i). Nie wiem, które kompilatory potrafią z tego korzystać.

Wniosek jest prosty - jeśli da się zamienić jakiegoś trudno przewidywalnego ifa na arytmetykę (nawet kilka instrukcji!) to zwykle się to opłaca. Zresztą nawet łatwo przewidywalne ify mogą być problemem, bo jednostka przewidywania skoków też ma ograniczoną pojemność i na dużym, najeżonym ifami kodzie np. takim jak w typowym kompilatorze zwykle dość szybko się poddaje.