Jaki jest koszt wydajności posiadania metody wirtualnej w klasie C ++?

Posiadanie co najmniej jednej metody wirtualnej w klasie C ++ (lub dowolnej z jej klas nadrzędnych) oznacza, że ​​klasa będzie miała wirtualną tabelę, a każda instancja będzie miała wirtualny wskaźnik.

Więc koszt pamięci jest dość jasny. Najważniejszy jest koszt pamięci w instancjach (zwłaszcza jeśli instancje są małe, na przykład jeśli mają zawierać tylko liczbę całkowitą: w tym przypadku posiadanie wirtualnego wskaźnika w każdej instancji może podwoić rozmiar instancji. przestrzeń pamięci wykorzystywana przez wirtualne tabele, wydaje mi się, że jest zwykle pomijalna w porównaniu z miejscem zajmowanym przez rzeczywisty kod metody.

To prowadzi mnie do mojego pytania: czy istnieje wymierny koszt wydajności (tj. Wpływ na szybkość), aby uczynić metodę wirtualną? W tabeli wirtualnej będzie wyszukiwane w czasie wykonywania, przy każdym wywołaniu metody, więc jeśli są bardzo częste wywołania tej metody, a ta metoda jest bardzo krótka, to może wystąpić wymierny spadek wydajności? Myślę, że to zależy od platformy, ale czy ktoś przeprowadził jakieś testy porównawcze?

Pytam, ponieważ natknąłem się na błąd, który był spowodowany tym, że programista zapomniał zdefiniować metodę wirtualną. To nie pierwszy raz, kiedy widzę tego rodzaju błąd. I pomyślałem: dlaczego dodać słowa kluczowego wirtualnych, gdy są potrzebne, a nie usunięcie słowa kluczowego wirtualnych, gdy jesteśmy absolutnie pewni, że to jest nie potrzebne? Jeśli koszt wydajności jest niski, myślę, że po prostu zalecę w moim zespole: po prostu uczyń domyślnie każdą metodę wirtualną, w tym destruktor, w każdej klasie i usuwaj ją tylko wtedy, gdy zajdzie taka potrzeba. Czy to brzmi dla ciebie szalenie?

I zabrakło niektóre czasy na procesorze PowerPC 3GHz na zamówienie. W tej architekturze wywołanie funkcji wirtualnej kosztuje 7 nanosekund dłużej niż bezpośrednie (niewirtualne) wywołanie funkcji.

Nie warto więc martwić się kosztami, chyba że funkcja jest czymś w rodzaju trywialnego akcesorium Get () / Set (), w którym wszystko inne niż inline jest trochę marnotrawstwem. Obciążenie 7 ns w przypadku funkcji, która rozwija się do 0,5 ns, jest poważne; 7ns narzut funkcji, której wykonanie zajmuje 500 ms, jest bez znaczenia.

Duży koszt funkcji wirtualnych nie polega tak naprawdę na wyszukiwaniu wskaźnika funkcji w tabeli vtable (zwykle jest to tylko jeden cykl), ale na przeskok pośredni zwykle nie można przewidzieć rozgałęzienia. Może to spowodować duży bąbelek potoku, ponieważ procesor nie może pobrać żadnych instrukcji, dopóki pośredni skok (wywołanie przez wskaźnik funkcji) nie zostanie wycofany i nie zostanie obliczony nowy wskaźnik instrukcji. Tak więc koszt wywołania funkcji wirtualnej jest znacznie większy, niż mogłoby się wydawać, patrząc na zestaw ... ale wciąż tylko 7 nanosekund.

Edycja: Andrew, Not Sure i inni również podnoszą bardzo dobry punkt widzenia, że ​​wywołanie funkcji wirtualnej może spowodować pominięcie pamięci podręcznej instrukcji: jeśli przeskoczysz do adresu kodowego, którego nie ma w pamięci podręcznej, cały program zatrzymuje się instrukcje są pobierane z pamięci głównej. To zawsze jest znaczące przeciągnięcie: na ksenonie około 650 cykli (według moich testów).

Jednak nie jest to problem specyficzny dla funkcji wirtualnych, ponieważ nawet bezpośrednie wywołanie funkcji spowoduje błąd, jeśli przeskoczysz do instrukcji, których nie ma w pamięci podręcznej. Liczy się to, czy funkcja została uruchomiona wcześniej (co zwiększa prawdopodobieństwo, że będzie znajdować się w pamięci podręcznej) i czy Twoja architektura może przewidywać gałęzie statyczne (nie wirtualne) i pobierać te instrukcje z wyprzedzeniem do pamięci podręcznej. Mój PPC nie, ale być może najnowszy sprzęt Intela tak.

Moje czasy kontrolują wpływ błędów icache na wykonanie (celowo, ponieważ próbowałem osobno zbadać potok procesora), więc dyskontują ten koszt.

Podczas wywoływania funkcji wirtualnej istnieje zdecydowanie wymierny narzut - wywołanie musi korzystać z tabeli vtable, aby rozwiązać adres funkcji dla tego typu obiektu. Dodatkowe instrukcje są najmniejszym z Twoich zmartwień. Vtables nie tylko zapobiega wielu potencjalnym optymalizacjom kompilatora (ponieważ typ jest polimorficzny kompilatora), ale może również powodować odrzucanie I-Cache.

Oczywiście to, czy te kary są znaczące, czy nie, zależy od aplikacji, częstotliwości wykonywania tych ścieżek kodu i wzorców dziedziczenia.

Jednak moim zdaniem posiadanie domyślnie wirtualnego wszystkiego jest ogólnym rozwiązaniem problemu, który można rozwiązać innymi sposobami.

Być może mógłbyś przyjrzeć się, jak klasy są projektowane / dokumentowane / pisane. Generalnie nagłówek klasy powinien jasno określać, które funkcje mogą być przesłonięte przez klasy pochodne i jak są wywoływane. Poproszenie programistów o napisanie tej dokumentacji jest pomocne w upewnieniu się, że są one poprawnie oznaczone jako wirtualne.

Powiedziałbym również, że deklarowanie każdej funkcji jako wirtualnej może prowadzić do większej liczby błędów niż po prostu zapomnienie o oznaczeniu czegoś jako wirtualnego. Jeśli wszystkie funkcje są wirtualne, wszystko można zastąpić klasami podstawowymi - publicznymi, chronionymi, prywatnymi - wszystko staje się uczciwą grą. Podklasy przypadkowo lub celowo mogą wtedy zmienić zachowanie funkcji, które następnie powodują problemy, gdy są używane w podstawowej implementacji.

To zależy. :) (Czy spodziewałeś się czegoś innego?)

Gdy klasa otrzyma funkcję wirtualną, nie może już być typem danych POD (może nim nie być wcześniej, w takim przypadku nie będzie to miało znaczenia), a to uniemożliwia cały szereg optymalizacji.

std :: copy () na zwykłych typach POD może uciekać się do prostej procedury memcpy, ale typy inne niż POD muszą być obsługiwane ostrożniej.

Konstrukcja staje się znacznie wolniejsza, ponieważ vtable musi zostać zainicjowany. W najgorszym przypadku różnica w wydajności między typami danych POD i bez POD może być znacząca.

W najgorszym przypadku możesz zobaczyć 5x wolniejsze wykonanie (ta liczba jest pobierana z projektu uniwersyteckiego, który ostatnio robiłem, aby ponownie zaimplementować kilka standardowych klas bibliotecznych. Konstruowanie naszego kontenera trwało około 5 razy dłużej, gdy tylko typ przechowywanych danych otrzymał vtable)

Oczywiście w większości przypadków jest mało prawdopodobne, aby zauważyłeś jakąkolwiek mierzalną różnicę w wydajności, ma to po prostu wskazać, że w niektórych przypadkach granicznych może to być kosztowne.

Jednak wydajność nie powinna być tutaj najważniejsza. Uczynienie wszystkiego wirtualnym nie jest idealnym rozwiązaniem z innych powodów.

Zezwolenie na przesłonięcie wszystkiego w klasach pochodnych znacznie utrudnia utrzymanie niezmienników klas. W jaki sposób klasa gwarantuje, że pozostanie w spójnym stanie, jeśli którakolwiek z jej metod może zostać w dowolnym momencie przedefiniowana?

Uczynienie wszystkiego wirtualnym może wyeliminować kilka potencjalnych błędów, ale wprowadza też nowe.

Jeśli potrzebujesz funkcjonalności wirtualnej wysyłki, musisz zapłacić cenę. Zaletą C ++ jest to, że możesz użyć bardzo wydajnej implementacji wirtualnego wysyłania dostarczonej przez kompilator, zamiast prawdopodobnie nieefektywnej wersji, którą sam implementujesz.

Jednak ociąganie się z nad głową, jeśli nie potrzebujesz, prawdopodobnie posuwa się za daleko. A większość klas nie jest przeznaczona do dziedziczenia - stworzenie dobrej klasy bazowej wymaga czegoś więcej niż uczynienia jej funkcji wirtualnymi.

Wirtualna wysyłka jest o rząd wielkości wolniejsza niż niektóre alternatywy - nie z powodu pośrednictwa, a raczej zapobiegania inliningowi. Poniżej ilustruję to poprzez zestawienie wirtualnego wysyłania z implementacją osadzającą „numer typu (identyfikujący)” w obiektach i używając instrukcji switch w celu wybrania kodu specyficznego dla typu. Pozwala to całkowicie uniknąć narzutu wywołań funkcji - wystarczy wykonać lokalny skok. Istnieje potencjalny koszt utrzymania, zależności rekompilacji itp. Z powodu wymuszonej lokalizacji (w przełączniku) funkcji specyficznej dla typu.

REALIZACJA

#include <iostream>
#include <vector>

// virtual dispatch model...

struct Base
{
    virtual int f() const { return 1; }
};

struct Derived : Base
{
    virtual int f() const { return 2; }
};

// alternative: member variable encodes runtime type...

struct Type
{
    Type(int type) : type_(type) { }
    int type_;
};

struct A : Type
{
    A() : Type(1) { }
    int f() const { return 1; }
};

struct B : Type
{
    B() : Type(2) { }
    int f() const { return 2; }
};

struct Timer
{
    Timer() { clock_gettime(CLOCK_MONOTONIC, &from); }
    struct timespec from;
    double elapsed() const
    {
        struct timespec to;
        clock_gettime(CLOCK_MONOTONIC, &to);
        return to.tv_sec - from.tv_sec + 1E-9 * (to.tv_nsec - from.tv_nsec);
    }
};

int main(int argc)
{
  for (int j = 0; j < 3; ++j)
  {
    typedef std::vector<Base*> V;
    V v;

    for (int i = 0; i < 1000; ++i)
        v.push_back(i % 2 ? new Base : (Base*)new Derived);

    int total = 0;

    Timer tv;

    for (int i = 0; i < 100000; ++i)
        for (V::const_iterator i = v.begin(); i != v.end(); ++i)
            total += (*i)->f();

    double tve = tv.elapsed();

    std::cout << "virtual dispatch: " << total << ' ' << tve << '\n';

    // ----------------------------

    typedef std::vector<Type*> W;
    W w;

    for (int i = 0; i < 1000; ++i)
        w.push_back(i % 2 ? (Type*)new A : (Type*)new B);

    total = 0;

    Timer tw;

    for (int i = 0; i < 100000; ++i)
        for (W::const_iterator i = w.begin(); i != w.end(); ++i)
        {
            if ((*i)->type_ == 1)
                total += ((A*)(*i))->f();
            else
                total += ((B*)(*i))->f();
        }

    double twe = tw.elapsed();

    std::cout << "switched: " << total << ' ' << twe << '\n';

    // ----------------------------

    total = 0;

    Timer tw2;

    for (int i = 0; i < 100000; ++i)
        for (W::const_iterator i = w.begin(); i != w.end(); ++i)
            total += (*i)->type_;

    double tw2e = tw2.elapsed();

    std::cout << "overheads: " << total << ' ' << tw2e << '\n';
  }
}

WYNIKI WYDAJNOŚCI

W moim systemie Linux:

~/dev  g++ -O2 -o vdt vdt.cc -lrt
~/dev  ./vdt                     
virtual dispatch: 150000000 1.28025
switched: 150000000 0.344314
overhead: 150000000 0.229018
virtual dispatch: 150000000 1.285
switched: 150000000 0.345367
overhead: 150000000 0.231051
virtual dispatch: 150000000 1.28969
switched: 150000000 0.345876
overhead: 150000000 0.230726

Sugeruje to, że podejście z przełączaniem numerów typu inline jest około (1,28 - 0,23) / (0,344 - 0,23) = 9,2 razy szybsze. Oczywiście jest to specyficzne dla dokładnie testowanego systemu / flag kompilatora i wersji itp., Ale ogólnie orientacyjne.

KOMENTARZE RE WIRTUALNEJ WYSYŁKI

Trzeba jednak powiedzieć, że narzuty wywołań funkcji wirtualnych są czymś, co rzadko ma znaczenie, a potem tylko w przypadku często nazywanych trywialnych funkcji (takich jak pobierające i ustawiające). Nawet wtedy możesz być w stanie udostępnić jedną funkcję, aby uzyskać i ustawić wiele rzeczy naraz, minimalizując koszty. Ludzie zbytnio martwią się o wirtualną wysyłkę - wykonaj też profilowanie, zanim znajdziesz niezręczną alternatywę. Głównym problemem z nimi jest to, że wykonują one wywołanie funkcji poza linią, chociaż również delokalizują wykonywany kod, co zmienia wzorce wykorzystania pamięci podręcznej (na lepsze lub (częściej) gorzej).

W większości scenariuszy dodatkowy koszt jest praktycznie zerowy. (przepraszam za kalambur). ejac opublikował już rozsądne miary względne.

Największą rzeczą, z której rezygnujesz, są możliwe optymalizacje dzięki inlining. Mogą być szczególnie dobre, jeśli wywoływana jest funkcja ze stałymi parametrami. Rzadko robi to realną różnicę, ale w kilku przypadkach może być ogromna.

Odnośnie optymalizacji:
ważne jest, aby znać i brać pod uwagę względny koszt konstrukcji Twojego języka. Notacja Big O to tylko połowa sukcesu - jak skaluje się Twoja aplikacja . Druga połowa to stały czynnik przed nim.

Z zasady nie wychodziłbym z siebie, aby unikać funkcji wirtualnych, chyba że istnieją wyraźne i konkretne oznaki, że jest to szyjka butelki. Czysty projekt zawsze jest najważniejszy - ale to tylko jeden interesariusz nie powinien nadmiernie ranić innych.

Przemyślany przykład: pusty wirtualny destruktor w tablicy miliona małych elementów może przedrzeć się przez co najmniej 4 MB danych, niszcząc pamięć podręczną. Jeśli ten destruktor może zostać wstawiony, dane nie zostaną dotknięte.

Pisząc kod biblioteki, takie rozważania nie są przedwczesne. Nigdy nie wiadomo, ile pętli zostanie umieszczonych wokół Twojej funkcji.

Chociaż wszyscy inni mają rację co do wydajności metod wirtualnych itp., Myślę, że prawdziwym problemem jest to, czy zespół wie o definicji słowa kluczowego virtual w C ++.

Rozważmy ten kod, jaki jest wynik?

#include <stdio.h>

class A
{
public:
    void Foo()
    {
        printf("A::Foo()\n");
    }
};

class B : public A
{
public:
    void Foo()
    {
        printf("B::Foo()\n");
    }
};

int main(int argc, char** argv)
{    
    A* a = new A();
    a->Foo();

    B* b = new B();
    b->Foo();

    A* a2 = new B();
    a2->Foo();

    return 0;
}

Nic dziwnego:

A::Foo()
B::Foo()
A::Foo()

Ponieważ nic nie jest wirtualne. Jeśli słowo kluczowe virtual zostanie dodane na początku Foo w obu klasach A i B, otrzymamy to dla wyniku:

A::Foo()
B::Foo()
B::Foo()

Prawie to, czego wszyscy oczekują.

Wspomniałeś teraz, że są błędy, ponieważ ktoś zapomniał dodać wirtualne słowo kluczowe. Rozważ więc ten kod (w którym wirtualne słowo kluczowe jest dodawane do klasy A, ale nie do klasy B). Jaki jest zatem wynik?

#include <stdio.h>

class A
{
public:
    virtual void Foo()
    {
        printf("A::Foo()\n");
    }
};

class B : public A
{
public:
    void Foo()
    {
        printf("B::Foo()\n");
    }
};

int main(int argc, char** argv)
{    
    A* a = new A();
    a->Foo();

    B* b = new B();
    b->Foo();

    A* a2 = new B();
    a2->Foo();

    return 0;
}

Odpowiedź: To samo, co w przypadku dodania wirtualnego słowa kluczowego do B? Powodem jest to, że podpis dla B :: Foo pasuje dokładnie tak, jak A :: Foo () i ponieważ Foo A jest wirtualny, więc jest również B.

Rozważmy teraz przypadek, w którym Foo B jest wirtualne, a A nie. Jaki jest zatem wynik? W tym przypadku wyjście to

A::Foo()
B::Foo()
A::Foo()

Słowo kluczowe wirtualne działa w dół w hierarchii, a nie w górę. Nigdy nie sprawia, że ​​metody klasy bazowej są wirtualne. Po raz pierwszy w hierarchii napotykamy metodę wirtualną, gdy zaczyna się polimorfizm. Nie ma sposobu, aby późniejsze klasy powodowały, że poprzednie klasy miały metody wirtualne.

Nie zapominaj, że metody wirtualne oznaczają, że ta klasa daje przyszłym klasom możliwość nadpisania / zmiany niektórych jej zachowań.

Jeśli więc masz regułę usuwania wirtualnego słowa kluczowego, może to nie przynieść zamierzonego efektu.

Wirtualne słowo kluczowe w C ++ to potężna koncepcja. Powinieneś upewnić się, że każdy członek zespołu naprawdę zna tę koncepcję, aby można ją było wykorzystać zgodnie z projektem.

W zależności od platformy, narzut wirtualnego połączenia może być bardzo niepożądany. Deklarując każdą funkcję jako wirtualną, w zasadzie wywołujesz je wszystkie za pomocą wskaźnika funkcji. Przynajmniej jest to dodatkowa dereferencja, ale na niektórych platformach PPC używa do tego mikrokodowanych lub w inny sposób powolnych instrukcji.

Z tego powodu odradzałbym twoją sugestię, ale jeśli pomaga to w zapobieganiu błędom, może być warte kompromisu. Nie mogę się powstrzymać od myśli, że musi być jakiś kompromis, który warto znaleźć.

Aby wywołać metodę wirtualną, wystarczy kilka dodatkowych instrukcji asm.

Ale myślę, że nie martwisz się, że fun (int a, int b) ma kilka dodatkowych instrukcji „push” w porównaniu do fun (). Więc nie martw się też o wirtuale, dopóki nie znajdziesz się w specjalnej sytuacji i nie zobaczysz, że to naprawdę prowadzi do problemów.

PS Jeśli masz metodę wirtualną, upewnij się, że masz wirtualny destruktor. W ten sposób unikniesz ewentualnych problemów

W odpowiedzi na komentarze „xtofl” i „Tom”. Zrobiłem małe testy z 3 funkcjami:

1. Wirtualny
2. Normalna
3. Normalny z 3 parametrami int

Mój test był prostą iteracją:

for(int it = 0; it < 100000000; it ++) {
    test.Method();
}

A oto wyniki:

1. 3,913 sek
2. 3873 sek
3. 3,970 sek

Został skompilowany przez VC ++ w trybie debugowania. Zrobiłem tylko 5 testów na metodę i obliczyłem średnią wartość (więc wyniki mogą być dość niedokładne) ... Tak czy inaczej, wartości są prawie równe przy założeniu 100 milionów wywołań. A metoda z 3 dodatkowymi wciśnięciami / popchnięciami była wolniejsza.

Najważniejsze jest to, że jeśli nie podoba ci się analogia z push / pop, pomyśl o dodatkowym if / else w swoim kodzie? Czy myślisz o potoku procesora, kiedy dodajesz dodatkowe if / else ;-) Ponadto nigdy nie wiesz, na jakim procesorze będzie działał kod ... Zwykły kompilator może generować kod bardziej optymalny dla jednego procesora i mniej optymalny dla drugiego ( Intel Kompilator C ++ )