Городские легенды о медленных вызовах виртуальных функций
Традиционно компиляторы реализуют вызовы виртуальных функций через двойную косвенную адресацию — если класс содержит хотя бы одну виртуальную функцию, то в начале каждого объекта этого класса хранится адрес таблицы виртуальных функций. Если компилятор не знает конкретный тип объекта, на который указывает указатель, то для вызова виртуальной функции нужно сначала взять указатель на объект, прочитать адрес начала таблицы, затем по номеру метода прочитать адрес, где хранится реализация функции, затем вызвать функцию.Процесс поиска конкретной функции по указателю на объект называется поздним связыванием и выполняется во время работы программы. Позднее связывание не только увеличивает накладные расходы на вызов, но и препятствует оптимизации кода компилятором. Из-за этого сами виртуальные функции принято считать замедляющими работу.
В тексте выше ключевое слово «если». Что, если компилятор знает, какую функцию на самом деле надо вызывать? В Стандарте (далее ссылки на Стандарт C++03) ничего не сказано про таблицы виртуальных методов. Вместо этого в 5.2.2/1 ([expr.call], «вызов функции») сказано, что если в программе содержится вызов виртуальной функции, то должна быть вызвана соответствующая функция, выбранная по правилам из 10.3/2 ([class.virtual], «виртуальные функции»), а там сказано, что TL; DR; должна быть выбрана функция из самого производного класса, в котором функция определена или переопределена.
Соответственно, если компилятор может, разобрав код, выяснить точный тип объекта, он не обязан использовать позднее связывание — и не важно, вызывается метод у конкретного объекта, по ссылке или по указателю на объект.
От бессмысленных рассуждений™ перейдем к коду, который будем пробовать на gcc.godbolt.org
Нам понадобятся вот эти два класса:
class Base { public: virtual ~Base () {} virtual int Magic () { return 9000; } };
class Derived: public Base { public: virtual int Magic () { return 100500; } }; Для начала такой код:
int main () { Derived derived; return derived.Magic (); } clang 3.4.1 с -O2 отвечает на это так: main: # @main movl $100500, %eax # imm = 0×18894 ret Нетрудно видеть, что машинный код соответствует программе, содержащей только return 100500; Это не особенно интересно — ведь здесь нет указателей и ссылок.Ладно, медленно помешивая, добавляем указатели и ссылки:
int magic (Base& object) { return object.Magic (); }
int main () { Base* base = new Derived (); int result = magic (*base); delete base; return result; } clang 3.4.1 с -O2 отвечает на это так: magic (Base&): # @magic (Base&) movq (%rdi), %rax jmpq *(%rax) # TAILCALL
main: # @main movl $100500, %eax # imm = 0×18894 ret ОХ ЩИ ОШИБКА В КОМПИЛЯТОРЕ Нет, с компилятором все в порядке, но агрессивность оптимизации отрицать бессмысленно. Снова return 100500;
Для сравнения, gcc 4.9.0 с -O2:
main: subq $8, %rsp movl $8, %edi call operator new (unsigned long) movq vtable for Derived+16, (%rax) movq %rax, %rdi call Derived::~Derived () movl $100500, %eax addq $8, %rsp ret call Derived::~Derived () — из-за виртуального деструктора, gcc в таких случаях ставит вызов :: operator delete () внутрь деструктора:
Derived::~Derived (): jmp operator delete (void*) хотя мог бы и по месту подставить. Вот так: movq %rax, %rdi call operator delete (void*) Мог бы, но не стал. В то же время тело метода Derived: Magic () подставлено в место вызова и оптимизировано вместе с окружающим кодом.Небольшое отступление… Если вы любите пространно рассуждать о том, насколько хорошо компилятор в принципе может оптимизировать код, пример выше для вас. И вызов Derived: Magic (), и удаление объекта компилятор мог оптимизировать одинаково успешно, но один из них он оптимизировал, а второй — нет. Отступление закончено.
Для сравнения, gcc 4.9.0 с -O1
magic (Base&): subq $8, %rsp movq (%rdi), %rax call *(%rax) addq $8, %rsp ret main: pushq %rbp pushq %rbx subq $8, %rsp movl $8, %edi call operator new (unsigned long) movq %rax, %rbx movq vtable for Derived+16, (%rax) movq %rax, %rdi call magic (Base&) movl %eax, %ebp testq %rbx, %rbx je .L12 movq (%rbx), %rax movq %rbx, %rdi call *16(%rax) .L12: movl %ebp, %eax addq $8, %rsp popq %rbx popq %rbp ret Вот, может ведь, если хорошо попросить. В этом коде «все в порядке» — куча доступов к памяти и вызов метода инструкцией call с косвенной адресацией (call *16(%rax)).
Впрочем, примеры успеха с -O2 выглядят надуманными — весь код находится в одной единице трансляции, а это существенно упрощает оптимизацию.
На помощь спешит LTO (или как там называется оптимизация нескольких единиц трансляции в вашем компиляторе).
Делим код на несколько единиц трансляции…
//Classes.h class Base { public: virtual int Magic (); virtual ~Base (); };
class Derived: public Base { public: virtual int Magic (); };
//Classes.cpp
#include
Base::~Base () { }
int Base: Magic () { return 9000; }
int Derived: Magic () { return 100500; }
//main.cpp
#include
int main () { Base* base = new Derived (); int result = magic (*base); delete base; return result; } Здесь и далее будем использовать MinGW с gcc 4.9.0
g++ -flto -g -O3 main.cpp Classes.cpp objdump -d -M intel -S --no-show-raw-insn a.exe >a.txt int main () { 402830: push ebp 402831: mov ebp, esp 402833: and esp,0xfffffff0 402836: sub esp,0×10 402839: call 402050 <___main> Base* base = new Derived (); 40283e: mov DWORD PTR [esp],0×4 вызов :: operator new () 402845: call 4015d8 <__Znwj> запись указателя на vtable 40284a: mov DWORD PTR [eax],0×404058 int result = magic (*base); delete base; 402850: mov ecx, eax 402852: call 4015c0 <__ZN7DerivedD0Ev> return result; } на место возвращаемого значения записывается константа 402857: mov eax,0×18894 40285c: leave 40285d: ret Здесь нас интересует инструкция mov eax, 0×18894 (100500 в шестнадцатеричной записи) — снова компилятор выбрал нужную функцию, подставил ее тело в место вызова и оптимизировал окружающий код.Слишком просто, поэтому добавляем фабрику (Derived и Base те же)…
//Factory.h
#include
class Factory { public: static Base* CreateInstance (); };
//Factory.cpp
#include
Base* Factory: CreateInstance () { return new Derived (); }
//main.cpp
#include
int magic (Base& object) { return object.Magic (); }
int main () { Base* base = Factory: CreateInstance (); int result = magic (*base); delete base; return result; } Компилируем, дизассемблируем… Исходно результат выглядит не очень понятно™ — из-за агрессивной оптимизации машинный код и исходный код оказались сопоставлены не самым удобным для чтения образом, ниже машинный код оставлен как есть, а часть строк исходного кода размещена максимально близко к соответствующему машинному коду. int main () { 402830: push ebp 402831: mov ebp, esp 402833: push esi 402834: push ebx 402835: and esp,0xfffffff0 402838: sub esp,0×10 40283b: call 402050 <___main> return new Derived (); 402840: mov DWORD PTR [esp],0×4 вызов :: operator new () 402847: call 4015d8 <__Znwj> 40284c: mov ebx, eax
int magic (Base& object) { return object.Magic (); 40284e: mov ecx, eax запись указателя на vtable 402850: mov DWORD PTR [eax],0×404058 прямой вызов Derived: Magic () 402856: call 401580 <__ZN7Derived5MagicEv>
int main () { delete base; 40285b: mov ecx, ebx 40285d: mov esi, eax 40285f: call 4015b0 <__ZN7DerivedD0Ev> return result;
402864: lea esp,[ebp-0×8] 402867: mov eax, esi 402869: pop ebx 40286a: pop esi 40286b: pop ebp 40286c: ret (дальше пропущено) Здесь нас интересует строка
402856: call 401580 <__ZN7Derived5MagicEv> Это прямой вызов Derived: Magic ():
00401580 <__ZN7Derived5MagicEv>:
int Derived: Magic () { return 100500; } 401580: mov eax,0×18894 401585: ret Компилятор правильно определил, какую функцию нужно вызвать, но не стал подставлять тело функции в место вызова.
Параметризуем фабрику (Base и Derived те же)…
//Factory.h
#include
class Factory { public: static Base* CreateInstance (ClassType classType); };
//Factory.cpp
#include
Base* Factory: CreateInstance (ClassType classType) { switch (classType) { case BaseType: return new Base (); case DerivedType: return new Derived (); } }
//main.cpp
#include
int main () { Base* base = Factory: CreateInstance (DerivedType); int result = magic (*base); delete base; return result; } Получаем… тот же код, что и в предыдущей попытке.Теперь party hard будем вычислять параметр фабрики при работе программы…
#include
int magic (Base& object) { return object.Magic (); }
int main () { Base* base = Factory: CreateInstance (rand () ? BaseType: DerivedType); int result = magic (*base); delete base; return result; } Получаем… (результат опять выглядит не очень понятно) int main () { 402830: push ebp 402831: mov ebp, esp 402833: push esi 402834: push ebx 402835: and esp,0xfffffff0 402838: sub esp,0×10 40283b: call 402050 <___main> Base* base = Factory: CreateInstance (rand () ? BaseType: DerivedType); вызов rand () 402840: call 4027c8 <_rand>
Base* Factory: CreateInstance (ClassType classType) { switch (classType) { проверка из объединенных вместе тернарного оператора и switch 402845: test eax, eax 402847: mov DWORD PTR [esp],0×4 ветвление 40284e: jne 402875 <_main+0x45> если rand () вернула не ноль, происходит переход вперед на адрес 402875 если rand () вернула ноль, перехода нет и … case DerivedType: return new Derived (); вызов :: operator new () 402850: call 4015d8 <__Znwj> запись указателя на vtable класса Derived 402855: mov DWORD PTR [eax],0×404070 40285b: mov ebx, eax
int magic (Base& object) { return object.Magic (); здесь происходит слияние двух ветвей - управление либо «проваливается» сюда, либо безусловно приходит из ветви, начинающейся с адреса 402875 (rand () != 0) 40285d: mov eax, DWORD PTR [ebx] 40285f: mov ecx, ebx косвенный вызов Magic () 402861: call DWORD PTR [eax] 402863: mov esi, eax
int main () { delete base; 402865: mov eax, DWORD PTR [ebx] 402867: mov ecx, ebx косвенный вызов удаления объекта 402869: call DWORD PTR [eax+0×8] return result; } 40286c: lea esp,[ebp-0×8] 40286f: mov eax, esi 402871: pop ebx 402872: pop esi 402873: pop ebp 402874: ret
Base* Factory: CreateInstance (ClassType classType) { switch (classType) { case BaseType: return new Base (); сюда управление приходит при ветвлении по адресу 40284e если rand () != 0 вызов :: operator new () 402875: call 4015d8 <__Znwj> запись указателя на vtable класса Base 40287a: mov DWORD PTR [eax],0×404058 402880: mov ebx, eax окончание ветви и безусловный переход в точку слияния 402882: jmp 40285d <_main+0x2d> Довольно любопытный результат. Код метода фабрики полностью подставлен по месту. В зависимости от результата вызова функции rand () прямо внутри main () выполняется ветвление и создание экземпляров соответствующих классов. Компилятор мог бы дальше поставить и прямые вызовы в каждой из ветвей, но не справился с оптимизацией и скатился в два косвенных вызова — один для вызова метода Magic () с поздним связыванием, второй — для удаления объекта, тоже с поздним связыванием.
Как видим, вызовы виртуальных функций не обязывают использовать позднее связывание, а что произойдет в реальном мире — зависит от компилятора, его настроек и конкретного кода.
Дмитрий Мещеряков, департамент продуктов для разработчиков
