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

Я прогнал несколько таймингов на работающем по порядку процессоре PowerPC с частотой 3 ГГц. В этой архитектуре вызов виртуальной функции стоит на 7 наносекунд больше, чем прямой (не виртуальный) вызов функции.

Так что не стоит беспокоиться о стоимости, если только функция не является чем-то вроде тривиального аксессора Get () / Set (), в котором все, кроме встроенного, является расточительным. Накладные расходы в 7 нс на функцию, встроенную в 0,5 нс, являются серьезными; накладные расходы в 7 нс на функцию, выполнение которой занимает 500 мс, бессмысленны.

Большая стоимость виртуальных функций на самом деле заключается не в поиске указателя функции в vtable (обычно это всего лишь один цикл), а в том, что косвенный переход обычно не может быть предсказан ветвлением. Это может вызвать большой пузырь конвейера, поскольку процессор не может получить никаких инструкций до тех пор, пока косвенный переход (вызов через указатель функции) не прекратится и не будет вычислен новый указатель инструкций. Итак, стоимость вызова виртуальной функции намного больше, чем может показаться при взгляде на сборку ... но все же всего 7 наносекунд.

Изменить: Эндрю, Not Sure и другие также поднимают очень хороший вопрос о том, что вызов виртуальной функции может вызвать промах в кэше инструкций: если вы перейдете на кодовый адрес, которого нет в кеше, тогда вся программа заходит в тупик, пока инструкции извлекаются из основной памяти. Это всегда значительный провал: на Xenon около 650 циклов (по моим тестам).

Однако это не проблема виртуальных функций, потому что даже прямой вызов функции вызовет промах, если вы перейдете к инструкциям, которых нет в кеше. Важно то, выполнялась ли функция раньше (что увеличивает вероятность того, что она находится в кеше), и может ли ваша архитектура предсказывать статические (не виртуальные) ветки и заблаговременно извлекать эти инструкции в кеш. Мой PPC нет, но, возможно, самое последнее оборудование Intel делает.

Мои тайминги контролируют влияние промахов icache на выполнение (намеренно, поскольку я пытался изолированно исследовать конвейер ЦП), поэтому они скидывают эту стоимость.

При вызове виртуальной функции определенно существуют измеримые накладные расходы - вызов должен использовать vtable для разрешения адреса функции для этого типа объекта. Дополнительные инструкции - наименьшее из ваших беспокойств. Vtables не только предотвращает многие потенциальные оптимизации компилятора (поскольку тип является полиморфным компилятору), они также могут разрушить ваш I-Cache.

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

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

Возможно, вы могли бы посмотреть, как создаются / документируются / пишутся классы. Обычно заголовок класса должен четко указывать, какие функции могут быть переопределены производными классами и как они вызываются. Если программисты напишут эту документацию, это поможет убедиться, что они правильно помечены как виртуальные.

Я бы также сказал, что объявление каждой функции виртуальной может привести к большему количеству ошибок, чем просто забыть пометить что-то как виртуальное. Если все функции виртуальные, все можно заменить базовыми классами - общедоступными, защищенными, частными - все становится честной игрой. Случайно или намеренно подклассы могут изменить поведение функций, которые затем вызывают проблемы при использовании в базовой реализации.

Это зависит. :) (А вы чего-нибудь еще ждали?)

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

std :: copy () для простых типов POD может прибегать к простой процедуре memcpy, но с типами, не относящимися к POD, нужно обращаться более осторожно.

Строительство становится намного медленнее, потому что необходимо инициализировать vtable. В худшем случае разница в производительности между типами данных POD и не-POD может быть значительной.

В худшем случае вы можете увидеть в 5 раз более медленное выполнение (это число взято из университетского проекта, который я недавно реализовал, чтобы переопределить несколько стандартных библиотечных классов. На создание нашего контейнера потребовалось примерно в 5 раз больше времени, как только тип данных, который он хранит, получил vtable)

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

Однако производительность не должна быть здесь вашим главным приоритетом. Сделать все виртуальным - не лучшее решение по другим причинам.

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

Сделав все виртуальным, можно устранить несколько потенциальных ошибок, но при этом появятся новые.

Если вам нужна функциональность виртуальной рассылки, вы должны заплатить цену. Преимущество C ++ заключается в том, что вы можете использовать очень эффективную реализацию виртуальной диспетчеризации, предоставляемую компилятором, вместо возможно неэффективной версии, которую вы реализуете самостоятельно.

Однако возиться с накладными расходами, если они вам не нужны, возможно, зайдет слишком далеко. И большинство классов не предназначены для наследования - для создания хорошего базового класса требуется нечто большее, чем просто сделать его функции виртуальными.

Виртуальная отправка на порядок медленнее некоторых альтернатив - не столько из-за косвенного обращения, сколько из-за предотвращения встраивания. Ниже я проиллюстрирую это, сопоставив виртуальную диспетчеризацию с реализацией, встраивающей «тип (-идентифицирующее) число» в объекты и используя оператор switch для выбора кода, зависящего от типа. Это полностью исключает накладные расходы на вызов функции - просто выполняется локальный переход. Есть потенциальные затраты на ремонтопригодность, зависимости перекомпиляции и т. Д. Из-за принудительной локализации (в переключателе) функциональных возможностей, зависящих от типа.

РЕАЛИЗАЦИЯ

#include <iostream>
#include <vector>

// virtual dispatch model...

struct Base
{
    virtual int f() const { return 1; }
};

struct Derived : Base
{
    virtual int f() const { return 2; }
};

// alternative: member variable encodes runtime type...

struct Type
{
    Type(int type) : type_(type) { }
    int type_;
};

struct A : Type
{
    A() : Type(1) { }
    int f() const { return 1; }
};

struct B : Type
{
    B() : Type(2) { }
    int f() const { return 2; }
};

struct Timer
{
    Timer() { clock_gettime(CLOCK_MONOTONIC, &from); }
    struct timespec from;
    double elapsed() const
    {
        struct timespec to;
        clock_gettime(CLOCK_MONOTONIC, &to);
        return to.tv_sec - from.tv_sec + 1E-9 * (to.tv_nsec - from.tv_nsec);
    }
};

int main(int argc)
{
  for (int j = 0; j < 3; ++j)
  {
    typedef std::vector<Base*> V;
    V v;

    for (int i = 0; i < 1000; ++i)
        v.push_back(i % 2 ? new Base : (Base*)new Derived);

    int total = 0;

    Timer tv;

    for (int i = 0; i < 100000; ++i)
        for (V::const_iterator i = v.begin(); i != v.end(); ++i)
            total += (*i)->f();

    double tve = tv.elapsed();

    std::cout << "virtual dispatch: " << total << ' ' << tve << '\n';

    // ----------------------------

    typedef std::vector<Type*> W;
    W w;

    for (int i = 0; i < 1000; ++i)
        w.push_back(i % 2 ? (Type*)new A : (Type*)new B);

    total = 0;

    Timer tw;

    for (int i = 0; i < 100000; ++i)
        for (W::const_iterator i = w.begin(); i != w.end(); ++i)
        {
            if ((*i)->type_ == 1)
                total += ((A*)(*i))->f();
            else
                total += ((B*)(*i))->f();
        }

    double twe = tw.elapsed();

    std::cout << "switched: " << total << ' ' << twe << '\n';

    // ----------------------------

    total = 0;

    Timer tw2;

    for (int i = 0; i < 100000; ++i)
        for (W::const_iterator i = w.begin(); i != w.end(); ++i)
            total += (*i)->type_;

    double tw2e = tw2.elapsed();

    std::cout << "overheads: " << total << ' ' << tw2e << '\n';
  }
}

РЕЗУЛЬТАТЫ ДЕЯТЕЛЬНОСТИ

В моей системе Linux:

~/dev  g++ -O2 -o vdt vdt.cc -lrt
~/dev  ./vdt                     
virtual dispatch: 150000000 1.28025
switched: 150000000 0.344314
overhead: 150000000 0.229018
virtual dispatch: 150000000 1.285
switched: 150000000 0.345367
overhead: 150000000 0.231051
virtual dispatch: 150000000 1.28969
switched: 150000000 0.345876
overhead: 150000000 0.230726

Это говорит о том, что встроенный подход с переключением номеров типов примерно в (1,28–0,23) / (0,344–0,23) = 9,2 раз быстрее. Конечно, это специфично для конкретной тестируемой системы / флагов компилятора, версии и т. Д., Но в целом показательно.

КОММЕНТАРИИ ДО ВИРТУАЛЬНОЙ ОТПРАВКИ

Однако следует сказать, что накладные расходы на вызов виртуальных функций редко бывают значительными, и то только для часто называемых тривиальных функций (таких как геттеры и сеттеры). Даже в этом случае вы можете предоставить единую функцию для получения и настройки сразу множества вещей, минимизируя затраты. Люди слишком беспокоятся о виртуальной диспетчеризации - поэтому сделайте профилирование, прежде чем искать неудобные альтернативы. Основная проблема с ними заключается в том, что они выполняют внешний вызов функции, хотя они также делают локализацию выполняемого кода, который изменяет шаблоны использования кеша (в лучшую или (чаще) худшую сторону).

Дополнительные затраты практически равны нулю в большинстве сценариев. (простите за каламбур). ejac уже опубликовал разумные относительные меры.

Самое главное, от чего вы отказываетесь, - это возможные оптимизации за счет встраивания. Они могут быть особенно хороши, если функция вызывается с постоянными параметрами. Это редко дает реальную разницу, но в некоторых случаях она может быть огромной.

Относительно оптимизации:
Важно знать и учитывать относительную стоимость конструкций вашего языка. Нотация Big O - это только половина дела - как масштабируется ваше приложение. Другая половина - это постоянный фактор перед ним.

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

Надуманный пример: пустой виртуальный деструктор в массиве из миллиона мелких элементов может обработать не менее 4 МБ данных, что приведет к потере вашего кеша. Если этот деструктор можно встроить, данные не будут затронуты.

При написании библиотечного кода такие соображения далеко не преждевременны. Вы никогда не знаете, сколько циклов будет окружено вашей функцией.

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

Рассмотрим этот код, каков результат?

#include <stdio.h>

class A
{
public:
    void Foo()
    {
        printf("A::Foo()\n");
    }
};

class B : public A
{
public:
    void Foo()
    {
        printf("B::Foo()\n");
    }
};

int main(int argc, char** argv)
{    
    A* a = new A();
    a->Foo();

    B* b = new B();
    b->Foo();

    A* a2 = new B();
    a2->Foo();

    return 0;
}

Здесь ничего удивительного:

A::Foo()
B::Foo()
A::Foo()

Поскольку ничего виртуального нет. Если ключевое слово virtual добавлено в начало Foo в классах A и B, мы получим это для вывода:

A::Foo()
B::Foo()
B::Foo()

Практически то, чего все ожидают.

Вы упомянули, что есть ошибки, потому что кто-то забыл добавить виртуальное ключевое слово. Итак, рассмотрите этот код (где ключевое слово virtual добавлено к классу A, но не к классу B). Что же тогда на выходе?

#include <stdio.h>

class A
{
public:
    virtual void Foo()
    {
        printf("A::Foo()\n");
    }
};

class B : public A
{
public:
    void Foo()
    {
        printf("B::Foo()\n");
    }
};

int main(int argc, char** argv)
{    
    A* a = new A();
    a->Foo();

    B* b = new B();
    b->Foo();

    A* a2 = new B();
    a2->Foo();

    return 0;
}

Ответ: Так же, как если бы виртуальное ключевое слово было добавлено к B? Причина в том, что подпись для B :: Foo совпадает точно так же, как A :: Foo (), и поскольку Foo для A является виртуальным, то же самое и для B.

Теперь рассмотрим случай, когда Foo B виртуально, а A - нет. Что же тогда на выходе? В этом случае на выходе будет

A::Foo()
B::Foo()
A::Foo()

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

Не забывайте, что виртуальные методы означают, что этот класс дает будущим классам возможность переопределять / изменять некоторые из его поведений.

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

Ключевое слово virtual в C ++ - мощная концепция. Вы должны убедиться, что каждый член команды действительно знает эту концепцию, чтобы ее можно было использовать так, как задумано.

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

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

Для вызова виртуального метода потребуется всего пара дополнительных инструкций asm.

Но я не думаю, что вы беспокоитесь о том, что fun (int a, int b) имеет пару дополнительных инструкций push по сравнению с fun (). Так что не беспокойтесь о виртуальных машинах, пока вы не окажетесь в особой ситуации и не увидите, что это действительно приводит к проблемам.

P.S. Если у вас есть виртуальный метод, убедитесь, что у вас есть виртуальный деструктор. Так вы избежите возможных проблем

В ответ на комментарии «xtofl» и «Tom». Я провел небольшие тесты с 3 функциями:

1. Виртуальный
2. Обычный
3. Нормальный с 3 параметрами int

Мой тест был простой итерацией:

for(int it = 0; it < 100000000; it ++) {
    test.Method();
}

И вот результаты:

1. 3,913 с
2. 3,873 сек
3. 3,970 с

Он был скомпилирован VC ++ в режиме отладки. Я провел только 5 тестов на метод и вычислил среднее значение (так что результаты могут быть довольно неточными) ... В любом случае, значения почти равны при 100 миллионах вызовов. И метод с 3 дополнительными толчками / толчками был медленнее.

Главное, что если вам не нравится аналогия с push / pop, подумайте о дополнительных if / else в вашем коде? Вы думаете о конвейере ЦП, когда добавляете дополнительные if / else ;-) Кроме того, вы никогда не знаете, на каком ЦП будет выполняться код ... Обычный компилятор может генерировать код, более оптимальный для одного процессора и менее оптимальный для другого (Компилятор Intel C ++)