Полиморфные структуры данных и производительность
В этой статье мы рассмотрим как обычно происходит работа с динамическим полиморфизмом, где теряется производительность и как её можно улучшить, используя интересные структуры данных.
В С++ не так чтобы много способов получить из коробки динамический полиморфизм. Способов буквально два: виртуальные функции и std: variant.
про std: any
std: any неприменим нигде кроме каких-то костылей в dll и про него лучше забыть, благо есть аналоги с гораздо большим потенциалом, но об этом в другой статье
Рассмотрим эти способы подробнее:
виртуальные функции:
позволяют создать контейнер указателей на базовый тип, а потом складывать туда любых наследников.
struct base {
virtual ~base() = default;
};
...
std::vector things; Сразу проблемы:
если нужен указатель, то как управлять памятью?
если нужно копирование контейнера, то оно будет неправильным (скопируются указатели). И так как контейнер использует внутри конструкторы, нам ничего не остаётся кроме как написать свою обёртку или функцию копирования — что, вообще-то, крайне неудобно, затратно и опасно в плане багов
так как в контейнере лежат элементы с разными указателями на vtable, процессор и компилятор не состоянии предугадать vtable какого типа лежит следующим и это приводит к постоянным кеш-мисам, что значительно замедляет и итерацию и в целом использование подобного контейнера.
нестандартные альтернативы
проблемы с лишними аллокациями памяти и копированием/удобством в целом отлично решаются решениями основанными на стирании типов, например https://github.com/kelbon/AnyAny, но это не тема этой статьи
std: variant
позволяет складывать любые из *известных заранее* типов в контейнер
using myvar = std::variant;
...
std::vector things; Это решает проблемы с конструкторами и выделением памяти, к тому же элементы теперь расположены более менее локально. Но это вносит кучу своих проблем:
типы должны быть известны заранее, невозможны «рекурсивные» структуры данных, например AST на варианте уже не напишешь
Любое увеличение количества типов должно изменить ВСЕ сигнатуры всех функций использующих этот вариант. Как минимум придётся перекомпилирвать весь проект
void foo (const std: variant
просто сломается при введении ещё одного типа
Проблемы с исключениями и неэффективность при большой разнице sizeof
К тому же у обоих рассмотренных вариантов нет опции быстро посмотреть только интересующие типы, придётся идти и к тому же заниматься динамическим кастом/визитом
Заметим, что часто нам нужен именно контейнер полиморфных типов, а не просто одна штука. Также я уже упомянул про то, что неплохо бы уметь предсказывать какой тип будет следующим. Это приводит нас к идее сортировать значения внутри контейнера по типу! Хм, интересно. И это действительно значительно улучшает производительность при итерации, но согласитесь как-то неудобно и затратно, к тому же придётся каждый раз при вставке и удалении думать об этом.
А как это исправлять?
Я пошёл дальше, почему бы не сделать контейнер ведущий себя как контейнер из variant
Кстати, об интерфейсе, нам нужны операции:
вставка для каждого типа T из Ts…
удаление для каждого типа T из Ts…
просмотр контейнера для типа T
аналог посещения (visit) для всех значений контейнера
К тому же кажется, что контейнер может быть разным в зависимости от задачи, так что сделаем его кастомизируемым. Назвал я это чудо variant_swarm (буквально рой вариантов)
Итак, как реализовать это? Всё довольно просто:
// БАЗА с настомизируемым контейнером
template typename Container, typename... Ts>
struct basic_variant_swarm {
private:
std::tuple...> containers;
public:
// операция "посмотреть контейнеры для типов Types..."
auto& view();
// операция "посетить все типы из контейнеров для Types..."
void visit(visitor);
// операция вставки, перегруженная для каждого из типов Ts...
auto insert(*сложный момент* auto value)
// операция вставки, перегруженная для каждого из типов Ts...
auto erase(*сложный момент* auto iterator)
};
// алиас для самого частого случая
template
using variant_swarm = basic_variant_swarm; Конечно всё немного сложнее и это очень условный минимальный набор. Но в целом всё понятно — у нас есть tuple из контейнеров для каждого типа и перегруженные под каждый тип операции. Это интуитивно и просто.
Использовать это можно примерно так:
variant_swarm 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;});
Полный код можно посмотреть здесь: https://github.com/kelbon/AnyAny/blob/main/include/variant_swarm.hpp
Обратите внимание, значения будут появляется в 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 things;
// использование structured binding из С++17
auto [a, b, c] = things;
// реализуемо?) Итак, посмотрим как выглядит каркас реализации:
// конечно мы поддерживаем аллокаоры, мы же серьёзные люди!
template >
struct data_parallel_vector {
private:
// как доставать поля?
std::tuple...> field_containers;
public:
using iterator; // как делать итератор?
// операция "посмотреть поля по номерам Nbs..."
// Отмечу, что она не может возвращать ссылку на контейнер,
// потому что тогда юзер может сломать инварианты нашего контейнера
// например удалить элементы
template
constexpr std::span<...> view();
// тут все операции которые поддерживаются вектором
// и могут поддерживаться нашим контейнером, а их крайне много...
}; Тут С++ явно бросает нам вызов, чего только стоит специализация std: vector
Для реализации итератора достаточно заметить, что для I-того элемента в каждом контейнере лежит I-тое его поле. Поэтому мы можем создать random access итератор состоящий из тупла итераторов на контейнеры.
Остальное — лучше смотреть в реализации, иначе статья будет больше хабра. Кстати, реализация полностью тут:
https://github.com/kelbon/AnyAny/blob/main/include/data_parallel_vector.hpp
Пример использования (да, это работает):
struct mytype {
int i;
float d;
bool x;
};
...
data_parallel_vector things;
// a, b, c это здесь std::span span и span
auto [a, b, c] = things;
// А вы что, думали это нереализуемо? Итоги
Мы реализовали контейнер сум-типов, который позволяет совершенно без оверхеда и удобно использовать рантайм полиморфизм подобный контейнеру std: variant
И контейнер-тип-произведение, который ведёт себя как std: vector
Надеюсь статья была для вас интересна, предлагайте свои улучшения/идеи в комментариях!
