Prędkości << >> mnożenia i dzielenia

Możesz używać <<do mnożenia i >>dzielenia liczb w pythonie, kiedy je mierzę, stwierdzam, że użycie binarnego przesunięcia jest 10 razy szybsze niż dzielenie lub mnożenie w zwykły sposób.

Dlaczego używa <<i >>jest dużo szybszy niż *i /?

Jakie procesy stoją za sceną *i są /tak powolne?

Przyjrzyjmy się dwóm małym programom C, które zmieniają się nieco i dzielą.

#include <stdlib.h>

int main(int argc, char* argv[]) {
        int i = atoi(argv[0]);
        int b = i << 2;
}

#include <stdlib.h>

int main(int argc, char* argv[]) {
        int i = atoi(argv[0]);
        int d = i / 4;
}

Następnie są one kompilowane, gcc -Saby zobaczyć, jaki będzie rzeczywisty zestaw.

W wersji z przesunięciem bitowym od wezwania atoido powrotu:

    callq   _atoi
    movl    $0, %ecx
    movl    %eax, -20(%rbp)
    movl    -20(%rbp), %eax
    shll    $2, %eax
    movl    %eax, -24(%rbp)
    movl    %ecx, %eax
    addq    $32, %rsp
    popq    %rbp
    ret

Podczas podziału wersji:

    callq   _atoi
    movl    $0, %ecx
    movl    $4, %edx
    movl    %eax, -20(%rbp)
    movl    -20(%rbp), %eax
    movl    %edx, -28(%rbp)         ## 4-byte Spill
    cltd
    movl    -28(%rbp), %r8d         ## 4-byte Reload
    idivl   %r8d
    movl    %eax, -24(%rbp)
    movl    %ecx, %eax
    addq    $32, %rsp
    popq    %rbp
    ret

Wystarczy spojrzeć na to i istnieje kilka innych instrukcji w wersji divide w porównaniu do przesunięcia bitów.

Kluczem jest to, co oni robią?

W wersji z przesunięciem bitów kluczową instrukcją jest shll $2, %eaxprzesunięcie logiczne w lewo - istnieje podział, a wszystko inne przesuwa wartości.

W wersji dzielącej możesz zobaczyć idivl %r8d- ale tuż nad tym jest cltd(zamień długi na podwójny) i pewną dodatkową logikę wokół wycieku i przeładowania. Ta dodatkowa praca, wiedząc, że mamy do czynienia z matematyką, a nie z bitami, jest często konieczna, aby uniknąć różnych błędów, które mogą wystąpić, wykonując tylko matematykę bitową.

Zróbmy szybkie pomnożenie:

#include <stdlib.h>

int main(int argc, char* argv[]) {
    int i = atoi(argv[0]);
    int b = i >> 2;
}

#include <stdlib.h>

int main(int argc, char* argv[]) {
    int i = atoi(argv[0]);
    int d = i * 4;
}

Zamiast przejść przez to wszystko, jest jedna linia inna:

$ diff mult.s bit.s
24c24
> 2 dolary,% eax
---
<sarl 2 $,% eax

Tutaj kompilator był w stanie stwierdzić, że matematyki można dokonać za pomocą przesunięcia, jednak zamiast przesunięcia logicznego dokonuje przesunięcia arytmetycznego. Różnica między nimi byłaby oczywista, gdybyśmy je uruchomili - sarlzachowuje znak. Tak więc, -2 * 4 = -8podczas gdy shllnie.

Spójrzmy na to w szybkim skrypcie perla:

#!/usr/bin/perl

$foo = 4;
print $foo << 2, "\n";
print $foo * 4, "\n";

$foo = -4;
print $foo << 2, "\n";
print $foo * 4, "\n";

Wynik:

16
16
18446744073709551600
-16

Um ... -4 << 2to 18446744073709551600nie jest dokładnie to, czego się prawdopodobnie spodziewasz w przypadku mnożenia i dzielenia. Ma rację, ale nie jest mnożeniem liczb całkowitych.

I dlatego uważaj na przedwczesną optymalizację. Pozwól, aby kompilator zoptymalizował się dla Ciebie - wie, co naprawdę próbujesz zrobić i prawdopodobnie wykona to lepiej, z mniejszą liczbą błędów.

Istniejące odpowiedzi tak naprawdę nie dotyczyły sprzętowej strony rzeczy, więc tutaj jest trochę pod tym kątem. Powszechnie wiadomo, że mnożenie i dzielenie są znacznie wolniejsze niż przesuwanie, ale dzisiejsza historia jest bardziej dopracowana.

Na przykład z pewnością prawdą jest, że mnożenie jest bardziej złożoną operacją do wdrożenia sprzętowego, ale nie zawsze kończy się wolniej . Jak się okazuje, addjest również znacznie bardziej skomplikowany do wdrożenia niż xor(lub ogólnie każda operacja bitowa), ale add(i sub) zwykle otrzymuje wystarczającą liczbę tranzystorów poświęconych ich działaniu, które w końcu są tak samo szybkie jak operatory bitowe. Nie można więc patrzeć na złożoność implementacji sprzętu jako wskazówkę dotyczącą szybkości.

Przyjrzyjmy się zatem szczegółowo przesunięciom w porównaniu z „pełnymi” operatorami, takimi jak mnożenie i przesuwanie.

Przeniesienie

Na prawie całym sprzęcie przesuwanie o stałą wartość (tj. O wartość, którą kompilator może określić w czasie kompilacji) jest szybkie . W szczególności zwykle dzieje się to z opóźnieniem jednego cyklu i przy przepustowości 1 na cykl lub lepszej. Na niektórych urządzeniach (np. Niektóre układy Intel i ARM) pewne przesunięcia o stałą mogą być nawet „wolne”, ponieważ można je wbudować w inną instrukcję ( leaw Intelu specjalne zdolności zmiany pierwszego źródła w ARM).

Przesunięcie o zmienną wartość jest bardziej szarym obszarem. Na starszych urządzeniach było to czasami bardzo wolne, a prędkość zmieniała się z pokolenia na pokolenie. Na przykład w początkowej wersji P4 Intela przesunięcie o zmienną kwotę było notorycznie wolne - wymagało czasu proporcjonalnego do wielkości przesunięcia! Na tej platformie stosowanie mnożenia w celu zastąpienia zmian może być opłacalne (tzn. Świat wywrócił się do góry nogami). W przypadku wcześniejszych układów Intela, a także kolejnych generacji, zmiana o zmienną liczbę nie była tak bolesna.

W obecnych układach Intela przesuwanie o zmienną kwotę nie jest szczególnie szybkie, ale też nie jest straszne. Architektura x86 jest hamowana, jeśli chodzi o zmienne przesunięcia, ponieważ zdefiniowali operację w nietypowy sposób: przesunięcia o wartości 0 nie modyfikują flag warunków, ale wszystkie inne przesunięcia tak. Utrudnia to efektywną zmianę nazwy rejestru flag, ponieważ nie można ustalić, dopóki przesunięcie nie wykona, czy kolejne instrukcje powinny odczytać kody warunków zapisane przez przesunięcie lub niektóre wcześniejsze instrukcje. Co więcej, przesunięcia zapisują tylko do części rejestru flag, co może powodować częściowe zatrzymanie flag.

Wynik jest taki, że w ostatnich architekturach Intela przesunięcie o zmienną kwotę zajmuje trzy „mikrooperacje”, podczas gdy większość innych prostych operacji (dodawanie, bitowe operacje, a nawet mnożenie) zajmuje tylko 1. Takie przesunięcia mogą być wykonywane co najwyżej raz na 2 cykle .

Mnożenie

Trend w nowoczesnym sprzęcie do komputerów stacjonarnych i laptopów sprawia, że ​​mnożenie jest szybkim działaniem. W przypadku najnowszych układów Intel i AMD w rzeczywistości można wydać jedno zwielokrotnienie w każdym cyklu (nazywamy to wzajemnością ). Opóźnienia jednak z mnożeniem 3 cykle. Oznacza to, że otrzymujesz wynik dowolnego mnożenia 3 cykle po jego uruchomieniu, ale możesz rozpocząć nowe mnożenie w każdym cyklu. Która wartość (1 cykl lub 3 cykle) jest ważniejsza, zależy od struktury twojego algorytmu. Jeśli mnożenie jest częścią krytycznego łańcucha zależności, opóźnienie jest ważne. Jeśli nie, wzajemna przepustowość lub inne czynniki mogą być ważniejsze.

Kluczową kwestią jest to, że w nowoczesnych układach laptopów (lub lepszych) mnożenie jest szybką operacją i prawdopodobnie będzie szybsze niż sekwencja instrukcji 3 lub 4, którą wydałby kompilator, aby „uzyskać zaokrąglenie” dla przesunięć o zmniejszonej sile. W przypadku zmiennych przesunięć, w przypadku Intela, zwielokrotnianie byłoby ogólnie preferowane ze względu na wyżej wymienione problemy.

Na mniejszych platformach kompaktowych mnożenie może być jeszcze wolniejsze, ponieważ zbudowanie pełnego i szybkiego 32-bitowego, a szczególnie 64-bitowego mnożnika wymaga dużo tranzystorów i mocy. Jeśli ktoś mógłby podać szczegółowe informacje na temat wydajności zwielokrotniania na ostatnich mobilnych chipach, byłoby to bardzo mile widziane.

Podzielić

Podział jest zarówno bardziej złożoną operacją, pod względem sprzętowym, jak i zwielokrotnieniem, a także jest znacznie mniej powszechny w rzeczywistym kodzie - co oznacza, że ​​prawdopodobnie przydzielono mu mniej zasobów. Trend nowoczesnych żetonów wciąż prowadzi do szybszych dzielników, ale nawet nowoczesne żetony z najwyższej półki potrzebują 10-40 cykli, aby dokonać podziału i są tylko częściowo przetwarzane. Ogólnie podziały 64-bitowe są nawet wolniejsze niż podziały 32-bitowe. W przeciwieństwie do większości innych operacji, podział może zająć zmienną liczbę cykli w zależności od argumentów.

Unikaj podziałów i zastępuj je zmianami (lub pozwól kompilatorowi to zrobić, ale może być konieczne sprawdzenie zestawu), jeśli możesz!

BINARY_LSHIFT i BINARY_RSHIFT są prostszymi procesami algorytmicznymi niż BINARY_MULTIPLY i BINARY_FLOOR_DIVIDE i mogą wymagać mniejszej liczby cykli zegara. To znaczy, jeśli masz dowolną liczbę binarną i potrzebujesz przesunięcia bitów o N, wszystko, co musisz zrobić, to przesunąć cyfry na tyle spacji i zastąpić je zerami. Mnożenie binarne jest na ogół bardziej skomplikowane , chociaż techniki takie jak mnożnik Dadda sprawiają, że jest dość szybki.

To prawda, że ​​kompilator optymalizujący może rozpoznać przypadki, gdy pomnożymy / podzielimy przez potęgę dwóch i zastąpimy je odpowiednim przesunięciem w lewo / w prawo. Patrząc na zdemontowany kod bajtu, python najwyraźniej nie robi tego:

>>> dis.dis(lambda x: x*4)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (4)
              6 BINARY_MULTIPLY     
              7 RETURN_VALUE        

>>> dis.dis(lambda x: x<<2)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (2)
              6 BINARY_LSHIFT       
              7 RETURN_VALUE        


>>> dis.dis(lambda x: x//2)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (2)
              6 BINARY_FLOOR_DIVIDE 
              7 RETURN_VALUE        

>>> dis.dis(lambda x: x>>1)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (1)
              6 BINARY_RSHIFT       
              7 RETURN_VALUE        

Jednak w moim procesorze uważam, że mnożenie i przesunięcie w lewo / w prawo mają podobne czasy, a podział podłogi (przez potęgę dwóch) jest o około 25% wolniejszy:

>>> import timeit

>>> timeit.repeat("z=a + 4", setup="a = 37")
[0.03717184066772461, 0.03291916847229004, 0.03287005424499512]

>>> timeit.repeat("z=a - 4", setup="a = 37")
[0.03534698486328125, 0.03207516670227051, 0.03196907043457031]

>>> timeit.repeat("z=a * 4", setup="a = 37")
[0.04594111442565918, 0.0408930778503418, 0.045324087142944336]

>>> timeit.repeat("z=a // 4", setup="a = 37")
[0.05412912368774414, 0.05091404914855957, 0.04910898208618164]

>>> timeit.repeat("z=a << 2", setup="a = 37")
[0.04751706123352051, 0.04259490966796875, 0.041903018951416016]

>>> timeit.repeat("z=a >> 2", setup="a = 37")
[0.04719185829162598, 0.04201006889343262, 0.042105913162231445]