Czy mnożenie i dzielenie za pomocą operatorów zmiany biegów w C jest rzeczywiście szybsze?


288

Mnożenie i dzielenie można osiągnąć na przykład za pomocą operatorów bitowych

i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)

i tak dalej.

Czy w rzeczywistości szybsze jest użycie powiedz (i<<3)+(i<<1)do pomnożenia przez 10 niż i*10bezpośrednie? Czy jest jakiś rodzaj danych wejściowych, których nie można pomnożyć ani podzielić w ten sposób?


8
W rzeczywistości możliwy jest tani podział przez stałą inną niż potęga dwóch, ale jest to podchwytliwy subjet, do którego nie odpowiada się słowem „/ Division… / split” w pytaniu. Zobacz na przykład hackersdelight.org/divcMore.pdf (lub pobierz książkę „Rozkosz hakera”, jeśli możesz).
Pascal Cuoq,

46
Brzmi jak coś, co można łatwo przetestować.
juanchopanza

25
Jak zwykle - to zależy. Pewnego razu próbowałem tego w asemblerze na procesorze Intel 8088 (IBM PC / XT), gdzie mnożenie wymagało zegarów bazillionowych. Przesunięcia i dodania były wykonywane znacznie szybciej, więc wydawało się, że to dobry pomysł. Jednak podczas mnożenia jednostka magistrali mogła swobodnie wypełnić kolejkę instrukcji, a następna instrukcja mogła wtedy rozpocząć się natychmiast. Po serii przesunięć i dodawania kolejka instrukcji byłaby pusta, a procesor musiałby czekać na pobranie kolejnej instrukcji z pamięci (jeden bajt na raz!). Mierz, mierz, mierz!
Bo Persson

19
Pamiętaj też, że przesunięcie w prawo jest dobrze zdefiniowane tylko dla liczb całkowitych bez znaku . Jeśli masz podpisaną liczbę całkowitą, nie jest określone, czy 0 lub najwyższy bit są dopełniane od lewej strony. (I nie zapomnij o czasie potrzebnym na przeczytanie kodu przez kogoś innego (nawet
ciebie

29
Właściwie dobry kompilator optymalizujący zaimplementuje mnożenie i dzielenie z przesunięciami, gdy są one szybsze.
Peter G.

Odpowiedzi:


487

Krótka odpowiedź: mało prawdopodobne.

Długa odpowiedź: Twój kompilator ma optymalizator, który wie, jak mnożyć tak szybko, jak jest to możliwe w architekturze procesora docelowego. Najlepiej jest wyraźnie powiedzieć kompilatorowi o swoich zamiarach (tzn. I * 2 zamiast i << 1) i pozwolić mu zdecydować, jaka jest najszybsza sekwencja kodu asemblera. Możliwe jest nawet, że sam procesor zaimplementował instrukcję mnożenia jako sekwencję przesunięć i dodawania w mikrokodzie.

Podsumowując - nie marnuj dużo czasu na to. Jeśli masz zamiar się zmienić, to zmień. Jeśli masz zamiar pomnożyć, pomnóż. Rób to, co jest semantycznie klarowne - Twoi współpracownicy podziękują Ci później. Lub, bardziej prawdopodobne, przeklinać cię później, jeśli zrobisz inaczej.


31
Tak, jak powiedziano, możliwe korzyści dla prawie każdej aplikacji całkowicie przewyższą wprowadzoną niejasność. Nie martw się o tego rodzaju optymalizację przedwcześnie. Zbuduj to, co jest semmatycznie jasne, zidentyfikuj wąskie gardła i stamtąd zoptymalizuj ...
Dave

4
Uzgodnione, optymalizacja pod kątem czytelności i łatwości konserwacji prawdopodobnie zapewni ci więcej czasu na faktyczną optymalizację rzeczy, które według profilera są ścieżkami do gorącego kodu.
doug65536

5
Te komentarze brzmią tak, jakbyś rezygnował z potencjalnej wydajności od mówienia kompilatorowi, jak wykonać swoją pracę. Tak nie jest . W rzeczywistości otrzymujesz lepszy kod z wersji gcc -O3x86 return i*10niż z wersji shift . Jako ktoś, kto dużo patrzy na dane wyjściowe kompilatora (zobacz wiele moich odpowiedzi na asm / optymalizację), nie jestem zaskoczony. Są chwile, kiedy może pomóc utrzymać kompilator w jednej ręce , ale nie jest to jeden z nich. gcc jest dobry w matematyce liczb całkowitych, ponieważ jest ważny.
Peter Cordes,

Właśnie pobrałem szkic arduino, który ma millis() >> 2; Czy byłoby zbyt wiele prosić o podział?
Paul Wieland,

1
Testowałem i / 32vs i >> 5i i / 4vs i >> 2na gcc dla kory-a9 (która nie ma podziału sprzętowego) z optymalizacją -O3, a wynikowy montaż był dokładnie taki sam. Najpierw nie lubiłem używać podziałów, ale opisuje to moją intencję, a wyniki są takie same.
robsn

91

Tylko konkretny punkt pomiaru: wiele lat temu porównałem dwie wersje mojego algorytmu mieszającego:

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = 127 * h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

i

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = (h << 7) - h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

Na każdej maszynie, na której testowałem, pierwsza była co najmniej tak szybka jak druga. Nieoczekiwanie było to czasem szybsze (np. Na Sun Sparc). Gdy sprzęt nie obsługiwał szybkiego mnożenia (a większość nie wtedy), kompilator konwertuje mnożenie na odpowiednie kombinacje przesunięć i dodawania / dodawania. A ponieważ znał ostateczny cel, czasami mógł to zrobić w mniejszej liczbie instrukcji niż wtedy, gdy wyraźnie pisałeś zmiany i dodawanie / dodawanie.

Zauważ, że było to około 15 lat temu. Miejmy nadzieję, że od tego czasu kompilatory stały się lepsze, więc możesz liczyć na to, że kompilator zrobi właściwą rzecz, prawdopodobnie lepszą niż mógłbyś. (Ponadto, kod wygląda tak C'ish, ponieważ był ponad 15 lat temu. Oczywiście std::stringużyłbym dzisiaj i iteratorów).


5
Być może zainteresuje Cię poniższy post na blogu, w którym autor zauważa, że ​​współczesne kompilatory optymalizujące wydają się przekształcać typowe wzorce, z których programiści mogą korzystać, myśląc, że są bardziej wydajni w swoich matematycznych formach, aby naprawdę wygenerować dla nich najbardziej wydajną sekwencję instrukcji . shape-of-code.coding-guidelines.com/2009/06/30/…
Pascal Cuoq

@PascalCuoq Nie ma w tym nic nowego. Odkryłem prawie to samo dla Sun CC blisko 20 lat temu.
James Kanze

67

Oprócz wszystkich innych dobrych odpowiedzi tutaj, pozwól mi wskazać kolejny powód, aby nie używać shift, gdy masz na myśli dzielenie lub mnożenie. Nigdy nie widziałem, aby ktoś wprowadzał błąd, zapominając o względnym priorytecie mnożenia i dodawania. Widziałem błędy wprowadzane, gdy programiści serwisowi zapomnieli, że „pomnożenie” przez zmianę jest logicznie zwielokrotnieniem, ale nie składniowym z takim samym pierwszeństwem jak mnożenie. x * 2 + zi x << 1 + zbardzo się różnią!

Jeśli pracujesz na liczbach, użyj operatorów arytmetycznych, takich jak + - * / %. Jeśli pracujesz nad tablicami bitów, użyj bitowych operatorów kręcących, takich jak & ^ | >>. Nie mieszaj ich; Wyrażenie, które ma zarówno tandetne bicie, jak i arytmetykę, jest błędem, który czeka.


5
Można tego uniknąć za pomocą prostego nawiasu?
Joel B

21
@Jel: Jasne. Jeśli pamiętasz, że ich potrzebujesz. Chodzi mi o to, że łatwo o tym zapomnieć. Ludzie, którzy wpadają w mentalny nawyk czytania „x << 1” tak, jakby to był „x * 2”, zaczynają mentalnie myśleć, że << jest tym samym priorytetem co mnożenie, a tak nie jest.
Eric Lippert,

1
Cóż, uważam, że wyrażenie „(hi << 8) + lo” jest bardziej odkrywcze niż „hi * 256 + lo”. Prawdopodobnie jest to kwestia gustu, ale czasami łatwiej jest pisać kręcenie bitów. W większości przypadków jednak całkowicie zgadzam się z twoim punktem widzenia.
Ivan Danilov

32
@Ivan: A „(hi << 8) | lo” jest jeszcze bardziej wyraźne. Ustawienie niskich bitów tablicy bitów nie jest dodawaniem liczb całkowitych . To ustawienie bitów , więc napisać kod, który ustawia bity.
Eric Lippert,

1
Łał. Nie myślałem o tym wcześniej. Dzięki.
Ivan Danilov

50

Zależy to od procesora i kompilatora. Niektóre kompilatory już optymalizują kod w ten sposób, inne nie. Musisz więc sprawdzać za każdym razem, gdy Twój kod wymaga optymalizacji.

Chyba że rozpaczliwie potrzebujesz optymalizacji, nie szyfrowałbym kodu źródłowego tylko po to, aby zapisać instrukcję asemblera lub cykl procesora.


3
Żeby dodać przybliżone oszacowanie: w typowym 16-bitowym procesorze (80C166) dodanie dwóch liczb całkowitych następuje w 1-2 cyklach, mnożenie w 10 cyklach i podział w 20 cyklach. Plus niektóre operacje przesuwania, jeśli zoptymalizujesz i * 10 do wielu operacji (każde przesunięcie o kolejny cykl +1). Najpopularniejsze kompilatory (Keil / Tasking) nie optymalizują, chyba że do mnożenia / dzielenia przez potęgę 2.
Jens

55
Ogólnie rzecz biorąc, kompilator optymalizuje kod lepiej niż ty.
user703016

Zgadzam się, że przy mnożeniu „ilości” operator mnożenia jest ogólnie lepszy, ale przy dzieleniu podpisanych wartości przez potęgi 2 >>operator jest szybszy niż, /a jeśli podpisane wartości mogą być ujemne, często jest również semantycznie lepszy. Jeśli potrzebna jest wartość, która x>>4by wytworzyła, jest to o wiele jaśniejsze niż x < 0 ? -((-1-x)/16)-1 : x/16;i nie wyobrażam sobie, jak kompilator może zoptymalizować to ostatnie wyrażenie do czegoś fajnego.
supercat

38

Czy w rzeczywistości szybsze jest użycie powiedz (i << 3) + (i << 1) do pomnożenia przez 10 niż bezpośrednie użycie i * 10?

Może, ale nie musi być na twoim komputerze - jeśli cię to obchodzi, zmierz swoje rzeczywiste użycie.

Studium przypadku - od 486 do rdzenia i7

Benchmarking jest bardzo trudny do przeprowadzenia w sensowny sposób, ale możemy spojrzeć na kilka faktów. Z http://www.penguin.cz/~literakl/intel/s.html#SAL i http://www.penguin.cz/~literakl/intel/i.html#IMUL otrzymujemy pojęcie o cyklach zegara x86 potrzebne do przesunięcia arytmetycznego i mnożenia. Powiedzmy, że trzymamy się „486” (najnowszego wymienionego), 32-bitowych rejestrów i natychmiastowych, IMUL zajmuje 13-42 cykli i IDIV 44. Każda SAL zajmuje 2 i dodaje 1, więc nawet przy kilku z nich zmienia się powierzchownie jak zwycięzca.

Obecnie z rdzeniem i7:

(z http://software.intel.com/en-us/forums/showthread.php?t=61481 )

Opóźnienie wynosi 1 cykl dla dodawania liczb całkowitych i 3 cykle dla mnożenia liczb całkowitych . Opóźnienia i przelotność można znaleźć w załączniku C „Podręcznika optymalizacji architektury Intel® 64 i IA-32”, który znajduje się na stronie http://www.intel.com/products/processor/manuals/ .

(z jakiegoś napadu Intela)

Korzystając z SSE, Core i7 może wydawać jednoczesne instrukcje dodawania i mnożenia, co daje szczytową szybkość 8 operacji zmiennoprzecinkowych (FLOP) na cykl zegara

To daje wyobrażenie o tym, jak daleko zaszło. Ciekawostki związane z optymalizacją - takie jak przesunięcie bitów w porównaniu do *- które zostały potraktowane poważnie nawet w latach 90., są teraz przestarzałe. Przesunięcie bitów jest wciąż szybsze, ale w przypadku braku mocy dwóch mul / dz, zanim wykonasz wszystkie swoje zmiany i dodasz wyniki, będzie znowu wolniejszy. Następnie więcej instrukcji oznacza więcej błędów pamięci podręcznej, więcej potencjalnych problemów w przetwarzaniu potokowym, większe wykorzystanie rejestrów tymczasowych może oznaczać więcej zapisywania i przywracania zawartości rejestru ze stosu ... szybko staje się zbyt skomplikowane, aby ostatecznie obliczyć wszystkie wpływy, ale są one głównie negatywne.

funkcjonalność w kodzie źródłowym a implementacja

Mówiąc bardziej ogólnie, twoje pytanie jest oznaczone jako C i C ++. Jako języki trzeciej generacji są one specjalnie zaprojektowane, aby ukryć szczegóły podstawowego zestawu instrukcji procesora. Aby spełnić ich Standardy językowe, muszą obsługiwać operacje mnożenia i przenoszenia (i wiele innych), nawet jeśli nie obsługuje tego sprzęt . W takich przypadkach muszą zsyntetyzować wymagany wynik przy użyciu wielu innych instrukcji. Podobnie muszą zapewniać obsługę oprogramowania dla operacji zmiennoprzecinkowych, jeśli procesor go nie ma i nie ma FPU. Nowoczesne procesory wszystkie obsługują *i<<, więc może się to wydawać absurdalnie teoretyczne i historyczne, ale istotne jest to, że swoboda wyboru implementacji przebiega w obie strony: nawet jeśli procesor posiada instrukcję, która implementuje operację wymaganą w kodzie źródłowym w ogólnym przypadku, kompilator może wybierz coś innego, co woli, ponieważ jest to lepsze w konkretnym przypadku, z którym ma do czynienia kompilator.

Przykłady (z hipotetycznym językiem asemblera)

source           literal approach         optimised approach
#define N 0
int x;           .word x                xor registerA, registerA
x *= N;          move x -> registerA
                 move x -> registerB
                 A = B * immediate(0)
                 store registerA -> x
  ...............do something more with x...............

Instrukcje takie jak wyłączne lub ( xor) nie mają związku z kodem źródłowym, ale xor-cokolwiek ze sobą usuwa wszystkie bity, więc można go użyć do ustawienia czegoś na 0. Kod źródłowy sugerujący, że adresy pamięci nie wymagają użycia.

Tego rodzaju włamania były używane tak długo, jak długo istniały komputery. Na początku 3GLs, aby zabezpieczyć programistę, wyjście kompilatora musiało zaspokoić istniejącego hardcorowego, optymalizującego ręcznie dewelopera w asemblerze. społeczność, że wygenerowany kod nie był wolniejszy, bardziej szczegółowy lub w inny sposób gorszy. Kompilatory szybko przyjęły wiele świetnych optymalizacji - stały się lepiej scentralizowanym magazynem, niż mógłby to być każdy programista w języku asemblera, choć zawsze istnieje szansa, że ​​przegapią konkretną optymalizację, która jest kluczowa w konkretnym przypadku - ludzie mogą czasem wykręć to i szukaj czegoś lepszego, podczas gdy kompilatory robią tak, jak im powiedzono, dopóki ktoś nie wróci do nich tym doświadczeniem.

Tak więc, nawet jeśli przesuwanie i dodawanie jest jeszcze szybsze na określonym sprzęcie, pisarz kompilatora prawdopodobnie zadziałał dokładnie wtedy, gdy jest bezpieczny i korzystny.

Konserwowalność

Jeśli twój sprzęt ulegnie zmianie, możesz go ponownie skompilować, a on spojrzy na docelowy procesor i dokona innego najlepszego wyboru, podczas gdy raczej nie będziesz chciał ponownie przeglądać swoich „optymalizacji” lub listy, które środowiska kompilacji powinny używać mnożenia, a które powinny się zmieniać. Pomyśl o wszystkich „optymalizacjach” o przesunięciu nieco dwóch bitów, napisanych ponad 10 lat temu, które spowalniają kod, w którym się znajdują, ponieważ działa na nowoczesnych procesorach ...!

Na szczęście dobre kompilatory, takie jak GCC, mogą zazwyczaj zastąpić serię przesunięć bitowych i arytmetyki bezpośrednim zwielokrotnieniem, gdy włączona jest jakakolwiek optymalizacja (tj. ...main(...) { return (argc << 4) + (argc << 2) + argc; }-> imull $21, 8(%ebp), %eax), więc rekompilacja może pomóc nawet bez poprawiania kodu, ale nie jest to gwarantowane.

Dziwny kod bitshiftingu, który implementuje mnożenie lub dzielenie, jest o wiele mniej wyrazisty w stosunku do tego, co próbujesz osiągnąć koncepcyjnie, więc inni programiści będą tym zdezorientowani, a zdezorientowany programista bardziej prawdopodobne jest wprowadzenie błędów lub usunięcie czegoś niezbędnego w celu przywrócenia zdrowego rozsądku. Jeśli robisz rzeczy nieoczywiste tylko wtedy, gdy są naprawdę namacalnie korzystne, a następnie dobrze je dokumentujesz (ale i tak nie dokumentujesz innych rzeczy, które są intuicyjne), wszyscy będą szczęśliwsi.

Rozwiązania ogólne a rozwiązania częściowe

Jeśli masz trochę dodatkowej wiedzy, na przykład, że intnaprawdę będziesz przechowywać tylko wartości x, ya znastępnie możesz być w stanie wypracować instrukcje, które działają dla tych wartości i uzyskać wynik szybciej niż wtedy, gdy kompilator nie ma ten wgląd i wymaga implementacji, która działa dla wszystkich intwartości. Rozważ na przykład swoje pytanie:

Mnożenie i dzielenie można osiągnąć za pomocą operatorów bitów ...

Ilustrujesz mnożenie, ale co powiesz na podział?

int x;
x >> 1;   // divide by 2?

Zgodnie ze standardem C ++ 5.8:

-3- Wartość E1 >> E2 to E1 z przesuniętymi w prawo pozycjami bitów E2. Jeśli E1 ma typ bez znaku lub jeśli E1 ma typ ze znakiem i nieujemną wartość, wartość wyniku jest integralną częścią ilorazu E1 podzielonego przez liczbę 2 podniesioną do potęgi E2. Jeśli E1 ma typ ze znakiem i wartość ujemną, wynikowa wartość jest zdefiniowana w implementacji.

Zatem przesunięcie bitów ma wynik zdefiniowany w implementacji, gdy xjest ujemny: może nie działać w ten sam sposób na różnych komputerach. Ale /działa o wiele bardziej przewidywalnie. (Może to również nie być całkowicie spójne, ponieważ różne maszyny mogą mieć różne reprezentacje liczb ujemnych, a zatem różne zakresy, nawet jeśli ta sama liczba bitów tworzy tę reprezentację.)

Możesz powiedzieć: „Nie obchodzi mnie to… intprzechowywanie wieku pracownika, nigdy nie może być negatywne”. Jeśli masz taki szczególny wgląd, to tak - Twoja >>bezpieczna optymalizacja może zostać pominięta przez kompilator, o ile nie zrobisz tego wprost w kodzie. Jest to jednak ryzykowne i rzadko przydatne, ponieważ przez większość czasu nie będziesz mieć takiego wglądu, a inni programiści pracujący nad tym samym kodem nie będą wiedzieć, że postawiłeś dom na pewne niezwykłe oczekiwania dotyczące danych, które „ Zajmę się ... to, co wydaje się całkowicie bezpieczną zmianą, może się nie udać z powodu twojej „optymalizacji”.

Czy jest jakiś rodzaj danych wejściowych, których nie można pomnożyć ani podzielić w ten sposób?

Tak ... jak wspomniano powyżej, liczby ujemne mają zachowanie zdefiniowane w implementacji, gdy są „podzielone” przez przesunięcie bitów.


2
Bardzo miła odpowiedź. Porównanie Core i7 vs. 486 jest pouczające!
Drew Hall

We wszystkich powszechnych architekturach intVal>>1będą miały tę samą semantykę, która różni się od tych intVal/2w sposób, który jest czasem użyteczny. Jeśli trzeba obliczyć w przenośny sposób wartość, którą przyniosłyby zwykłe architektury intVal >> 1, wyrażenie musiałoby być bardziej skomplikowane i trudniejsze do odczytania, i prawdopodobnie wygenerowałby znacznie gorszy kod niż wygenerowany intVal >> 1.
supercat,

35

Właśnie wypróbowałem na moim komputerze kompilując to:

int a = ...;
int b = a * 10;

Podczas demontażu generuje dane wyjściowe:

MOV EAX,DWORD PTR SS:[ESP+1C] ; Move a into EAX
LEA EAX,DWORD PTR DS:[EAX+EAX*4] ; Multiply by 5 without shift !
SHL EAX, 1 ; Multiply by 2 using shift

Ta wersja jest szybsza niż twój zoptymalizowany ręcznie kod z czystym przesunięciem i dodawaniem.

Naprawdę nigdy nie wiesz, co wymyśli kompilator, więc lepiej po prostu napisać normalne mnożenie i pozwolić mu zoptymalizować to, co chce, z wyjątkiem bardzo dokładnych przypadków, w których wiesz, że kompilator nie może zoptymalizować.


1
Otrzymalibyście za to dużą aprobatę, gdyby pominąć część dotyczącą wektora. Jeśli kompilator może naprawić mnożenie, może także zobaczyć, że wektor się nie zmienia.
Bo Persson

Skąd kompilator może wiedzieć, że rozmiar wektora się nie zmieni bez przyjęcia naprawdę niebezpiecznych założeń? A może nigdy nie słyszałeś o współbieżności ...
Charles Goodwin,

1
Ok, więc zapętlasz globalny wektor bez blokad? I zapętlam lokalny wektor, którego adres nie został jeszcze zajęty, i wywołuję tylko stałe funkcje członka. Przynajmniej mój kompilator zdaje sobie sprawę, że rozmiar wektora się nie zmieni. (i wkrótce ktoś prawdopodobnie oznaczy nas na czacie :-).
Bo Persson

1
@ BoPersson Wreszcie, po całym tym czasie, usunąłem moje stwierdzenie, że kompilator nie jest w stanie zoptymalizować vector<T>::size(). Mój kompilator był dość stary! :)
user703016

21

Przesuwanie jest zazwyczaj dużo szybsze niż mnożenie na poziomie instrukcji, ale możesz tracić czas na przedwczesne optymalizacje. Kompilator może wykonywać te optymalizacje w czasie kompilacji. Zrób to sam, wpłynie na czytelność i prawdopodobnie nie wpłynie na wydajność. Prawdopodobnie warto robić takie rzeczy tylko wtedy, gdy profilujesz i uważasz, że jest to wąskie gardło.

W rzeczywistości sztuczka z podziałem, znana jako „podział magiczny”, może przynieść ogromne korzyści. Ponownie powinieneś najpierw profilować, aby zobaczyć, czy jest to potrzebne. Ale jeśli go użyjesz, znajdziesz przydatne programy, które pomogą Ci dowiedzieć się, jakie instrukcje są potrzebne dla tej samej semantyki podziału. Oto przykład: http://www.masm32.com/board/index.php?topic=12421.0

Przykład, który podniosłem z wątku OP na MASM32:

include ConstDiv.inc
...
mov eax,9999999
; divide eax by 100000
cdiv 100000
; edx = quotient

Wygeneruje:

mov eax,9999999
mov edx,0A7C5AC47h
add eax,1
.if !CARRY?
    mul edx
.endif
shr edx,16

7
@Drew z jakiegoś powodu twój komentarz rozśmieszył mnie i rozlał moją kawę. dzięki.
asawyer

30
Brak losowych wątków na forum na temat polubienia matematyki. Każdy, kto lubi matematykę, wie, jak trudno jest wygenerować prawdziwy „losowy” wątek na forum.
Joel B,

1
Prawdopodobnie warto robić takie rzeczy tylko wtedy, gdy profilujesz i stwierdzisz, że jest to wąskie gardło i wdrożyłeś alternatywy i profil ponownie i uzyskasz co najmniej 10-krotną przewagę wydajności .
Lie Ryan

12

Instrukcje przesunięcia i mnożenia liczb całkowitych mają podobną wydajność na większości współczesnych procesorów - instrukcje mnożenia liczb całkowitych były stosunkowo powolne w latach 80., ale generalnie nie jest to już prawdą. Instrukcje mnożenia liczb całkowitych mogą mieć większe opóźnienia , więc nadal mogą zdarzyć się przypadki, w których preferowane jest przesunięcie. To samo dotyczy przypadków, w których możesz utrzymywać więcej jednostek wykonawczych zajętych (chociaż może to zmniejszyć obie strony).

Dzielenie liczb całkowitych jest jednak nadal stosunkowo wolne, więc stosowanie przesunięcia zamiast dzielenia przez potęgę 2 to nadal wygrana, a większość kompilatorów zastosuje to jako optymalizację. Należy jednak pamiętać, że aby ta optymalizacja była prawidłowa, dywidenda musi być niepodpisana lub musi być znana jako dodatnia. W przypadku dywidendy ujemnej przesunięcie i podział nie są równoważne!

#include <stdio.h>

int main(void)
{
    int i;

    for (i = 5; i >= -5; --i)
    {
        printf("%d / 2 = %d, %d >> 1 = %d\n", i, i / 2, i, i >> 1);
    }
    return 0;
}

Wynik:

5 / 2 = 2, 5 >> 1 = 2
4 / 2 = 2, 4 >> 1 = 2
3 / 2 = 1, 3 >> 1 = 1
2 / 2 = 1, 2 >> 1 = 1
1 / 2 = 0, 1 >> 1 = 0
0 / 2 = 0, 0 >> 1 = 0
-1 / 2 = 0, -1 >> 1 = -1
-2 / 2 = -1, -2 >> 1 = -1
-3 / 2 = -1, -3 >> 1 = -2
-4 / 2 = -2, -4 >> 1 = -2
-5 / 2 = -2, -5 >> 1 = -3

Więc jeśli chcesz pomóc kompilatorowi, upewnij się, że zmienna lub wyrażenie w dywidendzie jest jawnie niepodpisane.


4
Mnożniki liczb całkowitych są mikrokodowane, na przykład na PPU PlayStation 3, i blokują cały potok. Na niektórych platformach zaleca się unikanie mnożenia liczb całkowitych :)
Maister

2
Wiele niepodpisanych dywizji jest - zakładając, że kompilator wie jak - implementowanych przy użyciu niepodpisanych mnożników. Jeden lub dwa pomnożenia @ kilka cykli zegara każdy może wykonać tę samą pracę, co podział @ 40 cykli każdy i więcej.
Olof Forshell

1
@Olof: prawda, ale poprawne tylko dla dzielenia według stałej czasowej kompilacji
Paul R

4

Zależy to całkowicie od urządzenia docelowego, języka, celu itp.

Chrupanie pikseli w sterowniku karty graficznej? Bardzo prawdopodobne, że tak!

Aplikacja biznesowa .NET dla Twojego działu? Absolutnie nie ma powodu, aby w to zaglądać.

W przypadku wysokowydajnej gry na urządzenie mobilne warto przyjrzeć się temu, ale dopiero po przeprowadzeniu łatwiejszych optymalizacji.


2

Nie rób, chyba że jest to absolutnie konieczne, a zamiar kodu wymaga przesunięcia, a nie mnożenia / dzielenia.

W typowym dniu - możesz potencjalnie zaoszczędzić kilka cykli maszyny (lub stracić, ponieważ kompilator wie lepiej, co zoptymalizować), ale koszt nie jest tego wart - spędzasz czas na drobnych szczegółach, a nie na faktycznej pracy, utrzymanie kodu staje się trudniejsze i twoi współpracownicy cię przeklną.

Być może trzeba to zrobić w przypadku obliczeń o dużym obciążeniu, w których każdy zapisany cykl oznacza minuty czasu wykonywania. Ale powinieneś optymalizować jedno miejsce na raz i przeprowadzać testy wydajności za każdym razem, aby sprawdzić, czy naprawdę przyspieszysz lub złamałeś logikę kompilatorów.


1

O ile wiem w niektórych maszynach mnożenie może wymagać od 16 do 32 cykli maszynowych. Więc tak , w zależności od typu maszyny, operatorzy Bitshift są szybsze niż mnożenie / dzielenie.

Jednak niektóre maszyny mają procesor matematyczny, który zawiera specjalne instrukcje dotyczące mnożenia / dzielenia.


7
Ludzie piszący kompilatory dla tych maszyn prawdopodobnie również przeczytali Hackers Delight i odpowiednio je zoptymalizowali.
Bo Persson,

1

Zgadzam się z zaznaczoną odpowiedzią Drew Hala. Odpowiedź mogłaby jednak przynieść dodatkowe uwagi.

Dla zdecydowanej większości programistów procesor i kompilator nie są już odpowiednie do pytania. Większość z nas daleko wykracza poza 8088 i MS-DOS. Być może dotyczy to tylko tych, którzy wciąż pracują nad wbudowanymi procesorami ...

W moim oprogramowaniu do matematyki należy używać Math (add / sub / mul / div). Podczas konwersji między typami danych należy używać Shift, np. ushort do bajtu jako n >> 8, a nie n / 256.


Ja też się z tobą zgadzam. Podświadomie stosuję się do tych samych wytycznych, chociaż nigdy nie miałem formalnego wymogu, aby to zrobić.
Drew Hall

0

W przypadku liczb całkowitych ze znakiem i prawej zmiany vs podziału może to mieć znaczenie. W przypadku liczb ujemnych zaokrąglenie zmiany zaokrągla się w kierunku ujemnej nieskończoności, natomiast podział zaokrągla w kierunku zera. Oczywiście kompilator zmieni podział na coś tańszego, ale zwykle zmieni go na coś, co ma takie samo zachowanie zaokrąglania jak podział, ponieważ albo nie jest w stanie udowodnić, że zmienna nie będzie ujemna, albo po prostu nie opieka. Więc jeśli możesz udowodnić, że liczba nie będzie ujemna lub jeśli nie obchodzi Cię, w jaki sposób będzie ona zaokrąglać, możesz przeprowadzić tę optymalizację w sposób, który bardziej prawdopodobne jest, aby coś zmienić.


lub rzuć numer naunsigned
Lie Ryan

4
Czy na pewno zachowanie zmiany biegów jest znormalizowane? Miałem wrażenie, że przesunięcie w prawo na ujemne wartości int jest zdefiniowane w implementacji.
Kerrek SB

1
Podczas gdy być może powinieneś wspomnieć, że kod, który opiera się na jakimkolwiek konkretnym zachowaniu dla liczb ujemnych z przesunięciem w prawo, powinien udokumentować ten wymóg, korzyść z przesunięcia w prawo jest ogromna w przypadkach, gdy naturalnie daje odpowiednią wartość, a operator podziału generuje kod do zmarnowania czas obliczania niepożądanej wartości, którą kod użytkownika musiałby wtedy marnować dodatkowy czas na dostosowanie, aby uzyskać to, co przesunięcie dałoby w pierwszej kolejności. Właściwie, gdybym miał moje druty, kompilatory miałyby opcję skrzeczenia przy próbach wykonania podpisanego podziału, ponieważ ...
supercat,

1
... kod, który wie, że argumenty są dodatnie, może poprawić optymalizację, jeśli rzutuje na niepodpisany przed podziałem (ewentualnie rzutowanie z powrotem do podpisanego później), a kod, który wie, że argumenty mogą być ujemne, powinien w ogóle jawnie traktować tę sprawę (w takim przypadku równie dobrze można założyć, że są pozytywne).
supercat

0

Test Pythona przeprowadzający to samo pomnożenie 100 milionów razy w stosunku do tych samych liczb losowych.

>>> from timeit import timeit
>>> setup_str = 'import scipy; from scipy import random; scipy.random.seed(0)'
>>> N = 10*1000*1000
>>> timeit('x=random.randint(65536);', setup=setup_str, number=N)
1.894096851348877 # Time from generating the random #s and no opperati

>>> timeit('x=random.randint(65536); x*2', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); x << 1', setup=setup_str, number=N)
2.2616429328918457

>>> timeit('x=random.randint(65536); x*10', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); (x << 3) + (x<<1)', setup=setup_str, number=N)
2.9485139846801758

>>> timeit('x=random.randint(65536); x // 2', setup=setup_str, number=N)
2.490908145904541
>>> timeit('x=random.randint(65536); x / 2', setup=setup_str, number=N)
2.4757170677185059
>>> timeit('x=random.randint(65536); x >> 1', setup=setup_str, number=N)
2.2316000461578369

Tak więc, dokonując zmiany zamiast mnożenia / dzielenia przez potęgę dwóch w pythonie, istnieje niewielka poprawa (~ 10% dla podziału; ~ 1% dla mnożenia). Jeśli nie ma potęgi dwóch, prawdopodobnie nastąpi znaczne spowolnienie.

Znowu te #s zmienią się w zależności od twojego procesora, twojego kompilatora (lub interpretera - zrobiłem to w pythonie dla uproszczenia).

Jak w przypadku wszystkich innych, nie optymalizuj przedwcześnie. Napisz bardzo czytelny kod, profil, jeśli nie jest wystarczająco szybki, a następnie spróbuj zoptymalizować wolne części. Pamiętaj, że twój kompilator jest znacznie lepszy w optymalizacji niż ty.


0

Istnieją optymalizacje, których kompilator nie może wykonać, ponieważ działają one tylko dla ograniczonego zestawu danych wejściowych.

Poniżej znajduje się przykładowy kod c ++, który może wykonać szybszy podział, wykonując 64-bitowe „Mnożenie przez odwrotność”. Zarówno licznik, jak i mianownik muszą znajdować się poniżej pewnego progu. Zauważ, że musi być skompilowany, aby użyć instrukcji 64-bitowych, aby był w rzeczywistości szybszy niż normalne dzielenie.

#include <stdio.h>
#include <chrono>

static const unsigned s_bc = 32;
static const unsigned long long s_p = 1ULL << s_bc;
static const unsigned long long s_hp = s_p / 2;

static unsigned long long s_f;
static unsigned long long s_fr;

static void fastDivInitialize(const unsigned d)
{
    s_f = s_p / d;
    s_fr = s_f * (s_p - (s_f * d));
}

static unsigned fastDiv(const unsigned n)
{
    return (s_f * n + ((s_fr * n + s_hp) >> s_bc)) >> s_bc;
}

static bool fastDivCheck(const unsigned n, const unsigned d)
{
    // 32 to 64 cycles latency on modern cpus
    const unsigned expected = n / d;

    // At least 10 cycles latency on modern cpus
    const unsigned result = fastDiv(n);

    if (result != expected)
    {
        printf("Failed for: %u/%u != %u\n", n, d, expected);
        return false;
    }

    return true;
}

int main()
{
    unsigned result = 0;

    // Make sure to verify it works for your expected set of inputs
    const unsigned MAX_N = 65535;
    const unsigned MAX_D = 40000;

    const double ONE_SECOND_COUNT = 1000000000.0;

    auto t0 = std::chrono::steady_clock::now();
    unsigned count = 0;
    printf("Verifying...\n");
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        fastDivInitialize(d);
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            count += !fastDivCheck(n, d);
        }
    }
    auto t1 = std::chrono::steady_clock::now();
    printf("Errors: %u / %u (%.4fs)\n", count, MAX_D * (MAX_N + 1), (t1 - t0).count() / ONE_SECOND_COUNT);

    t0 = t1;
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        fastDivInitialize(d);
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            result += fastDiv(n);
        }
    }
    t1 = std::chrono::steady_clock::now();
    printf("Fast division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);

    t0 = t1;
    count = 0;
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            result += n / d;
        }
    }
    t1 = std::chrono::steady_clock::now();
    printf("Normal division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);

    getchar();
    return result;
}

0

Myślę, że w jednym przypadku, który chcesz pomnożyć lub podzielić przez potęgę dwóch, nie można pomylić się z użyciem operatorów bitshift, nawet jeśli kompilator konwertuje je na MUL / DIV, ponieważ niektóre procesory mikrokodują (tak naprawdę makro) i tak, więc w tych przypadkach osiągniesz poprawę, szczególnie jeśli przesunięcie jest większe niż 1. Lub bardziej wyraźnie, jeśli CPU nie ma operatorów przesunięcia bitów, i tak będzie to MUL / DIV, ale jeśli CPU ma operatory bitshift, unikamy gałęzi mikrokodu, a to kilka instrukcji mniej.

Piszę teraz trochę kodu, który wymaga wielu operacji podwajania / zmniejszania o połowę, ponieważ działa on na gęstym drzewie binarnym, i jest jeszcze jedna operacja, która, jak podejrzewam, może być bardziej optymalna niż dodatek - lewy (potęga dwóch razy ) zmiana z dodatkiem. Można to zastąpić przesunięciem w lewo i xorem, jeśli przesunięcie jest szersze niż liczba bitów, które chcesz dodać, łatwym przykładem jest (i << 1) ^ 1, co dodaje jeden do podwojonej wartości. Nie dotyczy to oczywiście przesunięcia w prawo (potęga dwóch podziałów), ponieważ tylko przesunięcie w lewo (mały endian) wypełnia lukę zerami.

W moim kodzie te mnożą się / dzielą przez dwa, a moce dwóch operacji są bardzo intensywnie używane, a ponieważ formuły są już dość krótkie, każda instrukcja, którą można wyeliminować, może być znaczącym zyskiem. Jeśli procesor nie obsługuje tych operatorów zmiany bitów, zysk nie nastąpi, ale nie nastąpi utrata.

Ponadto w algorytmach, które piszę, reprezentują one wizualnie ruchy, które występują, więc w tym sensie są bardziej wyraźne. Lewa strona drzewa binarnego jest większa, a prawa jest mniejsza. Ponadto w moim kodzie liczby nieparzyste i parzyste mają szczególne znaczenie, a wszystkie dzieci leworęczne w drzewie są nieparzyste, a wszystkie dzieci praworęczne i korzeń są parzyste. W niektórych przypadkach, których jeszcze nie spotkałem, ale może nawet nie pomyślałem o tym, x & 1 może być bardziej optymalną operacją w porównaniu do x% 2. x i 1 dla liczby parzystej da zero, ale da 1 dla liczby nieparzystej.

Idąc nieco dalej niż zwykła identyfikacja nieparzysta / parzysta, jeśli otrzymam zero dla x i 3, wiem, że 4 jest współczynnikiem naszej liczby, i to samo dla x% 7 dla 8 i tak dalej. Wiem, że te przypadki prawdopodobnie mają ograniczoną użyteczność, ale miło jest wiedzieć, że można uniknąć operacji modułu i zamiast tego użyć operacji logiki bitowej, ponieważ operacje bitowe są prawie zawsze najszybsze i najmniej prawdopodobne, że będą dwuznaczne dla kompilatora.

Właściwie wynajduję pole gęstych drzew podwójnych, więc spodziewam się, że ludzie mogą nie zrozumieć wartości tego komentarza, ponieważ bardzo rzadko ludzie chcą dokonywać faktoryzacji tylko na potęgach dwóch, lub tylko potęgować / dzielić potęgi dwóch.



0

Jeśli porównasz dane wyjściowe dla składni x + x, x * 2 i x << 1 w kompilatorze gcc, uzyskasz ten sam wynik w zestawie x86: https://godbolt.org/z/JLpp0j

        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     eax, DWORD PTR [rbp-4]
        add     eax, eax
        pop     rbp
        ret

Możesz więc uznać gcc za wystarczająco inteligentnego, aby określić własne najlepsze rozwiązanie niezależnie od tego, co wpisałeś.


0

Ja też chciałem sprawdzić, czy uda mi się pokonać Dom. jest to bardziej ogólna bitowa liczba dowolna przez mnożenie dowolnej liczby. utworzone przeze mnie makra są około 25% więcej lub dwa razy wolniejsze niż normalne * mnożenie. jak powiedzieli inni, jeśli jest blisko wielokrotności 2 lub składa się z kilku wielokrotności 2, możesz wygrać. jak X * 23 złożony z (X << 4) + (X << 2) + (X << 1) + X będzie wolniejszy niż X * 65 złożony z (X << 6) + X.

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

#define MULTIPLYINTBYMINUS(X,Y) (-((X >> 30) & 1)&(Y<<30))+(-((X >> 29) & 1)&(Y<<29))+(-((X >> 28) & 1)&(Y<<28))+(-((X >> 27) & 1)&(Y<<27))+(-((X >> 26) & 1)&(Y<<26))+(-((X >> 25) & 1)&(Y<<25))+(-((X >> 24) & 1)&(Y<<24))+(-((X >> 23) & 1)&(Y<<23))+(-((X >> 22) & 1)&(Y<<22))+(-((X >> 21) & 1)&(Y<<21))+(-((X >> 20) & 1)&(Y<<20))+(-((X >> 19) & 1)&(Y<<19))+(-((X >> 18) & 1)&(Y<<18))+(-((X >> 17) & 1)&(Y<<17))+(-((X >> 16) & 1)&(Y<<16))+(-((X >> 15) & 1)&(Y<<15))+(-((X >> 14) & 1)&(Y<<14))+(-((X >> 13) & 1)&(Y<<13))+(-((X >> 12) & 1)&(Y<<12))+(-((X >> 11) & 1)&(Y<<11))+(-((X >> 10) & 1)&(Y<<10))+(-((X >> 9) & 1)&(Y<<9))+(-((X >> 8) & 1)&(Y<<8))+(-((X >> 7) & 1)&(Y<<7))+(-((X >> 6) & 1)&(Y<<6))+(-((X >> 5) & 1)&(Y<<5))+(-((X >> 4) & 1)&(Y<<4))+(-((X >> 3) & 1)&(Y<<3))+(-((X >> 2) & 1)&(Y<<2))+(-((X >> 1) & 1)&(Y<<1))+(-((X >> 0) & 1)&(Y<<0))
#define MULTIPLYINTBYSHIFT(X,Y) (((((X >> 30) & 1)<<31)>>31)&(Y<<30))+(((((X >> 29) & 1)<<31)>>31)&(Y<<29))+(((((X >> 28) & 1)<<31)>>31)&(Y<<28))+(((((X >> 27) & 1)<<31)>>31)&(Y<<27))+(((((X >> 26) & 1)<<31)>>31)&(Y<<26))+(((((X >> 25) & 1)<<31)>>31)&(Y<<25))+(((((X >> 24) & 1)<<31)>>31)&(Y<<24))+(((((X >> 23) & 1)<<31)>>31)&(Y<<23))+(((((X >> 22) & 1)<<31)>>31)&(Y<<22))+(((((X >> 21) & 1)<<31)>>31)&(Y<<21))+(((((X >> 20) & 1)<<31)>>31)&(Y<<20))+(((((X >> 19) & 1)<<31)>>31)&(Y<<19))+(((((X >> 18) & 1)<<31)>>31)&(Y<<18))+(((((X >> 17) & 1)<<31)>>31)&(Y<<17))+(((((X >> 16) & 1)<<31)>>31)&(Y<<16))+(((((X >> 15) & 1)<<31)>>31)&(Y<<15))+(((((X >> 14) & 1)<<31)>>31)&(Y<<14))+(((((X >> 13) & 1)<<31)>>31)&(Y<<13))+(((((X >> 12) & 1)<<31)>>31)&(Y<<12))+(((((X >> 11) & 1)<<31)>>31)&(Y<<11))+(((((X >> 10) & 1)<<31)>>31)&(Y<<10))+(((((X >> 9) & 1)<<31)>>31)&(Y<<9))+(((((X >> 8) & 1)<<31)>>31)&(Y<<8))+(((((X >> 7) & 1)<<31)>>31)&(Y<<7))+(((((X >> 6) & 1)<<31)>>31)&(Y<<6))+(((((X >> 5) & 1)<<31)>>31)&(Y<<5))+(((((X >> 4) & 1)<<31)>>31)&(Y<<4))+(((((X >> 3) & 1)<<31)>>31)&(Y<<3))+(((((X >> 2) & 1)<<31)>>31)&(Y<<2))+(((((X >> 1) & 1)<<31)>>31)&(Y<<1))+(((((X >> 0) & 1)<<31)>>31)&(Y<<0))
int main()
{
    int randomnumber=23;
    int randomnumber2=23;
    int checknum=23;
    clock_t start, diff;
    srand(time(0));
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum=MULTIPLYINTBYMINUS(randomnumber,randomnumber2);
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    int msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("MULTIPLYINTBYMINUS Time %d milliseconds", msec);
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum=MULTIPLYINTBYSHIFT(randomnumber,randomnumber2);
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("MULTIPLYINTBYSHIFT Time %d milliseconds", msec);
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum= randomnumber*randomnumber2;
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("normal * Time %d milliseconds", msec);
    return 0;
}
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.