Давайте вспомним, как работают виртуальные методы. Если класс содержит один или более виртуальный метод, компилятор для такого класса создает таблицу виртуальных методов, а в сам класс добавляет виртуальный табличный указатель. Компилятор также генерирует код в конструкторе класса для инициализации виртуального табличного указателя. Выбор вызываемого виртуального метода производится на этапе выполнения программы при помощи выбора адреса метода из созданной таблицы.
Итого имеем следующие дополнительные затраты:
1) Дополнительный указатель в классе (указатель на таблицу виртуальных методов);
2) Дополнительный код в конструкторе класса (для инициализации виртуального табличного указателя);
3) Дополнительный код при каждом вызове виртуального метода (разыменование указателя на таблицу виртуальных методов и поиск по таблице нужного адреса виртуального метода).
К счастью, компиляторы сейчас поддерживают такую оптимизацию как девиртуализация (devirtualization). Суть её заключается в том, что виртуальный метод вызывается напрямую, если компилятор точно знает тип вызываемого объекта и таблица виртуальных методов при этом не используется. Такая оптимизация появилась довольно давно. Например, для gcc — начиная с версии 4.7, для clang'a начиная с версии 3.8 (появился флаг -fstrict-vtable-pointers).
Но всё же, можно ли пользоваться полиморфизмом без виртуальных функций вообще? Ответ: да, можно. На помощь приходит так называемый «странно повторяющийся шаблон» (Curiously Recurring Template Pattern или CRTP). Правда это будет уже статический полиморфизм. Он отличается от привычного динамического.
Давайте рассмотрим пример преобразования класса с виртуальными методами в класс с шаблоном:
class IA {
public:
virtual void helloFunction() = 0;
};
class B : public IA {
public:
void helloFunction(){
std::cout<< "Hello from B";
}
};Превращается в:
template <typename T>
class IA {
public:
void helloFunction(){
static_cast<T*>(this)->helloFunction();
}
};
class B : public IA<B> {
public:
void helloFunction(){
std::cout<< "Hello from B";
}
};Обращение:
template <typename T>
void sayHello(IA<T>* object) {
object->helloFunction();
}Класс IA принимает шаблоном порождённый класс и кастует указатель на this к порождённому классу. static_cast производит проверку приведения на уровне компиляции, следовательно, не влияет на производительность. Класс B порождён от класса IA, который в свою очередь шаблонизирован классом B.
Дополнительные затраты — дополнительный указатель в классе, дополнительный код в конструкторе класса, дополнительный код при каждом вызове виртуального метода, как в первом случае отсутствуют. Если ваш компилятор не поддерживает оптимизацию девиртуализации, то такой код будет работать быстрее и занимать меньше памяти.
Спасибо за внимание.
Надеюсь, кому-нибудь заметка будет полезна.
Комментарии (62)
ukhegg
16.08.2016 21:19+1Если не ошибаюсь, то до полиморфизма здесь далеко. Имеем дело с простым вызовом функций с одинаковым именем у совершенно разных классов.
struct C : public IA<C>{ std::string helloFunction(std::string param = "Say hello param") { cout<< "Hello from C"; } }; ... C c; sayHello(&c);
выведет «Hello from C», а вот сигнатура функции уже сооовсем другая
DistortNeo
16.08.2016 22:07+5Отличие между CRTP и виртальными функциями принципиальное, т.к. CRTP — это статический полиморфизм через шаблоны, а не динамические вызовы.
Без CRTP вызов функции бы выглядел как:
template <typename T> void sayHello(T* object) { object->helloFunction(); }
CRTP в данном случае играет роль концептов, которые всё никак не введут в C++.
Минус CRTP — легко выстрелить в ногу, забыв переопределить метод.
monah_tuk
17.08.2016 07:37Минус CRTP — легко выстрелить в ногу, забыв переопределить метод.
если использовать в связке с NVI. Точнее тут не совсем NVI, но суть та же: интерфейс (в шаблоне) и реализация — разные методы, с разным именем и/или сигнатурой. В таком случае, если забудешь реализацию и где-то будет вызов интерфейса — будет ошибка компиляции.
Т.е. что-то вроде:
template <typename T> class IA { public: helloFunction(){ static_cast<T*>(this)->doHelloFunction(); } };
минус тут в том, что эта самая
doHelloFunction()тоже должна быть публичной (public:), что бы можно было её вызвать из базового класса. В NVI такой проблемы нет. Ну или делать в наследнике что-то вроде:
friend class IA<C>;
А так, IMHO, CRTP чаще используется когда нужен реюз кода, и не нужно наследование в виде "C является IA" ("is a").
cranium256
16.08.2016 22:31+11. Я правильно понимаю, что в коде примеров вы по ошибке пропустили для методов указание типа возвращаемого значения? Или в последних стандартах по этому поводу есть указания?
2. Я правильно понимаю, что при использовании CRTP при вызове helloFunction() для экземпляра базового класса программа уйдёт в нирвану до момента исчерпания стека?Flame_xXx
17.08.2016 09:251. Да, пропустил. Спасибо, поправил.
2. Да. Как выше писали, «это еще один способ выстрелить себе в ногу». Причём довольно легко и непринуждённо :)
Dudraug
18.08.2016 13:01#include <iostream> #include <type_traits> #define HAS_MEM_FUNC(func, name) template<typename T, typename Sign> struct name { typedef char yes[1]; typedef char no [2]; template <typename U, U> struct type_check; template <typename _1> static yes &chk(type_check<Sign, &_1::func > *); template <typename > static no &chk(...); static bool const value = sizeof(chk<T>(0)) == sizeof(yes); } HAS_MEM_FUNC(Do, has_do); template<class T> class IA { public: void Do() { static_assert(has_do<T, void(T::*)()>::value, "Derived class has no Do function"); static_cast<T*>(this)->Do(); } protected: IA() {} IA(const IA&) {} IA(IA&&) {} protected: }; template<class WorkingClass> void RunDo(IA<WorkingClass>& p) { p.Do(); } class C : public IA<C> { }; class B : public IA<B> { public: void Do() { std::cout << "I'm B!!!" << std::endl; } }; int main() { B b; RunDo(b); C c; // RunDo(c); // IA<B> ia; // RunDo(ia); }
Door
16.08.2016 22:40Как по мне — так тут один решающий недостаток — нельзя написать просто:
std::vector<std::unique_ptr<IA>>
qw1
16.08.2016 22:54+3Полиморфизм часто нужен, чтобы положить в одну коллекцию объекты разных типов и единообразно вызывать их метод helloFunction, например итерируя по коллекции. С предложенным подходом так не сделаешь, т.е. это не полноценная замена.
SBKarr
17.08.2016 09:11Для коллекций есть несколько методов type erasure, и полиморфизм здесь, имхо, не самый удачный. Если только полиморфизм не решает попутно других задач. В хорошей архитектуре каждый элемент на своём месте, чтобы не создавать лишних сущностей и лишней нагрузки.
Dudraug
18.08.2016 13:23+1Да, это статический полиморфизм. Нельзя использовать коллекцию базовых объектов, нельзя вернуть ссылку/указатель на базовый объект из некой функции, но реально ссылающуюся на разные объекты в зависимости от разных условий и вызвать у нее потом некий метод например тот же Do(). Да, этого нельзя. Это ограничения статического полиморфизма, но быть полиморфным код выше от этого не перестал.
snizovtsev
16.08.2016 23:32+1Кто то не знал об CRTP и его недостатках? Уже в C++11 особой надобности в нем нет: если расставить final и использовать конкретные типы, то компилятору не придется гадать о применимости девиртуализации. И волки сыты (код быстрый), и овцы целы (readability, type checking). А если еще использовать LTO… (вот на эту тему было бы интересно увидеть статью).
А чтобы понять, как правильно применять статический полиморфизм — посмотрите устройство traits в rust. В C++ пока нехватает фич (концептов и модулей), чтобы такой код можно было широко применять в продакшне.
monah_tuk
17.08.2016 07:41CRTP, как минимум, очень полезен при реюзе кода, когда наследование используется, но отношение "is a" неприменимо или применимо с явной натяжкой, так что он пригодится в C++11, и 14, и 17 и т.д.
iCpu
17.08.2016 08:03Погодите, наследуеся но не является? Если это импорт части реализации, тогда это агрегация. А если это ни то, ни другое, то это просто дерьмовый дизайн.
monah_tuk
17.08.2016 08:56Если это импорт части реализации, тогда это агрегация.
именно, что импорт общей и обобщённой реализации. Просто покажите, как это сделать красиво и удобно с точки зрения пользователя интерфейса класса в C++ чистой агрегацией. Потому как я воспринимал до сиго момента агрегацию как:
class Foo { ... }; class Bar { Foo m_foo; ... };
и как красиво и без лишнего кода вытащить интерфейсы
Foo, как часть интерфейсаBarв таком случае — я слабо представляю. Особенно когда обобщённый код должен знать о типе агрегатора, простой пример:
template<typename T> struct Creator { static std::unique_ptr<T> create() {...} }; struct Foo : public Creator<Foo> {}; ... auto ptr = Foo::create();
Fooя не являетсяCreator'ом, но подмешивается единожды написанная обобщённая функциональность.iCpu
17.08.2016 09:26+1Ну, так и есть, дерьмовый дизайн. И не нужно этого стыдиться.
Foo я не является Creator'ом, но подмешивается единожды написанная обобщённая функциональность.
Ну да, не является Creator, но является Creator(Foo)
Пруфы в студию!
Мне интересно, где такое могло понадобиться?monah_tuk
17.08.2016 11:07Ну, так и есть, дерьмовый дизайн. И не нужно этого стыдиться.
Ок. Но я до сих пор не вижу вашего примера.
Ну да, не является Creator, но является Creator(Foo)
Стоп. С точки зрения языка, да,
Foois aCreator<Foo>, я это даже не пытался оспаривать. Но, внимание, аналогичный код дляBarбудет даватьCreator<Bar>, при этомCreator<Foo>иCreator<Bar>— это разные классы. Как следствие, при таком подходе не создаётся иерархии классов с общим корнем. Таким образом, с точки зрения языка — это наследование, но по сути — это не реализация отношения "is a", а подмешивания готовой функциональности к данному классу, способ реюза кода.iCpu
17.08.2016 11:24+1Хммм… Меня замкнуло на контексте поста. А если подумать, я был неправ. Опять. Что ж, бывает. Примите мои извинения.
monah_tuk
17.08.2016 11:29+1Мне интересно, где такое могло понадобиться?
Вот, кстати, достаточно интересная статья на тему: http://scrutator.me/post/2014/06/26/crtp_demystified.aspx (пропускаем первую часть про статический полиморфизм и переходит к смешиванию типов) и там же примеры: Boost.Operators (что куда лучше и интереснее
std::rel_ops), трюк сstd::enable_shared_from_this.
fck_r_sns
17.08.2016 09:40+1когда наследование используется, но отношение «is a» неприменимо
Это по определению приватное наследование. Хотя лучше использовать агрегацию, как уже рядом заметили.iCpu
17.08.2016 10:28-2Нет, приватное наследование не скрывает свойство «является», скрываются лишь методы базового класса.
fck_r_sns
17.08.2016 10:45+3Что Вы имеете в виду под «не скрывает свойство «является»»?
class Base {}; class Derived : private Base {}; ... Base *b = new Derived(); ...
Мы получим ошибку компиляции: "'Base' is an inaccessible base of 'Derived'"
В C++ отношение «is a» достигается только при публичном наследовании. При приватном/защищенном мы не можем пользоваться объектом производного класса через указатель на базовый класс, а это значит, что отношение «is a» не применимо. То есть это свойство не то что «не скрыто» — его просто нет.
monah_tuk
17.08.2016 11:07При приватном наследовании, как минимум, придётся вручную вытягивать (
using ...) в паблик нужные методы из базового класса, ради которых, быть может, всё и затевалось: http://ideone.com/v85SqB. Плюс примера, показывающего использование агрегации для расширения интерфейса класса я всё ещё не увидел в данной ветке.
Я сам люблю агрегацию. Я не отказываюсь от приватного наследования (привет
noncopyable), но иногда случаются ситуации, когда появляются методы в несвязанных классах, почти строка в строку повторяющие друг друга с мелкими отличиями в деталях, вроде имени класса или около того. Обычно такие методы несут какой-то утилитарных характер. Собственно в таких ситуациях возникает вопрос: а как минимальным объёмом кода, не создавая новой иерархии зареюзать подобный код?fck_r_sns
17.08.2016 11:13Плюс примера, показывающего использование агрегации для расширения интерфейса класса я всё ещё не увидел в данной ветке.
Элегантного способа в C++ нет, насколько я знаю.
Не элегантный — делегирование/проксирование.monah_tuk
17.08.2016 11:45+1Не элегантный — делегирование/проксирование.
CRTP я бы сюда тоже добавил. Причём по объёму дополнительного кода он, возможно, будет даже самым оптимальным (см https://habrahabr.ru/post/307902/#comment_9754908), но тоже не без своих заморочек.
semenyakinVS
16.08.2016 23:46-1Помимо приведённых выше замечаний, проблемы будут возникать если функция sayHello(...) в какой-то момент окажется виртуальным методом, который не умеет быть шаблонным.
Вообще же — действительно интересно было бы глянуть кейс, при котором понадобились такие неприятные оптимизации.
П.С.: «а в сам класс добавляет виртуальный табличный указатель» — возможно я неправильно понял мысль, но, если я не ошибаюсь, указатель на таблицу виртуальных функций располагается в рамках объекта, а не класса — чтобы ни имелось в виду в качестве «добавления в класс» (ссылка по теме).
Antervis
17.08.2016 07:16вызов виртуальной функции дороже вызова обычной примерно на 10 асм-инструкций (может зависеть от компилятора и применения девиртуализации). Грубо говоря, за всё время эксплуатации ваша программа скорее всего не наэкономит столько времени, сколько уйдет на применение статического полиморфизма вместо динамического
monah_tuk
17.08.2016 07:46+2Вы забыли про косвенную адресацию при работе с таблицей указателей. Нынче рандомные обращение к памяти не сильно эффективная штука ;-) Но в остальном да — ооооочень интересен кейс, где не хватило возможностей компилятора и вылезли тормоза. Тем паче, что в C-style полиморфизме (структуры с полями-указателями на функцию, которая принимает эту структуру) проблема ровно та же с косвенной адресацией, но только ручками.
Amomum
17.08.2016 11:10Еще небольшой минус CRTP — приходится выдумывать однообразные названия для методов: hello() -> sayHello() -> doSayHello() — потому что одинаково их называть на разных уровнях иерархии нельзя.
Antervis
17.08.2016 13:19Можно же
прощеclass Base { public: template <typename T = Base> inline void func() { if (!std::is_same<T,Base>::value) static_cast<T*>(this)->func(); else std::cout << "base" << std::endl; } }; class Derived : public Base { public: void func() { std::cout << "derived" << std::endl; } }; class SecondDerived : public Derived { public: void func() { std::cout << "second derived" << std::endl; } }; int main() { Base b; b.func(); Derived d; d.func(); SecondDerived sd; sd.func(); }Shamov
17.08.2016 14:54Можно ещё проще:
Скрытый текстclass Base { public: void func() { std::cout << "base" << std::endl; } }; class Derived : public Base { public: void func() { std::cout << "derived" << std::endl; } }; class SecondDerived : public Derived { public: void func() { std::cout << "second derived" << std::endl; } }; int main() { Base b; b.func(); Derived d; d.func(); SecondDerived sd; sd.func(); }
Shamov
17.08.2016 13:05+1Это какой-то обман. Основная идея виртуальных функций в том, что когда я вызываю такую функцию, я реально не знаю, какая именно реализация вызовется. И не только я этого не знаю. Вообще никто не знает. Это станет известно только во время выполнения. Здесь же получается, что конкретная реализация, которая вызовется, известна заранее. Пусть даже информация об этом вводится в класс через задний проход (через параметр шаблона).
maydjin
17.08.2016 18:29+2[-||||-]
Да и не ради производительности этот шаблон шаблонного программирования на c++ используют в основном, а для наследования реализации.
Рекомендую почитать Вандервуда и Джосаттиса "Шаблоны C++. Справочник разработчика", сиё чтиво слегка устарело конечно, но в общем и целом хорошая вводная в метапрограммирование на плюсах.
Shamov
17.08.2016 19:09+1Плохо рекламируете :) «Наследование реализации» звучит как-то несногсшибательно. Сразу возникает мысль: «Зачем мне это надо? Наверное, фигня какая-то.» Нужна более привлекательная приманка. Надо сказать, что наследование реализации, полученной через параметр шаблона, позволяет убрать код всех нешаблонных методов в сpp-файл.
VYakushev
Так и не понял почему же вызов виртуальных методов «тормозил» у новоиспеченных программистов.
Sirikid
Я тоже ожидал увидеть какой-нибудь хитровывернутый кейс, из-за которого немного неверный код новичков тормозил.
elephanten
Можно пофантазировать, что вызов метода выполнялся достаточно часто, чтобы сказывалось наличие таблицы виртуальных функций, но не слишком, чтобы этот указатель успевал вылетать из кэша.
Flame_xXx
На самом деле они только прочитали про механизм вызовов виртуальных функций и, привыкшие к функциональному программированию, решили что дело в нём, хотя это было совсем не так.
Tujh
Может именно так и нужно было начинать эту статью, а то уж больно провокационное начало вышло :)
Flame_xXx
Возможно. Это моя первая статья. В дальнейшем буду иметь ввиду
vladimirkolyada
Так к функциональному или процедурному?:)
Flame_xXx
*процедурному
Flame_xXx
по-быстрому набросал пример.
вывод:
сравним с
вывод:
iCpu
У вас во втором случае бесполезный вызов вырежет компилятор. Нужно выводить его в консоль. И, желательно получать начальное значение из рандома.
Flame_xXx
Сделал. Ситуация не поменялась
iCpu
https://ideone.com/f17DTU
У меня получились немного другие результаты.
Дабы не было недопонимания, я не собираюсь оспаривать то, что дёргать виртуальный метод — медленнее, чем дёргать указатель на функцию. Я оспариваю какие-то сверхъестественные числа, которые можно получить только после оптимизации под корень. Медленнее в 5-6 раз, но не на порядки.
Flame_xXx
Согласен с Вами. Во втором случае компилятор действительно что-то подозрительно наоптимизировал. Но результат одинаковый. Сейчас разбираюсь в чём подвох. Я сам, честно говоря, ожидал разницы в 5-8 раз. Кстати, в Вашем примере всего один виртуальный метод. В моём же было 7
iCpu
Ваше право сделать форк и исправить. А наоптимизировал он простую вещь: если 100000 раз вызывать ++, почему бы сразу не вызвать += 100000 всего 1 раз?
А ещё я слил карму у долбаных функциональщиков и не могу в тэги, что печально. Долбаные функциональщики, размечтались, что могут реализовать одну лишь инкапсуляцию и назвать её ООП! Что эти нигеры себе позволяют!?!
Flame_xXx
Да, действительно, результаты получаются похожими на Ваши. Добавил +rand() и вывод в лог непосредственно в helloFunction7. Значит, мой компилятор лучше оптимизирует код с шаблонами, а об виртуальные функции чаще спотыкается, раз такая разница была в первом случае