В этой статье мы рассмотрим как обычно происходит работа с динамическим полиморфизмом, где теряется производительность и как её можно улучшить, используя интересные структуры данных.
В С++ не так чтобы много способов получить из коробки динамический полиморфизм. Способов буквально два: виртуальные функции и std::variant.
про std::any
std::any неприменим нигде кроме каких-то костылей в dll и про него лучше забыть, благо есть аналоги с гораздо большим потенциалом, но об этом в другой статье
Рассмотрим эти способы подробнее:
-
виртуальные функции:
позволяют создать контейнер указателей на базовый тип, а потом складывать туда любых наследников.
struct base {
virtual ~base() = default;
};
...
std::vector<base*> things;Сразу проблемы:
если нужен указатель, то как управлять памятью?
если нужно копирование контейнера, то оно будет неправильным(скопируются указатели). И так как контейнер использует внутри конструкторы, нам ничего не остаётся кроме как написать свою обёртку или функцию копирования - что, вообще-то, крайне неудобно, затратно и опасно в плане багов
так как в контейнере лежат элементы с разными указателями на vtable, процессор и компилятор не состоянии предугадать vtable какого типа лежит следующим и это приводит к постоянным кеш-мисам, что значительно замедляет и итерацию и в целом использование подобного контейнера.
нестандартные альтернативы
проблемы с лишними аллокациями памяти и копированием/удобством в целом отлично решаются решениями основанными на стирании типов, например https://github.com/kelbon/AnyAny, но это не тема этой статьи
-
std::variant
позволяет складывать любые из *известных заранее* типов в контейнер
using myvar = std::variant<A, int, B>;
...
std::vector<myvar> things;Это решает проблемы с конструкторами и выделением памяти, к тому же элементы теперь расположены более менее локально. Но это вносит кучу своих проблем:
типы должны быть известны заранее, невозможны "рекурсивные" структуры данных, например AST на варианте уже не напишешь
-
Любое увеличение количества типов должно изменить ВСЕ сигнатуры всех функций использующих этот вариант. Как минимум придётся перекомпилирвать весь проект
void foo(const std::variant<int, float, double>&);
просто сломается при введении ещё одного типа
Проблемы с исключениями и неэффективность при большой разнице sizeof
К тому же у обоих рассмотренных вариантов нет опции быстро посмотреть только интересующие типы, придётся идти и к тому же заниматься динамическим кастом/визитом
Заметим, что часто нам нужен именно контейнер полиморфных типов, а не просто одна штука. Также я уже упомянул про то, что неплохо бы уметь предсказывать какой тип будет следующим. Это приводит нас к идее сортировать значения внутри контейнера по типу! Хм, интересно. И это действительно значительно улучшает производительность при итерации, но согласитесь как-то неудобно и затратно, к тому же придётся каждый раз при вставке и удалении думать об этом.
А как это исправлять?
Я пошёл дальше, почему бы не сделать контейнер ведущий себя как контейнер из variant<Ts...>, но на самом деле хранящий каждый тип в отдельном контейнере? Тогда мы сразу совершенно избавились бы от кастов/прыжков по vtable, std::visit и прочего. В действительности мы избавились бы от полиморфизма вообще, хотя он и оставался бы со стороны публичного интерфейса.
Кстати, об интерфейсе, нам нужны операции:
вставка для каждого типа T из Ts...
удаление для каждого типа T из Ts...
просмотр контейнера для типа T
аналог посещения(visit) для всех значений контейнера
К тому же кажется, что контейнер может быть разным в зависимости от задачи, так что сделаем его кастомизируемым. Назвал я это чудо variant_swarm (буквально рой вариантов)
Итак, как реализовать это? Всё довольно просто:
// БАЗА с настомизируемым контейнером
template <template <typename> typename Container, typename... Ts>
struct basic_variant_swarm {
private:
std::tuple<Container<Ts>...> containers;
public:
// операция "посмотреть контейнеры для типов Types..."
auto& view<Types...>();
// операция "посетить все типы из контейнеров для Types..."
void visit<Types...>(visitor);
// операция вставки, перегруженная для каждого из типов Ts...
auto insert(*сложный момент* auto value)
// операция вставки, перегруженная для каждого из типов Ts...
auto erase(*сложный момент* auto iterator)
};
// алиас для самого частого случая
template<typename... Ts>
using variant_swarm = basic_variant_swarm<std::vector, Ts...>;Конечно всё немного сложнее и это очень условный минимальный набор. Но в целом всё понятно - у нас есть tuple из контейнеров для каждого типа и перегруженные под каждый тип операции. Это интуитивно и просто.
Использовать это можно примерно так:
variant_swarm<int, double, std::string> f;
// в операции вставки нет никакого динамического полиморфизма,
// всё решено на компиляции
f.insert("hello");
f.insert(155);
f.insert(3.14);
// должно вывести "hello" 155 3.14 в КАКОМ-ТО порядке
f.visit_all([](auto& v) { std::cout<< v << std::endl;});
Полный код можно посмотреть здесь
Обратите внимание, значения будут появляется в visit_all упорядоченно по типам. А что если хочется упорядочить по индексу?
На самом деле ничего сложного, в самом деле достаточно заменить контейнер на unordered_map и вставлять вместе со значением текущее количество элементов в контейнере как ключ. Тогда операция find(index) определяется за ожидаемое время O(1).
Но двинемся дальше.
Получается, что мы определили контейнер сумтипов, если говорить терминами высших эльфов. Сразу хочется подумать, а какой аналог такой вещи был бы для типа-произведения, также известного в C++ как std::tuple? Не буду долго томить, просто ПОЧЕМУ БЫ НЕ хранить каждое поле tuple или агрегата как отдельный контейнер и так организовать data parallel контейнер?
Опять сразу определимся с интерфейсом, кажется эта штука должна вести себя практически также как std::vector снаружи, уметь хранить агрегаты и туплы, но просто делать это более эффективно и также поддерживать операцию "посмотреть филд №3 для всех сразу". И сразу заметим, что наш контейнер не сможет быть contiguous ренжом, только random_access всилу того как элементы располагаются в памяти.
Ну и с точки зрения эстетической красоты хотелось бы, чтобы это просто работало:
struct mytype {
int i;
float d;
char x;
};
...
data_parallel_vector<mytype> things;
// использование structured binding из С++17
auto [a, b, c] = things;
// реализуемо?)Итак, посмотрим как выглядит каркас реализации:
// конечно мы поддерживаем аллокаоры, мы же серьёзные люди!
template <typename T, typename Alloc = std::allocator<T>>
struct data_parallel_vector {
private:
// как доставать поля?
std::tuple<std::vector<???, Alloc>...> field_containers;
public:
using iterator; // как делать итератор?
// операция "посмотреть поля по номерам Nbs..."
// Отмечу, что она не может возвращать ссылку на контейнер,
// потому что тогда юзер может сломать инварианты нашего контейнера
// например удалить элементы
template <std::size_t... Nbs>
constexpr std::span<...> view();
// тут все операции которые поддерживаются вектором
// и могут поддерживаться нашим контейнером, а их крайне много...
};Тут С++ явно бросает нам вызов, чего только стоит специализация std::vector<bool>, которая может сломать нам буквально всё.
Для реализации итератора достаточно заметить, что для I-того элемента в каждом контейнере лежит I-тое его поле. Поэтому мы можем создать random access итератор состоящий из тупла итераторов на контейнеры.
Остальное - лучше смотреть в реализации, иначе статья будет больше хабра. Кстати, реализация полностью тут.
Пример использования (да, это работает):
struct mytype {
int i;
float d;
bool x;
};
...
data_parallel_vector<mytype> things;
// a, b, c это здесь std::span<int> span<double> и span<bool>
auto [a, b, c] = things;
// А вы что, думали это нереализуемо?Итоги
Мы реализовали контейнер сум-типов, который позволяет совершенно без оверхеда и удобно использовать рантайм полиморфизм подобный контейнеру std::variant<Ts...>
И контейнер-тип-произведение, который ведёт себя как std::vector<T>, но позволяет делать параллельные вычисления или, например, ECS систему в играх гораздо удобнее и эффективнее
Надеюсь статья была для вас интересна, предлагайте свои улучшения/идеи в комментариях!
Комментарии (45)
pharo
05.12.2022 20:06+4Полиморфные структуры данных и производительность
Извините, но где в статье про производительность?
Kelbon Автор
05.12.2022 20:08Очевидно где, такая структура данных повышает локальность данных до предела, позволяет мгновенно получить доступ значениям заданных типов, убрать динамик касты и visit
zzzzzzerg
05.12.2022 21:14+1Это в общем-то общее знание. А есть подтверждение в цифрах - было так, мы сделали так и стало так?
Kelbon Автор
05.12.2022 21:24https://www.youtube.com/watch?v=n6PvvE_tEPk&t=1225s&ab_channel=CppCon
Вот в этом докладе есть какие-то измерения про потерю производительности из-за кеш мисов по vtable. Но это лишь малая частьНу и да, конечно же стоит упомянуть, что при той версии что с разделёнными контейнерами можно функцию и заинлайнить и даже векторизовать. С виртуальными функциями это даже теоретически невозможно. Это громадный плюс
zzzzzzerg
05.12.2022 21:26+2Спасибо за видео. Но хотелось бы увидеть ваши цифры, из первых рук, так сказать.
pharo
05.12.2022 21:49Интересно увидеть в цифрах какие то выводы (на вычислительных задачах)
К, примеру может подойдёт учебная задача реализации RPN калькулятора?
Топик на Github reverse-polish-notation
P.S. Ещё интереснее с использованием профайлера или «даже» ассемблерного кода.
Xop
05.12.2022 22:27+2Рискую нарваться на "опять любители раста понабежали", но в Rust уже есть встроенный тип enum, который как раз variant, плюс в языке куча синтаксического сахара для работы с ним. Не ради критики или попытки обесценить (на самом деле статья огонь, жаль в последнее время мало такого пишут), но для рекламы любимого языка.
Kelbon Автор
05.12.2022 22:30в С++ есть std::variant, только вот это не помогает сделать эффективный контейнер таких типов. Не знаю получится ли в расте реализовать нечто подобное, так как там нет перегрузок и шаблонных шаблонных параметров
Xop
05.12.2022 23:04+1Пардон, сначала невнимательно прочитал - я сначала подумал, что у вас аналог std::variant, но на самом деле это аналог std::vector<std::variant>>, но с разложением значений различных типов по отдельным векторам и сортировкой по типам (прям по канонам data oriented design). Да, в стандартной библиотеке раста такого нет, но реализовать не вижу большой проблемы - по крайней мере если не параметризовать типом самого контейнера.
0xd34df00d
06.12.2022 02:31+1Про раст я тоже не знаю, но в х-ле AoS преобразуется в SoA легко и просто тайпклассами (и еще там их дженерик-вывод прикрутить можно).
Kelbon Автор
06.12.2022 07:56-1вопрос есть ли смысл делать подобное на хаскеле, если там невозможно добиться локальности данных / убирания оверхеда, т.к. оверхед заложен в язык
0xd34df00d
06.12.2022 08:14+5Почему невозможно? Unboxed (и Storable) располагают данные в памяти последовательно и локально, не имеют лишнего индерекшна из-за ленивости, и так далее.
iCpu
06.12.2022 07:29"Полиморфные структуры данных и производительность"?
Насколько я понял, поставленную в первом абзаце задачу вы не решили. Где здесь, собственно, "полиморфизм", если вы решили задачу разворачивания вектора структур в структуру из векторов. Где здесь, собственно, "динамический", если у вас всё на статике и этапе компиляции?Не, сама по себе структура прикольная - и очень полезна в числодробилках. Возможно, я её у вас даже и притырю. Просто назовите статью честно, "Преобразование AoS в SoA на двадцатых шаблонах", и будет вам почёт и уважение.
А так, я пришёл за пельменями, а меня шарлоткой накормили. Вкусно, конечно, но не то.Kelbon Автор
06.12.2022 07:57кажется вы пропустили середину статьи про variant_swarm, там есть динамический полиморфизм
iCpu
06.12.2022 08:41Кажется, не пропустил. Перечень типов вами заранее определён в шаблоне. Где здесь динамика?
Тем более, где здесь полиморфизм?(Ладно, это я погорячился.)Kelbon Автор
06.12.2022 08:51+1Перечень типов известен на компиляции. Где здесь полиморфизм? /s
iCpu
06.12.2022 10:01Перечень типов известен на компиляции.
Это и называется "статический". Динамический - это когда перечень типов на этапе компиляции не известен и уточняется на этапе выполнения. И может прилететь из-вне, например, из инъекции кода.
На самом деле, менять придётся не то, чтобы очень много -
std::tupleзаменить наstd::map<std::type_index, ...>и добавить код расширения-сужения списка типов в рантайме. Ну и, возможно, вынести шаблонные методы доступа из класса, чтобы их можно было перегружать. Хотя, может я и излишне оптимистичен.Kelbon Автор
06.12.2022 10:15Вы не поняли, типы всегда известны на компиляции. Просто иногда они устроены так, что создают полиморфизм. И в variant swarm есть динамический полиморфизм, т.к. он ведёт себя как набор std::variant<Ts...>.
Для тех случаев что вы описываете в библиотеке есть другие инструменты, такие как полиморфные ссылки и референсы, any_with<...> и подобное.Смысла в map<index> что то там я особого не вижу, потому что это не поможет компилятору инлайнить и оптимизировать код.
Это будет непоследовательная память и оптимизатору неизвестно когда один тип сменится другим(он даже не сможет понять из кода, что там есть какие то типы). Кроме того вам придётся оставить на элементах контейнера какие то части полиморфизма, либо продолжать их визитить, либо добавлять vtable, тогда как в текущем решении это могут быть абсолютно произвольные типы без каких-либо изощрений для того чтобы они вели себя полиморфно.iCpu
06.12.2022 10:28+3Так и std::variant - это статически полиморфный тип. Статический и динамический полиморфизм на примерах.
К вашей реализации вопросов нет. Вы введение к статье перепишите, вы там за динамику много пишите, а у вас её нет.
Kelbon Автор
06.12.2022 10:32variant это инструмент динамического полиморфизма, вы только на рантайме знаете что лежит в variant<Ts...> его поведение на динамике меняется в зависимости от того что там лежит
AnthonyMikh
07.12.2022 21:38-1int — это инструмент динамического полиморфизма, вы только в рантайме знаете, лежит ли там 0, 1 или 42. /s
Kelbon Автор
06.12.2022 10:21Например, пусть у нас есть типы А B и C, типичная ситуация, когда виртуальный метод не делает ничего для А, но делает полезную работу для B и какую-то мелочь для C.
Если вы имеетеstd::vector<Base*> x;При итерации и вызове .foo() оптимизатору ничего не останется, кроме как честно вызывать каждую из функций, даже если она не делает совершенно ничего.
Если же вы сделалиaa::variant_swarm<A, B, C> yто оптимизатор при вызове .visit_all видит, что сначала вызыватся в цикле .foo для A, которое ничего не делает - значит этот цикл можно вовсе выкинуть.
Затем вызывается в цикле .foo для B, это можно заинлайнить, оптимизировать и векторизовать.
Затем вызывается в цикле .foo для С, это можно также заинлайнить или убрать цикл, если возможно.
Таким образом сам по себе бенчмарк типичных ситуаций будет выглядеть абсурдно - ускорение в бесконечность раз, ведь был цикл, а теперь пусто
Ещё интересный вариант - увидеть что циклы можно объединить и схлопнуть, что иногда сильно ускоряет код.iCpu
06.12.2022 10:40+3Всё это хорошо. Но динамический полиморфизм называется динамическим потому, что я на этапе выполнения могу добавить тип
D- и у меня всё отработает корректно. Откуда я его добавлю? Не_твоего_ума_дело.dll подгружу, например.Kelbon Автор
06.12.2022 10:45-1
(нейросеть отвечает)
То что описываете вы это другое явление, одно из свойств какого-то вида полиморфизма, а не весь полиморфизмiCpu
06.12.2022 10:52+1В Java нет статического полиморфизма, в ней только динамический. Все методы там виртуальные - и инстанцируются jit'ом. Все типы наследуются от Object, а контейнеры хранят наследников интерфейса. По крайней мере, году в 2015 всё ещё было так.
Примите уже как данность, что всё, что имеет угловые скобки <> в C++ - это статика.
Kelbon Автор
06.12.2022 10:54-1
iCpu
06.12.2022 11:39+1Задаёшь неправильные вопросы.
@
Получаешь бесполезные ответы.Так спроси, что такое статический полиморфизм в C++.
И что, собственно, меня должно удивить в any_with? То, что там кто-то на std::any насыпал сверху vtable_ptr? Не, похвально, конечно, но по удобству на 5 шагов отстаёт от CRTP. Чтобы описать интерфейс, нужно туеву хучу лишних движений совершить.
Kelbon Автор
06.12.2022 12:02CRTP это статический полиморфизм.
any_with<...> это динамический полиморфизм. В том числе это работает при подключении длл.Советую разобраться в том о чём вы спорите
P.S. std::any уже содержит vtable с копированием и деструктором.
iCpu
06.12.2022 12:39У вас в статье сколько упоминаний any_with? Подсказываю,
Вы в статье писали про
basic_variant_swarmиdata_parallel_vector, а они не про динамический полиморфизм.Но да ладно, хватит спорить из-за фигни.
Kelbon Автор
06.12.2022 12:59Это был ответ на ваше утверждение, что всё в С++ с <> является "статикой"
Kelbon Автор
06.12.2022 10:55Тогда вам стоит увидеть это:
https://github.com/kelbon/AnyAny
(см. any_with<...>)
eao197
06.12.2022 14:30+1Прочитал статью, прочитал имеющиеся на данный момент комментарии. Увидел, что недостаточно комментариев о том, что статья не имеет отношения к динамическому полиморфизму, хотя вначале его и упоминает.
Так что этот комментарий призван исправить недостаток таких комментариев. Посему: статья не имеет отношения к динамическому полиморфизму и этот самый динамический полиморфизм вначале статьи был упомянут напрасно (либо с кликбейтной целью).
Kelbon Автор
06.12.2022 15:32На основании чего вы считаете, что variant_swarm<Ts...> не ведёт себя как контейнер полиморфных типов?
eao197
06.12.2022 15:38+2На том же основании, что и ув.тов. @iCpu. Динамический полиморфизм появляется тогда, когда мы в compile-time видим лишь абстрактный базовый тип A, а в run-time у нас может появится экземпляр любого другого типа X, который удовлетворяет интерфейсу A (в терминах C++: в compile-time мы имеем базовый тип A, в run-time любой наследник от A). Причем если в контейнере лежит сразу несколько значений (v1, v2, v3, ...), то каждый из них может принадлежать любому типу наследнику X1, X2, X3, ... Причем в том числе и тем типам-наследников, которых еще не существовало в момент компиляции нашего кода с контейнером.
Kelbon Автор
06.12.2022 16:10Нет, динамический полиморфизм это когда объект ведёт себя по разному в зависимости от своего динамического типа. Или функция ведёт себя по разному в зависимости от динамических типов своих аргументов
А вы описываете один единственный возможный для вас полиморфизм на виртуальных функциях.
eao197
06.12.2022 16:16Нет, динамический полиморфизм это когда объект ведёт себя по разному в зависимости от своего динамического типа.
Мне непонятно почему здесь "Нет", т.к. то, что вы написали является прямым следствием того, что описал я. Ведь если за интерфейсом A в динамике обнаруживается X, то мы как раз и получаем то поведение, которое реализует именно X. Если за A стоит не X, а Y, то получим поведение от Y. Вот вам и "ведет себя по разному".
А вы описываете один единственный возможный для вас полиморфизм на виртуальных функциях.
Просто в C++ вы по другому динамический полиморфизм и не получите.
И нет, ни std::variant, ни std::any не являются примерами динамического полиморфизма в C++, т.к. вам всегда нужно знать точный тип, который вы собираетесь извлечь из std::variant/any.
Kelbon Автор
06.12.2022 16:17-1Мне непонятно почему здесь "Нет", т.к. то, что вы написали является прямым следствием того, что описал я
потому что все караси рыбы, но не все рыбы караси. У вас логическая ошибка в определении динамического полиморфизма
eao197
06.12.2022 16:20Вы попробуйте подставить в мое описание вместо "A" своих "карасей", а вместо X -- свою "рыбу". А потом наоборот. И увидите, что "все караси рыбы, но не все рыбы караси". А так же и отсутствие логической ошибки, которая вам померещилась.
Kelbon Автор
06.12.2022 16:20И нет, ни std::variant, ни std::any не являются примерами динамического полиморфизма в C++, т.к. вам всегда нужно знать точный тип, который вы собираетесь извлечь из std::variant/any.
То есть std::visit и тот факт, что any можно не кастовать ни к чему и оно выполнит полиморфно копирование/деструктор вас не смущает
eao197
06.12.2022 17:27+2any можно не кастовать ни к чему и оно выполнит полиморфно копирование/деструктор вас не смущает
Не смущает, поскольку без знания того, что лежит внутри any практически никакой пользы от содержимого any не получить. За исключением некоторых вырожденных случаев.
bfDeveloper
Я так понял, что в векторе вы взяли magic_get (который нынче Boost.PFR) и развернули массив структур в структуру массивов. Интересное упражнение.
А что насчёт индексов и выборок? Для ECS же важно уметь выбирать наборы компонент. Типа для всех, содержащих компоненту Health и Collision, запустить систему нанесения урона при столкновении.
Kelbon Автор
Можете посмотреть на интерфейс контейнеров в хедерах, там есть выбор .view<Types...> и .view<Nbs...>, для variant_swarm тоже есть возможность посетить только нужные типы и посмотреть на только нужные
https://github.com/kelbon/AnyAny/blob/fbb1b0ea2c9a83f00ba18b657cbb68d7ab3b82b4/include/variant_swarm.hpp#L104
Kelbon Автор
Техника эта была известна ещё до Boost PFR и никаких зависимостей в библиотеке нет, можете посмотреть в noexport/data_parallel_vector_details.hpp как это реализовано