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

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

В С++ не так чтобы много способов получить из коробки динамический полиморфизм. Способов буквально два: виртуальные функции и 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 систему в играх гораздо удобнее и эффективнее

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