Почему стоимость виртуального вызова C++ зависит от количества производных классов?

Question

EDIT: По просьбе n.m., я включил полный код, который использовал, несмотря на его многословие.

Я написал небольшую примерную программу, которую я использовал для изучения накладных расходов виртуальных вызовов.

timer.h:

#include <chrono> 
#include <cstdint> 

class Timer { 
    typedef std::chrono::high_resolution_clock clock; 
    typedef clock::time_point time_point; 
    typedef clock::duration duration; 

    time_point begin; 
    time_point end; 
public: 
    void start() 
    { 
     begin = clock::now(); 
    } 

    void stop() 
    { 
     end = clock::now(); 
    } 

    double as_seconds() 
    { 
     duration dur = end - begin; 

     return (double) dur.count() * (double) duration::period::num/(double) duration::period::den; 
    } 
}; 

virtual.h:

#pragma once 

static const int NUM_DERIVED = 10; 

struct Base { 
    int val; 

#ifdef NO_VIRTUAL 
    #define virtual 
#endif 
    virtual void f(); 
    virtual ~Base(); 
#undef virtual 
}; 

Base *create_base(unsigned max_derived); 

virtual.cpp:

#include <algorithm> 
#include <iostream> 
#include <memory> 
#include <typeinfo> 
#include <vector> 
#include "virtual.h" 
#include "timer.h" 

template <typename Container> 
void measure_call(const Container &c) 
{ 
    Timer t; 

    t.start(); 
    for (auto &ptr : c) { 
     ptr->f(); 
    } 
    t.stop(); 

    std::cout << "Virtual calls: " << c.size() << '\n'; 
    std::cout << "Elapsed time (s): " << t.as_seconds() << '\n'; 
} 

int main() 
{ 
    typedef std::unique_ptr<Base> base_ptr; 
    typedef std::vector<base_ptr> base_vector; 

    const int NUM_VEC = 10000000; 
    const int NUM_DERIVED_USED = NUM_DERIVED; 

    base_vector vec1; 
    base_vector vec2; 

    Timer t; 

    vec1.reserve(NUM_VEC); 
    vec2.reserve(NUM_VEC); 
    for (int i = 0; i < NUM_VEC; ++i) { 
     Base *b1 = create_base(1); 
     Base *b2 = create_base(NUM_DERIVED_USED); 
     vec1.emplace_back(b1); 
     vec2.emplace_back(b2); 
    } 

    std::cout << "Measuring random vector of " << 1 << " derived classes\n"; 
    measure_call(vec1); 
    std::cout << '\n'; 

    std::cout << "Measuring random vector of " << NUM_DERIVED_USED << " derived classes\n"; 
    measure_call(vec2); 
    std::cout << '\n'; 

    std::cout << "Sorted vector of " << NUM_DERIVED << " derived clases\n"; 
    std::sort(
     vec2.begin(), vec2.end(), 
     [](const base_ptr &a, const base_ptr &b) -> bool 
     { 
      return typeid(*a).hash_code() < typeid(*b).hash_code(); 
     } 
    ); 
    for (int i = 0; i < 20; ++i) { 
     int idx = vec2.size()/20 * i; 
     std::cout << "vector[" << idx << "]: " << typeid(*vec2[idx]).name() << '\n'; 
    } 
    std::cout << '\n'; 

    std::cout << "Measuring sorted vector of " << NUM_DERIVED_USED << " derived classes\n"; 
    measure_call(vec2); 

    return 0; 
} 

virtual_impl.cpp:

#include <cstdlib> 
#include "virtual.h" 

template <int N> 
struct Derived : Base { 
    void f() { Base::val = N; } 
    ~Derived() {} 
}; 

void Base::f() {} 

Base::~Base() {} 

Base *create_base(unsigned max_derived) 
{ 
    unsigned n = max_derived > NUM_DERIVED ? NUM_DERIVED : max_derived; 

    switch (rand() % n) { 
    case 9: 
     return new Derived<9>; 
    case 8: 
     return new Derived<8>; 
    case 7: 
     return new Derived<7>; 
    case 6: 
     return new Derived<6>; 
    case 5: 
     return new Derived<5>; 
    case 4: 
     return new Derived<4>; 
    case 3: 
     return new Derived<3>; 
    case 2: 
     return new Derived<2>; 
    case 1: 
     return new Derived<1>; 
    case 0: 
     return new Derived<0>; 
    default: 
     return nullptr; 
    } 
} 

компилировать virtual_impl.cpp в разделяемую библиотеку, чтобы предотвратить компилятор от возни и devirtualizing или встраивание вещи:

$ g++ -shared --std=c++11 -O3 virtual_impl.cpp -o libvirtual_impl.so 
$ g++ --std=c++11 -O3 virtual.cpp -L. -lvirtual_impl -o virtual 
$ ./virtual 

В результате я получаю:

Measuring random vector of 1 derived classes 
Virtual calls: 10000000 
Elapsed time (s): 0.039333 

Measuring random vector of 10 derived classes 
Virtual calls: 10000000 
Elapsed time (s): 0.089604 

Sorted vector of 10 derived clases 
vector[0]: 7DerivedILi8EE 
vector[500000]: 7DerivedILi8EE 
vector[1000000]: 7DerivedILi8EE 
vector[1500000]: 7DerivedILi7EE 
vector[2000000]: 7DerivedILi7EE 
vector[2500000]: 7DerivedILi2EE 
vector[3000000]: 7DerivedILi2EE 
vector[3500000]: 7DerivedILi9EE 
vector[4000000]: 7DerivedILi9EE 
vector[4500000]: 7DerivedILi0EE 
vector[5000000]: 7DerivedILi1EE 
vector[5500000]: 7DerivedILi1EE 
vector[6000000]: 7DerivedILi1EE 
vector[6500000]: 7DerivedILi6EE 
vector[7000000]: 7DerivedILi6EE 
vector[7500000]: 7DerivedILi4EE 
vector[8000000]: 7DerivedILi4EE 
vector[8500000]: 7DerivedILi3EE 
vector[9000000]: 7DerivedILi5EE 
vector[9500000]: 7DerivedILi5EE 

Measuring sorted vector of 10 derived classes 
Virtual calls: 10000000 
Elapsed time (s): 0.115058 

Как вы можете видеть, с 10 производных классов, стоимость почти в 3 раза больше, чем только с одним производным классом. Прогнозирование ветви кажется вероятной целью, но как-то в списке, отсортированном по типу, производительность хуже, чем в случайном списке!

EDIT2: В генерации кода, похоже, нет черной магии. Я нашел разборку для measure_call здесь:

(gdb) disassemble 
Dump of assembler code for function _Z12measure_callISt6vectorISt10unique_ptrI4BaseSt14default_deleteIS2_EESaIS5_EEEvRKT_: 
0x0000000100002170: push r14 
0x0000000100002172: push r13 
0x0000000100002174: push r12 
0x0000000100002176: mov r12,rdi 
0x0000000100002179: push rbp 
0x000000010000217a: push rbx 
0x000000010000217b: sub rsp,0x10 
0x000000010000217f: call 0x10000283e <dyld_stub__ZNSt6chrono3_V212system_clock3nowEv> 
0x0000000100002184: mov rbp,QWORD PTR [r12+0x8] 
0x0000000100002189: mov rbx,QWORD PTR [r12] 
0x000000010000218d: mov r13,rax 
0x0000000100002190: cmp rbx,rbp 
0x0000000100002193: je  0x1000021b1 <_Z12measure_callISt6vectorISt10unique_ptrI4BaseSt14default_deleteIS2_EESaIS5_EEEvRKT_+65> 
0x0000000100002195: nop DWORD PTR [rax+rax+0x0] 
0x000000010000219a: nop WORD PTR [rax+rax+0x0] 
0x00000001000021a0: mov rdi,QWORD PTR [rbx] 
0x00000001000021a3: add rbx,0x8 
0x00000001000021a7: mov rcx,QWORD PTR [rdi] 
0x00000001000021aa: call QWORD PTR [rcx] 
0x00000001000021ac: cmp rbp,rbx 
0x00000001000021af: jne 0x1000021a0 <_Z12measure_callISt6vectorISt10unique_ptrI4BaseSt14default_deleteIS2_EESaIS5_EEEvRKT_+48> 
0x00000001000021b1: call 0x10000283e <dyld_stub__ZNSt6chrono3_V212system_clock3nowEv> 
[iostream stuff follows] 

Answer 1

Вопрос заключается в следующем:

void f() { Base::val = N; } 

и это:

for (auto &ptr : c) { 
    ptr->f(); 
} 

Сортировка по типу рандомизирует, какое место памяти вы читаете из (чтобы получить виртуальные таблицы адреса) присвоения (Base::val), который будет прогнозом развития карликов для 10 vtables.

Answer 2

Вы не показывают реализацию create_base, поэтому я только гадать, но я думаю, что вы видите эффект предсказания ветвлений.

с create_base(1), все указатели указывают объекты одного и того же производного класса, поэтому все вызовы переходят к одной и той же производной виртуальной функции. Поэтому, после первого, предсказатель ветвления правильно предсказывает целевой адрес непрямой ветви и нет задержки ветвления.

С помощью create_base(10) вы создаете указатели на 10 различных производных классов, каждый со своей собственной производной виртуальной функцией. Таким образом, каждый вызов относится к другому адресу, что приводит к тому, что предсказатель целевой ветви пропускает много (90%?) Времени.

Если попытаться использовать create_base(2), я думаю, вы увидите, что его на полпути между 1 и 10 случаями (mispredict половины времени), и большими значениями быстро приближается к 10 случая.