Czy „IF” jest drogie?

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?

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ń.

„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.

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.

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.

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.

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ć.

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

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

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/ )

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).

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.

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.

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.

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ść? .

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?

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.