Полиморфные структуры данных и производительность

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

В С++ не так чтобы много способов получить из коробки динамический полиморфизм. Способов буквально два: виртуальные функции и std::variant.

Рассмотрим эти способы подробнее:

1. виртуальные функции:

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

struct base {   virtual ~base() = default; };  ... std::vector<base*> things;

Сразу проблемы:

• если нужен указатель, то как управлять памятью?

• если нужно копирование контейнера, то оно будет неправильным(скопируются указатели). И так как контейнер использует внутри конструкторы, нам ничего не остаётся кроме как написать свою обёртку или функцию копирования — что, вообще-то, крайне неудобно, затратно и опасно в плане багов

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

2. 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 систему в играх гораздо удобнее и эффективнее

Надеюсь статья была для вас интересна, предлагайте свои улучшения/идеи в комментариях!