Wskazówki na temat optymalizacji niskiego poziomu C ++ [zamknięte]

Zakładając, że masz już algorytm najlepszego wyboru, jakie rozwiązania niskiego poziomu możesz zaoferować w celu wyciśnięcia kilku ostatnich kropli słodkiej słodkiej liczby klatek z kodu C ++?

Oczywiste jest, że te wskazówki dotyczą tylko tej krytycznej sekcji kodu, którą już zaznaczyłeś w swoim module profilującym, ale powinny to być niestrukturalne ulepszenia niskiego poziomu. Ziarnałem przykład.

Zoptymalizuj układ danych! (Dotyczy to większej liczby języków niż tylko C ++)

Możesz zajść dość głęboko, dostosowując to specjalnie do swoich danych, procesora, ładnie obsługując wiele rdzeni itp. Ale podstawowa koncepcja jest następująca:

Kiedy przetwarzasz rzeczy w ciasnej pętli, chcesz, aby dane dla każdej iteracji były jak najmniejsze i jak najbliżej siebie w pamięci. Oznacza to, że ideał to tablica lub wektor obiektów (nie wskaźników), które zawierają tylko dane niezbędne do obliczeń.

W ten sposób, gdy CPU pobierze dane do pierwszej iteracji pętli, kolejne kilka iteracji danych zostanie załadowanych do pamięci podręcznej.

Naprawdę procesor jest szybki, a kompilator jest dobry. Tak naprawdę niewiele można zrobić, używając mniejszej liczby szybszych instrukcji. Spójność pamięci podręcznej jest tam, gdzie jest (to przypadkowy artykuł, w którym Iogoglowałem - zawiera dobry przykład uzyskiwania spójności pamięci podręcznej dla algorytmu, który nie tylko przebiega liniowo przez dane).

Bardzo, bardzo niska wskazówka, ale taka, która może się przydać:

Większość kompilatorów obsługuje pewną formę wyraźnych wskazówek warunkowych. GCC ma funkcję o nazwie __builtin_expect, która pozwala poinformować kompilator o prawdopodobnej wartości wyniku. GCC może wykorzystać te dane do optymalizacji warunków warunkowych, aby działały tak szybko, jak to możliwe w oczekiwanym przypadku, z nieco wolniejszym wykonaniem w nieoczekiwanym przypadku.

if(__builtin_expect(entity->extremely_unlikely_flag, 0)) {
  // code that is rarely run
}

Widziałem przyspieszenie o 10-20% przy właściwym użyciu tego.

Pierwszą rzeczą, którą musisz zrozumieć, jest sprzęt, na którym pracujesz. Jak radzi sobie z rozgałęzianiem? Co z buforowaniem? Czy ma zestaw instrukcji SIMD? Z ilu procesorów może korzystać? Czy musi dzielić czas procesora z czymkolwiek innym?

Możesz rozwiązać ten sam problem na bardzo różne sposoby - nawet twój wybór algorytmu powinien zależeć od sprzętu. W niektórych przypadkach O (N) może działać wolniej niż O (NlogN) (w zależności od implementacji).

Jako ogólny przegląd optymalizacji, pierwszą rzeczą, którą chciałbym zrobić, jest przyjrzenie się dokładnie, jakie problemy i jakie dane próbujesz rozwiązać. Następnie zoptymalizuj to. Jeśli chcesz uzyskać ekstremalną wydajność, zapomnij o ogólnych rozwiązaniach - możesz w specjalnej obudowie umieścić wszystko, co nie pasuje do najczęściej używanej skrzynki.

Następnie profil. Profil, profil, profil. Spójrz na wykorzystanie pamięci, spójrz na kary za rozgałęzienie, spójrz na ogólne wywołanie funkcji, spójrz na wykorzystanie potoku. Sprawdź, co spowalnia Twój kod. Prawdopodobnie jest to dostęp do danych (napisałem artykuł zatytułowany „The Latency Elephant” o narzutach związanych z dostępem do danych - google. Nie mogę opublikować tutaj 2 linków, ponieważ nie mam wystarczającej „reputacji”), więc dokładnie to zbadaj i następnie zoptymalizuj układ danych ( fajne, duże, płaskie, jednorodne tablice są niesamowite ) i dostęp do danych (w miarę możliwości pobierz).

Po zminimalizowaniu obciążenia podsystemu pamięci, spróbuj ustalić, czy instrukcje są teraz wąskim gardłem (mam nadzieję, że są), a następnie spójrz na implementacje SIMD Twojego algorytmu - implementacje Structure-of-Arrays (SoA) mogą być bardzo danymi i wydajna pamięć podręczna instrukcji. Jeśli SIMD nie pasuje do twojego problemu, konieczne może być wewnętrzne kodowanie i asembler.

Jeśli nadal potrzebujesz większej prędkości, idź równolegle. Jeśli korzystasz z systemu PS3, to SPU są twoimi przyjaciółmi. Używaj ich, kochaj ich. Jeśli już napisałeś rozwiązanie SIMD, otrzymasz ogromną korzyść, przechodząc do SPU.

A potem profiluj więcej. Test w scenariuszach gry - czy ten kod wciąż stanowi wąskie gardło? Czy możesz zmienić sposób używania tego kodu na wyższym poziomie, aby zminimalizować jego użycie (tak naprawdę powinien to być Twój pierwszy krok)? Czy możesz odłożyć obliczenia na wiele ramek?

Na dowolnej platformie dowiedz się jak najwięcej na temat dostępnego sprzętu i profilerów. Nie zakładaj, że wiesz, co to jest wąskie gardło - znajdź to za pomocą swojego profilera. I upewnij się, że masz heurystykę, aby ustalić, czy rzeczywiście przyspieszyłeś grę.

A następnie profiluj to ponownie.

Pierwszy krok: przemyśl dokładnie swoje dane w stosunku do algorytmów. O (log n) nie zawsze jest szybsze niż O (n). Prosty przykład: tablicę skrótów zawierającą tylko kilka kluczy często lepiej zastępuje się wyszukiwaniem liniowym.

Drugi krok: spójrz na wygenerowany zespół. C ++ wprowadza wiele ukrytych kodów do tabeli. Czasami zakrada się na ciebie bez twojej wiedzy.

Ale zakładając, że to naprawdę czas na pedałowanie do metalu: Profil. Poważnie. Losowe stosowanie „sztuczek wydajnościowych” może być tak samo bolesne, jak i pomocne.

Wtedy wszystko zależy od tego, jakie są twoje wąskie gardła.

brak pamięci podręcznej danych => zoptymalizuj układ danych. Oto dobry punkt wyjścia: http://gamesfromwithin.com/data-oriented-design

brak pamięci podręcznej kodu => Spójrz na wywołania funkcji wirtualnych, nadmierną głębokość stosu wywołań itp. Częstą przyczyną złej wydajności jest błędne przekonanie, że klasy podstawowe muszą być wirtualne.

Inne typowe pochłaniacze wydajności C ++:

• Nadmierny przydział / dezalokacja. Jeśli ma to krytyczne znaczenie dla wydajności, nie należy wywoływać w środowisku wykonawczym. Zawsze.
• Kopiuj konstrukcję. Unikaj, gdziekolwiek możesz. Jeśli może to być stałe odniesienie, uczyń je jednym.

Wszystkie powyższe są natychmiast widoczne, gdy spojrzysz na zestaw, więc patrz wyżej;)

Usuń niepotrzebne gałęzie

Na niektórych platformach i niektórych kompilatorach gałęzie mogą wyrzucić cały potok, więc nawet nieznaczne, jeśli () bloki mogą być drogie.

Architektura PowerPC (PS3 / X360) oferuje zmiennoprzecinkową wybierz polecenie, fsel. Można tego użyć zamiast gałęzi, jeśli bloki są prostymi przypisaniami:

float result = 0;
if (foo > bar) { result = 2.0f; }
else { result = 1.0f; }

Staje się:

float result = fsel(foo-bar, 2.0f, 1.0f);

Gdy pierwszy parametr jest większy lub równy 0, zwracany jest drugi parametr, w przeciwnym razie trzeci.

Koszt utraty gałęzi jest taki, że zarówno blok if {}, jak i blok else {} zostaną wykonane, więc jeśli ktoś jest kosztowną operacją lub dereferencją jest wskaźnik NULL, ta optymalizacja nie jest odpowiednia.

Czasami twój kompilator już wykonał tę pracę, więc najpierw sprawdź swój zestaw.

Oto więcej informacji na temat rozgałęziania i fsel:

http://assemblyrequired.crashworks.org/tag/intrinsics/

Unikaj dostępu do pamięci, a zwłaszcza losowych za wszelką cenę.

To jedna z najważniejszych rzeczy, które należy zoptymalizować w nowoczesnych procesorach. Możesz wykonać całą masę arytmetyki, a nawet wiele źle przewidywanych gałęzi w czasie oczekiwania na dane z pamięci RAM.

Możesz także przeczytać tę zasadę na odwrót: wykonaj jak najwięcej obliczeń między dostępami do pamięci.

Użyj kompilatora wewnętrznego.

Upewnij się, że kompilator generuje najbardziej wydajny zestaw dla niektórych operacji, używając wewnętrznych elementów - konstrukcji, które wyglądają jak wywołania funkcji, które kompilator zamienia w zoptymalizowany zestaw:

Oto odniesienie do Visual Studio , a tutaj do GCC

Usuń niepotrzebne wywołania funkcji wirtualnej

Wysłanie funkcji wirtualnej może być bardzo powolne. W tym artykule dobrze wyjaśniono, dlaczego. Jeśli to możliwe, w przypadku funkcji, które są wywoływane wiele razy na klatkę, należy ich unikać.

Możesz to zrobić na kilka sposobów. Czasami możesz po prostu przepisać klasy tak, aby nie potrzebowały dziedziczenia - być może okazuje się, że MachineGun jest jedyną podklasą broni i możesz je połączyć.

Za pomocą szablonów można zastąpić polimorfizm w czasie wykonywania polimorfizmem w czasie kompilacji. Działa to tylko wtedy, gdy znasz podtyp twoich obiektów w czasie wykonywania i może być poważnym przepisem.

Moja podstawowa zasada brzmi: nie rób niczego, co nie jest konieczne .

Jeśli stwierdzisz, że dana funkcja stanowi wąskie gardło, możesz ją zoptymalizować - lub możesz spróbować uchronić ją przed wywołaniem.

Nie musi to oznaczać, że używasz złego algorytmu. Może to oznaczać, że wykonujesz obliczenia na przykład dla każdej ramki, która może być buforowana przez krótki czas (lub całkowicie wstępnie obliczona).

Zawsze próbuję tego podejścia przed wszelkimi próbami naprawdę niskiego poziomu optymalizacji.

Użyj SIMD (przez SSE), jeśli jeszcze tego nie robisz. Gamasutra ma fajny artykuł na ten temat . Możesz pobrać kod źródłowy z prezentowanej biblioteki na końcu artykułu.

Zminimalizuj łańcuchy zależności, aby lepiej wykorzystać linię podziału procesora.

W prostych przypadkach kompilator może to zrobić za Ciebie, jeśli włączysz rozwijanie pętli. Jednak często tego nie robi, zwłaszcza gdy w grę wchodzą zmiennoprzecinkowe, ponieważ zmiana kolejności wyrażeń zmienia wynik.

Przykład:

float *data = ...;
int length = ...;

// Slow version
float total = 0.0f;
int i;
for (i=0; i < length; i++)
{
  total += data[i]
}

// Fast version
float total1, total2, total3, total4;
for (i=0; i < length-3; i += 4)
{
  total1 += data[i];
  total2 += data[i+1];
  total3 += data[i+2];
  total4 += data[i+3];
}
for (; i < length; i++)
{
  total += data[i]
}
total += (total1 + total2) + (total3 + total4);

Nie pomijaj swojego kompilatora - jeśli używasz gcc na Intelu, możesz łatwo uzyskać wzrost wydajności, na przykład przechodząc na kompilator Intel C / C ++. Jeśli celujesz w platformę ARM, sprawdź komercyjny kompilator ARM. Jeśli korzystasz z iPhone'a, Apple po prostu zezwolił na używanie Clanga, zaczynając od zestawu SDK dla iOS 4.0.

Jednym z problemów, który prawdopodobnie napotkasz podczas optymalizacji, szczególnie na x86, jest to, że wiele intuicyjnych rzeczy działa przeciwko tobie na nowoczesnych implementacjach procesora. Niestety dla większości z nas możliwość optymalizacji kompilatora już dawno minęła. Kompilator może planować instrukcje w strumieniu na podstawie własnej wewnętrznej wiedzy o procesorze. Ponadto procesor może również ponownie zaplanować instrukcje w oparciu o własne potrzeby. Nawet jeśli myślisz o optymalnym sposobie aranżacji metody, istnieje szansa, że ​​kompilator lub procesor już to wymyślił i przeprowadził już tę optymalizację.

Moją najlepszą radą byłoby zignorowanie optymalizacji niskiego poziomu i skupienie się na optymalizacji wyższego poziomu. Kompilator i procesor nie mogą zmienić algorytmu z algorytmu O (n ^ 2) na algorytm O (1), bez względu na to, jak są one dobre. Będzie to wymagało od ciebie przyjrzenia się dokładnie temu, co próbujesz zrobić i znalezienia lepszego sposobu na zrobienie tego. Pozwól kompilatorowi i procesorowi martwić się niskim poziomem, a skoncentruj się na poziomach średnich i wysokich.

The Ograniczać słów kluczowych jest potencjalnie przydatne, szczególnie w przypadkach, gdy trzeba manipulować obiekty ze wskaźnikami. Pozwala to kompilatorowi założyć, że wskazany obiekt nie zostanie zmodyfikowany w żaden inny sposób, co z kolei pozwoli mu na bardziej agresywną optymalizację, taką jak przechowywanie części obiektu w rejestrach lub zmiana kolejności odczytu i zapisu w bardziej efektywny sposób.

Jedną dobrą rzeczą w tym słowie kluczowym jest to, że jest to wskazówka, którą możesz zastosować raz i zobaczyć korzyści bez zmiany algorytmu. Złą stroną jest to, że jeśli użyjesz go w niewłaściwym miejscu, możesz zobaczyć uszkodzenie danych. Ale zwykle dość łatwo jest dostrzec, gdzie jest uzasadnione użycie - jest to jeden z niewielu przykładów, w których można racjonalnie oczekiwać, że programiści będą wiedzieć więcej, niż kompilator może bezpiecznie założyć, dlatego właśnie słowo kluczowe zostało wprowadzone.

Technicznie „ograniczenie” nie istnieje w standardowym C ++, ale odpowiedniki specyficzne dla platformy są dostępne dla większości kompilatorów C ++, dlatego warto to rozważyć.

Zobacz także: http://cellperformance.beyond3d.com/articles/2006/05/demystifying-the-restrict-keyword.html

Stwórz wszystko!

Im więcej informacji podasz kompilatorowi na temat danych, tym lepsze są optymalizacje (przynajmniej z mojego doświadczenia).

void foo(Bar * x) {...;}

staje się;

void foo(const Bar * const x) {...;}

Kompilator wie teraz, że wskaźnik x nie będzie się zmieniać, a dane, na które wskazuje, również się nie zmienią.

Inną dodatkową zaletą jest to, że możesz zmniejszyć liczbę przypadkowych błędów, powstrzymując siebie (lub innych) przed modyfikowaniem rzeczy, których nie powinni.

Najczęściej najlepszym sposobem na zwiększenie wydajności jest zmiana algorytmu. Im mniej ogólne wdrożenie, tym bliżej metalu.

Zakładając, że zostało to zrobione ....

Jeśli to naprawdę jest naprawdę krytyczny kod, staraj się unikać odczytów pamięci, staraj się unikać obliczania rzeczy, które można wstępnie obliczyć (chociaż nie ma tabel odnośników, ponieważ naruszają regułę nr 1). Dowiedz się, co robi twój algorytm i napisz go w taki sposób, aby kompilator też o tym wiedział. Sprawdź zespół, aby się upewnić.

Unikaj błędów pamięci podręcznej. Przetwarzaj wsadowo, jak możesz. Unikaj funkcji wirtualnych i innych pośrednich.

Ostatecznie zmierz wszystko. Zasady zmieniają się cały czas. To, co kiedyś przyspieszało kod 3 lata temu, teraz go spowalnia. Dobrym przykładem jest „używaj podwójnych funkcji matematycznych zamiast wersji swobodnych”. Nie zdałbym sobie z tego sprawy, gdybym go nie przeczytał.

Zapomniałem - nie posiadaj domyślnych konstruktorów, które zainicjalizują twoje zmienne, a jeśli nalegasz, przynajmniej twórz konstruktory, które tego nie robią. Uważaj na rzeczy, które nie pojawiają się w profilach. Kiedy stracisz jeden niepotrzebny cykl w wierszu kodu, nic nie pojawi się w twoim narzędziu profilującym, ale ogólnie stracisz dużo cykli. Ponownie wiedz, co robi Twój kod. Spraw, aby Twoja podstawowa funkcja była szczupła, a nie niezawodna. Wersje niezawodne można wywoływać w razie potrzeby, ale nie zawsze są potrzebne. Wszechstronność ma swoją cenę - wydajność jest jednym.

Edytowane w celu wyjaśnienia, dlaczego nie ma domyślnej inicjalizacji: Wiele kodów mówi: Vector3 bla; bla = DoSomething ();

Inicjalizacja w konstruktorze to strata czasu. Również w tym przypadku zmarnowany czas jest niewielki (prawdopodobnie wyczyszczenie wektora), jednak jeśli programiści robią to zwykle, sumuje się. Ponadto wiele funkcji tworzy tymczasowe (myśl przeciążone operatory), które są inicjowane do zera i przypisywane natychmiast. Ukryte utracone cykle, które są zbyt małe, aby zobaczyć skok w twoim profilerze, ale krwawią cykle w całej bazie kodu. Ponadto niektórzy ludzie robią znacznie więcej w konstruktorach (co oczywiście jest nie-nie). Widziałem wielomiesięczne zyski z nieużywanej zmiennej, w której konstruktor był trochę ciężki. Gdy tylko konstruktor wywoła skutki uboczne, kompilator nie będzie mógł go zoptymalizować, więc jeśli nigdy nie użyjesz powyższego kodu, wolę albo nieinicjalizujący konstruktor, albo, jak powiedziałem,

Vector3 bla (noInit); bla = doSomething ();

Zmniejsz ocenę ekspresji boolowskiej

Ten jest naprawdę desperacki, ponieważ stanowi bardzo subtelną, ale niebezpieczną zmianę w kodzie. Jednak jeśli masz warunek, który jest oceniany nadmiernie wiele razy, możesz zmniejszyć narzut oceny boolowskiej, używając zamiast tego operatorów bitowych. Więc:

if ((foo && bar) || blah) { ... } 

Staje się:

if ((foo & bar) | blah) { ... }

Zamiast tego używamy arytmetyki liczb całkowitych. Jeśli foos i słupki są stałe lub oceniane przed if (), może to być szybsze niż normalna wersja boolowska.

Jako bonus, wersja arytmetyczna ma mniej rozgałęzień niż zwykła wersja boolowska. Który jest kolejnym sposobem optymalizacji .

Dużym minusem jest to, że tracisz leniwą ocenę - cały blok jest oceniany, więc nie możesz tego zrobić foo != NULL & foo->dereference(). Z tego powodu można twierdzić, że jest to trudne do utrzymania, więc kompromis może być zbyt duży.

Miej oko na zużycie stosu

Wszystko, co dodajesz do stosu, to dodatkowe naciśnięcie i konstrukcja, gdy wywoływana jest funkcja. Gdy potrzebna jest duża ilość miejsca na stosie, czasem korzystne może być przydzielenie pamięci roboczej z wyprzedzeniem, a jeśli platforma, na której pracujesz, ma dostępną szybką pamięć RAM - tym lepiej!