Myślę, że bardziej pomocna byłaby pytająca, aby uzyskać bardziej zróżnicowaną odpowiedź, ponieważ widzę kilka niezbadanych założeń w pytaniach oraz w niektórych odpowiedziach lub komentarzach.
Wynikowy względny czas działania przesunięcia i pomnożenia nie ma nic wspólnego z C. Kiedy mówię C, nie mam na myśli wystąpienia konkretnej implementacji, takiej jak ta czy inna wersja GCC, ale język. Nie zamierzam brać tego za absurdalne, ale przykładam ekstremalny przykład: możesz zaimplementować całkowicie zgodny ze standardami kompilator C i powielać mnożenie przez godzinę, podczas gdy przesunięcie zajmuje milisekundy - lub odwrotnie. Nie znam żadnych ograniczeń wydajności w C lub C ++.
Argumentacja może nie dotyczyć tej techniki. Twoim zamiarem było prawdopodobnie przetestowanie względnej wydajności wykonywania zmian w stosunku do mnożenia i wybrałeś C, ponieważ jest ogólnie postrzegany jako język programowania niskiego poziomu, więc można oczekiwać, że jego kod źródłowy przełoży się na odpowiednie instrukcje bardziej bezpośrednio. Takie pytania są bardzo częste i uważam, że dobra odpowiedź powinna wskazywać, że nawet w C twój kod źródłowy nie przekłada się na instrukcje tak bezpośrednio, jak myślisz w danym przypadku. Poniżej podałem kilka możliwych wyników kompilacji.
W tym miejscu pojawiają się komentarze podważające użyteczność zastąpienia tej równoważności w prawdziwym oprogramowaniu. Niektóre komentarze można znaleźć w komentarzach do twojego pytania, np. Erica Lipperta. Jest to zgodne z reakcją, na którą zazwyczaj reagują bardziej doświadczeni inżynierowie w odpowiedzi na takie optymalizacje. Jeśli użyjesz zmian binarnych w kodzie produkcyjnym jako ogólnego sposobu pomnażania i dzielenia, ludzie najprawdopodobniej będą się denerwować przy twoim kodzie i będą w pewnym stopniu reagować emocjonalnie („Słyszałem to bezsensowne twierdzenie o JavaScript dla dobra nieba”), aby to może nie mieć sensu początkującym programistom, chyba że lepiej zrozumieją przyczyny tych reakcji.
Przyczyny te są przede wszystkim połączeniem zmniejszonej czytelności i bezskuteczności takiej optymalizacji, o czym zapewne już wiesz, porównując ich względną wydajność. Nie sądzę jednak, aby ludzie mieli tak silną reakcję, gdyby jedynym przykładem takiej optymalizacji było zastąpienie zmiany przez mnożenie. Pytania takie jak twoje często pojawiają się w różnych formach i w różnych kontekstach. Myślę, że bardziej doświadczeni inżynierowie tak silnie reagują, przynajmniej czasami, na to, że istnieje możliwość znacznie szerszego zakresu szkód, gdy ludzie swobodnie stosują takie mikrooptymalizacje w całej bazie kodu. Jeśli pracujesz w firmie takiej jak Microsoft na bazie dużego kodu, poświęcisz dużo czasu na czytanie kodu źródłowego innych inżynierów lub spróbujesz znaleźć w nim określony kod. Może nawet być twoim własnym kodem, który będziesz próbował zrozumieć za kilka lat, szczególnie w najbardziej nieodpowiednich momentach, na przykład gdy musisz naprawić awarię produkcyjną po otrzymanym połączeniu na pager obowiązek w piątek wieczorem, aby wyruszyć na noc zabawy z przyjaciółmi… Jeśli poświęcisz tyle czasu na czytanie kodu, z pewnością docenisz jego czytelność. Wyobraź sobie, że czytasz swoją ulubioną powieść, ale wydawca postanowił wydać nowe wydanie, w którym używa abbrv. wszystkie ovr th plc bcs thy thnk it svs spc. Jest to podobne do reakcji innych inżynierów na Twój kod, jeśli posypiesz je takimi optymalizacjami. Jak wskazały inne odpowiedzi, lepiej jasno powiedzieć, co masz na myśli,
Jednak nawet w tych środowiskach może się okazać, że rozwiązujesz pytanie podczas rozmowy kwalifikacyjnej, w której oczekuje się, że znasz tę lub inną równoważność. Znajomość ich nie jest zła i dobry inżynier byłby świadomy arytmetycznego efektu przesunięcia binarnego. Zauważ, że nie powiedziałem, że to czyni dobrego inżyniera, ale że dobry inżynier wiedziałby, moim zdaniem. W szczególności nadal możesz znaleźć menedżera, zwykle pod koniec rozmowy, który uśmiechnie się szeroko, oczekując radości z ujawnienia ci tej „sztuczki” inteligentnej inżynierii w pytaniu kodującym i udowodnienia, że on / ona również był lub jest jednym z doświadczonych inżynierów, a nie „tylko” menedżerem. W takich sytuacjach postaraj się wyglądać pod wrażeniem i podziękuj mu / jej za oświecający wywiad.
Dlaczego nie widziałeś różnicy prędkości w C? Najbardziej prawdopodobną odpowiedzią jest to, że oba zaowocowały tym samym kodem zestawu:
int shift(int i) { return i << 2; }
int multiply(int i) { return i * 2; }
Oba mogą się kompilować
shift(int):
lea eax, [0+rdi*4]
ret
W GCC bez optymalizacji, tj. Używając flagi „-O0”, możesz uzyskać:
shift(int):
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-4], edi
mov eax, DWORD PTR [rbp-4]
sal eax, 2
pop rbp
ret
multiply(int):
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-4], edi
mov eax, DWORD PTR [rbp-4]
add eax, eax
pop rbp
ret
Jak widać, przekazanie „-O0” do GCC nie oznacza, że nie będzie on zbyt mądry pod względem rodzaju tworzonego kodu. W szczególności zauważ, że nawet w tym przypadku kompilator unikał użycia instrukcji mnożenia. Możesz powtórzyć ten sam eksperyment z przesunięciami o inne liczby, a nawet mnożeniem przez liczby, które nie są potęgami dwóch. Są szanse, że na twojej platformie zobaczysz kombinację zmian i dodatków, ale bez mnożenia. Wydaje się, że kompilator wydaje się trochę zbiegiem okoliczności, aby najwidoczniej unikać mnożenia we wszystkich tych przypadkach, jeśli mnożenie i zmiany rzeczywiście miały ten sam koszt, prawda? Ale nie zamierzam podawać przypuszczeń na dowód, więc przejdźmy dalej.
Możesz ponownie uruchomić test z powyższym kodem i sprawdzić, czy zauważysz teraz różnicę prędkości. Nawet wtedy nie testujesz zmiany kontra mnożenie, jak widać przy braku mnożenia, ale kod, który został wygenerowany z określonym zestawem flag przez GCC dla operacji C przesunięcia i pomnożenia w konkretnym przypadku . Tak więc w innym teście możesz ręcznie edytować kod asemblera i zamiast tego użyć instrukcji „imul” w kodzie dla metody „mnożenia”.
Jeśli chcesz pokonać niektóre z tych inteligentnych cech kompilatora, możesz zdefiniować bardziej ogólną metodę przesunięcia i pomnożenia, a skończy się na czymś takim:
int shift(int i, int j) { return i << j; }
int multiply(int i, int j) { return i * j; }
Co może dać następujący kod zestawu:
shift(int, int):
mov eax, edi
mov ecx, esi
sal eax, cl
ret
multiply(int, int):
mov eax, edi
imul eax, esi
ret
Wreszcie mamy, nawet na najwyższym poziomie optymalizacji GCC 4.9, wyrażenie w instrukcjach montażu, których można się było spodziewać, gdy początkowo przystępujesz do testu. Myślę, że sama w sobie może być ważną lekcją optymalizacji wydajności. Widzimy różnicę, jaką wprowadziła, zastępując zmienne konkretnymi stałymi w naszym kodzie, pod względem inteligencji, którą kompilator jest w stanie zastosować. Mikrooptymalizacje, takie jak podstawienie z mnożeniem z przesunięciem, to niektóre optymalizacje na bardzo niskim poziomie, które kompilator może zwykle łatwo wykonać samodzielnie. Inne optymalizacje, które mają znacznie większy wpływ na wydajność, wymagają zrozumienia intencji koduktóre często nie jest dostępne dla kompilatora lub może się domyślać tylko heurystyka. To tutaj wkraczasz jako inżynier oprogramowania i na pewno zwykle nie polega na zastępowaniu mnożenia zmianami. Obejmuje to takie czynniki, jak unikanie zbędnego połączenia z usługą, która wytwarza operacje we / wy i może blokować proces. Jeśli pójdziesz na dysk twardy lub, na wszelki wypadek, do zdalnej bazy danych, aby uzyskać dodatkowe dane, które możesz uzyskać z tego, co już masz w pamięci, czas oczekiwania przeważa nad wykonaniem miliona instrukcji. Wydaje mi się, że odeszliśmy nieco od twojego pierwotnego pytania, ale myślę, że zwrócę na to uwagę pytającego, zwłaszcza jeśli przypuszczamy, że ktoś, kto dopiero zaczyna rozumieć tłumaczenie i wykonywanie kodu,
Który będzie szybszy? Myślę, że to dobre podejście, które wybrałeś, aby faktycznie przetestować różnicę wydajności. Zasadniczo łatwo jest być zaskoczonym wydajnością niektórych zmian kodu w środowisku wykonawczym. Istnieje wiele technik stosowanych przez współczesne procesory, a interakcja między oprogramowaniem może być również złożona. Nawet jeśli powinieneś uzyskać korzystne wyniki dla pewnej zmiany w jednej sytuacji, myślę, że niebezpiecznie jest wyciągnąć wniosek, że ten typ zmiany zawsze przyniesie korzyści w zakresie wydajności. Myślę, że raz takie testy są niebezpieczne, powiedz „Okej, teraz wiem, który jest szybszy!” a następnie zastosuj tę samą optymalizację do kodu produkcyjnego bez powtarzania pomiarów.
Co jeśli przesunięcie jest szybsze niż pomnożenie? Z pewnością istnieją przesłanki, dlaczego tak jest. Jak widać powyżej, GCC wydaje się myśleć (nawet bez optymalizacji), że unikanie bezpośredniego mnożenia na korzyść innych instrukcji jest dobrym pomysłem. Intel 64 i IA-32 Instrukcja Architektury Optymalizacja referencyjny daje wyobrażenie o względnej kosztów instrukcji procesora. Innym zasobem, bardziej skoncentrowanym na opóźnieniu instrukcji i przepustowości, jest http://www.agner.org/optimize/instruction_tables.pdf. Zauważ, że nie są one dobrym predykatorem absolutnego czasu wykonywania, ale wykonania instrukcji względem siebie. W ciasnej pętli, gdy test jest symulowany, metryka „przepustowości” powinna być najbardziej odpowiednia. Jest to liczba cykli, które jednostka wykonawcza będzie zwykle związana podczas wykonywania danej instrukcji.
A co jeśli przesunięcie NIE jest szybsze niż pomnożenie? Jak powiedziałem powyżej, nowoczesne architektury mogą być dość złożone, a takie rzeczy, jak przewidywanie gałęzi, buforowanie, potokowanie i równoległe jednostki wykonawcze mogą utrudniać przewidywanie względnej wydajności dwóch logicznie równoważnych fragmentów kodu. Naprawdę chcę to podkreślić, ponieważ w tym miejscu nie jestem zadowolony z większości odpowiedzi na takie pytania, a obóz ludzi wprost mówi, że po prostu nieprawda (już) jest taka, że zmiana jest szybsza niż mnożenie.
Nie, o ile mi wiadomo, nie wynaleźliśmy jakiegoś tajnego sosu inżynieryjnego w latach siedemdziesiątych lub kiedykolwiek, aby nagle zlikwidować różnicę kosztów jednostki mnożącej i nieco zmienionej. Ogólne zwielokrotnienie, pod względem logicznych bram, a na pewno pod względem logicznych operacji, jest wciąż bardziej skomplikowane niż przesunięcie z przesunięciem lufy w wielu scenariuszach, na wielu architekturach. Sposób, w jaki przekłada się to na ogólny czas działania na komputerze stacjonarnym, może być nieco nieprzejrzysty. Nie wiem na pewno, w jaki sposób są one implementowane w określonych procesorach, ale oto wyjaśnienie mnożenia: Czy mnożenie liczb całkowitych jest naprawdę taką samą szybkością jak dodawanie na nowoczesnym procesorze
Tutaj znajduje się wyjaśnienie mechanizmu przesuwającego lufy . Dokumenty, o których wspomniałem w poprzednim akapicie, przedstawiają inny pogląd na temat względnego kosztu operacji na podstawie instrukcji procesora. Inżynierowie z Intela często wydają się mieć podobne pytania: fora deweloperskie na forach Intel cykli zegara do mnożenia liczb całkowitych i dodawania w procesorze Core 2 duo
Tak, w większości rzeczywistych scenariuszy i prawie na pewno w JavaScript, próba wykorzystania tej równoważności ze względu na wydajność jest prawdopodobnie daremnym przedsięwzięciem. Jednak nawet jeśli wymuszymy stosowanie instrukcji mnożenia, a następnie nie zobaczymy żadnej różnicy w czasie wykonywania, to bardziej ze względu na charakter zastosowanej metryki kosztu, a dokładniej, a nie dlatego, że nie ma różnicy kosztów. Kompleksowe środowisko uruchomieniowe to jedna miara, a jeśli jest to jedyna, na której nam zależy, wszystko jest w porządku. Ale to nie znaczy, że wszystkie różnice kosztów między pomnażaniem a przesunięciem po prostu zniknęły. I myślę, że z pewnością nie jest dobrym pomysłem przekazanie tego pytania pytającemu, przez domniemanie lub w inny sposób, który oczywiście zaczyna dopiero rozumieć czynniki związane z czasem działania i kosztami nowoczesnego kodu. Inżynieria zawsze polega na kompromisach. Zapytanie i wyjaśnienie, jakie kompromisy dokonały nowoczesne procesory, aby pokazać czas wykonania, który my, jako użytkownicy, widzimy, może dać bardziej zróżnicowaną odpowiedź. I uważam, że bardziej zróżnicowana odpowiedź niż „to po prostu nie jest już prawdą” jest uzasadniona, jeśli chcemy, aby mniej inżynierów sprawdzało w mikrooptymalizowanym kodzie eliminującym czytelność, ponieważ wymaga to bardziej ogólnego zrozumienia natury takich „optymalizacji”, aby dostrzegaj różne, różnorodne wcielenia, niż po prostu odnosząc się do niektórych konkretnych przypadków jako nieaktualnych.
