Всем привет! Это продолжение статьи про мою ECS в моём движке Stellar Forge, и сегодня я хочу поднять тему архитектуры и немного более подробно раскрыть data oriented design в контексте ECS.
Первую часть можно найти здесь - https://habr.com/ru/articles/972708/ .

Итак, ECSS - Entity Component System with Sectors. В прошлой статье я описал что такое ECS и как его можно приготовить, а сегодня я расскажу вам в чем особенность моей ECS, что такое Sector, как эти секторы хранятся в памяти и что делает мою ECS такой быстрой.

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

Мы остановились на том что у нас есть:

struct Transform {//only data};
struct PhysicsComp {};
struct IsRenderable {bool is = true; };
struct Mesh{};
  
uint32_t entityId;
std::vector<entityId> entities;

std::map<Transform> t;
std::map<PhysicsComp> p;
std::map<IsRenderable> r;
std::map<Mesh> m;

Core::Update(float dt){
  std::vector<entityId>& world = GetWorld();
  for (auto& entity : world) {
    // Updater объектов это система - 
    PhysicsSys::Update(t[entity]);
    TransformSys::Update(p[entity]);
  }

  // сделаем вид что это другой поток
  for (auto& entity : world) {
    RenderSys::Draw(r[entity], m[entity]);
  }
}

Очевидно, что это не супер быстрая и оптимальная реализация ECS :)

Искать в мапах компоненты дорого, итерироваться по ним - невероятно дорого. Расширять это неудобно и сложно.

Registry

Нам нужна одна точка "входа" в мир ECS, этакий менеджер всех сущностей и компонентов - интерфейс взаимодействия с компонентами и сущностями.
Он отвечает за:

• создание компонентов

• удаление компонентов

• разметку секторов

• доступ к компонентам

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

Как хранить компоненты в реестре?

Очевидное решение - std::vector<ComponentsArray<ComponentTypes...>>.
И вот тут C++ вставляет палки в колеса телеги прогресса. Нельзя просто так взять и (С) сделать массив объектов некоего неизвестного конечного типа. Типы компонентов должны быть известны на этапе компиляции, а значит ComponentsArray не должен ничего знать про ComponentTypes.

Ниже я расскажу как решил эту проблему.

Sector - единица памяти

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

Так я и пришел к Sector. Это фиксированный блок памяти, в котором хранятся данные нескольких компонентов одновременно. Основная идея - иметь возможность объединять в одном секторе те компоненты, которые встречаются чаще всего и участвуют в самых горячих путях. Например, mesh и transform. Sector позволяет комбинировать до 32 компонентных слотов. При этом снаружи каждый компонент по-прежнему выглядит как отдельный объект, доступ к нему не отличается от обычного.

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

Важно, что такой layout довольно предсказуем для префетчера процессора. Когда данные компонентов лежат плотными блоками и идут строго подряд, префетчер начинает заранее подтягивать следующие кэш-линии, потому что паттерн чтения становится линейным. Даже если между последовательными transform-ами лежат данные mesh (или других компонентов), они всё равно находятся в пределах одного большого смежного блока памяти. В итоге процессор тратит меньше времени на случайные обращения и чаще попадает в L1/L2, а это и даёт тот самый прирост скорости.

Sector Layout

В первую очередь - нужно разметить память сектора под компоненты.

И эта разметка должна быть максимально быстрой.

Что может быть быстрее, чем compile time разметка?

// Types.h

template <typename Base, typename... Types>
struct OffsetArray {
    template<size_t N, size_t A>
    static consteval size_t align_up() noexcept {
        if constexpr((N & (N - 1)) == 0) {
            return (N + A - 1) & ~(A - 1);
        } else {
            return (N + (A - 1)) / A * A;
        }
    }

    static constexpr size_t count = sizeof...(Types);
    static constexpr size_t baseSize = align_up<sizeof(Base), alignof(Base)>();

    template <size_t I>
    static consteval size_t get() {
        using Tup = std::tuple<Types...>;
        using Cur = std::tuple_element_t<I, Tup>;
        if constexpr (I == 0) {
            return align_up<baseSize, alignof(Cur)>();
        }
        else {
            using Prev = std::tuple_element_t<I - 1, Tup>;
            constexpr size_t prev = get<I - 1>();
            return align_up<prev + sizeof(Prev), alignof(Cur)>();
        }
    }

    template <size_t... Is>
    static consteval std::array<size_t, count> make(std::index_sequence<Is...>) {
        return { get<Is>()... };
    }

    static constexpr uint32_t max_align = []{
        uint32_t m = alignof(Base);
        ((m = m < alignof(Types) ? alignof(Types) : m), ...);
        return m;
    }();

    static constexpr std::array<size_t, count> offsets = make(std::make_index_sequence<count>{});
    static constexpr size_t totalSize = align_up<offsets.back() + sizeof(std::tuple_element_t<count - 1, std::tuple<Types...>>), max_align>();

    template<class T, std::size_t Off>
    static consteval void check_one() {
        static_assert(Off % alignof(T) == 0, "component misaligned");
    }

    static consteval void static_checks() {
        []<std::size_t... Is>(std::index_sequence<Is...>) {
            (check_one<std::tuple_element_t<Is, std::tuple<Types...>>, offsets[Is]>(), ...);
        }(std::make_index_sequence<count>{});
        static_assert(totalSize % max_align == 0, "stride must be multiple of max_align");
    }
};

Я не понимаю как это работает (C)

Эта страшная метамагическая штука рекурсивно проходится по всем типам и считает offset и align для каждого, после чего сохраняет их в constexpr-массивы. Технически я здесь конструирую кастомный layout структуры под разные типы объектов. Далее эти compile-time данные хранятся в массиве секторов и используются для получения смещения до компонента в секторе.

// SectorLayoutMeta.h 

struct LayoutData {
    struct FunctionTable {
        void (*move)(void* dest, void* src);
        void (*copy)(void* dest, const void* src);
        void (*destructor)(void* src);
    };

    FunctionTable functionTable; // Type-erased operations for this component.
    size_t typeHash = 0;         // Optional: stable hash/ID of the component type.
    uint32_t isAliveMask = 0;    // Bit(s) set when the component is alive/present.
    uint32_t isNotAliveMask = 0; // Bit mask used to clear liveness (often ~isAliveMask & mask_width).
    uint16_t offset = 0;	     // Byte offset of the component within the Sector payload.
    uint16_t index = 0;          // Index of this component within the Sector layout.
    bool isTrivial = false;      // True if the component is trivially destructible/copiable/movable.
};

Meta (наш layout) - это static-данные. Они создаются один раз, переиспользуются, хранятся в static-пространстве и передаются в контейнер как аргумент конструктора. По сути, это легковесная рефлексия, которая даёт быстрый доступ к информации о размещении компонентов.

У каждого компонента есть свой id, по которому можно найти:

//SectorLayoutMeta.h

template<typename T>
inline static size_t TypeId() { return TypeIdImpl<std::remove_const_t<std::remove_pointer_t<std::remove_reference_t<T>>>>(); }

Далее все данные компонента кладутся в LayoutData, и это используется в секторе для расстановки.

//SectorLayoutMeta.h

template<typename U>
inline void initLayoutData(LayoutData& data, uint8_t& index, uint16_t offset) const noexcept {
    static_assert(std::is_move_constructible_v<U>, "Type must be move-constructible for use in SectorsArray");

    data.typeHash = SectorLayoutMeta::TypeId<U>();
    data.offset = offset;
    data.index = index++;
    data.isAliveMask = static_cast<uint32_t>(1u << data.index);
    data.isNotAliveMask = ~(data.isAliveMask);
    data.isTrivial = std::is_trivially_copyable_v<U>;

    data.functionTable.move = [](void* dest, void* src) { new(dest) U(std::move(*static_cast<U*>(src))); };

    data.functionTable.copy = [](void* dest, const void* src)
    {
        if constexpr (std::is_copy_constructible_v<U>) {
            new(dest) U(*static_cast<const U*>(src));
        }
        else { assert(false && "Attempt to copy a move-only type!"); }
    };

    data.functionTable.destructor = [](void* src) { std::destroy_at(static_cast<U*>(src)); };
}

Если компонент trivially copyable, то я могу обращаться с ним как с POD, и это даёт возможность очень быстро перемещать данные внутри массива. Поэтому эту информацию я тоже сохраняю в данные layout-а. Это позволяет контейнеру понимать, можно ли копировать компонент простым memcpy, или нужен полноценный конструктор/деструктор.

// SectorLayoutMeta.h 

template<typename... Types>
void initData()	{
    count = types::OffsetArray<Dummy::Sector, Types...>::count;
    totalSize = types::OffsetArray<Dummy::Sector, Types...>::totalSize;
    size_t idx = 0;
    ((typeIds[idx++] = TypeId<Types>()), ...);

    initLayoutData<Types...>();
    for (size_t i = 0; i < count; i++) {
        mIsTrivial = mIsTrivial && layout[i].isTrivial;
        if (!mIsTrivial) {
            break;
        }
    }
}

Окей, данные разметили, но мы пока не знаем, находится ли в секторе конкретный компонент. Как это узнать? Хранить информацию отдельно - неудобно и не кэш-френдли. Значит, положим её в сам сектор. В начало сектора нужно добавить данные о "живости" компонентов в нём.

Можно было бы взять std::bitset и тоже положить его в начало сектора (оказалось медленно и неудобно).

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

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

Два объекта по 4 байта как раз удачно элайнятся в 8 байт (совпадение, не иначе).

// Sector.h

struct alignas(8) Sector final {
    SectorId id;
    uint32_t isAliveData;
}

С точки зрения языка, Sector - это только Header, данные лежат сразу после него. Но логически, Sector - это всё вместе: и заголовок, и битовые маски, и массивы компонентных данных.

Память можно представить так:

[     id      ]
[ isAliveData ] // битовая маска наличия компонентов в секторе
[ ComponentA  ]
[ ComponentB  ]
[ ComponentC  ]
...

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

Очевидная проблема, которую я планирую исправить в следующих апдейтах - 4 байта isAlive это оверхед для сектора, в котором только один компонент (а это довольно частый кейс, так как группировать компоненты часто явно не нужно и даже может быть вредно).

Я пробовал добавлять 1 байт, и даже 1 бит под bool в начале каждого компонента (и в конце, каюсь, чтобы заиспользовать память, зарезервированную под alignment компонента, и сделать хранение isAlive почти бесплатным) для того, чтобы избежать ограничений на количество компонентов и сократить оверхед по памяти.

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

И один isAlive на сектор позволяет нам бесплатно узнавать, что весь сектор мертв, через isAlive == 0. Это пригодится в будущем для дефрагментации (да, такое у меня тоже есть).

Sectors Array

Мы плавно подошли к вопросу организации этих секторов в памяти. Как компоненты лежат в секторе - понятно, но как сами секторы лежат в памяти?
По чему итерироваться быстрее всего?
Правильно, по сишному массиву! (contiguous memory вам о чем-нибудь говорит? (С) женщина в кандибобере)

Нужно уложить эти данные как можно плотнее в памяти, и каждая деталь должна работать максимально быстро. Выше я упоминал, что у C++ есть одно легкое неудобство: все типы данных должны быть известны во время компиляции, и нельзя положить объекты разных типов в один std::vector. В обычном случае это можно решить через виртуализацию, но зачем нам этот рантайм-оверхед (если повезет - не рантайм, но на везение я рассчитывать не хочу)?

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

Массив секторов - не темплейтный класс, данные о разметке компонентов передаются в виде SectorLayoutMeta.

// SectorsArray.h

private:
    SectorsArray(SectorLayoutMeta* meta, Allocator&& allocator = {}) : mAllocator(std::move(allocator)) { mAllocator.init(meta);
        mSectorsMap.storeVector();
    }

public:
    template <typename... Types>
    static SectorsArray* create(Allocator&& allocator = {}) { static_assert(types::areUnique<Types...>, "Duplicates detected in SectorsArray types!");
        static SectorLayoutMeta* meta = SectorLayoutMeta::create<Types...>();
        return new SectorsArray(meta, std::move(allocator));
    }

И мы можем хранить этот массив внутри обычного stl контейнера, хотя фактически он хранит разные типы.

Внутри контейнера есть вектор SectorMap, в котором лежат указатели на секторы, ниже картинка как это работает:

Особенности хранения данных

Данные в SectorsArray лежат плотно и отсортированы. За плотность отвечает Allocator.

Я поддержал возможность задавать кастомные аллокаторы, но реализовал ChunkAllocator как дефолтный. Пользователь при желании может указать свой аллокатор через темплейтный аргумент, главное - реализовать методы, которые используются в контейнере :)

Память внутри чанка - это простой array. Выделяется память чанками по N секторов, где N - степень двойки.

Почему Chunk?

1. Выделение памяти заранее под весь чанк - быстрое добавление данных в конец

2. Удаление чанков - быстро и не аффектит данные в других чанках

3. Добавление чанков - не нужно искать кусок памяти бОльшего размера и мигрировать данные

4. Не нужно искать кусок памяти ОЧЕНЬ большого размера под ОЧЕНЬ много компонентов (но по возможности выделять следующий чанк памяти рядом)

Однако это создало некоторые проблемы во время итерации. Например, найти индекс чанка, по которому итерируемся, или следующего - достаточно тяжелая задача для CPU, так как задействуется деление с остатком (деление само по себе очень медленное). К счастью, мы всегда можем ограничить размер чанка степенью двойки и использовать побитовый сдвиг вместо деления.

Это ускорило поиск следующего чанка примерно в 40 раз!

static constexpr size_t calcChunkIndex(size_t sectorIdx) { return sectorIdx >> mChunkShift; }
static constexpr size_t calcInChunkShift(size_t sectorIdx, size_t sectorSize) { return (sectorIdx & (mChunkCapacity - 1)) * sectorSize; 

Итерация по секторам реализована на стороне аллокатора. Я решил, что для максимальной скорости итератор должен быть настолько низкоуровневым, насколько это вообще возможно. Поэтому более высокоуровневый итератор в контейнере использует низкоуровневый "курсор" из аллокатора. Про итерацию и её оптимизации я расскажу в отдельной статье. Основные нюансы там - это борьба с С++ и тем, как он превращается в команды процессора. Фундамент скорости заложен именно здесь, в аллокаторе и контейнере.

Большая фрагментация чанков может привести к снижению производительности, так как начнутся cache miss-ы. Поэтому стоит подбирать размер чанка под свои задачи правильно. И выделять память заранее: контейнер поддерживает reserve, и так шансы на то, что несколько чанков создадутся рядом, повышаются многократно.

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

Фрагментация

Один из нюансов моего контейнера в том, что все компоненты отсортированы по entityId. Это повышает скорость итерации за счёт того, что:

• при итерации все «потоки данных» идут по возрастанию entityId, последовательно;

• итераторы реализованы через простую арифметику адресов;

• каждый компонент сначала пытается «шагнуть вперёд» по памяти, и если не получилось - делает прыжок через поиск (который, кстати, O(1)).

Благодаря этому префетчер CPU часто угадывает, куда мы пойдём дальше, и итерация работает максимально быстро. Вдобавок сортировка по entityId даёт бонус в виде быстрого поиска сущностей.

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

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

Это помогло решить проблему медленного удаления компонентов из середины списка.

Конец

На этом месте статья подходит к концу. Я рассказал о структуре памяти своей ECS и о некоторой боли оптимизации.

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

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

Всем спасибо, кто дочитал! Буду рад вопросам :)

Бенчмарки - https://wagnerks.github.io/ecss_benchmarks/
Исходники открытые, кода немного, буду рад фидбеку) - https://github.com/wagnerks/ecss