Co jest szybsze: x << 1 czy x << 10?

Nie chcę niczego optymalizować, przysięgam, chcę tylko zadać to pytanie z ciekawości. Wiem, że na większości sprzętu jest komenda montaż bitowego przesunięcia (np shl, shr), co stanowi jedno polecenie. Ale czy ma znaczenie (w nanosekundach lub taktowaniu procesora), ile bitów przesuniesz. Innymi słowy, czy którekolwiek z poniższych jest szybsze na dowolnym procesorze?

x << 1;

i

x << 10;

I proszę, nie nienawidź mnie za to pytanie. :)

Potencjalnie zależy od procesora.

Jednak wszystkie nowoczesne procesory (x86, ARM) używają „beczki shifter” - modułu sprzętowego zaprojektowanego specjalnie do wykonywania dowolnych przesunięć w stałym czasie.

Więc najważniejsze jest ... nie. Bez różnicy.

Niektóre procesory wbudowane mają tylko instrukcję „shift-by-one”. Na takich procesorach kompilator zmieniłby się x << 3w ((x << 1) << 1) << 1.

Myślę, że Motorola MC68HCxx była jedną z bardziej popularnych rodzin z tym ograniczeniem. Na szczęście takie architektury są obecnie dość rzadkie, większość zawiera teraz beczkowaty przerzutnik ze zmiennym rozmiarem przesunięcia.

Intel 8051, który ma wiele nowoczesnych pochodnych, również nie może przesuwać dowolnej liczby bitów.

Jest na to wiele przypadków.

1. Wiele szybkich MPU ma przesuwnik beczkowy, podobny do multipleksera obwód elektroniczny, który wykonuje dowolne przesunięcie w stałym czasie.

2. Jeśli MPU ma tylko 1 bit przesunięcie, x << 10byłoby normalnie wolniejsze, jak zwykle odbywa się to przez 10 zmian lub kopiowanie bajtów z 2 zmianami.

3. Ale jest znany powszechny przypadek, w którym x << 10byłby jeszcze szybszy niż x << 1. Jeśli x jest 16-bitowe, tylko niższe 6 bitów jest ostrożne (wszystkie inne zostaną przesunięte), więc MPU musi załadować tylko mniejszy bajt, a zatem wykonać tylko jeden cykl dostępu do pamięci 8-bitowej, podczas gdy x << 10potrzebne są dwa cykle dostępu. Jeśli cykl dostępu jest wolniejszy niż shift (i wyczyści niższy bajt), x << 10będzie szybszy. Może to dotyczyć mikrokontrolerów z szybką wbudowaną pamięcią ROM programu podczas uzyskiwania dostępu do wolnej zewnętrznej pamięci RAM.

4. Oprócz przypadku 3, kompilator może dbać o liczbę znaczących bitów x << 10i optymalizować dalsze operacje do mniejszych szerokości, takich jak zamiana mnożenia 16x16 na 16x8 (ponieważ mniejszy bajt jest zawsze zerowy).

Uwaga, niektóre mikrokontrolery nie mają w ogóle instrukcji shift-left, add x,xzamiast tego używają .

W ARM można to zrobić jako efekt uboczny innej instrukcji. Więc potencjalnie nie ma żadnego opóźnienia dla żadnego z nich.

Oto mój ulubiony procesor , który x<<2zajmuje dwa razy więcej czasu x<<1:)

To zależy zarówno od procesora, jak i kompilatora. Nawet jeśli bazowy procesor ma dowolne przesunięcie bitów z przesuwnikiem baryłkowym, stanie się to tylko wtedy, gdy kompilator skorzysta z tego zasobu.

Należy pamiętać, że przesuwanie czegokolwiek poza szerokość w bitach danych jest „niezdefiniowanym zachowaniem” w C i C ++. Przesunięcie w prawo podpisanych danych jest również „definicją implementacji”. Zamiast zbytniego przejmowania się szybkością, obawiaj się, że otrzymujesz tę samą odpowiedź w różnych implementacjach.

Cytując z ANSI C sekcja 3.3.7:

3.3.7 Operatory z przesunięciem bitowym

Składnia

      shift-expression:
              additive-expression
              shift-expression <<  additive-expression
              shift-expression >>  additive-expression

Ograniczenia

Każdy z operandów powinien mieć typ całkowity.

Semantyka

Integralne promocje są wykonywane na każdym z operandów. Typ wyniku to promowany lewy operand. Jeśli wartość prawego operandu jest ujemna lub jest większa lub równa szerokości w bitach promowanego lewego operandu, zachowanie jest niezdefiniowane.

Wynikiem E1 << E2 są pozycje bitów E2 przesunięte w lewo; puste bity są wypełniane zerami. Jeśli E1 ma typ bez znaku, wartość wyniku jest pomnożona przez E1 przez ilość, 2 podniesiona do potęgi E2, zredukowana modulo ULONG_MAX + 1, jeśli E1 ma typ unsigned long, w przeciwnym razie UINT_MAX + 1. (Stałe ULONG_MAX i UINT_MAX są zdefiniowane w nagłówku.)

Wynikiem E1 >> E2 są pozycje bitów E2 przesunięte w prawo. Jeśli E1 ma typ bez znaku lub jeśli E1 ma typ ze znakiem i wartość nieujemną, wartość wyniku jest integralną częścią ilorazu E1 podzielonego przez wielkość 2 podniesioną do potęgi E2. Jeśli E1 ma typ ze znakiem i wartość ujemną, wynikowa wartość jest zdefiniowana przez implementację.

Więc:

x = y << z;

„<<”: y × 2 ^z ( nieokreślone, jeśli wystąpi przepełnienie);

x = y >> z;

„>>”: zdefiniowane w implementacji dla znaku ze znakiem (najczęściej wynik przesunięcia arytmetycznego: y / 2 ^z ).

Można sobie wyobrazić, że na 8-bitowym procesorze x<<1może być znacznie wolniejszy niż w x<<10przypadku wartości 16-bitowej.

Na przykład rozsądnym tłumaczeniem x<<1może być:

byte1 = (byte1 << 1) | (byte2 >> 7)
byte2 = (byte2 << 1)

podczas gdy x<<10byłoby prostsze:

byte1 = (byte2 << 2)
byte2 = 0

Zwróć uwagę, jak x<<1przesuwa się częściej, a nawet dalej niż x<<10. Ponadto wynik x<<10nie zależy od zawartości bajtu1. Mogłoby to dodatkowo przyspieszyć operację.

Na niektórych generacjach procesorów Intela (P2 czy P3? Ale nie AMD, jeśli dobrze pamiętam) operacje przesunięcia bitów są absurdalnie wolne. Bitshift o 1 bit powinien zawsze być szybki, ponieważ może po prostu użyć dodawania. Kolejną kwestią do rozważenia jest to, czy przesunięcia bitów o stałą liczbę bitów są szybsze niż przesunięcia o zmiennej długości. Nawet jeśli opkody mają tę samą prędkość, na x86 niestały prawy operand przesunięcia bitowego musi zajmować rejestr CL, co nakłada dodatkowe ograniczenia na alokację rejestrów i może również spowolnić program w ten sposób.

Jak zawsze, zależy to od kontekstu otaczającego kodu : np. Czy używasz x<<1jako indeksu tablicy? Lub dodać to do czegoś innego? W obu przypadkach małe liczby przesunięć (1 lub 2) mogą często zoptymalizować nawet bardziej, niż gdyby kompilator musiał po prostu przesunąć. Nie wspominając już o kompromisie między przepustowością a opóźnieniami a wąskimi gardłami front-endu. Wykonanie maleńkiego fragmentu nie jest jednowymiarowe.

Instrukcje zmiany sprzętu nie są jedyną opcją kompilatora podczas kompilacji x<<1, ale inne odpowiedzi w większości zakładają to.

x << 1jest dokładnie odpowiednikiemx+x for unsigned i dla liczb całkowitych z dopełnieniem ze znakiem uzupełniającym. Kompilatory zawsze wiedzą, na jaki sprzęt są przeznaczone, podczas kompilacji, więc mogą wykorzystać takie sztuczki.

Na Intel Haswell , addma przepustowość 4 na zegar, ale shlz natychmiastowym liczyć ma tylko 2 na przepustowość zegara. (Zobacz http://agner.org/optimize/, aby uzyskać tabele instrukcji i inne linki wx86tag wiki). Przesunięcia wektorów SIMD wynoszą 1 na zegar (2 w Skylake), ale sumy całkowitych wektorów SIMD to 2 na zegar (3 w Skylake). Jednak opóźnienie jest takie samo: 1 cykl.

Istnieje również specjalne kodowanie z przesunięciem o jeden, shlgdzie liczba jest niejawna w kodzie operacyjnym. 8086 nie miało natychmiastowych zmian liczenia, tylko o jeden i według clrejestru. Jest to szczególnie istotne w przypadku przesunięć w prawo, ponieważ możesz po prostu dodać zmiany w lewo, chyba że przesuwasz operand pamięci. Ale jeśli wartość będzie potrzebna później, lepiej najpierw załadować do rejestru. Ale w każdym razie, shl eax,1lub add eax,eaxjest o jeden bajt krótszy niż shl eax,10, a rozmiar kodu może bezpośrednio (dekodować / wąskie gardła front-endu) lub pośrednio (chybienia w pamięci podręcznej kodu L1I) wpływać na wydajność.

Mówiąc bardziej ogólnie, małe liczby przesunięć można czasami zoptymalizować do skalowanego indeksu w trybie adresowania na platformie x86. Większość innych powszechnie używanych obecnie architektur to RISC i nie ma trybów adresowania ze skalowanymi indeksami, ale architektura x86 jest na tyle powszechna, że ​​warto o tym wspomnieć. (jajko, jeśli indeksujesz tablicę elementów 4-bajtowych, jest miejsce na zwiększenie współczynnika skalowania o 1 int arr[]; arr[x<<1]).

Konieczność kopiowania + przesunięcia jest powszechna w sytuacjach, w których xnadal potrzebna jest pierwotna wartość . Ale większość instrukcji całkowitych x86 działa w miejscu. (Miejsce docelowe jest jednym ze źródeł instrukcji takich jak addlub shl.) Konwencja wywoływania Systemu V x86-64 przekazuje argumenty do rejestrów, przy czym pierwszy argument wchodzi edii zwraca wartość w eax, więc funkcja, która zwraca, powoduje x<<10również, że kompilator emituje copy + shift kod.

LEAInstrukcja pozwala shift-and-add (o liczbie zmianowym od 0 do 3, ponieważ używa trybu adresowania maszynowy kodowanie). Wynik umieszcza w oddzielnym rejestrze.

gcc i clang optymalizują te funkcje w ten sam sposób, co widać w eksploratorze kompilatora Godbolt :

int shl1(int x) { return x<<1; }
    lea     eax, [rdi+rdi]   # 1 cycle latency, 1 uop
    ret

int shl2(int x) { return x<<2; }
    lea     eax, [4*rdi]    # longer encoding: needs a disp32 of 0 because there's no base register, only scaled-index.
    ret

int times5(int x) { return x * 5; }
    lea     eax, [rdi + 4*rdi]
    ret

int shl10(int x) { return x<<10; }
    mov     eax, edi         # 1 uop, 0 or 1 cycle latency
    shl     eax, 10          # 1 uop, 1 cycle latency
    ret

LEA z 2 komponentami ma opóźnienie 1 cyklu i przepustowość 2 na takt w najnowszych procesorach Intel i AMD. (Rodzina Sandybridge i Bulldozer / Ryzen). W przypadku Intela jest to tylko 1 przepustowość na zegar z opóźnieniem 3c dla lea eax, [rdi + rsi + 123]. (Powiązane: Dlaczego ten kod C ++ jest szybszy niż mój odręczny zestaw do testowania hipotezy Collatza? Omawiamy to szczegółowo).

W każdym razie kopiowanie + przesunięcie o 10 wymaga osobnej movinstrukcji. Może to być zerowe opóźnienie na wielu ostatnich procesorach, ale nadal wymaga przepustowości front-endu i rozmiaru kodu. ( Czy plik MOV x86 naprawdę może być „darmowy”? Dlaczego w ogóle nie mogę tego odtworzyć? )

Również powiązane: Jak pomnożyć rejestr przez 37, używając tylko 2 kolejnych instrukcji leal w x86? .

Kompilator może również przekształcić otaczający kod, więc nie ma rzeczywistego przesunięcia lub jest połączony z innymi operacjami .

Na przykład if(x<<1) { }mógłby użyć anddo sprawdzenia wszystkich bitów oprócz wysokiego bitu. Na x86 użyłbyś testinstrukcji, takiej jak test eax, 0x7fffffff/ jz .falsezamiast shl eax,1 / jz. Ta optymalizacja działa dla dowolnej liczby zmian, a także działa na maszynach, na których zmiany z dużą liczbą są powolne (jak Pentium 4) lub nie istnieją (niektóre mikrokontrolery).

Wiele ISA ma instrukcje dotyczące manipulacji bitami poza zwykłym przesunięciem. np. PowerPC ma wiele instrukcji wyodrębniania / wstawiania pól bitowych. Lub ARM ma przesunięcia argumentów źródłowych jako część dowolnej innej instrukcji. (Tak więc instrukcje przesuwania / obracania są tylko specjalną formą move, używającą przesuniętego źródła).

Pamiętaj, C nie jest językiem asemblera . Zawsze patrz na zoptymalizowane dane wyjściowe kompilatora, gdy dostrajasz kod źródłowy w celu wydajnej kompilacji.