W C ++ dlaczego i jak działają funkcje wirtualne?

38

Czy ktoś może szczegółowo wyjaśnić, jak dokładnie działa wirtualna tabela i jakie wskaźniki są powiązane, gdy wywoływane są funkcje wirtualne.

Jeśli faktycznie są wolniejsze, czy możesz pokazać, że czas potrzebny na wykonanie funkcji wirtualnej jest dłuższy niż normalne metody klasowe? Łatwo jest zapomnieć o tym, jak / co się dzieje, nie widząc żadnego kodu.

MdT
źródło
5
Wyszukiwanie poprawnego wywołania metody z vtable zajmie oczywiście więcej czasu niż bezpośrednie wywoływanie metody, ponieważ jest więcej do zrobienia. Jak długo lub czy ten dodatkowy czas jest znaczący w kontekście twojego programu, to kolejne pytanie. en.wikipedia.org/wiki/Virtual_method_table
Robert Harvey
10
Wolniej niż co dokładnie? Widziałem kod, który miał zepsutą, powolną implementację zachowania dynamicznego z dużą liczbą instrukcji przełączania tylko dlatego, że jakiś programista słyszał, że funkcje wirtualne są wolne.
Christopher Creutzig
7
Często nie jest tak, że same wirtualne połączenia są powolne, ale że kompilator nie ma możliwości ich wstawienia.
Kevin Hsu
4
@Kevin Hsu: tak, to jest absolutnie. Niemal za każdym razem, gdy ktoś powie ci, że przyspieszyło wyeliminowanie „narzutu wywołania funkcji wirtualnej”, jeśli przyjrzysz się temu, skąd tak naprawdę pochodzi całe przyspieszenie, będą to optymalizacje, które są teraz możliwe, ponieważ kompilator nie mógł zoptymalizować wcześniej nieokreślone połączenie.
dnia
7
Nawet osoba, która potrafi odczytać kod asemblera, nie jest w stanie dokładnie przewidzieć jego narzutu w trakcie wykonywania procesora. Twórcy procesorów na komputery stacjonarne zainwestowali w dziesięciolecia badań nie tylko w przewidywanie gałęzi, ale także w przewidywanie wartości i wykonywanie spekulacyjne, co jest głównym powodem maskowania opóźnień funkcji wirtualnych. Czemu? Ponieważ systemy operacyjne i oprogramowanie komputerowe z nich często korzystają. (Nie powiedziałbym tego samego o mobilnych procesorach.)
rwong

Odpowiedzi:

55

Metody wirtualne są zwykle implementowane za pomocą tak zwanych wirtualnych tabel metod (w skrócie vtable), w których przechowywane są wskaźniki funkcji. Dodaje to pośrednie rzeczywiste wywołanie (muszę pobrać adres funkcji do wywołania z vtable, a następnie wywołać ją - w przeciwieństwie do zwykłego wywoływania z wyprzedzeniem). Oczywiście zajmuje to trochę czasu i trochę kodu.

Jednak niekoniecznie jest to główna przyczyna spowolnienia. Prawdziwy problem polega na tym, że kompilator (ogólnie / zwykle) nie może wiedzieć, która funkcja zostanie wywołana. Więc nie może go wstawić ani wykonać żadnych innych takich optymalizacji. To samo może dodać tuzin bezcelowych instrukcji (przygotowanie rejestrów, wywoływanie, a następnie przywrócenie stanu) i może hamować inne, pozornie niezwiązane optymalizacje. Co więcej, jeśli rozgałęziasz się jak szalony, wywołując wiele różnych implementacji, cierpisz z powodu tych samych trafień, które cierpiałbyś z powodu rozgałęziania się jak szalony innymi sposobami: pamięć podręczna i predyktor gałęzi ci nie pomogą, rozgałęzienia potrwają dłużej niż całkowicie przewidywalne Oddział.

Duże, ale : te hity wydajnościowe są zwykle zbyt małe, aby mieć znaczenie. Warto je rozważyć, jeśli chcesz utworzyć kod o wysokiej wydajności i rozważyć dodanie funkcji wirtualnej, która byłaby wywoływana z alarmującą częstotliwością. Jednak również pamiętać, że zastąpienie wywołania funkcji wirtualnych z innymi środkami rozgałęzienia ( if .. else, switch, wskaźników funkcji, etc.) nie rozwiązuje podstawowego problemu - może to równie dobrze być wolniejsze. Problemem (jeśli w ogóle istnieje) nie są funkcje wirtualne, ale (niepotrzebna) pośrednictwo.

Edycja: Różnica w instrukcjach połączeń jest opisana w innych odpowiedziach. Zasadniczo kod dla wywołania statycznego („normalnego”) to:

  • Skopiuj niektóre rejestry ze stosu, aby umożliwić wywoływanej funkcji korzystanie z tych rejestrów.
  • Skopiuj argumenty do predefiniowanych lokalizacji, aby wywoływana funkcja mogła je znaleźć bez względu na to, gdzie jest wywołana.
  • Naciśnij adres zwrotny.
  • Rozgałęzienie / skok do kodu funkcji, który jest adresem czasu kompilacji, a zatem zapisanym na stałe w pliku binarnym przez kompilator / linker.
  • Uzyskaj wartość zwrotną ze wstępnie zdefiniowanej lokalizacji i przywróć rejestry, których chcemy użyć.

Wirtualne wywołanie robi dokładnie to samo, z tym wyjątkiem, że adres funkcji nie jest znany w czasie kompilacji. Zamiast tego kilka instrukcji ...

  • Uzyskaj od obiektu wskaźnik vtable, który wskazuje na tablicę wskaźników funkcji (adresów funkcji), po jednym dla każdej funkcji wirtualnej, z obiektu.
  • Uzyskaj odpowiedni adres funkcji z tabeli vt do rejestru (indeks, w którym przechowywany jest poprawny adres funkcji, jest ustalany w czasie kompilacji).
  • Przejdź do adresu w tym rejestrze zamiast skakać na adres zakodowany na stałe.

Jeśli chodzi o gałęzie: gałąź to cokolwiek, co przeskakuje do innej instrukcji zamiast pozwolić na wykonanie następnej instrukcji. Obejmuje to if, switch, części różnych pętli, wywołania funkcji itp a czasami implementuje kompilatora rzeczy, które nie wydają się gałęzi w sposób, który rzeczywiście potrzebuje oddział pod maską. Zobacz Dlaczego przetwarzanie posortowanej tablicy jest szybsze niż nieposortowanej tablicy? dlaczego może to być powolne, co procesory robią, aby przeciwdziałać temu spowolnieniu i jak to nie jest lekarstwem na wszystko.

Społeczność
źródło
6
@ JörgWMittag wszystkie są tłumaczami i wciąż są wolniejsze niż kod binarny generowany przez kompilatory C ++
Sam
13
@ JörgWMittag Te optymalizacje mają na celu przede wszystkim uwolnienie pośredniego / późnego wiązania (prawie), gdy nie jest potrzebne , ponieważ w tych językach każde połączenie jest technicznie opóźnione. Jeśli naprawdę wywołujesz wiele różnych metod wirtualnych z jednego miejsca w krótkim czasie, te optymalizacje nie pomagają ani nie aktywnie szkodzą (stwórz dużo kodu do zera). Faceci w C ++ nie są bardzo zainteresowani tymi optymalizacjami, ponieważ znajdują się w zupełnie innej sytuacji ...
10
@ JörgWMittag ... Faceci z C ++ nie są bardzo zainteresowani tymi optymalizacjami, ponieważ znajdują się w zupełnie innej sytuacji: skompilowany w AOT sposób vtable jest już dość szybki, bardzo niewiele wywołań jest wirtualnych, wiele przypadków polimorfizmu jest wcześnie- związany (za pomocą szablonów), a zatem można go modyfikować w celu optymalizacji AOT Wreszcie, wykonanie tych optymalizacji adaptacyjnie (zamiast spekulacji w czasie kompilacji) wymaga wygenerowania kodu w czasie wykonywania, co wprowadza mnóstwo bólu głowy. Kompilatory JIT rozwiązały już te problemy z innych powodów, więc nie mają nic przeciwko, ale kompilatory AOT chcą tego uniknąć.
3
świetna odpowiedź, +1. Należy jednak zauważyć, że czasami rozgałęzienia są znane w czasie kompilacji, na przykład podczas pisania klas frameworka, które muszą obsługiwać różne zastosowania, ale gdy kod aplikacji wejdzie w interakcję z tymi klasami, określone użycie jest już znane. W takim przypadku alternatywą dla funkcji wirtualnych mogą być szablony C ++. Dobrym przykładem może być CRTP, który emuluje zachowanie funkcji wirtualnej bez żadnych vtables: en.wikipedia.org/wiki/Curiously_recurring_template_pattern
DXM
3
@James Masz rację. Próbowałem powiedzieć: każda pośrednictwo ma te same problemy, nie ma w tym nic szczególnego virtual.
23

Oto kilka faktycznych zdemontowanych kodów odpowiednio z wirtualnego wywołania funkcji i wywołania innego niż wirtualne:

mov    -0x8(%rbp),%rax
mov    (%rax),%rax
mov    (%rax),%rax
callq  *%rax

callq  0x4007aa

Możesz zobaczyć, że połączenie wirtualne wymaga trzech dodatkowych instrukcji, aby wyszukać poprawny adres, podczas gdy adres połączenia niewirtualnego może zostać wkompilowany.

Należy jednak pamiętać, że w większości przypadków ten dodatkowy czas wyszukiwania można uznać za nieistotny. W sytuacjach, w których czas wyszukiwania byłby znaczący, np. W pętli, wartość można zwykle buforować, wykonując pierwsze trzy instrukcje przed pętlą.

Inną sytuacją, w której czas wyszukiwania staje się znaczący, jest posiadanie kolekcji obiektów i wykonywanie pętli poprzez wywoływanie funkcji wirtualnej na każdym z nich. Jednakże w tym przypadku, będziesz potrzebować kilka sposobów wybierania, które działają zadzwonić i tak, i wirtualny tabeli odnośników jest równie dobrym sposobem jak każdy inny. W rzeczywistości, ponieważ kod wyszukiwania vtable jest tak szeroko stosowany, że jest mocno zoptymalizowany, więc próba obejścia go ręcznie ma duże szanse na pogorszenie wydajności.

Karl Bielefeldt
źródło
1
Należy zrozumieć, że wyszukiwanie vtable i wywołanie pośrednie w prawie wszystkich przypadkach będzie miało znikomy wpływ na całkowity czas działania wywoływanej metody.
John R. Strohm
11
@ JohnR.Strohm Znikome znaczenie jednego człowieka to wąskie gardło drugiego człowieka
James
1
-0x8(%rbp). o mój ... ta składnia AT&T.
Abyx
trzy dodatkowe instrukcje ” nie, tylko dwie: ładowanie vptr i ładowanie wskaźnika funkcji
ciekawy
@curiousguy to w rzeczywistości trzy dodatkowe instrukcje. Zapomniałeś, że na wskaźniku zawsze wywoływana jest metoda wirtualna , więc najpierw musisz załadować wskaźnik do rejestru. Podsumowując, pierwszym krokiem jest załadowanie adresu, który zmienna wskaźnika ma do rejestru% rax, a następnie zgodnie z adresem w rejestrze, załaduj vtpr na ten adres, aby zarejestrować% rax, a następnie zgodnie z tym adresem w zarejestruj się, załaduj adres metody, która ma zostać wywołana, do% rax, a następnie callq *% rax !.
Gab 是 好人
18

Wolniej niż co ?

Funkcje wirtualne rozwiązują problem, którego nie można rozwiązać za pomocą bezpośrednich wywołań funkcji. Ogólnie można porównywać tylko dwa programy, które obliczają to samo. „Ten ray tracer jest szybszy niż ten kompilator” nie ma sensu, a ta zasada uogólnia nawet na małe rzeczy, takie jak poszczególne funkcje lub konstrukcje języka programowania.

Jeśli nie używasz funkcji wirtualnej, aby dynamicznie przełączać się na fragment kodu oparty na układzie odniesienia, na przykład typ obiektu, będziesz musiał użyć czegoś innego, na przykład switchinstrukcji, aby osiągnąć to samo. To, że coś innego ma swoje własne koszty ogólne, a także wpływ na organizację programu, które wpływają na jego utrzymanie i globalne wyniki.

Zauważ, że w C ++ wywołania funkcji wirtualnych nie zawsze są dynamiczne. Kiedy wywołania są wykonywane na obiekcie, którego dokładny typ jest znany (ponieważ obiekt nie jest wskaźnikiem ani referencją, lub ponieważ jego typ można inaczej wywnioskować statycznie), wówczas są to zwykłe wywołania funkcji składowych. Oznacza to nie tylko, że nie ma narzutu związanego z wysyłką, ale także, że połączenia te mogą być wprowadzane w taki sam sposób, jak zwykłe połączenia.

Innymi słowy, Twój kompilator C ++ może działać, gdy funkcje wirtualne nie wymagają wirtualnego wysyłania, więc zwykle nie ma powodu, aby martwić się ich wydajnością w porównaniu z funkcjami innymi niż wirtualne.

Nowość: Nie możemy również zapominać o bibliotekach udostępnionych. Jeśli używasz klasy znajdującej się we wspólnej bibliotece, wywołanie zwykłej funkcji składowej nie będzie po prostu ładną sekwencją instrukcji, taką jak callq 0x4007aa. Musi przejść przez kilka obręczy, takich jak pośrednie poprzez „tabelę łączy programów” lub jakąś taką strukturę. Dlatego pośrednia biblioteka współdzielona może w pewnym stopniu (jeśli nie całkowicie) zrównoważyć różnicę kosztów między (prawdziwie pośrednim) połączeniem wirtualnym a połączeniem bezpośrednim. Dlatego rozumowanie dotyczące kompromisów funkcji wirtualnych musi uwzględniać budowę programu: czy klasa obiektu docelowego jest monolitycznie połączona z programem, który wykonuje wywołanie.

Kaz
źródło
4
„Wolniej niż co?” - jeśli stworzysz metodę wirtualną, która nie musi być, masz całkiem niezły materiał porównawczy.
tdammers
2
Dziękujemy za zwrócenie uwagi, że wywołania funkcji wirtualnych nie zawsze są dynamiczne. Każda inna odpowiedź tutaj wygląda na to, że deklarowanie wirtualnej funkcji oznacza automatyczne obniżenie wydajności, niezależnie od okoliczności.
Syndog,
12

ponieważ połączenie wirtualne jest równoważne z

res_t (*foo)(arg_t);
foo = (obj->vtable[foo_offset]);
foo(obj,args)

gdzie przy użyciu funkcji innej niż wirtualna kompilator może stale składać pierwszą linię, jest to dereferencja dodatek i wywołanie dynamiczne przekształcone w wywołanie statyczne

pozwala to również wstawić funkcję (ze wszystkimi konsekwencjami optymalizacji)

maniak zapadkowy
źródło