«ECS — like» вектор на с++

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

И не смотря на их всеобъемлющую вариативность, в жизни встречаются ситуации когда один вектор не может решить задачу. Точнее может, но через костыли…

О чем я?

Странная на первый взгляд картинка, не о чем. Как она связана со статьей? Я вставил ее с одной целью, я хочу чтобы вы ответили на вопрос: что вы можете сказать о мяче?

Ну… у него есть позиция.

Но он же движется? значит у него есть позиция в каждый момент времени

однако у него также имеется скорость, ускорение, и прочие параметры, которые приходится хранить для каждого момента времени, если объект, тело или прочее имеет что имеет дискретный характер. И ладно если использовать сохраненные данные один раз, использовать их очень редко, и вообще их никак не модифицировать, то в целом можно обойтись парой векторов.

Однако когда речь заходит о прямой и частой работе с такими данными появляются сложности. Надо следить за синхронным состоянием данных:

std::vector<glm::vec3> pos;std::vector<double>    velocity;std::vector<double>    time;// Удаляем пятую точку из pos...pos.erase(pos.begin() + 5);// ...и забыли удалить этот элемент из velocity и time// Данные рассинхронизированы = баги

за типобезопасным доступом

std::vector<glm::vec3> pos;std::vector<double>    velocity;// Что хранится в 3-м векторе? ускорение? время?velocity[5] = glm::vec4(1.0f); // Ок, а что это за индекс 5?

за соответствием ответственности:

class GameObject {    glm::vec3 position;    // есть всегда    glm::vec3 velocity;    // есть у всего? или optional?    Light light;           // неужто все объекты могут светиться? };//лишнии потраченные ресурсы

На самом деле, что-то из этого можно решить упорством, жертвами, однако есть ресурс который гораздо важнее всего — время.

Почему?

Собственно начну с причины, которая заставила меня этим заняться.

Условно представим вертекс (вертекс — точка в пространстве, в графике — контейнер атрибутов, что не мешает ему хранить позицию подстать обыкновенной точке с позицией). У него есть атрибуты, основной — позиция. Теперь заглянем чуть дальше, вертексы привязаны к основному объекту в графике — к сеткам. Имея два вертекса, мы можем нарисовать линию, имея три, уже треугольник. А как правило треугольники — это основной ресурс в графике.

Однако треугольники далеко не абстрактный объект, особенно в графике. У него есть цвет, текстурные позиции, нормали для освещения, что логично подводит нас к концепции хранения параллельных данных.

А в чем проблема тупо хранить эти четыре атрибута? Этот вопрос возвращает нас к прошлом разделу, это проблема ответственности, зачем мне для линий текстурные координаты? Или зачем мне цвет для текстурированных объектов?

И ладно, если бы это было так легко. Клепать N! классов мешей, где N — число атрибутов. И в действительности, этот подход имеет место — в продакшене. Крупные игровые движки в коммерческой разработке пишут сотни таких классов, сотни обработчиков сеток. Все из-за простоты. Это до тупого простой вариант решения проблемы. Благодаря нему, легко объяснять архитектуру движка новым сотрудникам, ускоряется время компиляции. Одни плюсы… Но в одиночку это тяжелая и унылая задача, поэтому я решил сделать красиво и удобно для будущей работы с графикой. Собственно мой тип данных решает все указанные выше проблемы.

Чтобы понять, как именно мой тип данных решает эти проблемы, сначала посмотрим на два способа хранения параллельных данных в памяти.

SoA и AoS

Параллельные данные можно хранить двумя способами. Самый очевидный это массив структур(AoS):

struct Particle {  float x, y, z; // Координаты по трем осям  float vx, vy, vz; // Скорости по трем осям  float ax, ay, az; // Ускорения по трем осям};std::vector<Particle> particles(N);

И второй вариант — структура массивов(SoA), то как мы смотрели на хранение данных в начале статьи:

struct Particles {  std::vector<float> x, y, z; // Координаты по трем осям  std::vector<float> vx, vy, vz; // Скорости по трем осям  std::vector<float> ax, ay, az; // Ускорения по трем осям};

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

Если интересно, насколько SoA быстрее AoS, то вот хорошая статейка:

Принципы DOD в C++: Часть 2. AoS, SoA. Мнимая панацея для быстродействия

Приветствую всех, кто хочет делать свой код быстрым и оптимальным. Традиционно, если нам нужно больш…

habr.com

Ecs-like вектор

Почему вообще «ECS-like»? Если вспомнить классический паттерн Entity-Component-System, то там сущность (Entity) — это по сути просто индекс, пустой идентификатор. А все данные размазаны по плоским массивам компонентов. Мой контейнер делает ровно то же самое: логический «элемент» (будь то вертекс или физическая частица) существует только как индекс i. А его данные параллельно лежат в соответствующих векторах.

Определившись с концепцией хранения данных, остается вопрос, как это все реализовать?

Я пишу на с++, и лучшим кандидатом на роль хранителя является std::tuple.

#include <tuple>int main() {  std::tuple<int, float> data;  // обращение к полю через std::get<номер элемента>(объект);  std::get<0>(data) = 3;  std::get<0>(data) = 5.3f;}  //текущее содержимоей тупла - data {3, 5.3f}

Казалось бы, идеальное решение!

Берем std::tuple<std::vector<T1>, std::vector<T2>, ...> и все готово. Доступ можно организовать через std::get<T>, компилятор сам все выведет!

Сначала я так и подумал. А потом столкнулся с небольшими проблемами. Допустим, я хочу хранить позицию объекта и его скорость. И то, и другое в моем движке — это обычный трехмерный вектор glm::vec3. И вот тут std::tuple показывает проблемы: если мы попросим std::get<std::vector<glm::vec3>>, компилятор просто выпадет в осадок. У нас в кортеже два одинаковых типа! Как он должен понять, куда мы хотим обратиться — к позиции или к скорости?

Конечно, можно обращаться по индексу: std::get<0> для позиции, std::get<1> для скорости… Но будем честны, такой код убивает всю читаемость и превращает проект в абра-кадабру. Чуть не уследил, перепутал индексы, и треугольник улетел за пределы экрана.

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

#include <vector>#include <glm/glm.hpp>struct Position {  using type = glm::vec3;};struct Velocity {  using type = glm::vec3;}int main() {  std::vector<typename Position::type> points;  std::vector<typename Velocity::type> velocities;}// Вуаля - по факту это два одинаковых вектора, но теперь мы можем отличить их по тегу

Идея проста: мы не храним «просто вектора типов», мы привязываем их к уникальным структурам-маркерам. Мы создаем легковесные структуры (например, Position или Color), внутри которых жестко определяем реальный тип данных (тот же glm::vec3 или glm::vec4), а заодно можем задать дефолтные значения.

Теперь для компилятора это абсолютно разные сущности. Мы просим у нашего контейнера не абстрактный вектор флоатов, а вектор, строго привязанный к конкретному тегу. Это решает проблему коллизии типов в std::tuple и делает API невероятно выразительным.

attribute_vector — как ответ запросу

Собственно для большей наглядности перейдем к документации.

Прежде всего, чуть ближе рассмотрим какие что требуется от структур-тегов:

struct Имя_тега {  using type = имя_типа_данных;  static type defaultValue() { return дефолтное_значение_для_тега; }};

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

В качестве примеров тегов я приложил заголовочный файл tags.h

#pragma once#include <glm/glm.hpp>namespace engine {struct Position {using type = glm::vec3;static type defaultValue() {return glm::vec3(0.f, 0.f, 0.f);}};struct Color {using type = glm::vec4;static type defaultValue() {return glm::vec4(0.f, 0.f, 0.f, 0.f);}};struct TexCoords {using type = glm::vec2;static type defaultValue() {return glm::vec2(0.f, 0.f);}};}

Здесь представлены, наверное, самые используемые теги для графики, и на их основе вы можете писать свои теги. Теперь можно приступить и к примеру пользования самим типом данных. Кстати в моем репозитории есть .спп файл с тестами engine/tests/test.cpp, почти всех основных функций, тем не менее, ниже я все равно продемонстрирую самые прикольные вещи для которых я и делал это:

Конструирование

#include <attribute_vector/attribute_vector.h>int main() {  // Конструктор по умолчанию  default_vector<Position, Color, TexCoords> vec;  // Конструктор с заданым размером  default_vector<Position, Color> vec(5);  // Конструктор с инит_листами(важен порядок и соответствие типов листов с тегами)  default_vector<Position, Color> vec(      { glm::vec3(0,0,0), glm::vec3(1,1,1), glm::vec3(2,2,2) },      { glm::vec4(1,0,0,1), glm::vec4(0,1,0,1), glm::vec4(0,0,1,1) }  );  // Отсутствие когерентности контейнеров ловится на этапе компиляции,  // так что можете не бояться, если ошибетесь. Вы сразу узнаете  default_vector<Position, Color> vec(    { glm::vec3(0,0,0) },    { glm::vec4(1,0,0,1), glm::vec4(0,1,0,1) }  // разный размер!);}

default_vector?

Да, но я не хочу смутить вас этим названием. По сути это и есть attribute_vector. А дефолт_вектор это псевдоним атрибут_вектора, который в качестве контейнера данных использует stl::vector. Я обозначил отдельный алиас в связи с тем, что атрибут_вектор может хранить не только stl::vector так что да, контейнерами SoA в атрибут_векторе могут быть и другие контейнеры, вроде stl::array или std::deque , но с важной оговоркой, однако вернемся к этому позднее.

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

Запись и чтение

Получить доступ к одному атрибуту:

#include <attribute_vector/attribute_vector.h>int main() {  // атрибут_вектор с размером = 1  default_vector<Position, Color, TexCoords> vec(1);  auto positions = vec.attribute<Position>();  positions[0] = glm::vec3(1.0f, 0.0f, 0.0f);}

attribute<Tag>() возвращает объект, который ведёт себя как ссылка на std::vector<Tag::type>. Можно читать, писать, брать .data(), итерироваться.

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

Для работы с несколькими атрибутами одновременно — with<Tags...>():

#include <attribute_vector/attribute_vector.h>int main() {  default_vector<Position, Color, TexCoords> vec(1);  auto proxy = vec.with<Position, Color>();}

proxy — это «окно» в выбранные атрибуты. Все операции через него применяются к каждому из выбранных векторов одновременно.

Добавление элементов

#include <attribute_vector/attribute_vector.h>int main() {  default_vector<Position, Color, TexCoords> vec(1);  auto proxy = vec.with<Position, Color>();  // Один элемент в конец  proxy.push_back(      glm::vec3(0.0f, 0.0f, 0.0f),      glm::vec4(1.0f, 0.0f, 0.0f, 1.0f)  );    // Несколько одинаковых элементов в середину  proxy.insert(2, 5,      glm::vec3(0.0f),      glm::vec4(1.0f)  );    // Из init-листов  proxy.insert_list(0,      { glm::vec3(0,0,0), glm::vec3(1,1,1) },      { glm::vec4(1,0,0,1), glm::vec4(0,1,0,1) }  );}

Возможно, вы предположите: а что происходит вектором не включенным в with? А все просто, когда вы, условно, пушите по одному элементу в мульти_прокси (with возвращает тип данных multi_proxy), то те контейнеры, что не включены в мульти_прокси, но есть в коллекции атрибут_вектора, будут заполнены дефолтными значениями, как раз теми самыми, что мы указываем в тегах. И так происходит со всеми операциями что изменяют состояние размера вектора.

Удаление

proxy.erase(1);       // один элементproxy.erase(0, 3);    // диапазон

Размер и вместимость

proxy.size();         // текущий размерproxy.capacity();     // вместимостьproxy.resize(20,    glm::vec3(0.0f),    glm::vec4(0.0f));proxy.reserve(100);

Вставка из другого прокси

С этого момента становится интереснее. Это еще одна крутейшая возможность — возможность включения подмножеств в надмножества.

Допустим, есть два набора данных с разными тегами:

default_vector<Position, Color, TexCoords> bigMesh(10);default_vector<Position> smallMesh(3);

Благодаря этой возможности smallMesh можно вставить в bigMesh:

bigMesh.with<Position, Color, TexCoords>()    .insert(2, smallMesh.with<Position>());

Теги, которые есть в обоих векторах — скопируются. Теги, которых нет в источнике (Color, TexCoords) — заполнятся значениями по умолчанию. Размеры всех векторов остаются одинаковыми.

Работает и в обратную сторону. Если источник шире приёмника — скопируются только пересекающиеся теги, остальные игнорируются.

Upload

Метод upload работает как insert, но не добавляет новые элементы, а перезаписывает существующие, начиная с указанной позиции:

auto target = bigMesh.with<Position, Color>();auto source = smallMesh.with<Position>();target.upload(5, source);  // запишет данные поверх, начиная с индекса 5

Если источник не покрывает все теги приёмника — недостающие просто не трогаются. Это удобно для частичного обновления GPU-буферов.

Прямой доступ к данным для GPU

Поскольку данные хранятся как отдельные массивы, их можно напрямую передавать в OpenGL:

auto proxy = mesh.with<Position, TexCoords>();glBufferSubData(GL_ARRAY_BUFFER, 0,    proxy.size() * sizeof(glm::vec3),    proxy.vector<Position>().data());

Никакой сборки interleaved-буферов на CPU. Данные уже лежат именно так, как их ожидает вершинный шейдер.

Про attribute_vector

Собственно теперь можно рассказать про сам attribute_vector, то из-за чего я и пишу статью.

template<template<typename...> typename Vec, typename... Tags>class attribute_vector;

Первый шаблонный аргумент attribute_vector — это контейнер: std::vector, std::array, std::deque, или что-то своё. Возможность его подмены есть третья крутейшая опция этого типа данных.

default_vector

В примерах выше я использовал default_vector. Это алиас:

template<typename... Tags>using default_vector = attribute_vector<std::vector, Tags...>;

Но std::vector — не единственный вариант. Первый аргумент задаёт, в чём именно хранятся данные каждого атрибута.

Какие контейнеры подходят

Подходит любой контейнер, который ведёт себя как std::vector<T>:

• Имеет value_type

• Умеет push_back, insert, erase, resize, reserve

• Даёт доступ к сырым данным через .data() и .size()

• Имеет begin() и end()

Примеры из стандартной библиотеки:

Пример с std::deque

attribute_vector<std::vector, ParticlePos, ParticleVel, ParticleLife, ParticleColor> particles;// Симуляция: только позиция и скоростьauto sim = particles.with<ParticlePos, ParticleVel>();for (size_t i = 0; i < sim.size(); i++) {    sim.attribute<ParticlePos>()[i] += sim.attribute<ParticleVel>()[i] * dt;}// Рендер: только позиция и цветrenderer.draw(particles.with<ParticlePos, ParticleColor>());

Работает почти так же, как с вектором. Быстрая вставка в начало — как следует из документации deque. Но proxy.vector<Position>().data() не скомпилируется: у deque нет сплошного куска памяти. Однако он все же может скомпилироваться на некоторых компиляторах, однако я не советую этим пользоваться в своих проектах, если вам необходим deque, то лучших вариантом будет сделать обертку с методом .data(). Пример такого будет дальше.

std::array и константный размер

Можно хранить данные в std::array:

template<typename... Tags>using array_vector = attribute_vector<std::array, Tags...>;

Но здесь появляется нюанс. std::array не умеет resize, push_back или insert — его размер фиксирован на этапе компиляции. Поэтому array_vector нельзя передавать в функции, которые меняют размер. Компилятор может выдать:

error: 'class std::array<...>' has no member named 'push_back'

Это не баг. Это как с deque. Если контейнер фиксирован — данные фиксированы. Если контейнер динамический — данные можно масштабировать. Может в будущих версиях я сделаю рефлексию методов контейнера и буду отсекать то что контейнер не умеет делать, в этом контексте, уже можно будет использовать deque и array без страха.

Свой контейнер

Но уже сейчас, вам ничто не мешает написать обёртку над типом, в моем случае мне понадобился std::vector , который может хранить версию данных. VersionedVector, который я покажу дальше — он добавляет счётчик версий и ведёт себя как std::vector. attribute_vector работает с ним без изменений. В этом и заключается гибкость attribute_vector.

Только графика?

Не смотря на невероятно крутую совместимость с графикой, атрибут_вектор может служить далеко не только для нее, например:

Частицы

Частицы имеют позицию, скорость, время жизни, цвет, размер. Все свойства меняются каждый кадр. SoA-раскладка позволяет симуляции обрабатывать только нужные атрибуты (скорость и позицию), а рендеру — загружать только позицию и цвет, не трогая скорость.

attribute_vector<std::vector, ParticlePos, ParticleVel, ParticleLife, ParticleColor> particles;// Симуляция: только позиция и скоростьauto sim = particles.with<ParticlePos, ParticleVel>();for (size_t i = 0; i < sim.size(); i++) {    sim.attribute<ParticlePos>()[i] += sim.attribute<ParticleVel>()[i] * dt;}// Рендер: только позиция и цветrenderer.draw(particles.with<ParticlePos, ParticleColor>());

Таблицы в in-memory базе данных

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

attribute_vector<std::vector, Name, Age, Salary, Department> employees;// Выбрать имена и зарплаты всех, кто старше 30auto view = employees.with<Name, Age, Salary>();for (size_t i = 0; i < view.size(); i++) {    if (view.attribute<Age>()[i] > 30) {        std::cout << view.attribute<Name>()[i] << ": " << view.attribute<Salary>()[i]         << '\n';    }}

Временные ряды

Положение, цена, объём, временная метка — параллельные массивы. SoA позволяет быстро считать скользящие средние, строить графики.

attribute_vector<std::vector, Price, Volume, Timestamp> ticker;auto proxy = ticker.with<Price, Timestamp>();// Строим график: цена от времениplot(proxy.attribute<Timestamp>(), proxy.attribute<Price>());

Редактор свойств / Inspector как в Unity

Компоненты объекта (Transform, MeshRenderer, Collider) — это не классы, а проекции на подмножества тегов. Для редактора очень удобно.

attribute_vector<std::vector, Transform, MeshRenderer, Collider, Script, Tag> entities;// Получить все трансформы для окна сценыauto transforms = entities.attribute<Transform>();// Получить всё для инспектора конкретного объектаauto inspector = entities.with<Transform, MeshRenderer, Collider, Script>();inspector.upload(5, incomingData); // обновить из редактора

Событийная система

События имеют тип, временную метку и разную полезную нагрузку (позицию для клика, кнопку для ввода и т.д.). Можно хранить в одном контейнере, не плодя иерархии классов.

struct EventType { using type = int; /* ... */ };struct EventTime { using type = double; /* ... */ };struct MousePos  { using type = glm::vec2; /* ... */ };struct KeyCode   { using type = int; /* ... */ };attribute_vector<std::vector, EventType, EventTime, MousePos, KeyCode> events;// Обрабатываем клики: нужны Position и Timefor (auto& [pos, time] : events.with<MousePos, EventTime>()) { ... }// Обрабатываем ввод: Type и KeyCodefor (auto& [type, key] : events.with<EventType, KeyCode>()) { ... }

Нейронные сети

Веса и градиенты для каждого слоя хранятся как отдельные массивы. SoA упрощает батчирование и загрузку в GPU-буферы.

attribute_vector<std::vector, Weights, Biases, Gradients, Activations> layers;

Хотелось бы добавить, что attribute_vector не пытается заменить ECS-фреймворки. Он решает конкретную задачу: хранение гетерогенных данных с гарантией когерентности. Если вам приходилось вручную синхронизировать несколько векторов — вы знаете, зачем он нужен. Если нет — возможно, однажды он сэкономит вам вечер отладки.

Спасибо за внимание

Это моя первая статья на Хабре, но писал я ее стараясь. Так что открыт к конструктивной критике в комментариях. Если интересны детали реализации атрибут_вектора, то напишите об этом в комментарии, возможно кому то будет интересно, как я все это сделал. Кстати, ссылка на мою репу.