Міські легенди про повільних виклики віртуальних функцій

Традиційно компілятори реалізують виклики віртуальних функцій через подвійну непряму адресацію — якщо клас містить хоча б одну віртуальну функцію, то на початку кожного об'єкта цього класу зберігається адреса таблиці віртуальних функцій. Якщо компілятор не знає конкретний тип об'єкта, на який вказує покажчик, то для виклику віртуальної функції потрібно спочатку взяти вказівник на об'єкт, прочитати адресу початку таблиці, а потім за номером методу прочитати адресу, де зберігається реалізація функції, потім викликати функцію.

Процес пошуку конкретної функції за вказівником на об'єкт називається пізнім зв'язуванням і виконується під час роботи програми. Пізніше зв'язування не тільки збільшує накладні витрати на виклик, але і перешкоджає оптимізації коду компілятором. З-за цього самі віртуальні функції прийнято вважати уповільнюють роботу.

В тексті вище ключове слово «якщо». Що, якщо компілятор знає, яку функцію насправді треба викликати?

У Стандарті (далі посилання на Стандарт 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() з пізнім зв'язуванням, другий — для видалення об'єкта, теж з пізнім зв'язуванням.

Як бачимо, виклики віртуальних функцій не зобов'язують використовувати пізніше зв'язування, а що станеться в реальному світі — залежить від компілятора, його параметрів і конкретної коду.

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


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.