Które kody są szybsze na poziomie procesora? [Zamknięte]

W każdym języku programowania istnieją zestawy kodów polecanych w stosunku do innych. Próbowałem je tutaj wymienić w kolejności prędkości.

1. Bitowe
2. Dodawanie / odejmowanie liczb całkowitych
3. Mnożenie / dzielenie liczb całkowitych
4. Porównanie
5. Kontrola przepływu
6. Dodawanie / odejmowanie pływaka
7. Float Multiplication / Division

Tam, gdzie potrzebujesz kodu o wysokiej wydajności, C ++ można ręcznie zoptymalizować w asemblerze, aby użyć instrukcji SIMD lub bardziej wydajnego przepływu sterowania, typów danych itp. Więc próbuję zrozumieć, czy typ danych (int32 / float32 / float64) lub wykonywanej operacji ( *, +, &) wpływa na wydajność na poziomie centralnej.

1. Czy pojedynczy procesor jest wielokrotnie wolniejszy niż procesor dodatkowy?
2. W teorii MCU dowiadujesz się, że szybkość kodów zależy od liczby cykli procesora potrzebnych do wykonania. Czy to oznacza, że ​​mnożenie zajmuje 4 cykle, a dodawanie zajmuje 2?
3. Dokładnie jakie są charakterystyki prędkości podstawowych kodów matematyki i kontroli przepływu?
4. Jeśli wykonanie dwóch kodów zajmie taką samą liczbę cykli, to oba będą mogły być używane zamiennie bez żadnego zwiększenia / utraty wydajności?
5. Wszelkie inne szczegóły techniczne dotyczące wydajności procesora x86 są mile widziane

Przewodniki optymalizacji Agner Fog są doskonałe. Ma przewodniki, tabele czasów instrukcji i dokumenty na temat mikroarchitektury wszystkich najnowszych projektów procesorów x86 (sięgających wstecz aż do Pentium Intela). Zobacz także niektóre inne zasoby powiązane z /programming//tags/x86/info

Dla zabawy odpowiem na niektóre pytania (liczby z ostatnich procesorów Intel). Wybór operacji nie jest głównym czynnikiem optymalizacji kodu (chyba że można uniknąć podziału).

Czy pojedynczy procesor jest wielokrotnie wolniejszy niż procesor dodatkowy?

Tak (chyba że jest to siła 2). (3-4-krotne opóźnienie, z tylko jedną przepustowością na zegar w przypadku Intela). Nie wychodź jednak z drogi, aby tego uniknąć, ponieważ jest tak szybki, jak 2 lub 3 dodaje.

Dokładnie jakie są charakterystyki prędkości podstawowych kodów matematyki i kontroli przepływu?

Zobacz tabele instrukcji Agner Fog i przewodnik po mikroarchitekturze, jeśli chcesz dokładnie wiedzieć : P. Uważaj na skoki warunkowe. Bezwarunkowe skoki (takie jak wywołania funkcji) mają niewielki narzut, ale niewiele.

Jeśli wykonanie dwóch kodów zajmie taką samą liczbę cykli, to oba będą mogły być używane zamiennie bez żadnego zwiększenia / utraty wydajności?

Nie, mogą konkurować o ten sam port wykonawczy, co coś innego, lub nie. Zależy to od innych łańcuchów zależności, na których procesor może pracować równolegle. (W praktyce zazwyczaj nie podejmuje się żadnej przydatnej decyzji. Czasami pojawia się możliwość użycia przesunięcia wektorowego lub odtwarzania losowego wektorów, które działają na różnych portach procesorów Intel. Ale przesunięcie bajtów w całym rejestrze ( PSLLDQitp.) działa w jednostce losowej.)

Wszelkie inne szczegóły techniczne dotyczące wydajności procesora x86 są mile widziane

Dokumenty mikroarchy Agner Fog opisują potoki procesorów Intel i AMD na tyle szczegółowo, aby dokładnie określić, ile cykli powinna zająć pętla na iterację oraz czy wąskim gardłem jest wysoka przepustowość, łańcuch zależności lub rywalizacja o jeden port wykonawczy. Zobacz niektóre moje odpowiedzi na StackOverflow, takie jak ta lub ta .

Ponadto http://www.realworldtech.com/haswell-cpu/ (i podobne we wcześniejszych projektach) to fajna lektura, jeśli lubisz projektowanie procesorów.

Oto twoja lista posortowana według procesora Haswell na podstawie moich najlepszych gości. Jednak nie jest to naprawdę przydatny sposób myślenia o rzeczach do niczego poza dostrajaniem pętli asm. Efekty predykcji pamięci podręcznej / gałęzi zwykle dominują, więc napisz kod, aby miał dobre wzorce. Liczby są bardzo zmienne ręcznie i starają się uwzględnić wysokie opóźnienia, nawet jeśli przepustowość nie jest problemem, lub generować więcej błędów, które zapychają rurę, aby inne rzeczy działały równolegle. Esp. numery pamięci podręcznej / oddziału są bardzo wymyślne. Opóźnienia mają znaczenie dla zależności przenoszonych przez pętlę, przepustowość ma znaczenie, gdy każda iteracja jest niezależna.

TL: DR te liczby są tworzone na podstawie tego, co wyobrażam sobie dla „typowego” przypadku użycia, w zakresie kompromisów między opóźnieniem, wąskimi gardłami w portach wykonawczych i przepustowością front-endu (lub przeciągnięciami dla takich rzeczy jak brak gałęzi ). Proszę nie używać tych liczb do jakiejkolwiek poważnej analizy perf .

• 0,5 do 1 Bitowe / Dodawanie liczb całkowitych / Odejmowanie /
  przesuwanie i obracanie (liczba stałych kompilacji w czasie) /
  wersje wektorowe wszystkich z nich (1 do 4 na cykl, opóźnienie 1 cyklu)
• 1 wektor min, maks, porównanie-równe, porównanie-większe (aby utworzyć maskę)
• 1,5 losowych wektorów. Haswell i nowsze mają tylko jeden port losowy i wydaje mi się, że często trzeba tasować, jeśli potrzebujesz, więc ważę go nieco wyżej, aby zachęcić do myślenia o używaniu mniejszej liczby losowych. Nie są za darmo, szczególnie. jeśli potrzebujesz maski kontrolnej pshufb z pamięci.
• 1,5 ładowania / przechowywania (trafienie w pamięć podręczną L1. Przepustowość lepsza niż opóźnienie)
• 1.75 Mnożenie liczb całkowitych (opóźnienie 3c / jeden na 1c tput w Intel, 4c lat w AMD i tylko jeden na 2c tput). Małe stałe są jeszcze tańsze przy użyciu LEA i / lub ADD / SUB / shift . Ale oczywiście stałe czasu kompilacji są zawsze dobre i często można je zoptymalizować pod kątem innych rzeczy. (Mnożenie w pętli może być często zmniejszane przez kompilator na siłę tmp += 7zamiast w pętli tmp = i*7)
• 1.75 niektóre przetasowania wektora 256b (dodatkowe opóźnienia w insynach, które mogą przenosić dane między liniami 128b wektora AVX). (Lub od 3 do 7 na Ryzen, gdzie przetasowania na pasie wymagają znacznie więcej ulepszeń)
• 2 fp add / sub (i wektorowe wersje tego samego) (1 lub 2 na przepustowość cyklu, opóźnienie 3 do 5 cykli). Może być powolny, jeśli ograniczysz opóźnienia, np. Sumując tablicę za pomocą tylko 1 sumzmiennej. (Mógłbym to zważyć i fp mul tak niskie jak 1 lub tak wysokie jak 5 w zależności od przypadku użycia).
• 2 wektor fp mul lub FMA. (x * y + z jest tak samo tanie jak mul lub dodatek, jeśli kompilujesz z włączoną obsługą FMA).
• 2 wstawianie / wyodrębnianie rejestrów ogólnego przeznaczenia do elementów wektorowych ( _mm_insert_epi8itp.)
• 2,25 wektor int mul (elementy 16-bitowe lub pmaddubsw robi 8 * 8 -> 16-bit). Tańsze na Skylake, z lepszą przepustowością niż mular skalarny
• 2.25 przesunięcie / obrót według zmiennej liczby (opóźnienie 2c, jeden na przepustowość 2c w przypadku Intela, szybszy w przypadku AMD lub BMI2)
• 2.5 Porównanie bez rozgałęzień ( y = x ? a : b, lub y = x >= 0) ( test / setcclub cmov)
• 3 int-> liczba zmiennoprzecinkowa
• 3 doskonale przewidywane Kontrola przepływu (przewidywana gałąź, połączenie, powrót).
• 4 wektor int mul (elementy 32-bitowe) (2 ups, 10c latency na Haswell)
• 4 dzielenie liczb całkowitych lub %stała czasowa kompilacji (brak potęgi 2).
• 7 wektorowych operacji poziomych (np. PHADDDodawanie wartości w wektorze)
• 11 (wektor) FP Division (opóźnienie 10-13c, jeden na przepustowość 7c lub gorszy). (Może być tani, jeśli jest używany rzadko, ale przepustowość jest od 6 do 40 razy gorsza niż FP FP)
• 13? Kontrola przepływu (słabo przewidywana gałąź, może w 75% przewidywalna)
• Podział 13 int ( tak naprawdę , jest wolniejszy niż podział FP i nie można go wektoryzować). (zauważ, że kompilatory dzielą przez stałą za pomocą mul / shift / add z magiczną stałą , a div / mod przez potęgi 2 jest bardzo tanie).
• 16 (wektor) FP sqrt
• 25? load (trafienie w pamięć podręczną L3). (sklepy z pamięcią podręczną są tańsze niż ładunki).
• 50? FP trig / exp / log. Jeśli potrzebujesz dużo exp / log i nie potrzebujesz pełnej dokładności, możesz wymienić dokładność na szybkość z krótszym wielomianem i / lub tabelą. Możesz także wektoryzować SIMD.
• 50–80? zawsze przewidywany oddział, który kosztuje 15-20 cykli
• 200–400? load / store (brak pamięci podręcznej)
• 3000 ??? czytać stronę z pliku (trafienie pamięci podręcznej dysku systemu operacyjnego) (tworzenie liczb tutaj)
• 20000 ??? strona odczytu dysku (brak pamięci podręcznej dysku systemu operacyjnego, szybki dysk SSD) (całkowicie skompletowany numer)

Zrobiłem to całkowicie na podstawie domysłów . Jeśli coś wygląda nie tak, to dlatego, że myślałem o innym przypadku użycia lub o błędzie edycji.

Względny koszt rzeczy na procesorach AMD będzie podobny, z tym wyjątkiem, że mają szybsze przesuwacze liczb całkowitych, gdy liczba przesunięć jest zmienna. Procesory z rodziny AMD Bulldozer są oczywiście wolniejsze na większości kodów, z różnych powodów. (Ryzen jest całkiem dobry w wielu sprawach).

Pamiętaj, że naprawdę niemożliwe jest sprowadzenie rzeczy do jednowymiarowego kosztu . Oprócz błędów pamięci podręcznej i nieprzewidzianych oddziałów wąskim gardłem w bloku kodu może być opóźnienie, całkowita przepustowość uop (frontend) lub przepustowość określonego portu (port wykonania).

„Wolna” operacja, taka jak podział FP, może być bardzo tania, jeśli otaczający kod utrzymuje procesor zajęty inną pracą . (wektor FP div lub sqrt są po 1 uop, każdy ma po prostu złe opóźnienie i przepustowość. Blokują tylko jednostkę podziału, a nie cały port wykonania, na którym jest włączony. Div liczby całkowitej to kilka uops.) Więc jeśli masz tylko jeden podział FP za każde ~ 20 mul i dodanie, a CPU ma do wykonania inną pracę (np. niezależna iteracja w pętli), wtedy „koszt” div FP może być mniej więcej taki sam jak FP mul. Jest to prawdopodobnie najlepszy przykład czegoś, co ma niską przepustowość, gdy wszystko, co robisz, ale bardzo dobrze miesza się z innym kodem (gdy opóźnienie nie jest czynnikiem), z powodu niskiej całkowitej liczby błędów.

Zauważ, że dzielenie liczb całkowitych nie jest tak przyjazne dla otaczającego kodu: w Haswell jest 9 upops, z jednym na przepustowość 8-11c i opóźnieniem 22-29c. (Podział 64-bitowy jest znacznie wolniejszy, nawet na Skylake.) Tak więc opóźnienia i liczby przepustowości są nieco podobne do dzielenia FP, ale dzielenie FP jest tylko jednym zwiększeniem.

Aby zapoznać się z przykładami analizy krótkiej sekwencji insns pod kątem przepustowości, opóźnień i całkowitych błędów, zobacz niektóre z moich odpowiedzi SO:

• Sekcja „analiza wydajności” w tej odpowiedzi zawiera podsumowanie. Reszta odpowiedzi dotyczy optymalizacji pętli, która robi tosum += x[i] * y[i]przez rozwinięcie wielu akumulatorów wektorowych w celu ukrycia opóźnienia FMA. Jest dość techniczny i niskopoziomowy, ale pokazuje rodzaj wyjścia w języku asemblera, który chcesz uzyskać od kompilatora, i dlaczego ma to znaczenie.
• Dlaczego ten kod C ++ jest szybszy niż mój odręczny zestaw do testowania przypuszczeń Collatz? : ta popularna odpowiedź, którą napisałem, wyjaśnia, jak trzymać kompilator za rękę, aby w miarę możliwości ulepszyć asm. Również niektóre szczegóły optymalizacji asm, które pozwalają pokonać kompilator dla małych funkcji / pętli. IDK, dlaczego ma o wiele więcej głosów pozytywnych niż jakakolwiek inna odpowiedź.
• Jaki jest skuteczny sposób zliczania ustawionych bitów na pozycji lub niżej? : Perfekcyjna analiza sekwencji 6 insyn pod kątem interesującego problemu, w którym pewne trzymanie ręki w źródle C doprowadziło do ulepszenia kodu przez gcc. Niektóre z moich innych odpowiedzi dotyczą jeszcze krótszych sekwencji instrukcji.
• Najszybszy kalkulator wartości bezwzględnej za pomocą SSE
• Problemy z ADC / SBB i INC / DEC w ciasnych pętlach na niektórych procesorach
• Szybki wektoryzowany rsqrt i wzajemność z SSE / AVX w zależności od precyzji
• Sortujesz struktury 64-bitowe za pomocą AVX?
• /programming//search?q=user%3A224132+throughput+latency+cycles

IDK, jeśli inne osoby piszą odpowiedzi SO, w tym tego rodzaju analizy. O wiele łatwiej jest mi znaleźć własną, ponieważ wiem, że często zagłębiam się w ten szczegół i pamiętam, co napisałem.

To zależy od danego procesora, ale w przypadku nowoczesnego procesora lista wygląda mniej więcej tak:

1. Bitowe, dodawanie, odejmowanie, porównywanie, mnożenie
2. Podział
3. Kontrola przepływu (patrz odpowiedź 3)

W zależności od procesora może wystąpić znaczna opłata za pracę z 64-bitowymi typami danych.

Twoje pytania:

1. W ogóle lub wcale nie na nowoczesnym procesorze. Zależy od procesora.
2. Ta informacja jest trochę przestarzała od 20 do 30 lat (szkoła jest do kitu, masz już dowód), nowoczesne procesory obsługują zmienną liczbę instrukcji na zegar, ile zależy od tego, co wymyśli planista.
3. Podział jest nieco wolniejszy niż reszta, przepływ sterowania jest bardzo szybki, jeśli prognoza rozgałęzienia jest prawidłowa, i bardzo wolny, jeśli jest błędny (około 20 cykli, zależy od procesora). W rezultacie duża część kodu jest ograniczona głównie przepływem sterowania. Nie rób iftego, co możesz rozsądnie zrobić z arytmetyką.
4. Nie ma ustalonej liczby cykli, które wykonuje dowolna instrukcja, ale czasami dwie różne instrukcje mogą wykonywać się równo, umieszczając je w innym kontekście, a może nie, uruchamiają je na innym procesorze i prawdopodobnie zobaczysz trzeci wynik.
5. Poza przepływem kontroli drugim dużym marnotrawcą czasu jest brak pamięci podręcznej, za każdym razem, gdy spróbujesz odczytać dane, które nie są w pamięci podręcznej, procesor będzie musiał poczekać, aż zostanie pobrany z pamięci. Zasadniczo powinieneś próbować obsługiwać elementy danych obok siebie, zamiast wybierać dane z dowolnego miejsca.

I na koniec, jeśli tworzysz grę, nie przejmuj się tym zbytnio, lepiej skoncentruj się na tworzeniu dobrej gry niż przerywaniu cykli procesora.

Zrobiłem test operacji na liczbach całkowitych, który zapętlono milion razy na x64_64, doszedłem do krótkiego wniosku, jak poniżej,

dodaj --- 116 mikrosekund

sub ---- 116 mikrosekund

mul ---- 1036 mikrosekund

div ---- 13037 mikrosekund

powyższe dane już zmniejszyły narzut wywołany przez pętlę,

Instrukcje procesorów Intel można pobrać bezpłatnie ze strony internetowej. Są dość duże, ale technicznie mogą odpowiedzieć na twoje pytanie. W szczególności potrzebujesz instrukcji optymalizacji, ale instrukcja ma także czasy i opóźnienia dla większości głównych linii procesora dla instrukcji SIMD, ponieważ różnią się one od układu do układu.

Ogólnie uważam, że pełne gałęzie, a także ściganie za pomocą wskaźników (trawersy list linków, wywoływanie funkcji wirtualnych) są najlepsze w stosunku do perf killerów, ale procesory x86 / x64 są bardzo dobre w obu przypadkach, w porównaniu do innych architektur. Jeśli kiedykolwiek przeniesiesz się na inną platformę, zobaczysz, na ile poważny może być problem, jeśli piszesz kod o wysokiej wydajności.