Oto głupie zabawne pytanie:
Powiedzmy, że musimy wykonać prostą operację, w której potrzebujemy połowy wartości zmiennej. Są zazwyczaj dwa sposoby osiągnięcia tego celu:
y = x / 2.0;
// or...
y = x * 0.5;
Zakładając, że używamy standardowych operatorów dostarczonych z językiem, który z nich ma lepszą wydajność?
Domyślam się, że mnożenie jest zazwyczaj lepsze, więc staram się tego trzymać, kiedy koduję, ale chciałbym to potwierdzić.
Chociaż osobiście jestem zainteresowany odpowiedzią na Python 2.4-2.5, nie krępuj się również opublikować odpowiedzi w innych językach! A jeśli chcesz, możesz również opublikować inne, bardziej wyszukane sposoby (na przykład użycie operatorów z przesunięciem bitowym).
performance
programming-languages
Edmundito
źródło
źródło
Odpowiedzi:
Pyton:
mnożenie jest o 33% szybsze
Lua:
=> bez różnicy
LuaJIT:
=> to tylko 5% szybciej
wnioski: w Pythonie mnożenie jest szybsze niż dzielenie, ale gdy zbliżasz się do procesora za pomocą bardziej zaawansowanych maszyn wirtualnych lub JIT, przewaga znika. Jest całkiem możliwe, że przyszła maszyna wirtualna Pythona uczyniłaby to nieistotnym
źródło
Zawsze używaj tego, co jest najwyraźniejsze. Cokolwiek robisz, to próba przechytrzenia kompilatora. Jeśli kompilator jest w ogóle inteligentny, zrobi wszystko, co w jego mocy, aby zoptymalizować wynik, ale nic nie może sprawić, że następny facet nie będzie cię nienawidził za twoje gówniane rozwiązanie do przesuwania bitów (tak przy okazji, uwielbiam manipulację bitami, to fajne. Ale fajnie! = Czytelne )
Przedwczesna optymalizacja jest źródłem wszelkiego zła. Zawsze pamiętaj o trzech zasadach optymalizacji!
Jeśli jesteś ekspertem i potrafisz uzasadnić taką potrzebę, zastosuj następującą procedurę:
Ponadto robienie rzeczy, takich jak usuwanie wewnętrznych pętli, gdy nie są one wymagane, lub wybieranie połączonej listy w tablicy do sortowania przez wstawianie, nie jest optymalizacją, tylko programowaniem.
źródło
Myślę, że robi się to tak dziwaczne, że lepiej byłoby zrobić wszystko, co czyni kod bardziej czytelnym. Jeśli nie wykonasz tych operacji tysiące, jeśli nie miliony razy, wątpię, by ktokolwiek kiedykolwiek zauważył różnicę.
Jeśli naprawdę musisz dokonać wyboru, benchmarking to jedyna droga. Znajdź funkcje, które powodują problemy, a następnie dowiedz się, gdzie w funkcji występują problemy i napraw te sekcje. Wciąż jednak wątpię, czy pojedyncza operacja matematyczna (choćby powtarzana wiele, wiele razy) byłaby przyczyną jakiegokolwiek wąskiego gardła.
źródło
Mnożenie jest szybsze, dzielenie dokładniejsze. Stracisz precyzję, jeśli twoja liczba nie jest potęgą 2:
Nawet jeśli pozwolisz kompilatorowi obliczyć odwróconą stałą z idealną precyzją, odpowiedź może być inna.
Problem z szybkością może mieć znaczenie tylko w językach C / C ++ lub JIT, a nawet wtedy, gdy operacja jest zapętlona w wąskim gardle.
źródło
y = x * (1.0/3.0);
a kompilator generalnie obliczy 1/3 w czasie kompilacji. Tak, 1/3 nie jest idealnie reprezentowalna w IEEE-754, ale gdy jesteś wykonywania arytmetyki zmiennoprzecinkowej tracisz precyzji w każdym razie , czy robisz mnożenie lub dzielenie, ponieważ bity niskiego rzędu są zaokrąglone. Jeśli wiesz, że twoje obliczenia są tak wrażliwe na błąd zaokrąglania, powinieneś również wiedzieć, jak najlepiej rozwiązać problem.(1.0/3.0)
z dzieleniem przez3.0
. Uzyskałem do 1,0000036666774155 iw tej przestrzeni 7,3% wyników było innych. Przypuszczam, że różniły się one tylko o 1 bit, ale ponieważ arytmetyka IEEE gwarantuje zaokrąglenie do najbliższego poprawnego wyniku, podtrzymuję moje stwierdzenie, że podział jest dokładniejszy. To, czy różnica jest znacząca, zależy od Ciebie.Jeśli chcesz zoptymalizować swój kod, ale nadal jest jasny, spróbuj tego:
Kompilator powinien mieć możliwość dzielenia w czasie kompilacji, więc w czasie wykonywania otrzymujesz mnożenie. Spodziewałbym się, że precyzja będzie taka sama jak w
y = x / 2.0
kopercie.Tam, gdzie może to mieć znaczenie, LOT znajduje się w procesorach wbudowanych, w których do obliczania arytmetyki zmiennoprzecinkowej wymagana jest emulacja zmiennoprzecinkowa.
źródło
y = x / 2.0;
ale w prawdziwym świecie być może będziesz musiał skłonić kompilator do wykonania tańszego mnożenia. Może jest mniej jasne, dlaczegoy = x * (1.0 / 2.0);
jest lepsze, i lepiej byłobyy = x * 0.5;
zamiast tego stwierdzić . Ale zmień na2.0
a7.0
i wolałbym raczej zobaczyćy = x * (1.0 / 7.0);
niży = x * 0.142857142857;
.Zamierzam tylko dodać coś dla opcji „inne języki”.
C: Ponieważ to jest tylko ćwiczenie akademickie, to naprawdę nie robi różnicy, pomyślałem, że wniesie coś innego.
Skompilowałem do assemblacji bez optymalizacji i spojrzałem na wynik.
Kod:
skompilowane z
gcc tdiv.c -O1 -o tdiv.s -S
podział na 2:
i pomnożenie przez 0,5:
Jednak kiedy zmieniłem te
int
nadouble
s (co prawdopodobnie zrobiłby Python), otrzymałem to:podział:
mnożenie:
Nie testowałem żadnego z tego kodu, ale po zbadaniu kodu widać, że przy użyciu liczb całkowitych dzielenie przez 2 jest krótsze niż mnożenie przez 2. Używając podwójnych, mnożenie jest krótsze, ponieważ kompilator używa zmiennoprzecinkowych opkodów procesora, które prawdopodobnie działają szybciej (ale właściwie nie wiem) niż nie używam ich do tej samej operacji. Ostatecznie więc ta odpowiedź pokazała, że wydajność mnożenia przez 0,5 w porównaniu z dzieleniem przez 2 zależy od implementacji języka i platformy, na której działa. Ostatecznie różnica jest znikoma i jest czymś, o co praktycznie nigdy nie powinieneś się martwić, z wyjątkiem czytelności.
Na marginesie, możesz zobaczyć, że w moim programie
main()
powracaa + b
. Kiedy usuwam słowo kluczowe volatile, nigdy nie zgadniesz, jak wygląda zestaw (wyłączając konfigurację programu):wykonał zarówno dzielenie, mnożenie, jak i dodawanie w jednej instrukcji! Oczywiście nie musisz się tym martwić, jeśli optymalizator jest godny szacunku.
Przepraszam za zbyt długą odpowiedź.
źródło
movl $5, %eax
nazwa optymalizacji nie jest ważna ani nawet nie ma znaczenia. Po prostu chciałeś być protekcjonalny wobec czteroletniej odpowiedzi.Po pierwsze, jeśli nie pracujesz w C lub ASSEMBLY, prawdopodobnie jesteś w języku wyższego poziomu, w którym zastój w pamięci i ogólne koszty połączeń absolutnie przyćmiewają różnicę między mnożeniem i dzieleniem do punktu nieistotnego. Więc po prostu wybierz to, co w takim przypadku brzmi lepiej.
Jeśli mówisz z bardzo wysokiego poziomu, nie będzie to mierzalnie wolniejsze w przypadku niczego, do czego prawdopodobnie będziesz go używać. W innych odpowiedziach zobaczysz, że ludzie muszą wykonać milion mnożenia / dzielenia tylko po to, aby zmierzyć jakąś poniżej milisekundową różnicę między nimi.
Jeśli nadal jesteś ciekawy, z niskiego poziomu optymalizacji:
Potok dzielenia zwykle jest znacznie dłuższy niż mnożenia. Oznacza to, że uzyskanie wyniku zajmuje więcej czasu, ale jeśli potrafisz zająć procesor zadaniami niezależnymi, to nie kosztuje cię to więcej niż pomnożenie.
Długość różnicy w rurociągach jest całkowicie zależna od sprzętu. Ostatni sprzęt, którego użyłem, miał około 9 cykli dla mnożenia FPU i 50 cykli dla dzielenia FPU. Brzmi dużo, ale wtedy straciłbyś 1000 cykli z powodu utraty pamięci, dzięki czemu można spojrzeć z perspektywy.
Analogią jest umieszczenie ciasta w kuchence mikrofalowej podczas oglądania programu telewizyjnego. Całkowity czas, jaki zabrał ci z dala od programu telewizyjnego, to czas, w którym wstawiono go do kuchenki mikrofalowej i wyjąłeś z kuchenki mikrofalowej. Przez resztę czasu nadal oglądałeś program telewizyjny. Więc jeśli ciasto gotowało się 10 minut zamiast 1 minuty, w rzeczywistości nie zużywało więcej czasu na oglądanie telewizji.
W praktyce, jeśli chcesz osiągnąć poziom dbałości o różnicę między mnożeniem i dzieleniem, musisz zrozumieć potoki, pamięć podręczną, przestoje w gałęziach, prognozowanie poza kolejnością i zależności potoków. Jeśli to nie brzmi tak, jak zamierzałeś iść z tym pytaniem, to poprawną odpowiedzią jest zignorowanie różnicy między nimi.
Wiele (wiele) lat temu absolutnie konieczne było unikanie podziałów i zawsze stosowanie mnożeń, ale wtedy trafienia w pamięć były mniej istotne, a podziały znacznie gorsze. Obecnie oceniam czytelność wyżej, ale jeśli nie ma różnicy w czytelności, myślę, że dobrym nawykiem jest wybieranie mnożenia.
źródło
Napisz, którekolwiek z nich jaśniej określa twój zamiar.
Gdy program zacznie działać, dowiedz się, co jest powolne, i przyspiesz to.
Nie rób tego na odwrót.
źródło
Rób wszystko, czego potrzebujesz. Pomyśl najpierw o swoim czytelniku, nie martw się o wydajność, dopóki nie upewnisz się, że masz problem z wydajnością.
Kompilator wykona wydajność za Ciebie.
źródło
Jeśli pracujesz z liczbami całkowitymi lub typami nie zmiennoprzecinkowymi, nie zapomnij o operatorach przesunięcia bitów: << >>
źródło
Właściwie jest dobry powód, że zgodnie z ogólną zasadą mnożenie będzie szybsze niż dzielenie. Dzielenie zmiennoprzecinkowe w sprzęcie odbywa się za pomocą algorytmów przesunięcia i warunkowego odejmowania („dzielenie długie” z liczbami binarnymi) lub - co bardziej prawdopodobne w dzisiejszych czasach - za pomocą iteracji, takich jak algorytm Goldschmidta . Przesunięcie i odjęcie wymaga co najmniej jednego cyklu na bit precyzji (iteracje są prawie niemożliwe do zrównoleglenia, podobnie jak przesunięcie i dodanie mnożenia), a algorytmy iteracyjne wykonują co najmniej jedno mnożenie na iterację. W obu przypadkach jest wysoce prawdopodobne, że podział zajmie więcej cykli. Oczywiście nie wyjaśnia to dziwactw kompilatorów, przenoszenia danych ani precyzji. Jednak ogólnie rzecz biorąc, jeśli kodujesz wewnętrzną pętlę w części programu wrażliwej na czas, pisanie
0.5 * x
lub1.0/2.0 * x
raczejx / 2.0
jest to rozsądne. Pedanteria „kodowania tego, co najjaśniejsze” jest absolutnie prawdziwa, ale wszystkie trzy są tak bliskie czytelności, że pedanteria jest w tym przypadku po prostu pedantyczna.źródło
Zawsze nauczyłem się, że mnożenie jest bardziej wydajne.
źródło
Mnożenie jest zwykle szybsze - na pewno nigdy wolniejsze. Jeśli jednak nie jest to krytyczne dla szybkości, napisz, co jest najwyraźniejsze.
źródło
Dzielenie zmiennoprzecinkowe jest (ogólnie) szczególnie powolne, więc chociaż mnożenie zmiennoprzecinkowe jest również stosunkowo wolne, prawdopodobnie jest szybsze niż dzielenie zmiennoprzecinkowe.
Ale jestem bardziej skłonny odpowiedzieć „to naprawdę nie ma znaczenia”, chyba że profilowanie wykazało, że dzielenie jest wąskim gardłem w porównaniu z mnożeniem. Domyślam się jednak, że wybór mnożenia lub dzielenia nie będzie miał dużego wpływu na wydajność w Twojej aplikacji.
źródło
To staje się bardziej pytaniem, kiedy programujesz w asemblerze lub być może C. Wydaje mi się, że w większości współczesnych języków taka optymalizacja jest wykonywana za mnie.
źródło
Uważaj na to, że „zgadywanie, że mnożenie jest zazwyczaj lepsze, więc staram się tego trzymać podczas kodu”.
W kontekście tego konkretnego pytania, lepsze tutaj oznacza „szybciej”. Co nie jest zbyt przydatne.
Myślenie o szybkości może być poważnym błędem. Istnieją głębokie implikacje błędów w konkretnej algebraicznej formie obliczeń.
Zobacz Arytmetyka zmiennoprzecinkowa z analizą błędów . Zobacz Podstawowe zagadnienia arytmetyki zmiennoprzecinkowej i analizy błędów .
Chociaż niektóre wartości zmiennoprzecinkowe są dokładne, większość wartości zmiennoprzecinkowych jest przybliżeniem; są jakaś idealna wartość plus jakiś błąd. Każda operacja dotyczy idealnej wartości i wartości błędu.
Największe problemy wynikają z próby manipulowania dwiema prawie równymi liczbami. W wynikach dominują bity znajdujące się najbardziej po prawej stronie (bity błędu).
W tym przykładzie widać, że gdy wartości stają się mniejsze, różnica między prawie równymi liczbami tworzy niezerowe wyniki, w których prawidłowa odpowiedź to zero.
źródło
Czytałem gdzieś, że mnożenie jest bardziej wydajne w C / C ++; Brak pomysłu na języki tłumaczone - różnica jest prawdopodobnie nieistotna ze względu na wszystkie inne koszty ogólne.
O ile nie stanie się to problemem, trzymaj się tego, co jest łatwiejsze w utrzymaniu / czytelności - nienawidzę, gdy ludzie mi to mówią, ale to takie prawdziwe.
źródło
Sugerowałbym generalnie mnożenie, ponieważ nie musisz spędzać cykli, upewniając się, że twój dzielnik jest różny od 0. Oczywiście nie ma to zastosowania, jeśli twój dzielnik jest stałą.
źródło
Java android, wyprofilowana na Samsung GT-S5830
Wyniki?
Dzielenie jest około 20% szybsze niż mnożenie (!)
źródło
a = i*0.5
, niea *= 0.5
. W ten sposób większość programistów będzie używać operacji.Podobnie jak w przypadku postów # 24 (mnożenie jest szybsze) i # 30 - ale czasami oba są równie łatwe do zrozumienia:
~ Uważam, że oba są równie łatwe do odczytania i muszę je powtarzać miliardy razy. Warto więc wiedzieć, że mnożenie jest zwykle szybsze.
źródło
Jest różnica, ale zależy od kompilatora. Na początku w vs2003 (c ++) nie dostałem żadnej znaczącej różnicy dla typów podwójnych (64-bitowa zmiennoprzecinkowa). Jednak przeprowadzając testy ponownie na vs2010, wykryłem ogromną różnicę, nawet czterokrotnie szybszą dla mnożenia. Śledząc to, wydaje się, że vs2003 i vs2010 generują inny kod FPU.
W przypadku Pentium 4 2,8 GHz w porównaniu z 2003:
Na Xeon W3530, vs2003:
Na Xeon W3530, vs2010:
Wygląda na to, że w vs2003 dzielenie w pętli (więc dzielnik był używany wielokrotnie) zostało przetłumaczone na mnożenie z odwrotnością. W vs2010 ta optymalizacja nie jest już stosowana (przypuszczam, że między tymi dwiema metodami jest nieco inny wynik). Zauważ również, że procesor wykonuje podziały szybciej, gdy tylko twój licznik wynosi 0,0. Nie znam dokładnego algorytmu wbudowanego w chip, ale może jest to zależne od liczby.
Edycja 18-03-2013: obserwacja dotycząca vs2010
źródło
n/10.0
Wyrażeniem formularza(n * c1 + n * c2)
? Spodziewałbym się, że na większości procesorów dzielenie zajmie więcej czasu niż dwa mnożenia i dzielenie i uważam, że dzielenie przez dowolną stałą może dać poprawnie zaokrąglony wynik we wszystkich przypadkach przy użyciu wskazanego wzoru.Oto głupia, zabawna odpowiedź:
x / 2,0 nie jest równoważne z x * 0,5
Powiedzmy, że napisałeś tę metodę 22 października 2008 r.
Teraz, 10 lat później, dowiesz się, że możesz zoptymalizować ten fragment kodu. Do metody odwołują się setki formuł w całej aplikacji. Więc zmieniasz to i doświadczasz niezwykłej 5% poprawy wydajności.
Czy była to słuszna decyzja o zmianie kodu? W matematyce te dwa wyrażenia są rzeczywiście równoważne. W informatyce nie zawsze się to sprawdza. Więcej informacji można znaleźć w artykule Minimalizowanie skutków problemów z dokładnością . Jeśli obliczone wartości zostaną - w pewnym momencie - porównane z innymi wartościami, zmienisz wynik przypadków skrajnych. Na przykład:
Najważniejsze jest to; kiedy już zdecydujesz się na jedno z dwóch, trzymaj się tego!
źródło
2
i0.5
liczby mogą być reprezentowane dokładnie w IEEE 754, bez utraty precyzji (w przeciwieństwie do np.0.4
Lub0.1
, nie mogą).Cóż, jeśli założymy, że operacja dodawania / podrzędnej ścieżki kosztuje 1, to pomnóż koszty 5 i podziel koszty około 20.
źródło
Po tak długiej i interesującej dyskusji oto moje zdanie: Nie ma ostatecznej odpowiedzi na to pytanie. Jak niektórzy zauważyli, zależy to zarówno od sprzętu (por. Piotrk i gast128 ), jak i kompilatora (por. Testy @Javier ). Jeśli szybkość nie jest krytyczna, jeśli Twoja aplikacja nie musi przetwarzać w czasie rzeczywistym ogromnych ilości danych, możesz zdecydować się na przejrzystość za pomocą dzielenia, podczas gdy jeśli problemem jest szybkość przetwarzania lub obciążenie procesora, najbezpieczniejsze może być mnożenie. Wreszcie, jeśli nie wiesz dokładnie, na jakiej platformie zostanie wdrożona Twoja aplikacja, benchmark nie ma znaczenia. A dla przejrzystości kodu wystarczy jeden komentarz!
źródło
Technicznie nie ma czegoś takiego jak dzielenie, jest po prostu mnożenie przez elementy odwrotne. Na przykład nigdy nie dzielisz przez 2, w rzeczywistości mnożysz przez 0,5.
„Dzielenie” - oszukujmy się, że istnieje przez chwilę - jest zawsze trudniejsze niż mnożenie, ponieważ aby „podzielić”
x
przezy
jeden, trzeba najpierw obliczyć taką wartośćy^{-1}
,y*y^{-1} = 1
a następnie wykonać mnożeniex*y^{-1}
. Jeśli już wiesz,y^{-1}
to nie obliczanie tego zy
musi być optymalizacją.źródło