Czy „IF” jest drogie?

100

Nie mogę sobie przypomnieć, co dokładnie powiedział nasz nauczyciel tamtego dnia i mam nadzieję, że prawdopodobnie to wiesz.

Moduł to „Struktury danych i algorytmy”, a on powiedział nam coś w rodzaju:

ifStwierdzenie jest najdroższym [coś]. [coś] rejestruje [coś].

Tak, mam okropną pamięć i naprawdę bardzo mi przykro, ale googlowałem od wielu godzin i nic mi nie wyszło. Jakieś pomysły?

pek
źródło
29
Czy poprosisz nauczyciela o jakąś opcję?
Michael Myers
7
Dlaczego nie wyślesz e-maila do swojego nauczyciela? Jest mało prawdopodobne, że ktokolwiek na SO wie, co powiedział twój nauczyciel, chyba że był tam w tym czasie (lub twój nauczyciel sam przeczyta TAK).
Bill Karwin,
11
I oczywiście link do obowiązkowej odpowiedzi kolejowej
bobobobo
Instrukcje if, a zwłaszcza wyrażenia „?:” W językach z nawiasami klamrowymi, na które wpływ ma język C, można zaimplementować za pomocą specjalnych instrukcji wykonywania warunkowego na np. Procesorach x86 i arm. Są to instrukcje, które wykonują lub nie wykonują pewnych operacji na podstawie wcześniejszego testu. Korzystanie z tych doskonałych instrukcji całkowicie eliminuje potrzebę warunkowego skoku / rozgałęzienia / instrukcji „goto”. Ogromna poprawa wydajności w niektórych sytuacjach poprzez sprawienie, że przepływ programu jest całkowicie przewidywalny, ponieważ po prostu jedzie prosto bez (być może nieprzewidywalnego) przeskakiwania do różnych punktów w kodzie.
Cecil Ward
Dobry kompilator może czasami potrzebować trochę popchnięcia we właściwym kierunku, tak aby używał instrukcji warunkowych zamiast być głupim i używać skoków warunkowych, reorganizując kod i prawdopodobnie używając sprytnej arytmetyki w wyrażeniu lub? : wyrażenie. Nie baw się tym, chyba że naprawdę znasz swój ASM i przeczytałeś np. Przewodniki optymalizacji Agner Fog. Kompilatory czasami robią to dobrze, niezależnie od tego, czy instrukcje czy? : używane są wyrażenia.
Cecil Ward

Odpowiedzi:

188

Na najniższym poziomie (w sprzęcie) tak, jeśli są drogie. Aby zrozumieć dlaczego, musisz zrozumieć, jak działają potoki .

Bieżąca instrukcja do wykonania jest przechowywana w czymś, co zwykle nazywa się wskaźnikiem instrukcji (IP) lub licznikiem programu (PC); te terminy są synonimami, ale różne terminy są używane w różnych architekturach. W przypadku większości instrukcji komputer PC następnej instrukcji to tylko bieżący komputer osobisty plus długość bieżącej instrukcji. W przypadku większości architektur RISC wszystkie instrukcje mają stałą długość, więc komputer można zwiększać o stałą wartość. W przypadku architektur CISC, takich jak x86, instrukcje mogą mieć zmienną długość, więc logika, która dekoduje instrukcję, musi ustalić, jak długo bieżąca instrukcja ma znaleźć lokalizację następnej instrukcji.

Jednak w przypadku instrukcji rozgałęzienia następna instrukcja do wykonania nie jest następną lokalizacją po bieżącej instrukcji. Gałęzie to gotos - informują procesor, gdzie jest następna instrukcja. Gałęzie mogą być warunkowe lub bezwarunkowe, a lokalizacja docelowa może być stała lub obliczona.

Warunkowe i bezwarunkowe są łatwe do zrozumienia - gałąź warunkowa jest brana tylko wtedy, gdy zachodzi pewien warunek (np. Czy jedna liczba jest równa drugiej); jeśli gałąź nie jest przejęta, sterowanie przechodzi do następnej instrukcji po gałęzi jak zwykle. W przypadku gałęzi bezwarunkowych brana jest zawsze. Gałęzie warunkowe pojawiają się w ifinstrukcjach i testach kontrolnych pętli fori while. Bezwarunkowe gałęzie pojawiają się w nieskończonych pętlach, wywołaniach funkcji, zwrotach funkcji breaki continueinstrukcjach, niesławnych gotoinstrukcjach i wielu innych (listy te nie są wyczerpujące).

Oddział docelowy to kolejna ważna kwestia. Większość oddziałów ma ustalony cel - przechodzą do określonej lokalizacji w kodzie, która jest ustalana w czasie kompilacji. To zawieraif instrukcje, wszelkiego rodzaju pętle, zwykłe wywołania funkcji i wiele innych. Obliczone gałęzie obliczają miejsce docelowe gałęzi w czasie wykonywania. Obejmuje to switchinstrukcje (czasami), powracające z funkcji, wywołania funkcji wirtualnych i wywołania wskaźników funkcji.

Więc co to wszystko oznacza dla wydajności? Kiedy procesor widzi instrukcję rozgałęzienia pojawiającą się w jego potoku, musi dowiedzieć się, jak kontynuować zapełnianie potoku. Aby dowiedzieć się, jakie instrukcje pojawiają się po gałęzi w strumieniu programu, musi wiedzieć dwie rzeczy: (1) czy gałąź zostanie podjęta i (2) miejsce docelowe gałęzi. Ustalenie tego nazywa się prognozowaniem gałęzi i jest to trudny problem. Jeśli procesor zgadnie poprawnie, program działa dalej z pełną prędkością. Jeśli zamiast tego procesor zgadnie nieprawidłowo , po prostu spędził trochę czasu na obliczeniu niewłaściwej rzeczy. Teraz musi opróżnić swój potok i załadować go ponownie instrukcjami z właściwej ścieżki wykonania. Podsumowując: wielki hit wydajnościowy.

Tak więc powodem, dla którego wyciągi są drogie, są błędne przewidywania branży . To tylko na najniższym poziomie. Jeśli piszesz kod wysokiego poziomu, nie musisz się martwić o te szczegóły. Powinieneś przejmować się tym tylko wtedy, gdy piszesz kod krytyczny dla wydajności w C lub asemblerze. W takim przypadku pisanie kodu bez gałęzi może być często lepsze niż kod, który rozgałęzia się, nawet jeśli potrzeba kilku dodatkowych instrukcji. Istnieje kilka fajnych bit-twiddling sztuczki można zrobić, aby obliczyć takie rzeczy jak abs(), min()i max()bez rozgałęzień.

Adam Rosenfield
źródło
20
To nie tylko błędne przewidywania branży. Gałęzie uniemożliwiają również zmianę kolejności instrukcji na poziomie kompilatora, a także do pewnego stopnia na poziomie procesora (oczywiście w przypadku niesprawnego procesora). Dobra, szczegółowa odpowiedź.
jalf
5
Jeśli języki wysokiego poziomu są ostatecznie tłumaczone na języki niskiego poziomu i piszesz kod zorientowany na wydajność, czy nadal nic nie zyskujesz pisząc kod, który unika instrukcji if? Czy ta koncepcja nie przenosi się na języki wyższego poziomu?
c ..
19

„Kosztowny” to bardzo względny termin, zwłaszcza w odniesieniu do stwierdzenia „ if”, ponieważ trzeba również wziąć pod uwagę koszt tego schorzenia. Może to obejmować kilka krótkich instrukcji procesora lub testowanie wyniku funkcji, która wywołuje zdalną bazę danych.

Nie martwiłbym się tym. Jeśli nie zajmujesz się programowaniem osadzonym, prawdopodobnie nie powinieneś się martwić o koszt " if". Dla większości programistów to nigdy nie będzie decydującym czynnikiem wpływającym na wydajność aplikacji.

Joel Coehoorn
źródło
2
Zdecydowanie względne ... cmp / cond jmp jest nadal szybszy niż mul na wielu procesorach.
Brian Knoblauch,
4
Tak, zgadzam się, że nie powinienem się tym przejmować. Nie próbuję tu niczego optymalizować. Po prostu próbuję się dowiedzieć i nauczyć. ;)
pek
15

Gałęzie, zwłaszcza na mikroprocesorach architektury RISC, to jedne z najdroższych instrukcji. Dzieje się tak, ponieważ na wielu architekturach kompilator przewiduje, która ścieżka wykonania zostanie najprawdopodobniej wybrana i umieszcza te instrukcje jako następne w pliku wykonywalnym, więc będą one już znajdować się w pamięci podręcznej procesora, gdy nastąpi rozgałęzienie. Jeśli gałąź idzie w drugą stronę, musi wrócić do pamięci głównej i pobrać nowe instrukcje - to dość kosztowne. Na wielu architekturach RISC wszystkie instrukcje są jednym cyklem z wyjątkiem gałęzi (która często składa się z 2 cykli). Nie mówimy tutaj o dużych kosztach, więc nie martw się o to. Ponadto kompilator zoptymalizuje lepiej niż Ty w 99% przypadków: Jedną z naprawdę niesamowitych rzeczy w architekturze EPIC (przykładem jest Itanium) jest to, że buforuje (i rozpoczyna przetwarzanie) instrukcji z obu stron gałęzi, a następnie odrzuca zestaw, którego nie potrzebuje, gdy wynik gałęzi jest znany. Oszczędza to dodatkowy dostęp do pamięci typowej architektury w przypadku rozgałęzienia wzdłuż nieprzewidzianej ścieżki.

rmeador
źródło
13

Zapoznaj się z artykułem Lepsza wydajność dzięki eliminacji gałęzi w wydajności komórek. Innym zabawnym postem jest ten post o selekcji bez gałęzi na blogu Real Time Collision Detection.

Oprócz doskonałych odpowiedzi już opublikowanych w odpowiedzi na to pytanie, chciałbym przypomnieć, że chociaż instrukcje „jeśli” są uważane za kosztowne operacje niskiego poziomu, to próba wykorzystania technik programowania bez gałęzi w środowisku wyższego poziomu , takie jak język skryptowy lub warstwa logiki biznesowej (niezależnie od języka), mogą być śmiesznie nieodpowiednie.

W większości przypadków programy powinny być najpierw napisane dla przejrzystości, a następnie zoptymalizowane pod kątem wydajności. Istnieje wiele problematycznych dziedzin, w których wydajność jest najważniejsza, ale prosty fakt jest taki, że większość programistów nie pisze modułów do użytku w rdzeniu silnika renderującego lub wysokowydajnej symulacji dynamiki płynów, która działa przez wiele tygodni. Kiedy głównym priorytetem jest to, aby Twoje rozwiązanie „po prostu działało”, ostatnią rzeczą, o której myślisz, powinno być to, czy możesz zaoszczędzić na narzucie instrukcji warunkowej w swoim kodzie.

Parappa
źródło
W rzeczy samej! Można również dodać, że podczas kodowania w języku, który zachęca do wywołań (w zasadzie czegokolwiek innego niż assembler lub C bez standardowego biblioteki), interferencja potoków ze strony normalnych technik programowania przytłoczy wszelkie pytania dotyczące rozgałęzień warunkowych.
Ross Patterson
10

ifsama w sobie nie jest powolna. Powolność jest zawsze względna. Założę się o moje życie, że nigdy nie poczułeś „narzutu” stwierdzenia „jeśli”. Jeśli zamierzasz stworzyć kod o wysokiej wydajności, i tak możesz chcieć uniknąć rozgałęzień. Co sprawia, że ifpowoli to, że procesor jest wstępne ładowanie kod po ifopiera się na jakimś heurystyki i etażerka. Zatrzymuje również wykonywanie kodu przez potoki bezpośrednio po ifinstrukcji rozgałęzienia w kodzie maszynowym, ponieważ procesor nie wie jeszcze, jaka ścieżka zostanie wybrana (w procesorze potokowym wiele instrukcji jest przeplatanych i wykonywanych). Wykonywany kod może być wykonywany w odwrotnej kolejności (jeśli inna gałąź jest zajęta. Jest wywoływana branch misprediction) lub noopbyć wypełniony w tych miejscach, aby tak się nie stało.

Jeśli ifjest zła, to switchjest zbyt zły, i &&, ||też. Nie martw się tym.

Johannes Schaub - litb
źródło
7

Na najniższym możliwym poziomie ifskłada się (po obliczeniu wszystkich wymagań wstępnych specyficznych dla aplikacji if):

  • jakieś instrukcje testowe
  • przeskocz do jakiegoś miejsca w kodzie, jeśli test się powiedzie, w przeciwnym razie przejdź dalej.

Koszty z tym związane:

  • porównanie niskiego poziomu - zwykle praca na 1 procesorze, super tanie
  • potencjalny skok - który może być kosztowny

Rezon, dlaczego skoki są drogie:

  • można przeskoczyć do kodu arbirarnego, który mieszka w dowolnym miejscu w pamięci, jeśli okaże się, że nie jest on buforowany przez procesor - mamy problem, bo potrzebujemy dostępu do pamięci głównej, która jest wolniejsza
  • nowoczesne procesory przewidują rozgałęzienia. Próbują odgadnąć, czy się powiedzie, czy nie, i wykonują kod z wyprzedzeniem w potoku, więc przyspiesz to. Jeśli przewidywanie nie powiedzie się, wszystkie obliczenia wykonane wcześniej przez potok muszą zostać unieważnione. To również jest kosztowna operacja

Więc by podsumować:

  • Jeśli to może być szybkie, jeśli naprawdę, naprawdę zależy ci na wydajności.
  • Powinieneś się tym przejmować wtedy i tylko wtedy , gdy piszesz raytracer w czasie rzeczywistym, symulację biologiczną lub coś podobnego. W większości realnego świata nie ma powodu, by się tym przejmować.
Marcin
źródło
Przejdź na wyższy poziom: a co z instrukcjami zagnieżdżonymi i / lub złożonymi if? Koszt może stać się dość szybko zauważalny, jeśli ktoś napisze dużo takich stwierdzeń if. A ponieważ dla większości programistów, jeśli stwierdzenia wydają się tak fundamentalną operacją, unikanie zawiłych rozgałęzień warunkowych jest często sprowadzane do problemu stylistycznego. Stylistyczne obawy są nadal ważne, ale często w gorącym momencie mogą być pierwszym problemem, który należy zignorować.
jaydel
7

Nowoczesne procesory mają długie potoki wykonania, co oznacza, że ​​kilka instrukcji jest wykonywanych w różnych etapach w tym samym czasie. Nie zawsze mogą znać wynik jednej instrukcji, kiedy następna zaczyna działać. Kiedy napotkają skok warunkowy (jeśli), czasami muszą czekać, aż potok będzie pusty, zanim będą mogli wiedzieć, w którą stronę powinien iść wskaźnik instrukcji.

Myślę o tym jak o długim pociągu towarowym. Może szybko przewieźć dużo ładunku w linii prostej, ale słabo zakręca.

Pentium 4 (Prescott) miał słynną długą listę 31 stopni.

Więcej na Wikipedii

Guge
źródło
6

Może rozgałęzienie zabija wstępne pobieranie instrukcji procesora?

activout.se
źródło
Podczas moich ... „badań” dowiedziałem się o tabelach skoku i rozgałęzianiu instrukcji switch, ale nic o instrukcjach if. Czy mógłbyś trochę to rozwinąć?
pek
IIRC, procesor zwykle pobiera instrukcje z wyprzedzeniem wzdłuż jednej prawdopodobnej ścieżki wykonania, ale instrukcja „if”, która powoduje rozgałęzienie z przewidywanej ścieżki wykonania, unieważni wstępnie pobrane instrukcje, a procedura wstępna będzie musiała zostać zrestartowana.
activout.se
Każdy przyzwoity procesor powinien mieć możliwości przewidywania rozgałęzień, które będą próbowały odgadnąć, czy gałąź zostanie pobrana, czy nie, oraz instrukcje pobierania wstępnego na podstawie predykcji (co jest ogólnie całkiem dobre). GCC ma nawet rozszerzenia C, które pozwalają programiście podawać wskazówki dotyczące predyktorów gałęzi.
mipadi
2
Co więcej, procesor zwykle patrzy w przyszłość, aby rozpocząć wykonywanie nadchodzących instrukcji wcześniej (nie tylko je wstępnie pobrać), a kompilator próbuje zmienić kolejność instrukcji, co staje się niebezpieczne w różnych gałęziach, więc możesz naprawdę zabić planowanie instrukcji ze zbyt dużą liczbą gałęzi. Co szkodzi wydajności.
jalf
6

Zauważ również, że wewnątrz pętli nie ma koniecznie bardzo drogie.

Współczesny procesor przy pierwszej wizycie w instrukcji if zakłada, że ​​„if-body” ma zostać wzięte (lub inaczej powiedziane: zakłada również, że ciało pętli powinno zostać pobrane wiele razy) (*). Podczas drugiej i kolejnych wizyt może (CPU) zajrzeć do Tabeli historii rozgałęzień i zobaczyć, jak warunek był ostatnim razem (czy to prawda? Czy to fałsz?). Jeśli ostatnio było fałszywe, wykonanie spekulacyjne przejdzie do „else” elementu if lub poza pętlę.

(*) Reguła to w rzeczywistości „ gałąź do przodu nie zajęta, gałąź do tyłu zajęta ”. W instrukcji if występuje tylko skok [do przodu] (do punktu po treści if), jeśli warunek ma wartość false (pamiętaj: procesor i tak zakłada, że ​​nie bierze gałęzi / skoku), ale w pętli , może być gałąź do przodu do pozycji za pętlą (nie do wzięcia) i gałąź do tyłu po powtórzeniu (do wzięcia).

Jest to również jeden z powodów, dla których wywołanie funkcji wirtualnej lub wywołanie wskaźnika funkcji nie jest tak gorsze, jak wielu zakłada ( http://phresnel.org/blog/ )

Sebastian Mach
źródło
5

Jak zauważyło wielu, gałęzie warunkowe mogą działać bardzo wolno na nowoczesnym komputerze.

Biorąc to pod uwagę, istnieje wiele gałęzi warunkowych, które nie istnieją w instrukcjach if, nie zawsze możesz powiedzieć, co wymyśli kompilator, a martwienie się, jak długo potrwa podstawowe instrukcje, jest praktycznie zawsze niewłaściwą rzeczą do zrobienia. (Jeśli możesz powiedzieć, co kompilator wygeneruje niezawodnie, możesz nie mieć dobrego optymalizującego kompilatora).

David Thornley
źródło
4

Jedyne, co mogę sobie wyobrazić, to fakt, że plik if stwierdzenie generalnie może skutkować odgałęzieniem. W zależności od specyfiki architektury procesora, gałęzie mogą powodować blokady potoku lub inne sytuacje mniej niż optymalne.

Jest to jednak bardzo specyficzne dla sytuacji - większość nowoczesnych procesorów ma możliwości przewidywania rozgałęzień, które próbują zminimalizować negatywne skutki rozgałęzień. Innym przykładem może być sposób, w jaki architektura ARM (i prawdopodobnie inne) radzi sobie z logiką warunkową - ARM ma wykonywanie warunkowe na poziomie instrukcji, więc prosta logika warunkowa nie powoduje rozgałęzień - instrukcje są po prostu wykonywane jako NOP, jeśli warunki nie są spełnione.

Wszystko to powiedziawszy - popraw logikę, zanim zaczniesz się tym martwić. Nieprawidłowy kod jest tak niezoptymalizowany, jak tylko możesz.

Michael Burr
źródło
Słyszałem, że instrukcje warunkowe ARM blokują ILP, więc mogą po prostu rozwiązywać problem.
JD
3

Procesory są głęboko potokowane. Każda instrukcja rozgałęzienia (if / for / while / switch / etc) oznacza, że ​​procesor tak naprawdę nie wie, jaką instrukcję załadować i uruchomić w następnej kolejności.

Procesor albo zatrzymuje się, czekając, aby wiedzieć, co zrobić, albo zgaduje. W przypadku starszego procesora lub jeśli przypuszczenie jest błędne, będziesz musiał cierpieć z powodu przeciągnięcia potoku podczas jego działania i ładowania prawidłowej instrukcji. W zależności od procesora może to wynosić nawet 10-20 instrukcji o wartości przeciągnięcia.

Nowoczesne procesory starają się tego uniknąć, wykonując dobre przewidywanie rozgałęzień i wykonując wiele ścieżek w tym samym czasie, zachowując tylko tę samą. To bardzo pomaga, ale może zajść tylko do tej pory.

Powodzenia w klasie.

Ponadto, jeśli musisz się tym martwić w prawdziwym życiu, prawdopodobnie projektujesz system operacyjny, grafikę w czasie rzeczywistym, obliczenia naukowe lub coś podobnego związanego z procesorem. Profil przed zmartwieniem.

tfinniga
źródło
2

Pisz swoje programy w najbardziej przejrzysty, najprostszy i najczystszy sposób, który nie jest oczywiście nieefektywny. To najlepiej wykorzystuje najdroższe zasoby. Czy to pisanie, czy późniejsze debugowanie (wymaga zrozumienia) programu. Jeśli wydajność nie wystarczy, zmierzgdzie są wąskie gardła i zobacz, jak je złagodzić. Tylko w wyjątkowo rzadkich przypadkach będziesz musiał martwić się o indywidualne (źródłowe) instrukcje. Wydajność polega na wyborze odpowiednich algorytmów i struktur danych w pierwszej linii, starannym programowaniu i uzyskaniu wystarczająco szybkiej maszyny. Użyj dobrego kompilatora, zdziwiłbyś się, widząc rodzaj restrukturyzacji kodu, który robi nowoczesny kompilator. Restrukturyzacja kodu pod kątem wydajności to rodzaj środka ostatniej szansy, kod staje się bardziej złożony (a przez to bardziej błędny), trudniejszy do modyfikacji, a przez to ogólnie droższy.

vonbrand
źródło
1

Niektóre procesory (takie jak X86) zapewniają prognozowanie rozgałęzień na poziomie programowania, aby uniknąć takich opóźnień przewidywania rozgałęzień.

Niektóre kompilatory ujawniają je (jak GCC) jako rozszerzenie języków programowania wyższego poziomu (takich jak C / C ++).

Odwołaj się do makro prawdopodobnych () / mało prawdopodobnych () w jądrze Linuksa - jak one działają? Jaka jest ich korzyść? .

Arunprasad Rajkumar
źródło
0

Kiedyś pokłóciłem się z przyjacielem. Używał bardzo naiwnego algorytmu koła, ale twierdził, że jego jest szybszy niż mój (taki, który oblicza tylko 1/8 koła), ponieważ mój użył if. Ostatecznie instrukcja if została zastąpiona przez sqrt i jakoś szybciej. Może dlatego, że FPU ma wbudowany sqrt?

Demur Rumed
źródło
-1

Najdroższy pod względem użytkowania ALU? Wykorzystuje rejestry procesora do przechowywania wartości do porównania i zajmuje trochę czasu, aby pobrać i porównać wartości za każdym razem, gdy wykonywana jest instrukcja if.

Dlatego optymalizacja polega na wykonaniu jednego porównania i zapisaniu wyniku jako zmiennej przed uruchomieniem pętli.

Próbuję tylko zinterpretować brakujące słowa.


źródło