В программировании частая задача это работа с последовательными элементами. В этой, порой непростой задаче, нам часто помогают вектора. Вектора бывают самыми разными от 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, то вот хорошая статейка:
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;
// Выбрать имена и зарплаты всех, кто старше 30
auto 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 и Time
for (auto& [pos, time] : events.with<MousePos, EventTime>()) { ... }
// Обрабатываем ввод: Type и KeyCode
for (auto& [type, key] : events.with<EventType, KeyCode>()) { ... }Нейронные сети
Веса и градиенты для каждого слоя хранятся как отдельные массивы. SoA упрощает батчирование и загрузку в GPU-буферы.
attribute_vector<std::vector, Weights, Biases, Gradients, Activations> layers;Хотелось бы добавить, что attribute_vector не пытается заменить ECS-фреймворки. Он решает конкретную задачу: хранение гетерогенных данных с гарантией когерентности. Если вам приходилось вручную синхронизировать несколько векторов — вы знаете, зачем он нужен. Если нет — возможно, однажды он сэкономит вам вечер отладки.
Спасибо за внимание
Это моя первая статья на Хабре, но писал я ее стараясь. Так что открыт к конструктивной критике в комментариях. Если интересны детали реализации атрибут_вектора, то напишите об этом в комментарии, возможно кому то будет интересно, как я все это сделал. Кстати, ссылка на мою репу.
Автор: Desertoad
