Czy warto korzystać z funkcji wirtualnych, aby uniknąć rozgałęziania?

Wydaje się, że istnieją przybliżone odpowiedniki instrukcji do zrównania się z kosztem braku funkcji wirtualnych oddziału mają podobny kompromis:

• instrukcja a brak pamięci podręcznej danych
• bariera optymalizacji

Jeśli spojrzysz na coś takiego:

if (x==1) {
   p->do1();
}
else if (x==2) {
   p->do2();
}
else if (x==3) {
   p->do3();
}
...

Możesz mieć tablicę funkcji składowych lub jeśli wiele funkcji zależy od tej samej kategoryzacji lub istnieje bardziej złożona kategoryzacja, użyj funkcji wirtualnych:

p->do()

Ogólnie jednak, jak drogie są funkcje wirtualne w porównaniu z rozgałęzianiem. Trudno jest przetestować na wystarczającej liczbie platform, aby je uogólnić, więc zastanawiałem się, czy ktoś nie miał surowej zasady (cudownie, gdyby było tak proste, jak 4 ifs to punkt przerwania)

Ogólnie funkcje wirtualne są bardziej przejrzyste i pochyliłbym się w ich kierunku. Ale mam kilka bardzo krytycznych sekcji, w których mogę zmienić kod z funkcji wirtualnych na gałęzie. Wolałbym się nad tym zastanowić, zanim to podejmę. (nie jest to trywialna zmiana ani łatwa do przetestowania na wielu platformach)

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).

Obserwacje:

• W wielu przypadkach funkcje wirtualne są szybsze, ponieważ wyszukiwanie vtable jest O(1)operacją, podczas gdy else if()drabina jest O(n)operacją. Jest to jednak prawdą tylko wtedy, gdy rozkład przypadków jest płaski.

• Dla jednego if() ... elsewarunek jest szybszy, ponieważ zapisujesz narzut wywołania funkcji.

• Tak więc, gdy masz płaski rozkład przypadków, musi istnieć punkt progowy. Jedyne pytanie dotyczy tego, gdzie się znajduje.

• Jeśli użyjesz switch()zamiast else if()drabinkowych lub wirtualnych wywołań funkcji, kompilator może wygenerować jeszcze lepszy kod: może zrobić gałąź do lokalizacji, która jest przeglądana z tabeli, ale która nie jest wywołaniem funkcji. Oznacza to, że masz wszystkie właściwości wirtualnego wywołania funkcji bez całego narzutu wywołania funkcji.

• Jeśli jeden jest znacznie częstszy niż reszta, rozpoczęcie if() ... elseod tego przypadku zapewni najlepszą wydajność: Wykonasz jedną gałąź warunkową, która jest poprawnie przewidywana w większości przypadków.

• Twój kompilator nie ma wiedzy o oczekiwanym rozkładzie przypadków i przyjmie rozkład płaski.

Ponieważ kompilator prawdopodobnie ma kilka dobrych heurystyki w miejscu, do kiedy do kodu A switch()jako else if()drabiny lub jako odnośnika tabeli. Chciałbym zaufać jego osądowi, chyba że wiesz, że rozkład spraw jest stronniczy.

Moja rada jest następująca:

• Jeśli jeden z przypadków przewyższa resztę pod względem częstotliwości, użyj posortowanej else if()drabiny.

• W przeciwnym razie użyj switch()instrukcji, chyba że jedna z pozostałych metod znacznie poprawi czytelność kodu. Upewnij się, że nie kupujesz nieistotnego wzrostu wydajności przy znacznie zmniejszonej czytelności.

• Jeśli użyłeś a switch()i nadal nie jesteś zadowolony z wydajności, wykonaj porównanie, ale przygotuj się, aby dowiedzieć się, że switch()była to już najszybsza możliwość.

Czy warto korzystać z funkcji wirtualnych, aby uniknąć rozgałęziania?

Ogólnie tak. Korzyści z konserwacji są znaczące (testowanie w separacji, separacja problemów, poprawiona modułowość i rozszerzalność).

Ogólnie jednak, jak drogie są funkcje wirtualne w porównaniu z rozgałęzianiem. Trudno jest przetestować na wystarczającej liczbie platform, aby je uogólnić, więc zastanawiałem się, czy ktoś miał surową zasadę (cudownie, gdyby to było tak proste, jak 4, jeśli to punkt przerwania)

O ile nie profilujesz kodu i nie wiesz, że wysyłka między gałęziami ( ocena warunków ) zajmuje więcej czasu niż wykonywane obliczenia ( kod w gałęziach ), zoptymalizuj wykonywane obliczenia.

Oznacza to, że prawidłowa odpowiedź na pytanie „jak drogie są funkcje wirtualne w porównaniu do rozgałęziania” jest mierzona i sprawdzana.

Ogólna zasada : jeśli nie ma powyższej sytuacji (dyskryminacja gałęzi droższa niż obliczenia gałęzi), zoptymalizuj tę część kodu do prac konserwacyjnych (użyj funkcji wirtualnych).

Mówisz, że chcesz, aby ta sekcja działała tak szybko, jak to możliwe; Jak szybko to jest? Jakie jest twoje konkretne wymaganie?

Ogólnie funkcje wirtualne są bardziej przejrzyste i pochyliłbym się w ich kierunku. Ale mam kilka bardzo krytycznych sekcji, w których mogę zmienić kod z funkcji wirtualnych na gałęzie. Wolałbym się nad tym zastanowić, zanim to podejmę. (nie jest to trywialna zmiana ani łatwa do przetestowania na wielu platformach)

Następnie użyj funkcji wirtualnych. Pozwoli to nawet zoptymalizować w razie potrzeby platformę i nadal utrzymywać kod klienta w czystości.

Inne odpowiedzi już dostarczają dobrych argumentów teoretycznych. Chciałbym dodać wyniki eksperymentu, który niedawno przeprowadziłem, aby oszacować, czy dobrym pomysłem byłoby zaimplementowanie maszyny wirtualnej (VM) przy użyciu dużego switchnad kodem operacji, czy raczej interpretowanie kodu operacji jako indeksu w tablicę wskaźników funkcji. Chociaż nie jest to dokładnie to samo, co virtualwywołanie funkcji, myślę, że jest dość blisko.

Napisałem skrypt Pythona do losowego generowania kodu C ++ 14 dla maszyny wirtualnej z losowo wybieranym zestawem instrukcji (choć nierównomiernie, gęstsze próbkowanie dolnego zakresu) między 1 a 10000. Wygenerowana maszyna wirtualna zawsze miała 128 rejestrów i nie BARAN. Instrukcje nie mają znaczenia i wszystkie mają następującą formę.

inline void
op0004(machine_state& state) noexcept
{
  const auto c = word_t {0xcf2802e8d0baca1dUL};
  const auto r1 = state.registers[58];
  const auto r2 = state.registers[69];
  const auto r3 = ((r1 + c) | r2);
  state.registers[6] = r3;
}

Skrypt generuje również procedury wysyłki za pomocą switchinstrukcji…

inline int
dispatch(machine_state& state, const opcode_t opcode) noexcept
{
  switch (opcode)
  {
  case 0x0000: op0000(state); return 0;
  case 0x0001: op0001(state); return 0;
  // ...
  case 0x247a: op247a(state); return 0;
  case 0x247b: op247b(state); return 0;
  default:
    return -1;  // invalid opcode
  }
}

… I tablicę wskaźników funkcji.

inline int
dispatch(machine_state& state, const opcode_t opcode) noexcept
{
  typedef void (* func_type)(machine_state&);
  static const func_type table[VM_NUM_INSTRUCTIONS] = {
    op0000,
    op0001,
    // ...
    op247a,
    op247b,
  };
  if (opcode >= VM_NUM_INSTRUCTIONS)
    return -1;  // invalid opcode
  table[opcode](state);
  return 0;
}

Która procedura wysyłki została wygenerowana została losowo wybrana dla każdej wygenerowanej maszyny wirtualnej.

Do celów analizy porównawczej strumień kodów operacyjnych został wygenerowany przez std::random_devicelosowy silnik losowy Mersenne twister ()std::mt19937_64 ).

Kod dla każdego VM opracowano GCC 5.2.0 użyciu -DNDEBUG, -O3i -std=c++14przełączniki. Najpierw został skompilowany przy użyciu danych -fprofile-generateopcji i profilu zebranych w celu symulacji 1000 losowych instrukcji. Kod został następnie ponownie skompilowany z-fprofile-use opcją umożliwiającą optymalizację na podstawie zebranych danych profilu.

VM wykonano następnie (w tym samym procesie) cztery razy dla 50 000 000 cykli i zmierzono czas dla każdego przebiegu. Pierwszy test został odrzucony, aby wyeliminować efekty buforowania na zimno. PRNG nie został ponownie zaszczepiony między seriami, aby nie wykonały tej samej sekwencji instrukcji.

Dzięki tej konfiguracji zebrano 1000 punktów danych dla każdej procedury wysyłania. Dane zebrano na czterordzeniowym procesorze APU AMD A8-6600K z pamięcią podręczną 2048 KiB z 64-bitowym GNU / Linux bez graficznego pulpitu lub innych programów. Poniżej przedstawiono wykres średniego czasu procesora (ze standardowym odchyleniem) na instrukcję dla każdej maszyny wirtualnej.

Na podstawie tych danych mogłem zyskać pewność, że użycie tabeli funkcji jest dobrym pomysłem, z wyjątkiem być może bardzo małej liczby kodów operacyjnych. Nie mam wyjaśnienia wartości odstających odswitch wersji między 500 a 1000 instrukcji.

Cały kod źródłowy testu, a także pełne dane eksperymentalne i wykres w wysokiej rozdzielczości można znaleźć na mojej stronie internetowej .

Oprócz dobrej odpowiedzi cmastera, o której wspominałem, należy pamiętać, że wskaźniki funkcji są generalnie znacznie szybsze niż funkcje wirtualne. Wysyłanie funkcji wirtualnych zazwyczaj obejmuje najpierw podążanie za wskaźnikiem od obiektu do tabeli vt, odpowiednie indeksowanie, a następnie dereferencję wskaźnika funkcji. Ostatni krok jest taki sam, ale początkowo są dodatkowe kroki. Ponadto funkcje wirtualne zawsze traktują to jako argument, wskaźniki funkcji są bardziej elastyczne.

Kolejna rzecz, o której należy pamiętać: jeśli ścieżka krytyczna obejmuje pętlę, pomocne może być posortowanie pętli według miejsca docelowego wysyłki. Oczywiście jest to nlogn, podczas gdy przemierzanie pętli to tylko n, ale jeśli zamierzasz przechodzić wiele razy, może to być tego warte. Sortując według miejsca docelowego wysyłki, upewniasz się, że ten sam kod jest wykonywany wielokrotnie, utrzymując go w icache, minimalizując pomyłki w pamięci podręcznej.

Trzecia strategia, o której należy pamiętać: jeśli zdecydujesz się odejść od funkcji wirtualnych / wskaźników funkcji w kierunku strategii if / switch, możesz również dobrze skorzystać z przejścia z obiektów polimorficznych na coś w rodzaju boost :: variant (który również zapewnia przełącznik skrzynka w formie abstrakcji odwiedzającego). Obiekty polimorficzne muszą być przechowywane przez wskaźnik bazowy, więc twoje dane są wszędzie w buforze. Może to mieć większy wpływ na twoją ścieżkę krytyczną niż koszt wirtualnego wyszukiwania. Wariant jest przechowywany w linii jako związek dyskryminowany; ma rozmiar równy największemu typowi danych (plus mała stała). Jeśli Twoje obiekty nie różnią się zbytnio rozmiarem, jest to świetny sposób na ich obsługę.

W rzeczywistości nie zdziwiłbym się, gdyby poprawa spójności pamięci podręcznej danych miała większy wpływ niż twoje pierwotne pytanie, więc zdecydowanie zastanowiłbym się nad tym.

Czy mogę wyjaśnić, dlaczego uważam, że jest to problem XY ? (Nie jesteś sam, pytając ich.)

Zakładam, że twoim prawdziwym celem jest ogólne zaoszczędzenie czasu, a nie tylko zrozumienie kwestii związanych z brakami pamięci podręcznej i funkcjami wirtualnymi.

Oto przykład prawdziwego strojenia wydajności w prawdziwym oprogramowaniu.

W prawdziwym oprogramowaniu można to zrobić bez względu na to, jak doświadczony jest programista, można to zrobić lepiej. Nie wiadomo, jakie są, dopóki program nie zostanie napisany i nie będzie można dostroić wydajności. Prawie zawsze istnieje więcej niż jeden sposób na przyspieszenie programu. W końcu, mówiąc, że program jest optymalny, mówisz, że w panteonie możliwych programów do rozwiązania twojego problemu, żaden z nich nie zajmuje mniej czasu. Naprawdę?

W przykładzie, z którym się połączyłem, początkowo zajęło 2700 mikrosekund na „zadanie”. Naprawiono szereg sześciu problemów, poruszających się wokół pizzy w kierunku przeciwnym do ruchu wskazówek zegara. Pierwsze przyspieszenie usunęło 33% czasu. Drugi usunął 11%. Ale zauważ, że drugi nie był 11% w chwili, gdy został znaleziony, był 16%, ponieważ pierwszy problem zniknął . Podobnie trzeci problem został powiększony z 7,4% do 13% (prawie dwukrotnie), ponieważ zniknęły pierwsze dwa problemy.

Na koniec ten proces powiększenia pozwolił wyeliminować wszystkie oprócz 3,7 mikrosekundy. To 0,14% oryginalnego czasu lub przyspieszenie 730x.

Usunięcie początkowo dużych problemów daje umiarkowane przyspieszenie, ale torują one drogę do usunięcia późniejszych problemów. Te późniejsze problemy mogły początkowo stanowić nieznaczną część całości, ale po usunięciu wczesnych problemów te małe stają się duże i mogą powodować duże przyspieszenia. (Ważne jest, aby zrozumieć, że aby uzyskać ten wynik, nie można tego przegapić, a ten post pokazuje, jak łatwo mogą być).

Czy ostateczny program był optymalny? Prawdopodobnie nie. Żadne z tych przyspieszeń nie miało nic wspólnego z brakami w pamięci podręcznej. Czy pamięć podręczna nie ma teraz znaczenia? Może.

EDYCJA: Dostaję negatywne opinie od osób prowadzących „wysoce krytyczne sekcje” pytania PO. Nie wiesz, że coś jest „wysoce krytyczne”, dopóki nie dowiesz się, jaki ułamek czasu to stanowi. Jeśli średni koszt wywołania tych metod wynosi 10 lub więcej cykli, z czasem metoda ich wysłania prawdopodobnie nie będzie „krytyczna” w porównaniu z tym, co faktycznie robią. Widzę to w kółko, w którym ludzie traktują „potrzebowanie każdej nanosekundy” jako powód, by być głupim i głupim.