Городские легенды о медленных вызовах виртуальных функций

Традиционно компиляторы реализуют вызовы виртуальных функций через двойную косвенную адресацию — если класс содержит хотя бы одну виртуальную функцию, то в начале каждого объекта этого класса хранится адрес таблицы виртуальных функций. Если компилятор не знает конкретный тип объекта, на который указывает указатель, то для вызова виртуальной функции нужно сначала взять указатель на объект, прочитать адрес начала таблицы, затем по номеру метода прочитать адрес, где хранится реализация функции, затем вызвать функцию.

Процесс поиска конкретной функции по указателю на объект называется поздним связыванием и выполняется во время работы программы. Позднее связывание не только увеличивает накладные расходы на вызов, но и препятствует оптимизации кода компилятором. Из-за этого сами виртуальные функции принято считать замедляющими работу.

В тексте выше ключевое слово «если». Что, если компилятор знает, какую функцию на самом деле надо вызывать?

В Стандарте (далее ссылки на Стандарт 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 = 0x18894
    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 = 0x18894
    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 <Classes.h>
#include <stdio.h>

Base::~Base()
{
}

int Base::Magic()
{
    return 9000;
}

int Derived::Magic()
{
    return 100500;
}

//main.cpp
#include <Classes.h>
int magic( Base& object )
{
    return object.Magic();
}

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,0x10
    402839:	call   402050 <___main>
    Base* base = new Derived();
    40283e:	mov    DWORD PTR [esp],0x4
    вызов ::operator new()
    402845:	call   4015d8 <__Znwj>
    запись указателя на vtable
    40284a:	mov    DWORD PTR [eax],0x404058
    int result = magic( *base );
    delete base;
    402850:	mov    ecx,eax
    402852:	call   4015c0 <__ZN7DerivedD0Ev>
    return result;
}
    на место возвращаемого значения записывается константа 
    402857:	mov    eax,0x18894
    40285c:	leave  
    40285d:	ret    

Здесь нас интересует инструкция mov eax, 0x18894 (100500 в шестнадцатеричной записи) — снова компилятор выбрал нужную функцию, подставил ее тело в место вызова и оптимизировал окружающий код.

Слишком просто, поэтому добавляем фабрику (Derived и Base те же)…

//Factory.h
#include <Classes.h>

class Factory {
public:
    static Base* CreateInstance();
};

//Factory.cpp
#include <Factory.h>

Base* Factory::CreateInstance()
{
    return new Derived();
}

//main.cpp
#include <Factory.h>

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,0x10
    40283b:	call   402050 <___main>
    return new Derived();
    402840:	mov    DWORD PTR [esp],0x4
    вызов ::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],0x404058
    прямой вызов 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-0x8]
    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,0x18894
    401585:	ret 

Компилятор правильно определил, какую функцию нужно вызвать, но не стал подставлять тело функции в место вызова.

Параметризуем фабрику (Base и Derived те же)…

//Factory.h
#include <Classes.h>
enum ClassType {
    BaseType,
    DerivedType
};

class Factory {
public:
    static Base* CreateInstance(ClassType classType);
};

//Factory.cpp
#include <Factory.h>

Base* Factory::CreateInstance(ClassType classType)
{
    switch( classType ) {
        case BaseType:
           return new Base();
        case DerivedType:
           return new Derived();
    }
}

//main.cpp
#include <Factory.h>
int magic( Base& object )
{
    return object.Magic();
}

int main()
{
    Base* base = Factory::CreateInstance(DerivedType);
    int result = magic( *base );
    delete base;
    return result;
}

Получаем… тот же код, что и в предыдущей попытке.

Теперь party hard будем вычислять параметр фабрики при работе программы…

#include <Factory.h>
#include <cstdlib>

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,0x10
    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],0x4
    ветвление
    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],0x404070
    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+0x8]
    return result;
}
    40286c:	lea    esp,[ebp-0x8]
    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],0x404058
    402880:	mov    ebx,eax
    окончание ветви и безусловный переход в точку слияния
    402882:	jmp    40285d <_main+0x2d>

Довольно любопытный результат. Код метода фабрики полностью подставлен по месту. В зависимости от результата вызова функции rand() прямо внутри main() выполняется ветвление и создание экземпляров соответствующих классов. Компилятор мог бы дальше поставить и прямые вызовы в каждой из ветвей, но не справился с оптимизацией и скатился в два косвенных вызова – один для вызова метода Magic() с поздним связыванием, второй – для удаления объекта, тоже с поздним связыванием.

Как видим, вызовы виртуальных функций не обязывают использовать позднее связывание, а что произойдет в реальном мире – зависит от компилятора, его настроек и конкретного кода.

Дмитрий Мещеряков,
департамент продуктов для разработчиков

Автор: DmitryMe

Источник