Jaka jest różnica w wydajności między liczbami całkowitymi bez znaku i ze znakiem? [Zamknięte]


42

Zdaję sobie sprawę z wydajności osiągniętej podczas mieszania podpisanych int z floatami.

Czy jest gorsze mieszanie nieoznaczonych int z pływakami?

Czy jest jakieś trafienie podczas miksowania podpisanego / niepodpisanego bez pływaków?

Czy różne rozmiary (u32, u16, u8, i32, i16, i8) mają jakikolwiek wpływ na wydajność? Na jakich platformach?


2
Usunąłem tekst / znacznik specyficzny dla PS3, ponieważ jest to dobre pytanie dotyczące dowolnej architektury, a odpowiedź jest prawdziwa dla wszystkich architektur, które oddzielają rejestry liczb całkowitych i zmiennoprzecinkowych, czyli praktycznie wszystkie.

Odpowiedzi:


36

Ogromną karą za mieszanie ints (dowolnego rodzaju) i float jest to, że są one w różnych zestawach rejestrów. Aby przejść z jednego zestawu rejestrów do drugiego, musisz zapisać wartość w pamięci i odczytać ją z powrotem, co powoduje przeciągnięcie się do sklepu .

Przechodzenie między różnymi rozmiarami lub sygnaturami ints utrzymuje wszystko w tym samym zestawie rejestrów, dzięki czemu unikasz dużej kary. Mogą obowiązywać mniejsze kary z powodu rozszerzeń znaków itp., Ale są one znacznie mniejsze niż w sklepie z ładowaniem.


Artykuł, który podłączyłeś, stanowi, że procesor komórek PS3 jest wyjątkiem od tego, ponieważ najwyraźniej wszystko jest przechowywane w tym samym zestawie rejestrów (można je znaleźć w przybliżeniu w środku artykułu lub poszukać „Cell”).
bummzack 31.01.11

4
@bummzack: Dotyczy to tylko SPE, a nie PPE; SPE mają specjalne środowisko zmiennoprzecinkowe, a obsada jest wciąż stosunkowo droga. Ponadto koszty są nadal takie same dla liczb całkowitych ze znakiem i bez znaku.

To dobry artykuł i ważne jest, aby wiedzieć o LHS (i głosuję za to), ale moje pytanie dotyczy kar związanych z podpisywaniem. Wiem, że są małe i prawdopodobnie nieistotne, ale nadal chciałbym zobaczyć kilka prawdziwych liczb lub odniesień na ich temat.
Luis

1
@Luis - Próbowałem znaleźć na ten temat dokumentację publiczną, ale w tej chwili nie mogę jej znaleźć. Jeśli masz dostęp do dokumentacji Xbox360, jest tam dobry dokument autorstwa Bruce'a Dawsona, który obejmuje niektóre z nich (i ogólnie bardzo dobre).
celion

@Luis: Zamieściłem poniżej analizę, ale jeśli cię to zadowoli, proszę dać celionowi odpowiedź - wszystko, co powiedział, jest poprawne, wszystko co zrobiłem, to uruchomić GCC kilka razy.

12

Podejrzewam, że informacje o konsolach Xbox 360 i PS3 będą znajdować się za ścianami tylko dla licencjonowanych programistów, podobnie jak większość szczegółów niskiego poziomu. Możemy jednak zbudować równoważny program x86 i go zdemontować, aby uzyskać ogólny pomysł.

Najpierw zobaczmy, jakie koszty rozszerzenia bez podpisu:

unsigned char x = 1;
unsigned int y = 1;
unsigned int z;
z = x;
z = y;

Odpowiednia część rozkłada się na (za pomocą GCC 4.4.5):

    z = x;
  27:   0f b6 45 ff             movzbl -0x1(%ebp),%eax
  2b:   89 45 f4                mov    %eax,-0xc(%ebp)
    z = y;
  2e:   8b 45 f8                mov    -0x8(%ebp),%eax
  31:   89 45 f4                mov    %eax,-0xc(%ebp)

Więc w zasadzie to samo - w jednym przypadku przenosimy bajt, w drugim przenosimy słowo. Kolejny:

signed char x = 1;
signed int y = 1;
signed int z;
z = x;
z = y;

Zamienia się w:

   z = x;
  11:   0f be 45 ff             movsbl -0x1(%ebp),%eax
  15:   89 45 f4                mov    %eax,-0xc(%ebp)
    z = y;
  18:   8b 45 f8                mov    -0x8(%ebp),%eax
  1b:   89 45 f4                mov    %eax,-0xc(%ebp)

Koszt rozszerzenia znaku jest więc niezależnie od kosztu, movsbla nie movzbl- poziomu podinstrukcji. Zasadniczo jest to niemożliwe do oszacowania na nowoczesnych procesorach ze względu na sposób, w jaki działają nowoczesne procesory. Wszystko inne, od szybkości pamięci do buforowania do tego, co było wcześniej w potoku, zdominuje środowisko uruchomieniowe.

W ciągu ~ 10 minut, które zajęło mi napisanie tych testów, mogłem łatwo znaleźć prawdziwy błąd wydajności, a gdy tylko włączę dowolny poziom optymalizacji kompilatora, kod staje się nierozpoznawalny dla tak prostych zadań.

To nie jest przepełnienie stosu, więc mam nadzieję, że nikt tutaj nie twierdzi, że mikrooptymalizacja nie ma znaczenia. Gry często działają na danych, które są bardzo duże i bardzo liczbowe, więc uważna uwaga na rozgałęzienia, rzutowania, harmonogramowanie, wyrównanie struktury itd. Może dać bardzo krytyczne ulepszenia. Każdy, kto spędził dużo czasu na optymalizacji kodu PPC, prawdopodobnie ma co najmniej jedną horror o sklepach z ładowaniem hitów. Ale w tym przypadku to naprawdę nie ma znaczenia. Rozmiar pamięci typu liczb całkowitych nie wpływa na wydajność, o ile jest wyrównany i mieści się w rejestrze.


2
(CW, ponieważ tak naprawdę jest to tylko komentarz do odpowiedzi celiona i ponieważ jestem ciekawy, jakie zmiany w kodzie mogą być potrzebne, aby uczynić go bardziej ilustracyjnym.)

Informacje o procesorze PS3 są łatwo i legalnie dostępne, więc dyskusja na temat procesorów związanych z PS3 nie stanowi problemu. Dopóki Sony nie usunęło obsługi OtherOS, każdy mógł trzymać Linuksa na PS3 i go programować. GPU nie działało, ale procesor (w tym SPE) jest w porządku. Nawet bez obsługi OtherOS możesz łatwo pobrać odpowiedni GCC i zobaczyć, jaki jest gen kodu.
JasonD

@Jason: Oflagowałem swój post jako CW, więc jeśli ktoś to zrobi, może podać informacje. Jednak każdy, kto ma dostęp do oficjalnego kompilatora GameOS firmy Sony - który jest naprawdę jedynym, który ma znaczenie - prawdopodobnie nie ma takiej możliwości.

W rzeczywistości podpisana liczba całkowita jest droższa na PPC IIRC. Ma mały hit wydajności, ale jest tam ... również wiele szczegółów PSU PPU / SPU jest tutaj: jheriko-rtw.blogspot.co.uk/2011/07/ps3-ppuspu-docs.html i tutaj: jheriko-rtw.blogspot.co.uk/2011/03/ppc-instruction-set.html . Ciekawe, czym jest ten kompilator GameOS? Czy to jest kompilator GCC czy SNC? iirc inne niż wspomniane już podpisane porównania mają narzut, gdy mówimy o optymalizacji wewnętrznych pętli. Nie mam jednak dostępu do dokumentów opisujących to - a nawet gdybym ...
jheriko

4

Podpisane operacje na liczbach całkowitych mogą być droższe na prawie wszystkich architekturach. Na przykład dzielenie przez stałą jest szybsze, gdy nie jest podpisany, np .:

unsigned foo(unsigned a) { return a / 1024U; }

zostanie zoptymalizowany w celu:

unsigned foo(unsigned a) { return a >> 10; }

Ale...

int foo(int a) { return a / 1024; }

zoptymalizuje, aby:

int foo(int a) {
  return (a + 1023 * (a < 0)) >> 10;
}

lub w systemach, w których rozgałęzienie jest tanie,

int foo(int a) {
  if (a >= 0) return a >> 10;
  else return (a + 1023) >> 10;
}

To samo dotyczy modulo. Dotyczy to również non-potęgi-2 (ale przykład jest bardziej złożony). Jeśli w Twojej architekturze nie ma podziału sprzętowego (np. Większość ARM), niepodpisane podziały nie-stałych są również szybsze.

Mówienie kompilatorowi, że liczby ujemne nie mogą dać rezultatu, pomoże zoptymalizować wyrażenia, zwłaszcza te używane do zakończenia pętli i innych warunków warunkowych.

Jeśli chodzi o int różnej wielkości, tak, jest to niewielki wpływ, ale trzeba by to wyważyć w porównaniu z przenoszeniem mniejszej ilości pamięci. W dzisiejszych czasach zapewne zyskujesz więcej, uzyskując dostęp do mniejszej ilości pamięci niż tracisz dzięki zwiększeniu rozmiaru. W tym momencie jesteś bardzo zainteresowany mikrooptymalizacją.


Zredagowałem twój zoptymalizowany kod, aby lepiej odzwierciedlał to, co GCC faktycznie generuje, nawet na -O0. Posiadanie gałęzi było mylące, gdy test + lea pozwala ci to robić bez rozgałęzień.

2
Może na x86. Na ARMv7 jest po prostu warunkowo wykonywany.
John Ripley

3

Operacje z int podpisanymi lub niepodpisanymi mają taki sam koszt na obecnych procesorach (x86_64, x86, powerpc, uzbrojenie). W procesorze 32-bitowym u32, u16, u8 s32, s16, s8 powinny być takie same. Możesz mieć karę ze złym wyrównaniem.

Ale konwersja int na float lub float na int jest kosztowną operacją. Możesz łatwo znaleźć zoptymalizowane wdrożenie (SSE2, Neon ...).

Najważniejszym punktem jest prawdopodobnie dostęp do pamięci. Jeśli Twoje dane nie mieszczą się w pamięci podręcznej L1 / L2, stracisz więcej cyklu niż konwersji.


2

Jon Purdy mówi powyżej (nie mogę komentować), że niepodpisany może być wolniejszy, ponieważ nie może się przepełnić. Nie zgadzam się, arytmetyka bez znaku jest prostym modulo arytmetycznym moular 2 do liczby bitów w słowie. Zasadniczo podpisane operacje mogą ulec przepełnieniu, ale zwykle są wyłączone.

Czasami możesz zrobić sprytne (ale niezbyt czytelne) rzeczy, takie jak spakowanie dwóch lub więcej pozycji danych w int i uzyskanie wielu operacji na instrukcję (arytmetyka kieszeni). Ale musisz zrozumieć, co robisz. Oczywiście MMX pozwala ci to robić naturalnie. Ale czasem użycie największego rozmiaru słowa obsługiwanego przez sprzęt i ręczne pakowanie danych zapewnia najszybszą implementację.

Uważaj na wyrównanie danych. W większości wdrożeń sprzętowych niezrównane obciążenia i magazyny są wolniejsze. Naturalne wyrównanie oznacza, że ​​dla powiedzmy słowa 4-bajtowego adres jest wielokrotnością czterech, a adresy ośmiu bajtów powinny być wielokrotnościami ośmiu bajtów. Przenosi to na SSE (128 bitów sprzyja wyrównaniu 16 bajtów). AVX wkrótce rozszerzy te rozmiary rejestrów „wektorowych” do 256 bitów, a następnie 512 bitów. A wyrównane ładunki / sklepy będą szybsze niż te niewyrównane. Dla maniaków HW, niewyrównana operacja pamięci może obejmować takie rzeczy jak linia cacheline, a nawet granice strony, o które HW musi uważać.


1

Nieco lepiej jest używać podpisanych liczb całkowitych do indeksów pętli, ponieważ podpisane przepełnienie jest niezdefiniowane w C, więc kompilator przyjmie, że takie pętle mają mniej przypadków narożnych. Jest to kontrolowane przez „-fstrict-overflow” gcc (domyślnie włączony) i efekt jest prawdopodobnie trudny do zauważenia bez odczytu danych wyjściowych zestawu.

Poza tym x86 działa lepiej, jeśli nie miksujesz typów, ponieważ może używać operandów pamięci. Jeśli musi konwertować typy (rozszerzenia znakowe lub zerowe), oznacza to jawne obciążenie i użycie rejestru.

Trzymaj się int dla zmiennych lokalnych, a większość z nich nastąpi domyślnie.


0

Jak wskazuje celion, narzut związany z konwersją między liczbami całkowitymi i zmiennoprzecinkowymi ma w dużej mierze związek z kopiowaniem i konwersją wartości między rejestrami. Jedyny narzut związany z niepodpisanymi intami sam w sobie wynika z ich gwarantowanego zachowania, które wymaga pewnej ilości kontroli przepełnienia w skompilowanym kodzie.

Zasadniczo nie ma narzutu podczas konwersji liczb całkowitych ze znakiem i bez znaku. Dostęp do różnych rozmiarów liczb całkowitych może (nieskończenie mały) być szybszy lub wolniejszy w zależności od platformy. Ogólnie mówiąc, liczba całkowita najbliższa wielkości słowa platformy będzie najszybsza , ale ogólna różnica w wydajności zależy od wielu innych czynników, w szczególności wielkości pamięci podręcznej: jeśli użyjesz, uint64_tgdy wszystko, czego potrzebujesz uint32_t, może ponieważ mniej danych będzie od razu mieściło się w pamięci podręcznej, co może wiązać się z pewnym obciążeniem.

Jednak myślenie o tym jest trochę przesadne. Jeśli używasz typów odpowiednich dla danych, wszystko powinno działać idealnie dobrze, a ilość mocy, jaką można uzyskać, wybierając typy oparte na architekturze, jest i tak nieistotna.


Do jakiego sprawdzania przelewu chodzi? O ile nie masz na myśli poziomu niższego niż asembler, kod dodawania dwóch liczb całkowitych jest identyczny w większości systemów i nie jest tak naprawdę dłuższy w tych kilku, które używają np. Wielkości znaku. Po prostu inny.

@JoeWreschnig: Cholera. Wydaje mi się, że nie mogę go znaleźć, ale wiem, że widziałem przykłady różnych danych wyjściowych asemblera uwzględniających określone zachowanie zawijania, przynajmniej na niektórych platformach. Jedyny powiązany post, jaki udało mi się znaleźć: stackoverflow.com/questions/4712315/...
Jon Purdy

Różne dane wyjściowe asemblera dla różnych zachowań zawijanych polegają na tym, że kompilator może dokonać optymalizacji w podpisanym przypadku, że np. Jeśli b> 0 to a + b> a, ponieważ podpisane przepełnienie jest niezdefiniowane (a zatem nie można na nim polegać). To naprawdę zupełnie inna sytuacja.
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.