Kiedy testuję różnicę czasu między przesunięciem a pomnożeniem w C, nie ma różnicy. Czemu?

28

Nauczono mnie, że przesuwanie w systemie binarnym jest znacznie wydajniejsze niż mnożenie przez 2 ^ k. Chciałem więc eksperymentować i użyłem następującego kodu, aby to przetestować:

#include <time.h>
#include <stdio.h>

int main() {
    clock_t launch = clock();
    int test = 0x01;
    int runs;

    //simple loop that oscillates between int 1 and int 2
    for (runs = 0; runs < 100000000; runs++) {


    // I first compiled + ran it a few times with this:
    test *= 2;

    // then I recompiled + ran it a few times with:
    test <<= 1;

    // set back to 1 each time
    test >>= 1;
    }

    clock_t done = clock();
    double diff = (done - launch);
    printf("%f\n",diff);
}

W obu wersjach wydruk wyniósł około 440000, daj lub weź 10000. Nie było (przynajmniej wizualnie) istotnej różnicy między wynikami obu wersji. Więc moje pytanie brzmi: czy coś jest nie tak z moją metodologią? Czy powinna istnieć różnica wizualna? Czy to ma coś wspólnego z architekturą mojego komputera, kompilatora czy coś innego?

NicholasFolk
źródło
47
Ktokolwiek cię nauczył, to było w błędzie. Przekonanie to nie było prawdziwe od lat 70. XX wieku w przypadku zwykle używanych kompilatorów w typowo używanych architekturach. Dobrze dla ciebie za przetestowanie tego roszczenia. Słyszałem o tym bezsensownym oświadczeniu dotyczącym JavaScript na miłość boską.
Eric Lippert,
21
Najlepszym sposobem na udzielenie odpowiedzi na takie pytania jest przyjrzenie się kodowi asemblera, który tworzy kompilator. Kompilatory zazwyczaj mają opcję wygenerowania kopii generowanego języka asemblera. W przypadku kompilatorów GNU GCC jest to „-S”.
Charles E. Grant,
8
Należy zauważyć, że po sprawdzeniu tego za pomocą gcc -S, kod dla test *= 2jest faktycznie kompilowany do shll $1, %eax Po wywołaniu z gcc -O3 -Snie ma nawet pętli. Dwa połączenia zegarowe są oddzielone linią:callq _clock movq %rax, %rbx callq _clock
6
„Nauczono mnie, że przesuwanie w systemie binarnym jest znacznie wydajniejsze niż mnożenie przez 2 ^ k”; uczymy się wielu rzeczy, które okazują się błędne (a przynajmniej nieaktualne). Inteligentny kompilator użyje tej samej operacji shift dla obu.
John Bode
9
Zawsze, zawsze sprawdzaj wygenerowany kod zestawu podczas pracy z tego rodzaju optymalizacją, aby mieć pewność, że mierzysz to, co według ciebie mierzysz. Ogromna liczba pytań „dlaczego widzę te czasy” kończy się sprowadzaniem do kompilatora całkowicie eliminując operacje, ponieważ wyniki nie są używane.
Russell Borogove

Odpowiedzi:

44

Jak powiedziano w drugiej odpowiedzi, większość kompilatorów automatycznie zoptymalizuje multiplikacje, aby zrobić je z przesunięciami bitów.

Jest to bardzo ogólna zasada podczas optymalizacji: większość „optymalizacji” faktycznie źle wprowadza kompilację w to, co naprawdę masz na myśli, a nawet może obniżyć wydajność.

Optymalizuj tylko wtedy, gdy zauważysz problem z wydajnością i zmierzysz, na czym polega problem. (a większość pisanego przez nas kodu nie jest wykonywana tak często, więc nie musimy się tym przejmować)

Dużym minusem optymalizacji jest to, że „zoptymalizowany” kod jest często znacznie mniej czytelny. Więc w twoim przypadku, zawsze idź do mnożenia, gdy chcesz pomnożyć. I idź do przesuwania bitów, gdy chcesz przenieść bity.

Thirler
źródło
20
Zawsze używaj operacji semantycznie poprawnej. Jeśli manipulujesz maskami bitowymi lub umieszczasz małe liczby całkowite w obrębie większych liczb całkowitych, zmiana jest odpowiednią operacją.
ddyer
2
Czy kiedykolwiek (praktycznie mówiąc) istniałaby potrzeba optymalizacji mnożenia do operatora zmiany w aplikacji wysokiego poziomu? Wydaje się, ponieważ kompilator już optymalizuje, że jedyną użyteczną wiedzą jest programowanie na bardzo niskim poziomie (przynajmniej poniżej kompilatora).
NicholasFolk
11
@NicholasFolk nie. Rób to, co najprostsze do zrozumienia. Jeśli pisałeś asembler bezpośrednio, może być użyteczny ... lub jeśli piszesz optymalizujący kompilator, znowu może być użyteczny. Ale poza tymi dwoma przypadkami jest to sztuczka, która przesłania to, co robisz, i sprawia, że ​​następny programista (który jest mordercą z siekierą, który wie, gdzie mieszkasz ) przeklina twoje imię i myśli o podjęciu hobby.
2
@NicholasFolk: Optymalizacje na tym poziomie są prawie zawsze zasłaniane lub renderowane przez architekturę procesora. Kogo to obchodzi, jeśli zaoszczędzisz 50 cykli, gdy tylko pobierasz argumenty z pamięci i zapisujesz je z powrotem, przejmuje 100? Takie mikrooptymalizacje miały sens, gdy pamięć działała z (lub zbliżoną) prędkością procesora, ale dzisiaj nie tak bardzo.
TMN
2
Ponieważ mam dość oglądania tego 10% cytatu i uderzania go tutaj w głowę: „Nie ma wątpliwości, że graal wydajności prowadzi do nadużyć. Programiści tracą mnóstwo czasu na myślenie lub martwienie się o prędkość niekrytycznych części swoich programów, a te próby sprawności faktycznie mają silny wpływ negatywny podczas debugowania i konserwacja są uznawane Mamy. należy zapomnieć o małych wydajności, powiedzmy około 97% czasu: przedwczesny optymalizacji jest korzeniem całe zło ...
cHao
25

Kompilator rozpoznaje stałe i konwertuje mnożenia na przesunięcia, gdy jest to właściwe.

ddyer
źródło
Kompilator rozpoznaje stałe, które są potęgami 2 .... i konwertuje na zmiany. Nie wszystkie stałe można zmienić na zmiany.
szybko_nie
4
@quickly_now: Można je przekształcić w kombinacje przesunięć i dodatków / odejmowań.
Mehrdad
2
Klasycznym błędem optymalizatora kompilatora jest konwersja podziałów na odpowiednie przesunięcia, co działa dla dodatnich dywidend, ale jest wyłączone o 1 dla ujemnych.
ddyer
1
@ quickly_now Uważam, że termin „w stosownych przypadkach” obejmuje ideę, że niektóre stałe nie mogą być przepisywane jako zmiany.
Pharap
21

To, czy przesuwanie jest szybsze niż mnożenie, zależy od architektury twojego procesora. W czasach Pentium i wcześniejszych przesuwanie było często szybsze niż mnożenie, w zależności od liczby 1 bitów w twoim mnożniku. Na przykład, jeśli Twoja liczba mnoga to 320, to 101000000, dwa bity.

a *= 320;               // Slower
a = (a<<7) + (a<<9);    // Faster

Ale jeśli miałeś więcej niż dwa bity ...

a *= 324;                        // About same speed
a = (a<<2) + (a<<7) + (a<<9);    // About same speed

a *= 340;                                 // Faster
a = (a<<2) + (a<<4) + (a<<7) + (a<<9);    // Slower

Na małym mikrokontrolerze, takim jak PIC18 z jednym cyklem zwielokrotnienia, ale bez przesunięcia beczki , mnożenie jest szybsze, jeśli przesuwasz się o więcej niż 1 bit.

a  *= 2;   // Exactly the same speed
a <<= 1;   // Exactly the same speed

a  *= 4;   // Faster
a <<= 2;   // Slower

Zauważ, że jest to przeciwieństwo tego, co było prawdą na starszych procesorach Intel.

Ale wciąż nie jest to takie proste. Jeśli dobrze pamiętam, ze względu na architekturę superskalarną Pentium było w stanie przetwarzać jednocześnie jedną instrukcję mnożenia lub dwie instrukcje zmiany (o ile nie były od siebie zależne). Oznacza to, że jeśli chcesz pomnożyć dwie zmienne przez potęgę 2, przesunięcie może być lepsze.

a  *= 4;   // 
b  *= 4;   // 

a <<= 2;   // Both lines execute in a single cycle
b <<= 2;   // 
Rocketmagnet
źródło
5
+1 „To, czy przesuwanie jest szybsze niż mnożenie, zależy od architektury twojego procesora”. Dziękujemy za faktyczne zapoznanie się z historią i wykazanie, że większość mitów komputerowych ma logiczne podstawy.
Pharap
11

Masz kilka problemów z programem testowym.

Po pierwsze, tak naprawdę nie używasz wartości test. W ramach standardu C nie ma możliwości, aby wartość testspraw była ważna. Optymalizator może go całkowicie bezpłatnie usunąć. Po jego usunięciu pętla jest faktycznie pusta. Jedynym widocznym efektem byłoby ustawienie runs = 100000000, ale runstakże nie jest używane. Optymalizator może (i powinien!) Usunąć całą pętlę. Łatwa poprawka: wydrukuj również obliczoną wartość. Zauważ, że odpowiednio określony optymalizator może nadal optymalizować pętlę (opiera się całkowicie na stałych znanych w czasie kompilacji).

Po drugie, wykonujesz dwie operacje, które się wzajemnie anulują. Optymalizator może to zauważyć i anulować . Ponownie pozostawiając pustą pętlę i usunięty. Ten jest wręcz trudny do naprawienia. Możesz przełączyć się na unsigned int(więc przepełnienie nie jest niezdefiniowanym zachowaniem), ale to oczywiście powoduje po prostu 0. Proste rzeczy (np. Powiedzmy test += 1) są wystarczająco łatwe, aby optymalizator mógł je zrozumieć i tak się dzieje.

Wreszcie zakładasz, że test *= 2tak naprawdę zostanie skompilowany do mnożenia. To bardzo prosta optymalizacja; jeśli przesunięcie bitów jest szybsze, optymalizator użyje go zamiast tego. Aby obejść ten problem, należy użyć wbudowanego zestawu specyficznego dla implementacji.

Albo, jak sądzę, po prostu sprawdź kartę danych mikroprocesora, aby zobaczyć, która jest szybsza.

Kiedy sprawdziłem dane wyjściowe asemblacji kompilacji programu przy gcc -S -O3użyciu wersji 4.9, optymalizator faktycznie przejrzał wszystkie powyższe proste warianty i kilka innych. We wszystkich przypadkach usuwano pętlę (przypisując stałą do test), pozostały tylko wywołania clock(), konwersja / odejmowanie i printf.

derobert
źródło
1
Zauważ również, że optymalizator może (i będzie) optymalizować operacje na stałych (nawet w pętli), jak pokazano w sqrt c # vs sqrt c ++, gdzie optymalizator był w stanie zastąpić pętlę sumującą wartość z rzeczywistą sumą. Aby pokonać tę optymalizację, musisz użyć czegoś określonego w czasie wykonywania (np. Argument wiersza poleceń).
@MichaelT Yep. Właśnie to miałem na myśli: „Zauważ, że wystarczająco określony optymalizator może nadal optymalizować pętlę (opiera się całkowicie na stałych znanych w czasie kompilacji)”.
derobert
Rozumiem, co mówisz, ale nie sądzę, że kompilator usuwa całą pętlę. Możesz łatwo przetestować tę teorię, po prostu zwiększając liczbę iteracji. Zobaczysz, że zwiększenie iteracji powoduje, że program trwa dłużej. Gdyby pętla została całkowicie usunięta, tak nie byłoby.
DollarAkshay
@AkshayLAradhya Nie mogę powiedzieć, co robi twój kompilator, ale ponownie potwierdziłem, że gcc -O3(teraz z 7.3) nadal całkowicie usuwa pętlę. (Pamiętaj, aby przełączyć na długi zamiast int, jeśli jest to wymagane, w przeciwnym razie zoptymalizuje go do nieskończonej pętli z powodu przepełnienia).
derobert
8

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.

użytkownik 2880576
źródło
6

To, co widzisz, jest efektem optymalizatora.

Zadaniem optymalizatorów jest zmniejszenie wynikowego skompilowanego kodu do mniejszego lub szybszego (ale rzadko jednocześnie w tym samym czasie ... ale jak wiele rzeczy ... ZALEŻY od tego, jaki jest kod).

W PRINCIPLE każde wywołanie biblioteki mnożenia, a często nawet użycie mnożnika sprzętowego będzie wolniejsze niż zwykłe przesunięcie bitowe.

Więc ... jeśli naiwny kompilator wygeneruje wywołanie biblioteki dla operacji * 2, wtedy oczywiście będzie działał wolniej niż przesunięcie bitowe *.

Jednak istnieją optymalizatory, które wykrywają wzorce i zastanawiają się, jak zmniejszyć kod / przyspieszyć / cokolwiek. Widziałeś kompilator wykrywający, że * 2 jest tym samym, co zmiana.

Właśnie z ciekawości właśnie dzisiaj patrzyłem na wygenerowany asembler dla niektórych operacji takich jak * 5 ... właściwie nie patrząc na to, ale na inne rzeczy, i po drodze zauważyłem, że kompilator zmienił * 5 w:

  • przesunięcie
  • przesunięcie
  • dodaj oryginalny numer

Tak więc optymalizator mojego kompilatora był wystarczająco inteligentny (przynajmniej w przypadku niektórych małych stałych), aby generować wbudowane przesunięcia i dodaje zamiast wywołań do biblioteki mnożącej ogólnego przeznaczenia.

Sztuka optymalizacji kompilatorów to odrębny temat, pełen magii i naprawdę właściwie zrozumiany przez około 6 osób na całej planecie :)

szybko
źródło
3

Spróbuj zmierzyć czas z:

for (runs = 0; runs < 100000000; runs++) {
      ;
}

Kompilator powinien rozpoznać, że wartość parametru testnie zmienia się po każdej iteracji pętli, a wartość końcowa testnie jest używana, i całkowicie eliminując pętlę.

Russell Borogove
źródło
2

Mnożenie to kombinacja zmian i dodatków.

W przypadku, o którym wspomniałeś, nie sądzę, czy ma to znaczenie, czy kompilator go optymalizuje, czy nie - „pomnóż xprzez dwa” można zaimplementować jako:

  • Przesuń bity o xjedno miejsce w lewo.
  • Dodaj xdo x.

To są podstawowe operacje atomowe; jedno nie jest szybsze od drugiego.

Zmień to na „pomnóż xprzez cztery” (lub dowolne 2^k, k>1), a to trochę inaczej:

  • Przesuń bity o xdwa miejsca w lewo.
  • Dodaj xdo xi nazywają go y, dodać ydo y.

Na podstawową architekturę, to proste, aby zobaczyć, że zmiana jest bardziej wydajny - biorąc jeden vs. dwie operacje, ponieważ nie możemy dodać ydo ydopóki nie wiemy, co yjest.

Wypróbuj tę ostatnią (lub dowolną 2^k, k>1), z odpowiednimi opcjami, aby nie zoptymalizować ich pod kątem implementacji. Powinieneś przekonać się, że zmiana jest szybsza, biorąc O(1)pod uwagę wielokrotne dodawanie w O(k).

Oczywiście, gdy multiplikacja nie jest potęgą dwóch, konieczna jest kombinacja przesunięć i dodatków (jedna, w której liczba każdego jest niezerowa).

OJFord
źródło
1
Co to jest „podstawowa operacja atomowa”? Czy nie można argumentować, że podczas zmiany operację można zastosować do każdego bitu równolegle, podczas gdy w dodatku bity najbardziej na lewo zależą od innych bitów?
Bergi,
2
@Bergi: Zgaduję, że ma na myśli, że zarówno shift, jak i add są instrukcjami pojedynczej maszyny. Trzeba będzie spojrzeć na dokumentację zestawu instrukcji, aby zobaczyć liczbę cykli dla każdego, ale tak, dodawanie jest często operacją wielocyklową, podczas gdy zmiana jest zwykle wykonywana w jednym cyklu.
TMN
Tak, może tak być, ale mnożenie jest również instrukcją pojedynczej maszyny (choć oczywiście może wymagać więcej cykli)
Bergi
@Bergi, to też zależy od łuku. Jaki łuk myślisz o tych przesunięciach w mniejszej liczbie cykli niż dodanie 32-bitowe (lub x-bit, jeśli dotyczy)?
OJFord
Nie znam żadnej konkretnej architektury, nie (i moje kursy inżynierii komputerowej wyblakły), prawdopodobnie obie instrukcje zajmują mniej niż jeden cykl. Prawdopodobnie myślałem o mikrokodzie, a nawet bramkach logicznych, gdzie przesunięcie byłoby prawdopodobnie tańsze.
Bergi
1

Mnożenie podpisanych lub niepodpisanych wartości przez potęgę dwóch jest równoważne przesunięciu w lewo, a większość kompilatorów dokona zamiany. Podział wartości niepodpisanych lub wartości podpisanych, które kompilator może udowodnić, nigdy nie jest ujemny , jest równoważny przesunięciu w prawo, a większość kompilatorów dokona tego zastąpienia (chociaż niektóre nie są wystarczająco wyrafinowane, aby udowodnić, gdy podpisane wartości nie mogą być ujemne) .

Należy jednak zauważyć, że podział wartości potencjalnie ujemnych ze znakiem nie jest równoważny przesunięciu w prawo. Wyrażenie podobne (x+8)>>4nie jest równoważne z (x+8)/16. Pierwszy z nich, w 99% kompilatorów, odwzoruje wartości od -24 do -9 do -1, -8 do +7 do 0 i +8 do +23 do 1 [zaokrąglanie liczb prawie symetrycznie około zera]. Ten ostatni zamapuje od -39 do -24 do -1, od -23 do +7 do 0 i od +8 do +23 do +1 [rażąco asymetryczny i prawdopodobnie nie to, co było zamierzone]. Zauważ, że nawet jeśli nie oczekuje się, że wartości będą ujemne, użycie >>4prawdopodobnie da szybszy kod niż, /16chyba że kompilator udowodni, że wartości nie mogą być ujemne.

supercat
źródło
0

Kilka dodatkowych informacji, które właśnie sprawdziłem.

Na x86_64 kod operacyjny MUL ma 10-letnie opóźnienie cyklu i przepustowość 1/2 cyklu. MOV, ADD i SHL mają opóźnienie 1 cyklu, z przepustowością cyklu 2,5, 2,5 i 1,7.

Mnożenie przez 15 wymagałoby co najmniej 3 operacji SHL i 3 ADD i prawdopodobnie kilku MOV.

https://gmplib.org/~tege/x86-timing.pdf

Rich Remer
źródło
0

Twoja metodologia jest wadliwa. Przyrost pętli i samo sprawdzanie stanu zajmuje tyle czasu.

  • Spróbuj uruchomić pustą pętlę i zmierz czas (nazwij ją base).
  • Teraz dodaj 1 zmianę i zmierz czas (zadzwoń s1).
  • Następnie dodaj 10 operacji zmiany i zmierz czas (zadzwoń s2)

Jeśli wszystko idzie poprawnie, base-s2powinno być 10 razy więcej niż base-s1. W przeciwnym razie wchodzi tu coś innego.

Teraz sam tego próbowałem i pomyślałem: Jeśli pętle powodują problem, dlaczego nie usunąć ich całkowicie. Więc poszedłem naprzód i zrobiłem to:

int main(){

    int test = 2;
    clock_t launch = clock();

    test << 6;
    test << 6;
    test << 6;
    test << 6;
    //.... 1 million times
    test << 6;

    clock_t done = clock();
    printf("Time taken : %d\n", done - launch);
    return 0;
}

I masz swój wynik

1 milion operacji zmianowych w czasie poniżej 1 milisekundy? .

Zrobiłem to samo dla pomnożenia przez 64 i uzyskałem ten sam wynik. Prawdopodobnie więc kompilator całkowicie ignoruje operację, ponieważ inni wspominali, że wartość testu nigdy się nie zmienia.

Wynik zmiany biegów operatora

DollarAshshay
źródło