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

107

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

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

Это подводит меня к моему вопросу: есть ли измеримые затраты на производительность (т.е. влияние на скорость) для создания виртуального метода? Поиск в виртуальной таблице будет производиться во время выполнения при каждом вызове метода, поэтому, если есть очень частые вызовы этого метода и если этот метод очень короткий, то может быть ощутимое снижение производительности? Я думаю, это зависит от платформы, но кто-нибудь запускал тесты?

Причина, по которой я спрашиваю, заключается в том, что я обнаружил ошибку, которая произошла из-за того, что программист забыл определить виртуальный метод. Я не впервые вижу такую ​​ошибку. И я подумал: почему мы добавляем ключевое слово virtual, когда это необходимо, вместо того, чтобы удалять ключевое слово virtual, когда мы абсолютно уверены, что оно не нужно? Если стоимость производительности низкая, я думаю, что я просто порекомендую следующее в своей команде: просто сделайте каждый метод виртуальным по умолчанию, включая деструктор, в каждом классе, и удаляйте его только тогда, когда вам нужно. Вам это кажется безумным?

MiniQuark
источник
7
Сравнение виртуальных и не виртуальных вызовов не имеет смысла. Они предоставляют разный функционал. Если вы хотите сравнить вызовы виртуальных функций с эквивалентом C, вам необходимо добавить стоимость кода, который реализует эквивалентную функцию виртуальной функции.
Мартин Йорк,
Это либо оператор switch, либо большой оператор if. Если бы вы были умны, вы могли бы повторно реализовать использование таблицы указателей функций, но вероятность ошибиться намного выше.
Мартин Йорк,
7
Вопрос в вызовах функций, которые не обязательно должны быть виртуальными, поэтому сравнение имеет смысл.
Марк Рэнсом,

Ответы:

104

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

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

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

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

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

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

Crashworks
источник
3
Стоимость в циклах примерно равна количеству этапов конвейера между выборкой и окончанием вывода ветки из эксплуатации. Это немалые затраты, и они могут складываться, но если вы не пытаетесь написать жесткий высокопроизводительный цикл, вам, вероятно, придется поджарить более крупную рыбу.
Crashworks
На 7 наносекунд дольше, чем на что. Если нормальный вызов составляет 1 наносекунду, это очень важно, если нормальный вызов составляет 70 наносекунд, то это не так.
Мартин Йорк,
Если вы посмотрите на тайминги, я обнаружил, что для функции, которая стоит 0,66 нс, дифференциальные накладные расходы прямого вызова функции составляли 4,8 нс, а виртуальной функции - 12,3 нс (по сравнению со встроенной функцией). Вы хорошо заметили, что если сама функция стоит миллисекунду, то 7 нс ничего не значат.
Crashworks
2
Скорее 600 циклов, но это хороший момент. Я не учел это время, потому что меня интересовали только накладные расходы из-за пузыря конвейера и пролога / эпилога. Промах в icache также легко случается и при прямом вызове функции (в Xenon нет предиктора ветвления icache).
Crashworks
2
Незначительные детали, но в отношении «Однако это не проблема, специфичная для ...», это немного хуже для виртуальной отправки, поскольку есть дополнительная страница (или две, если она выходит за границу страницы), которая должна находиться в кеше. - для виртуальной таблицы рассылки класса.
Тони Делрой
19

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

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

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

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

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

Эндрю Грант
источник
Самая большая потерянная оптимизация - это встраивание, особенно если виртуальная функция часто бывает маленькой или пустой.
Zan Lynx,
@ Андрей: интересная точка зрения. Я несколько не согласен с вашим последним абзацем: если базовый класс имеет функцию, saveкоторая полагается на конкретную реализацию функции writeв базовом классе, то мне кажется, что она либо saveплохо закодирована, либо writeдолжна быть частной.
MiniQuark
2
То, что запись является частной, не предотвращает ее переопределения. Это еще один аргумент в пользу отказа от виртуализации по умолчанию. В любом случае я думал об обратном - обычная и хорошо написанная реализация заменяется чем-то с конкретным и несовместимым поведением.
Эндрю Грант,
Проголосовал за кеширование - для любой большой объектно-ориентированной базы кода, если вы не следуете практикам производительности локализации кода, ваши виртуальные вызовы могут очень легко вызвать промахи кеша и вызвать остановку.
Not Sure,
И срыв icache может быть действительно серьезным: 600 циклов в моих тестах.
Crashworks
9

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

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

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

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

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

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

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

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

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

Jalf
источник
7

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

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


источник
Хороший ответ, но, IMO, недостаточно решительный во 2-й половине: нагружать себя накладными расходами, если они вам не нужны, честно говоря, чокнутый - особенно при использовании этого языка, мантра которого - «не платите за то, что вы надеваете». Не пользуюсь ". Делать все виртуальным по умолчанию до тех пор, пока кто-нибудь не объяснит, почему это может / должно быть не виртуальным, - отвратительная политика.
underscore_d
5

Виртуальная отправка на порядок медленнее, чем некоторые альтернативы - не столько из-за косвенного обращения, сколько из-за предотвращения встраивания. Ниже я проиллюстрирую это, сравнивая виртуальную диспетчеризацию с реализацией, встраивающей «тип (-идентифицирующее) число» в объекты и используя оператор 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 раза быстрее. Конечно, это специфично для конкретной тестируемой системы / флагов компилятора, версии и т. Д., Но в целом показательно.


КОММЕНТАРИИ RE VIRTUAL DISPATCH

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

Тони Делрой
источник
Я задал вопрос по вашему коду, потому что у меня есть "странные" результаты при использовании g++/ clangи -lrt. Я подумал, что об этом стоит упомянуть для будущих читателей.
Холт
@Holt: хороший вопрос, учитывая загадочные результаты! Я рассмотрю его поближе через несколько дней, если у меня будет половина шанса. Ура.
Тони Делрой
3

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

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


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

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


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

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

Петерхен
источник
2

Хотя все остальные правы в отношении производительности виртуальных методов и тому подобного, я думаю, что реальная проблема заключается в том, знает ли команда об определении виртуального ключевого слова в 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 ++ - мощная концепция. Вы должны убедиться, что каждый член команды действительно знает эту концепцию, чтобы ее можно было использовать так, как задумано.

Томми Хуэй
источник
Привет, Томми, спасибо за руководство. У нас возникла ошибка из-за отсутствия ключевого слова virtual в методе базового класса. Кстати, я говорю: сделайте все функции виртуальными (а не наоборот), а затем, когда очевидно, что в этом нет необходимости, удалите ключевое слово virtual.
MiniQuark
@MiniQuark: Томми Хуи говорит, что если вы сделаете все функции виртуальными, программист может в конечном итоге удалить ключевое слово в производном классе, не осознавая, что это не имеет никакого эффекта. Вам понадобится какой-то способ гарантировать, что удаление виртуального ключевого слова всегда происходит в базовом классе.
М. Дадли
1

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

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

Дэн Олсон
источник
-1

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

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

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


В ответ на комментарии «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 ++ )

alex2k8
источник
2
дополнительный asm может просто вызвать ошибку страницы (чего не было бы для невиртуальных функций) - я думаю, вы сильно упрощаете проблему.
xtofl
2
+1 к комментарию xtofl. Виртуальные функции вводят косвенное обращение, которое вводит «пузыри» конвейера и влияет на поведение кэширования.
Tom
1
Сроки чего-либо в режиме отладки бессмысленно. MSVC делает очень медленный код в режиме отладки, и накладные расходы на цикл, вероятно, скрывают большую часть разницы. Если вы стремитесь к высокой производительности, да, вам следует подумать о минимизации ветвей if / else на быстром пути. См. Agner.org/optimize для получения дополнительной информации о низкоуровневой оптимизации производительности x86. (Также некоторые другие ссылки в wiki тегов x86
Питер Кордес,
1
@Tom: ключевым моментом здесь является то, что невиртуальные функции могут быть встроенными, а виртуальные - нет (если компилятор не может девиртуализировать, например, если вы использовали finalв своем переопределении и у вас есть указатель на производный тип, а не на базовый тип ). В этом тесте каждый раз вызывалась одна и та же виртуальная функция, поэтому он идеально предсказывал; отсутствие пузырей в трубопроводе, кроме случаев ограниченной callпропускной способности. И это косвенное callможет быть еще парой упов. Прогнозирование ветвлений хорошо работает даже для непрямых ветвей, особенно если они всегда в одном месте.
Питер Кордес
Это попадает в обычную ловушку микробенчмарков: это выглядит быстро, когда предикторы ветвления горячие и ничего больше не происходит. Накладные расходы на неправильное прогнозирование выше для косвенного, callчем для прямого call. (И да, обычные callинструкции тоже нуждаются в прогнозировании. Этап выборки должен знать следующий адрес для выборки до того, как этот блок будет декодирован, поэтому он должен прогнозировать следующий блок выборки на основе адреса текущего блока, а не адреса инструкции. как предсказать, где в этом блоке есть инструкция ветвления ...)
Питер Кордес