Chciałem wskoczyć tutaj wśród tych już i tak doskonałych odpowiedzi i przyznać, że podjąłem brzydkie podejście polegające na cofnięciu się do wzorca zmieniania kodu polimorficznego na switcheslub if/elsegałęzie ze zmierzonymi zyskami. Ale nie zrobiłem tego hurtowo, tylko dla najbardziej krytycznych ścieżek. Nie musi być tak czarno-biały.
Jako wyłączenie odpowiedzialności pracuję w obszarach takich jak raytracing, w których poprawność nie jest tak trudna do osiągnięcia (a często i tak jest niejasna i przybliżona), podczas gdy prędkość jest często jedną z najbardziej konkurencyjnych cech. Skrócenie czasu renderowania jest często jednym z najczęstszych żądań użytkowników, a my stale drapiemy się po głowach i zastanawiamy się, jak to osiągnąć w przypadku najbardziej krytycznych mierzonych ścieżek.
Refaktoryzacja polimorficzna warunków warunkowych
Po pierwsze, warto zrozumieć, dlaczego polimorfizm może być lepszy z punktu widzenia łatwości konserwacji niż rozgałęzienie warunkowe ( switchlub kilka if/elseinstrukcji). Główną korzyścią jest tutaj rozszerzalność .
Dzięki kodowi polimorficznemu możemy wprowadzić nowy podtyp do naszej bazy kodu, dodać jego instancje do jakiejś polimorficznej struktury danych i sprawić, że cały istniejący kod polimorficzny nadal działa automagicznie bez dalszych modyfikacji. Jeśli masz dużą porcję kodu rozproszonego po dużej bazie kodu, która przypomina: „Jeśli ten typ to„ foo ”, zrób to” , możesz znaleźć się w strasznym obciążeniu aktualizacją 50 różnych sekcji kodu w celu wprowadzenia nowy rodzaj rzeczy i wciąż brakuje kilku.
Korzyści związane z utrzymywaniem polimorfizmu w naturalny sposób zmniejszają się tutaj, jeśli masz tylko kilka, a nawet jedną sekcję bazy kodu, która musi wykonać takie kontrole typu.
Bariera optymalizacji
Sugerowałbym nie patrzeć na to z punktu widzenia rozgałęzień i potoków, i spojrzeć na to bardziej z punktu widzenia projektowania kompilatora barier optymalizacji. Istnieją sposoby na poprawę przewidywania gałęzi, które dotyczą obu przypadków, takie jak sortowanie danych na podstawie podtypu (jeśli pasuje do sekwencji).
Tym, co różni się bardziej między tymi dwiema strategiami, jest ilość informacji z góry optymalizatora. Znane wywołanie funkcji zapewnia znacznie więcej informacji, a wywołanie funkcji pośredniej, które wywołuje nieznaną funkcję w czasie kompilacji, prowadzi do bariery optymalizacji.
Gdy wywoływana funkcja jest znana, kompilatory mogą zniszczyć strukturę i zmiażdżyć ją do drobnych ekranów, wstawiając wywołania, eliminując potencjalne aliasing narzutów, wykonując lepszą pracę przy przydzielaniu instrukcji / rejestrów, prawdopodobnie nawet przestawiając pętle i inne formy gałęzi, generując trudne -kodowane miniaturowe LUT, gdy jest to właściwe (coś, co ostatnio GCC 5.3 zaskoczyło mnie switchstwierdzeniem, używając raczej zakodowanego LUT danych dla wyników niż tabeli skoków).
Niektóre z tych korzyści giną, gdy zaczynamy wprowadzać do miksu niewiadome czasu kompilacji, jak w przypadku pośredniego wywołania funkcji, i tam właśnie rozgałęzienie warunkowe może najprawdopodobniej dać przewagę.
Optymalizacja pamięci
Weźmy przykład gry wideo, która polega na wielokrotnym przetwarzaniu sekwencji stworzeń w ciasnej pętli. W takim przypadku możemy mieć pojemnik polimorficzny taki jak ten:
vector<Creature*> creatures;
Uwaga: dla uproszczenia unikałem unique_ptrtutaj.
... gdzie Creaturejest polimorficzny typ bazy. W tym przypadku jedną z trudności z kontenerami polimorficznymi jest to, że często chcą alokować pamięć dla każdego podtypu osobno / osobno (np. Używając domyślnego rzucania operator newdla każdego pojedynczego stworzenia).
To często będzie stanowić pierwszy priorytet optymalizacji (w razie potrzeby) opartej na pamięci, a nie na rozgałęzieniu. Jedną ze strategii jest zastosowanie stałego alokatora dla każdego podtypu, zachęcanie do ciągłej reprezentacji poprzez przydzielanie w dużych porcjach i łączenie pamięci dla każdego przydzielanego podtypu. Dzięki takiej strategii zdecydowanie może pomóc w sortowaniu tego creatureskontenera według podtypu (a także adresu), ponieważ nie tylko poprawia to przewidywanie gałęzi, ale także poprawia lokalizację odniesienia (umożliwiając dostęp do wielu stworzeń tego samego podtypu z jednej linii pamięci podręcznej przed eksmisją).
Częściowa dewirtualizacja struktur danych i pętli
Powiedzmy, że wykonałeś wszystkie te ruchy i nadal pragniesz większej prędkości. Warto zauważyć, że każdy krok, który podejmujemy tutaj, pogarsza łatwość konserwacji, a my będziemy już na etapie nieco szlifowania metalu ze zmniejszającymi się zwrotami wydajności. Zatem jeśli wejdziemy na to terytorium, musimy być dość znaczni, jeśli chcemy poświęcić łatwość utrzymania w celu uzyskania coraz mniejszych przyrostów wydajności.
Jednak następnym krokiem do wypróbowania (i zawsze z chęcią wycofania się z naszych zmian, jeśli to w ogóle nie pomoże) może być ręczna dewiralizacja.
Wskazówka dotycząca kontroli wersji: o ile nie jesteś o wiele bardziej inteligentny od optymalizacji, może warto w tym momencie utworzyć nowy oddział z chęcią wyrzucenia go, jeśli nasze działania optymalizacyjne nie powiodą się, co może się zdarzyć. Dla mnie to wszystko metodą prób i błędów po tego rodzaju punktach, nawet z profilerem w ręku.
Niemniej jednak nie musimy stosować tego sposobu myślenia hurtowo. Kontynuując nasz przykład, powiedzmy, że ta gra wideo składa się głównie z istot ludzkich. W takim przypadku możemy zdewastować tylko ludzkie stworzenia, wyciągając je i tworząc dla nich oddzielną strukturę danych.
vector<Human> humans; // common case
vector<Creature*> other_creatures; // additional rare-case creatures
Oznacza to, że wszystkie obszary w naszej bazie kodu, które muszą przetwarzać stworzenia, wymagają osobnej pętli ze specjalnymi przypadkami dla istot ludzkich. Eliminuje to jednak dynamiczne koszty wysyłki (a może, bardziej odpowiednio, barierę optymalizacji) dla ludzi, którzy są zdecydowanie najczęstszym typem stworzenia. Jeśli te obszary są duże i możemy sobie na to pozwolić, możemy to zrobić:
vector<Human> humans; // common case
vector<Creature*> other_creatures; // additional rare-case creatures
vector<Creature*> creatures; // contains humans and other creatures
... jeśli możemy sobie na to pozwolić, mniej krytyczne ścieżki mogą pozostać takimi, jakie są, i po prostu przetwarzać abstrakcyjnie wszystkie typy stworzeń. Ścieżki krytyczne mogą być przetwarzane humansw jednej i other_creaturesdrugiej pętli.
Możemy w razie potrzeby rozszerzyć tę strategię i potencjalnie zmniejszyć w ten sposób niektóre korzyści, ale warto zauważyć, jak bardzo ograniczamy łatwość utrzymania w tym procesie. Korzystanie z szablonów funkcji tutaj może pomóc wygenerować kod zarówno dla ludzi, jak i stworzeń bez ręcznego powielania logiki.
Częściowa dewirtualizacja klas
Coś, co zrobiłem lata temu, było naprawdę obrzydliwe i nawet nie jestem pewien, czy to już jest korzystne (było to w erze C ++ 03), było częściową dewiralizacją klasy. W takim przypadku już przechowywaliśmy identyfikator klasy z każdą instancją do innych celów (dostęp za pośrednictwem akcesorium w klasie podstawowej, która nie była wirtualna). Zrobiliśmy coś analogicznego do tego (moja pamięć jest trochę zamglona):
switch (obj->type())
{
case id_common_type:
static_cast<CommonType*>(obj)->non_virtual_do_something();
break;
...
default:
obj->virtual_do_something();
break;
}
... gdzie virtual_do_somethingzaimplementowano wywoływanie wersji innych niż wirtualne w podklasie. Wiem, że rażące jest robienie wyraźnego statycznego obniżenia, aby zdewiralizować wywołanie funkcji. Nie mam pojęcia, jak korzystne jest to teraz, ponieważ od lat nie próbowałem tego typu rzeczy. Po zapoznaniu się z projektowaniem zorientowanym na dane, uznałem, że powyższa strategia dzielenia struktur danych i pętli na gorąco / zimno jest o wiele bardziej użyteczna, otwierając więcej drzwi dla strategii optymalizacji (i znacznie mniej brzydka).
Dewirtualizacja hurtowa
Muszę przyznać, że nigdy tak daleko nie stosowałem sposobu myślenia optymalizacyjnego, więc nie mam pojęcia o korzyściach. Unikałem funkcji pośrednich w foresighcie w przypadkach, w których wiedziałem, że będzie tylko jeden centralny zestaw warunków warunkowych (np. Przetwarzanie zdarzeń z tylko jednym centralnym przetwarzaniem zdarzeń), ale nigdy nie zacząłem z polimorficznym sposobem myślenia i zoptymalizowałem go do końca aż do tutaj.
Teoretycznie bezpośrednimi korzyściami może być potencjalnie mniejszy sposób identyfikacji typu niż wskaźnik wirtualny (np. Pojedynczy bajt, jeśli można się zgodzić z pomysłem, że istnieje 256 unikalnych typów lub mniej), a także całkowite zatarcie tych barier optymalizacji .
W niektórych przypadkach pomocne może być również napisanie łatwiejszego w utrzymaniu kodu (w porównaniu ze zoptymalizowanymi przykładami ręcznej dewitualizacji powyżej), jeśli użyjesz tylko jednej switchinstrukcji centralnej bez konieczności dzielenia struktur danych i pętli na podstawie podtypu lub jeśli istnieje zamówienie -zależność w tych przypadkach, w których rzeczy muszą być przetwarzane w ściśle określonej kolejności (nawet jeśli powoduje to, że rozgałęziamy się w dowolnym miejscu). Dotyczy to przypadków, w których nie ma zbyt wielu miejsc do zrobienia switch.
Zasadniczo nie polecałbym tego, nawet przy nastawieniu krytycznym dla wydajności, chyba że jest to stosunkowo łatwe do utrzymania. „Łatwy w utrzymaniu” opierałby się na dwóch dominujących czynnikach:
- Brak rzeczywistej potrzeby rozszerzenia (np. Wiedząc, że masz dokładnie 8 rodzajów rzeczy do przetworzenia i nigdy więcej).
- Nie ma wielu miejsc w kodzie, które muszą sprawdzić te typy (np. Jedno centralne miejsce).
... jednak w większości przypadków zalecam powyższy scenariusz i przechodzę do bardziej wydajnych rozwiązań poprzez częściową dewializację w razie potrzeby. Daje to znacznie więcej miejsca na oddychanie, aby zrównoważyć potrzeby w zakresie rozszerzalności i konserwacji z wydajnością.
Funkcje wirtualne a wskaźniki funkcji
Na dodatek zauważyłem tutaj, że była dyskusja na temat funkcji wirtualnych vs. wskaźników funkcji. To prawda, że wywołanie funkcji wirtualnych wymaga trochę dodatkowej pracy, ale to nie znaczy, że są wolniejsze. Wbrew intuicji może nawet przyspieszyć.
Jest to sprzeczne z intuicją, ponieważ jesteśmy przyzwyczajeni do mierzenia kosztów pod względem instrukcji bez zwracania uwagi na dynamikę hierarchii pamięci, która ma zwykle znacznie większy wpływ.
Jeśli porównamy classz 20 funkcjami wirtualnymi w porównaniu z funkcją, structktóra przechowuje 20 wskaźników funkcji, i obie są tworzone wielokrotnie, to narzut pamięci każdej classinstancji w tym przypadku 8 bajtów dla wskaźnika wirtualnego na komputerach 64-bitowych, podczas gdy pamięć obciążenie structto 160 bajtów.
Praktyczny koszt może być o wiele bardziej obowiązkowy i nieobowiązkowy brak pamięci podręcznej z tabelą wskaźników funkcji w porównaniu z klasą za pomocą funkcji wirtualnych (i ewentualnie błędów strony przy wystarczająco dużej skali wejściowej). Koszt ten ma tendencję do zmniejszania nieco dodatkowej pracy związanej z indeksowaniem wirtualnego stołu.
Miałem również do czynienia ze starszymi bazami kodu C (starszymi ode mnie), w których obracanie takich structswypełnionych wskaźnikami funkcji i tworzenie wielu instancji faktycznie przyniosło znaczny wzrost wydajności (ponad 100% ulepszeń) poprzez przekształcenie ich w klasy z funkcjami wirtualnymi i po prostu ze względu na znaczne zmniejszenie zużycia pamięci, zwiększoną przyjazność pamięci podręcznej itp.
Z drugiej strony, kiedy porównania stają się bardziej na temat jabłek i jabłek, znalazłem również odwrotny sposób przełożenia z sposobu myślenia funkcji wirtualnej C ++ na sposób myślenia wskaźnika funkcji w stylu C, który jest przydatny w tego typu scenariuszach:
class Functionoid
{
public:
virtual ~Functionoid() {}
virtual void operator()() = 0;
};
... gdzie klasa przechowywała jedną, dość nadrzędną funkcję (lub dwie, jeśli policzymy wirtualny destruktor). W takich przypadkach zdecydowanie może pomóc w ścieżkach krytycznych, aby przekształcić to w to:
void (*func_ptr)(void* instance_data);
... idealnie za bezpiecznym interfejsem do ukrywania niebezpiecznych rzutów do / z void*.
W przypadkach, w których kusi nas użycie klasy z jedną funkcją wirtualną, może ona szybko pomóc w zamian za pomocą wskaźników funkcji. Głównym powodem niekoniecznie jest nawet obniżony koszt wywołania wskaźnika funkcji. Dzieje się tak dlatego, że nie mamy już pokusy, aby przydzielić każdą osobną funkcję funkcjonalną na rozproszonych obszarach sterty, jeśli agregujemy je w trwałą strukturę. Takie podejście może ułatwić uniknięcie narzutów związanych z hałdą i fragmentacją pamięci, jeśli dane instancji są jednorodne, np. I tylko zachowanie się zmienia.
Zdecydowanie są więc przypadki, w których użycie wskaźników funkcji może pomóc, ale często znalazłem to na odwrót, jeśli porównujemy kilka tabel wskaźników funkcji do pojedynczego vtable, który wymaga przechowywania tylko jednego wskaźnika na instancję klasy . Ta tabela często będzie znajdować się w jednej lub kilku liniach pamięci podręcznej L1, a także w ciasnych pętlach.
Wniosek
Tak czy inaczej, to moja mała uwaga na ten temat. Zalecam ostrożność w tych obszarach. Zaufaj pomiarom, a nie instynktowi, a biorąc pod uwagę sposób, w jaki te optymalizacje często pogarszają łatwość konserwacji, posuwaj się tylko tak daleko, jak możesz sobie pozwolić (i rozsądną drogą byłoby pomylenie się po stronie konserwacji).
