Игра++. Разбор контейнеров

Независимо от того, начинаете ли вы разрабатывать свою игру или присоединяетесь к уже существующему проекту, когда приходит время оптимизировать память и заниматься разным улучшайзингом, то всегда встают одни и те же вопросы. Стоит ли использовать собственные контейнеры? Если использовать свои, то какой лучше выбрать — похожий на vector, или больше подойдет map? Является ли связный список наилучшим выбором при частых вставках и удалениях элементов? А откуда эти вставки вообще взялись, но это конечно другой вопрос.

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

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

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

Game++. String interning

Game++. Cooking vectors

Game++. Dancing with allocators

Game++. Juggling STL algoritms

Game++. run, thread, run…

Game++. Building arcs

Game++. Unpacking containers <=== Вы тут

Предисловие

Из минусов использования стандартой библиотеки C++ от вендора или SDK — они предоставляют только интерфейс контейнеров, без возможности изменить аллокатор или поменять политику роста контейнера, не залезая внутрь реализации. В С++17 это немного исправили, добавив полиморфные алокаторы, но тоже сделали это не совсем неправильно, оставив внутри виртуальные вызовы для alloc/dealloc.

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

fixed array

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

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

template 
class array {
public:
  size_t size() const { retrn SIZE; }
  bool empty() const { return !size(); }
  const T * data() const;
  T * data();

  typedef ArrayIterator iterator;
  iterator begin();
  iterator end();

private:
  T values_[MAX_SIZE];
};

+--------------------------------------------+
|                                            |
|  +-----------+                             |
|  | size()    | -> SIZE (фиксированный)     |
|  +-----------+                             |
|                                            |
|  +-----------+                             |
|  | begin()   | --+                         |
|  +-----------+   |                         |
|                  |                         |
|  +-----------+   |                         |
|  | end()     | --+--------+                |
|  +-----------+   |        |                |
|                  |        |                |
|  +-----------+   |        |                |
|  | data()    | --+        |                |
|  +-----------+   |        |                |
|                  v        v                |
|  +-------------------------------+         |
|  | ВСТРОЕННЫЙ МАССИВ ФИКСИРОВАННОГО РАЗМЕРА|
|  |+------+------+------+------+  |         |
|  || T[0] | T[1] | T[2] | ...  |  |         |
|  |+------+------+------+------+  |         |
|  |<------- SIZE (константа) ---->|         |
|  | values_                       |         |
|  +-------------------------------+         |
|                                            |
+--------------------------------------------+

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

struct ParticleEmitter {
    gtl::array particles;
    // ...
};

template
class ResourcePool {
    gtl::array resources;
    gtl::array used;
    // ...
};

struct SkeletonJoint {
    gtl::array childJoints;
    gtl::array transformMatrix; // 4x4 matrix
};

struct Skeleton {
    gtl::array joints;
};

fixed matrix

Многомерные массивы представляют собой структуры данных, организующие элементы в двух или более измерениях, самые частые примеры таких структур это матрицы и текстуры. Они уже давно переросли в собственные реализации, решения в которых ушли далеко от обычных массивов. Cырые многомерные массивы тоже часто применяются и в большинстве случаев они реализованы в непрерывной области памяти, элементы хранятся в порядке «строка за строкой» (row-major order).

int matrix[3][4]; // 3 строки, 4 столбца
gtl::array, 3> matrix; // 3 строки, 4 столбца
boost::multi_array array_type

// Матрица трансформации 4x4
std::array, 4> transformMatrix = {{
    {1.0f, 0.0f, 0.0f, 0.0f},
    {0.0f, 1.0f, 0.0f, 0.0f},
    {0.0f, 0.0f, 1.0f, 0.0f},
    {0.0f, 0.0f, 0.0f, 1.0f}
}};
Eigen::Matrix4f transformMatrix = Eigen::Matrix4f::Identity();

Что позволяет сделать прямой доступ через множественную индексацию: matrix[i][j], в общем случае индекс конкретной ячейки рассчитывается по формуле.

flat_offset = (x0 - min0)*stride0 + (x1 - min1)*stride1 + ... + (xN - minN)*strideN

nonlinear matrix

vector> matrix(11035, vector(11035)); 

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

Поначалу различий практически нет, но с ростом размеров карты, числа тайлов, объектов и тд (или числа потоков) мы приходим к тому, что в тредах начинает расти время ожидания обновления общих данных, которые загружены в кеши разных ядер. Когда один из тредов изменил данные в матрице, остальные вынуждены эту информацию обновлять у себя. Обновление одного байта сбрасывает всю кешлинию, где лежит этот байт, и если она была загружена у кеше друого ядра — это приводит её обновлению, такой вот cache poisoning и получается хорошая cachelocality в этом случае только мешает. Вектор векторов меньше подвержен такому эффекту, но лучше всего показывает себя сегментированное octree, ограниченное по объему, об этом будет ниже.

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

linear dynamic matrix

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

struct Tile {
    TileType type;
    bool walkable;
    float height;
    // ...
};

struct TileMap {
    gtl::vector tiles;
    int width, height;

    TileMap(int width, int height) : width(width), height(height), 
                                     tiles(width * height) {}
    
    Tile& at(int x, int y) {
        return tiles[y * width + x];
    }
    
    gtl::array getNeighbors(int x, int y) {
        gtl::array neighbors = {nullptr, nullptr, nullptr, nullptr};
        if (x > 0) neighbors[0] = &at(x-1, y);
        if (y > 0) neighbors[1] = &at(x, y-1);
        if (x < width-1) neighbors[2] = &at(x+1, y);
        if (y < height-1) neighbors[3] = &at(x, y+1);
        return neighbors;
    }
};

class VoxelObj {
private:
    gtl::vector voxels;
    int width, height, depth;

public:
    VoxelObj(int width, int height, int depth) 
        : width(width), height(height), depth(depth),
          voxels(width * height * depth) {}
    
    uint8_t& at(int x, int y, int z) {
        return voxels[(z * height + y) * width + x];
    }
    
    Mesh generateMesh() {
        // создаем модель по воксельной сетке
        // ...
    }
};

тут мы уже плавно переходим к векторам, которые тоже имеют некоторые особенности.

linear vector

Самый обычный динамический массив (https://en.cppreference.com/w/cpp/container/vector), один из наиболее часто используемых контейнеров стандартной библиотеки C++, который особенно полезен в разработке при грамотном использовании.

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

Обеспечивает амортизированную сложность O(1) для добавления элементов в конец, при условии что есть свободное место. Это важно, потому что многие забывают про переалокацию массива и связанные с ней проблемы. Механизм роста у такого очень простой, при недостатке свободных элементов выделяется новый блок памяти (размер зависит от политики роста), затем элементы копируются/перемещаются из старого блока в новый (тут может быть несколько вариантов, от простого memcpy на POD данных, до deepcopy прохода, и это пожалуй основной минус этого класса), потом старая память освобождается. Т.е. в момент роста у нас будет нужно x2 памяти для хранения всех элементов. Но в общем такой механизм обеспечивает сложность O(1) для операции push_back, и не забываем, что отдельные операции могут быть дорогими, например вставка в начало.

template >
class vector {
private:
    T* _begin;      // Указатель на первый элемент
    T* _end;        // Указатель на позицию за последним элементом
    T* _capacity;   // Указатель на конец выделенной памяти
    Allocator _alloc; // Используемый аллокатор
    // ...
};

+--------------------------------------------+
|                                            |
|  +-----------+                             |
|  | _begin    | --+                         |
|  +-----------+   |                         |
|                  |                         |
|  +-----------+   |                         |
|  | _end      | --+------+                  |
|  +-----------+   |      |                  |
|                  |      |                  |
|  +-----------+   |      |                  |
|  | _capacity | --+------+------+           |
|  +-----------+   |      |      |           |
|                  |      |      |           |
|  +-----------+   |      |      |           |
|  | _alloc    |   |      |      |           |
|  +-----------+   |      |      |           |
|                  v      v      v           |
|  +-------------------------------+         |
|  | НЕПРЕРЫВНЫЙ БЛОК ПАМЯТИ       |         |
|  |+------+------+------+------+  |         |
|  || T[0] | T[1] | T[2] | ...  |  |         |
|  |+------+------+------+------+  |         |
|  |<------ size() ------->|       |         |
|  |<-------- capacity() --------->|         |
|  +-------------------------------+         |
|                                            |
+--------------------------------------------+

// Предварительное выделение памяти
vector entities;
entities.reserve(128);

// Оптимизация вставки элементов
entities.resize(128);
for (int i = 0; i < 128; ++i) {
    entities[i] = GameObject();
}

// Быстрое удаление без сохранения порядка
entities[idx] = gtl::move(entities.back());
entities.pop_back();

stable vector

Вектора удобны и широко используются, но имеют существенное ограничение: итераторы и ссылки на элементы становятся недействительными при удалении непоследнего элемента или расширении вектора, в отличие от стабильных контейнеров, вроде std::list или std::set, которые сохраняют валидность ссылок и итераторов, пока элемент не удалён. Однако стабильность исключает смежность элементов в памяти, что затрудняет создание «стабильного вектора» с характеристиками std::vector. Как и std::vector, он поддерживает итераторы с произвольным доступом, но жертвует смежностью элементов ради стабильности. Это означает, что ссылки и итераторы на элементы остаются действительными, пока элемент не удалён. Итератор, полученный от end(), также остаётся корректным до разрушения stable_vector..

По своей структуре часто напоминает list, размещенный в последовательном участке памяти.

template 
class stable_vector {
private:
    struct node {
        T value;
        bool valid;
        
        template 
        node(bool v, Args&&... args) : value(forward(args)...), valid(v) {}
    };
    
    vector> nodes;
    ...

                STABLE_VECTOR
+--------------------------------------------+
|                                            |
|  +-----------------------------------------+
|  | nodes     | std::vector>  |
|  +-----------+                             |
|  | [0] ------|--> +-----------------+      |
|  |           |    | node            |      |
|  |           |    | +-------------+ |      |
|  |           |    | | value: T    | |      |
|  |           |    | +-------------+ |      |
|  |           |    | | valid: true | |      |
|  |           |    | +-------------+ |      |
|  |           |    +-----------------+      |
|  | [1] ------|--> +-----------------+      |
|  |           |    | node            |      |
|  |           |    | +-------------+ |      |
|  |           |    | | value: T    | |      |
|  |           |    | +-------------+ |      |
|  |           |    | | valid: true | |      |
|  |           |    | +-------------+ |      |
|  |           |    +-----------------+      |
|  | [2] ------|--> +-----------------+      |
|  |           |    | node            |      |
|  |           |    | +-------------+ |      |
|  |           |    | | value: T    | |      |
|  |           |    | +-------------+ |      |
|  |           |    | | valid: false| | <-- удаленный элемент  
|  |           |    | +-------------+ |      |
|  |           |    +-----------------+      |
|  | ...       |                             |
|  | [n] ------|--> +-----------------+      |
|  |           |    | node            |      |
|  |           |    | +-------------+ |      |
|  |           |    | | value: T    | |      |
|  |           |    | +-------------+ |      |
|  |           |    | | valid: true | |      |
|  |           |    | +-------------+ |      |
|  |           |    +-----------------+      |
|  +-----------+                             |
|                                            |
+--------------------------------------------+

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

Также часто встречается в компонентной системе объектов, и можно безопасно ссылаться на компоненты объекта без риска получить dangling pointer/reference при добавлении/удалении компонентов.

Еще одно применение это графы, чтобы обеспечивать стабильные ссылки между узлами графа даже при изменении его структуры.

sparse vector

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

Представьте, что нам надо организовать массив игровых юнитов на уровне, но так же мы хотим оставить возможность частичной и по возможности быстрой сортировки груп юнитов. Учитывая что группы не бывают безразмерными, а обычно 4-8-16-32 в группе, можно намеренно оставлять пустые места после вставки нового элемента, таким образом когда вы создаете нового юнита, вы можете поставить его в нужное место без перемещения всех остальных..

Такой подход повсеместно применяется в стратегиях с большим числом юнитов, например SC2/Total Annihilation и практически не приводит к рантайм аллокациям памяти. Разработчики игры были вынуждены использовать такой механизм размещения юнитов, ибо технические средства того времени не позволяли делать это в рантайме. Если группа заканчивалась, то новая начинала создаваться на большем удалении от последнего выделенного элемента, так балансировалось ожидание больших групп юинтов, если игрок собирал армию.

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| A |   |   |   | B |   |   |   | С |   |   |   | D |   | E |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| A |   |   |   | B | B1|   |   | C | C1|   |   | D |   | E |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14

packed vector

Тут первыми на память приходят реализации битовой и числовой упаковки, например как std::bitset, или vector, которые позволяют существенно снизить расходы памяти на хранение определенных типов данных.

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

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

+--------------------------------------------+
|                                            |
|  +-----------+                             |
|  | chunks    |   vector        |
|  +-----------+                             |
|  | [0]       | --+                         |
|  | [1]       | ---+                        |
|  | [2]       | ----+                       |
|  | ...       |      \                      |
|  | [n]       | ------+                     |
|  +-----------+        \                    |
|                         \                  |
|  +-----------+           \                 |
|  | data      | --+        \                |
|  +-----------+   |         \               |
|                  v          v              |
|  +-------------------------------+         |
|  | НЕПРЕРЫВНЫЙ БЛОК СЖАТЫХ ДАННЫХ|         |
|  |+------------++-----------+    |         |
|  || Chunk 0    || Chunk 1   |... |         |
|  || offset=0   || offset=X  |    |         |
|  || size=X     || size=Y    |    |         |
|  |+------------++-----------+    |         |
|  +-------------------------------+         |
|                                            |
+--------------------------------------------+

template
class packed_vector {
    struct compressed_data_chunk {
      size_t offset;
      size_t size;
    };
    
    std::vector;
    void* data;
}

Другой, но близкий - подход это использовать компресиию на весь объем данных, не заморачиваясь поэлементо, и распаковывать упаковывать их при обращениях, например используя быстрые алгоритмы вроде LZW/Oodle на лету.

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

Особенно такой подход становится интересным, если алгоритмы компрессии поддерживаются железом, например PS5 реализует Kraken (Oodle). Т.е. файл на диске хранится в определенном формате, при чтении через sdk вы получаете его временную копию уже распакованной, которая обратно на диск попадает также упакованной, все работает прозрачно через провайдер sdk.

Таже схема будет работать и обычными данными в памяти, причем всю промежуточную работу на себя берет сдк, а вы просто бегаете по массиву.

static vector

В 2007 году EASTL выкатили концепцию small_vector, который имел небольшой буфер на 16 элементов внутри самого класса и при использовании большего числа элементов уже обращается к аллокатору за памятью.

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

В отличие от обычного vector или small_vector, static_vector полностью избегает динамической аллокации, храня все элементы в заранее выделенном буфере фиксированного размера. Этот подход обеспечивает предсказуемость использования памяти и отсутствие накладных расходов на управление ресурсами..

template 
class static_vector {
private:
    size_t size_ = 0;
    alignas(T) byte buffer_[Capacity * sizeof(T)];

    T* data() { return reinterpret_cast(buffer_); }
    const T* data() const { return reinterpret_cast(buffer_); }
    ....
}

+--------------------------------------------+
|                                            |
|  +-----------+                             |
|  | size_     | текущее количество элементов|
|  +-----------+                             |
|                                            |
|  +-----------+                             |
|  | data()    | --+                         |
|  +-----------+   |                         |
|                  |                         |
|                  v                         |
|  +-------------------------------+         |
|  | ВЫРОВНЕННЫЙ СТАТИЧЕСКИЙ БУФЕР |         |
|  | alignas(T) byte buffer_       |         |
|  |+------+------+------+------+  |         |
|  || T[0] | T[1] | T[2] | ...  |  |         |
|  |+------+------+------+------+  |         |
|  |<-- size_ -->|                 |         |
|  |<-------- Capacity ----------->|         |
|  +-------------------------------+         |
|                                            |
+--------------------------------------------+

small vector

Это контейнер, который сначала использует стековую память, а при её исчерпании переходит на динамическое выделение. Поддерживает операции вставки и удаления с конца за O(1), а в середине — за O(n). Позволяет задавать тип элементов, размер встроенного хранилища и тип аллокатора. В C++17 присутствует в реализации std::pmr::vector..

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

На текущем проекте анализ использования памяти показал, что размер вектора варьируется от 2 до 80 элементов в 80% случаев, и большинство краткоживущих объектов не превышают размер в 512 байт. Т.е. условно 40кб на стеке в худшем случае будет достаточно, чтобы избавиться от большинства алокаций. И в некоторых случаях такая замена на small_vector или аналог pmr::vector давала ощутимое снижение времени фрейма на 10-15%.

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

template
struct small_buffer_vector_allocator{
    alignas(alignof(T)) std::byte m_smallBuffer[MaxSize * sizeof(T)];
    std::allocator m_alloc{};
    bool m_smallBufferUsed = false;
        
    T* allocate(const size_t n) {
       if (n <= MaxSize) {
            m_smallBufferUsed = true;
             return reinterpret_cast(&m_smallBuffer);
        }

        m_smallBufferUsed = false;
        return m_alloc.allocate(n);
    }
    
    void deallocate(void* p, const size_t n) {
      if (&m_smallBuffer != p) 
          m_alloc.deallocate(static_cast(p), n);
      m_smallBufferUsed = false;
    }
}

+--------------------------------------------+
|                                            |
|  +-----------+                             |
|  | size_     | текущее количество элементов|
|  +-----------+                             |
|                                            |
|  +-----------+                             |
|  | capacity_ | общая емкость               |
|  +-----------+                             |
|                                            |
|  +-----------+                             |
|  | data_     | --+                         |
|  +-----------+   |                         |
|                  |                         |
|  +-----------+   |                         |
|  | alloc_    |   |                         |
|  +-----------+   |                         |
|                  |                         |
|  +---------------------+                   |
|  | LOCAL STORAGE       |                   |
|  | (встроенный буфер)  |<------+           |
|  | alignas(T) buffer_[N]       |           |
|  +---------------------+       |           |
|                                |           |
|                 Указывает на:  |           |
|                                v           |
|  +-------------------------------+         |
|  | ДАННЫЕ (локальные или в куче) |         |
|  |+------+------+------+------+  |         |
|  || T[0] | T[1] | T[2] | ...  |  |         |
|  |+------+------+------+------+  |         |
|  |<-- size_ -->|                 |         |
|  |<-------- capacity_ ---------->|         |
|  +-------------------------------+         |
|                                            |
+--------------------------------------------+

dirty_vector

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

Вместо немедленного удаления элементы просто помечаются как "грязные" (например, с помощью дополнительного флага или специального значения). Реальное удаление происходит при вызове clean() (или compact()), который удаляет все помеченные элементы и, если необходимо, сокращает память, при этом операции удаления выполняются за O(1), так как не требуют сдвига элементов.

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

+--------------------------------------------+
|                                            |
|  +-----------+                             |
|  | size_     | видимый размер (без dirty)  |
|  +-----------+                             |
|                                            |
|  +-----------+                             |
|  | real_size_| фактический размер с dirty  |
|  +-----------+                             |
|                                            |
|  +-----------+                             |
|  | capacity_ | общая емкость               |
|  +-----------+                             |
|                                            |
|  +-----------+                             |
|  | data_     | --+                         |
|  +-----------+   |                         |
|                  |                         |
|  +-----------+   |                         |
|  | dirty_flags| -|--+                      |
|  +-----------+   |  |                      |
|                  v  v                      |
|  +-------------------------------+         |
|  | НЕПРЕРЫВНЫЙ БЛОК ПАМЯТИ       |         |
|  |+------+------+------+------+  |         |
|  || T[0] | T[1] | T[2] | ...  |  |         |
|  || clean| dirty| clean| ...  |  |         |
|  |+------+------+------+------+  |         |
|  |<--- size_ --->|               |         |
|  |<------ real_size_ ----------->|         |
|  |<-------- capacity_ ---------->|         |
|  +-------------------------------+         |
|                                            |
+--------------------------------------------+

buddy_vector

Концепция контейнера появилась в играх серии Civilization, как ответ на потребность в простом алгоритме сохранения истории значений, например так хранилась история передвижения юнитов за последние N ходов для плавной интерполяции перемещений. Все также основано на стандартном vector, но с особой схемой размещения элементов. Вместо последовательного размещения, элементы в таком векторе располагаютcя "через один (N)", оставляя пустые ячейки между ними. Это позволяет реализовать смещение элементов без их физического перемещения в памяти.

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

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

┌───────────────────────────────────────────────────────┐
│                    BUDDY VECTOR                       │
├───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┤
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │10 │11 │12 │13 │  ← index = i + offset % cap
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
│ A │   │ B │   │ C │   │ D │   │ E │   │ F │   │ G │   │  ← значения
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
│ x |   │ x │   │ x │   │ x │   │ x │   │ x │   │ x │   │  ← занятые (x) и пустые ( )
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
      ↑       ↑       ↑       ↑       ↑       ↑
      │       │       │       │       │       │
      └───────┴───────┴───────┴───────┴───────┘

Итераторы и указатели

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

Что такое итератор — это «облегчённый» объект, аналогичный указателю T*. Каждый контейнер имеет свой тип итератора. iter++ перемещает итератор к следующему элементу. *iter возвращает ссылку на текущий элемент, это важно для работы с циклами (например, range-for).

Почему итераторы и указатели инвалидируются? Инвалидация означает, что итератор или указатель перестаёт указывать на корректный объект. Это происходит при изменении структуры контейнера, в std::vector после push_back() ссылки на элементы могут «протухнуть», если произошло перевыделение памяти.

В std::deque push_back() обычно не инвалидирует ссылки на существующие элементы, так как новые блоки добавляются без перераспределения старых.

Нестандартные контейнеры (например, static_vector, flat_map) имеют особенности инвалидации итераторов, нарппример вstatic_vector - инвалидация происходит только при выходе за пределы ёмкости, и является фактически крашем. В small_vector переход от внутреннего буфера к динамической памяти инвалидирует все итераторы.

deque

Двусторонние очереди (deque, double ended queue) — это контейнеры, которые можно расширять или сокращать с обоих концов. В отличие от vector, который представляет собой сплошной массив, deque позволяет вставлять элементы как в конец (с помощью push_back()), так и в начало (push_front()). Вектора такой возможности не имеют, так как поддерживают эффективное добавление только в конец.

Реализован как набор блоков (чанков) фиксированного размера, связанных между собой. Например, каждый блок может хранить 16–512 элементов и при добавлении элементов в начало или конец новый блок создается только при заполнении текущих. Это позволяет выполнять push_front() и push_back() за O(1) без перемещения существующих элементов..

template
struct simple_deque
{
    T* elements;
    T* first;
    T* last;
    size_t capacity;
};

bcdeque (block-compressed)

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

+----------------------------------+
| BLOCK_COMPRESSED_DEQUE        |
|                                  |
| +----------------+               |
| | blocks         |---+           |
| +----------------+   |           |
|                      v           |
| +-----+-----+-----+-----+        |
| | B0  | B1  | B2  | ... |        |
| |plain|compr|plain|     |        |
| +-----+-----+-----+-----+        |
|   |      |     |                 |
|   v      v     v                 |
| +----+ +----+ +----+             |
| |Data| |Zlib| |Data|             |
| +----+ +----+ +----+             |
|                                  |
+----------------------------------+

bounded_priority_deque

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

Примеров применения в играх достаточно: в Civilization транспортные юниты и рабочие используют bpdeque для решению задач передвижения по графу тайлов, в Witcher3 на этих структурах построены дневные циклы перемещения жителей в поселениях, чтобы они не толпились и не повторялись. В бою используется для координации действий юнитов в группе выбирая разные точки на орбите игрока и не давая им одновременно атаковать.

Представьте обычную очередь, где приоритетные задачи выталкиваются вперёд, а неважные выкидываются, если места не хватает. Когда в игре происходит много ивентов одновременно, мы можем банально их не успевать выполнять. Тут и помогает такая структура, которая гарантирует, что важные задачи будут выполнены первыми.

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

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

+-----------------------------------+
|  [HEAD]                    [TAIL] |
|  +---+---+---+---+---+---+---+   |
|  | 5 | 3 | 2 | 4 | 7 | 1 | 6 |   |  <- Элементы с приоритетами
|  +---+---+---+---+---+---+---+   |
|    ^               ^             |
|    |               |             |
| min_priority    max_priority     |
|    |               |             |
| [MIN_BOUND]    [MAX_BOUND]       |
+-----------------------------------+


ВСТАВКА С ПРИОРИТЕТОМ:
   
   insert(элемент, приоритет)
   
   Если приоритет < MIN_BOUND:
      +---+---+---+---+---+---+---+---+
      | X | 5 | 3 | 2 | 4 | 7 | 1 | 6 |  <- Вставка слева (HEAD)
      +---+---+---+---+---+---+---+---+
   
   Если приоритет > MAX_BOUND:
      +---+---+---+---+---+---+---+---+
      | 5 | 3 | 2 | 4 | 7 | 1 | 6 | X |  <- Вставка справа (TAIL)
      +---+---+---+---+---+---+---+---+
   
   Иначе (поиск позиции по приоритету):
      +---+---+---+---+---+---+---+
      | 5 | 3 | X | 2 | 4 | 7 | 6 |  <- Вставка в середину
      +---+---+---+---+---+---+---+

СБОР РЕСУРСОВ В СТРАТЕГИЯХ:
   
         [Дерево]  [Железо]
            |         |
   [БАЗА]---+----[Камень]
            |
      [Золото]
   
   BPDeque = [Железо, Дерево, Золото, Камень]
   
   - Приоритет = ценность_ресурса / расстояние_от_текущей_позиции
   - Ограничение = макс. число ресурсов в памяти юнита
   - Юнит движется к HEAD для оптимального маршрута

Точки патрулирования:

   [S]---[A]---[B]
    |     |     |
   [E]---[D]---[C]
   
   BPDeque = [S, A, B, C, D, E]  <- Контрольные точки в порядке обхода
   
   - Приоритет = время последнего посещения
   - MIN_BOUND = текущее время - макс. интервал
   - Охранник всегда идет к HEAD очереди
   - После посещения, точка перемещается в TAIL с обновленным приоритетом

intrusive_deque/list

Элементы содержат встроенные указатели, что исключает необходимость в отдельном массиве указателей и позволяет реализовать размещение объектов в кастомных аллокаторах, пулах и т.д. Особенно хорошо такие структуры работают в связке с пулом объетов (intrusive_deque + object_pool), пул объектов быстро выдает объекты, дека позволяет их быстро сортировать и обрабатывать нужным образом. Используется в основном для временных объектов (частицы, снаряды, ивенты, звуки шагов, столкновения и т.д.).

typedef struct nodes {
  struct list *next;
} nodes;

typedef struct item {
  int val;
  nodes items;
} item;

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

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

+----------------------------------+
| INTRUSIVE_DEQUE               |
|                                  |
| +----------------+               |
| | head           |---+           |
| +----------------+   |           |
| | tail           |---|---------+ |
| +----------------+   |         | |
|                      v         v |
| +------+      +------+      +------+
| |Node 0|<---->|Node 1|<---->|Node 2|
| |      |      |      |      |      |
| |Value |      |Value |      |Value |
| +------+      +------+      +------+
|                                  |
+----------------------------------+

Intrusive структуры часто применяются для работы с объектами, которые часто добавляются и удаляются: состояние игровых объектов (живой, убит, виден, скрыт и тд), список активных сущностей (NPC, пули, частицы), в физическом движке для хранения активных коллизий, в рендеринге для отслеживание отрисовываемых объектов.

octree

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

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

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

Правило деления обычно связано с плотностью объектов в октанте. Когда количество объектов в узле превышает некоторое пороговое значение, узел делится. Это позволяет адаптировать структуру октодерева к распределению объектов в пространстве, уделяя больше вычислительных ресурсов областям с большим числом объектов.

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

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

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

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

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

Концепция segmented octree, расширяет эту идею, позволяя создавать октанты только там, где это разрешено. Пространство разделяется не только на октанты, но и на сегменты для более эффективного управления памятью, в каждом из сегментов может быть установлены свои правила сегментации

quadtree/btree

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

Один из самых распространенных случаев использования — оптимизация обнаружения коллизий в играх, нет смыслы запускать полноценно симуляцию физики на объектах, которые невидны или далеко от игрока в большинстве случаев. Причем как в двух, так и трехмерных пространствах, перед тяжелой проверкой по геометрии, можно сделать быструю проверку по представлению уровня в 2д пространстве, или использовать quadtree для сокращения количества проверок перед основным запросом. Нет смысла проверять проходит ли луч через геометрию уровня, если объекты в несвязанных или блокированных квадрантах. Нет смысла обновлять полноценно юниты в областях, которые невидны или недоступны игроку, это только отбирает время кадра.

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

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

object_pool

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

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

┌───────────────────────────────────────┐
│           Object Pool                 │
│         (Inactive Objects)            │
├───────┬───────┬───────┬───────┬───────┤
│  [O1] │  [O2] │  [O3] │  [O4] │  [O5] │
└───────┴───────┴───────┴───────┴───────┘
   ▲       │               ▲       ▲
   │       ▼               │       │
┌──┴───────────────────────┴───┐   │
│         Active Objects       │   │
├──────────────────────────────┤   │
│  AI      ────► [O2]          │   │
│  Phys    ────► [O3]          │   │
└──────────────────────────────┘   │
                                   │
                                Render  ────► [O5]

template  
class Pool {
public:
    using const_iterator = typename std::array::const_iterator;

    template
    Pool(Args&& ...args)
        :num_of_avail_(N), storage_{}, status_{}
    {
        storage_.fill(T{std::forward(args)...});
        status_.set();
    }

    ...

 private:
    size_t num_of_avail_;
    std::array storage_; 
    std::bitset status_;
};

ring/circullar_buffer

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

Основа кольцевого буфера — обычный массив фиксированного размера. Для отслеживания позиций заведем два указателя: head (голова) и tail (хвост). Голова указывает, откуда мы будем читать элементы, а хвост куда будем записывать новые. При добавлении нового элемента, записываем его в позицию хвоста и двигаем хвост вперед. Я не рассматриваю сейчас более сложные варианты с возможной записью из нескольких потоков, или неблокирующиеся.

Когда читаем элемент, мы берем его из позиции головы и двигаем голову вперед. Самое интересное происходит, когда указатели доходят до конца массива — они просто "перепрыгивают" в начало. Это и создает эффект кольца или круга.

Кольцевые буферы часто используются в ситуациях, когда данные поступают постоянным потоком и должны обрабатываться последовательно: звук, видео, история ивентов — новые фрагменты добавляются в конец, обработанные удаляются из начала. Обмен ивентами между подсистемами игры (обработка ввода, UI) или потоками (система задач).

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

         Circular Buffer
 +-------------------------------+
 |                               |
 v                               |
 [_, _, _, _, _, _, _, _, _, _, _]
 ↑
h,t

 [A, B, C, _, _, _, _, _, _, _, _]
 ↑        ↑
 h        t

 [A, B, C, D, E, F, G, H, J, K, L]
    ↑                           ↑
    h                           t

 [G, B, C, D, E, F, G, H, J, K, L]
  ↑  ↑ - ---------------------- ->
  t  h

сached_hashtable

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

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

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

+------------------------------------------------------+
|                CACHED HASH TABLE                     |
+------------------------------------------------------+
                       |
    +------------------+-------------------+
    |                                      |
    v                                      v
+-------------+                     +---------------+
|    CACHE    |<------------------->|  MAIN TABLE   |
| (быстрый    |     Синхронизация   | (постоянное   |
|  доступ)    |                     |  хранение)    |
+-------------+                     +---------------+
    |                                      |
    | Поиск элемента                       | Поиск элемента
    | (сначала)                            | (если не найден
    |                                      |  в кэше)
    v                                      v
+-------------+                     +---------------+
| [K1] -> V1  |                     | [K1] -> V1    |
| [K2] -> V2  |                     | [K2] -> V2    |
| [K3] -> V3  |                     | [K3] -> V3    |
|     ...     |                     | [K4] -> V4    |
| [Kn] -> Vn  |                     |     ...       |
+-------------+                     | [Km] -> Vm    |
    ^                               +---------------+
    |                                      ^
    |                                      |
    +--------------------------------------+
               Вытеснение/Замещение   

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

Ключевой компонент такого подхода — стратегия управления кэшированием, которая определяет, какие элементы хранить в кэше, а какие вытеснять, когда кэш заполнен. В основном используют LRU (вытеснение элемента, к которому долго не обращались), LFU (вытесняем элемент, к которому реже всего обращались), FIFO (вытесняем элементы в порядке их добавления), свое кастомное правило (на одном из проектов было схлопывание каждого второго элемента)

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

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

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

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

handle_container

Для ряда объектов игрового движка (модели, текстуры, графическик буферы) их данные должны быть расположены подряд насколько это возможно, чтобы максимизировать локальность кэша при работе с ними. Цель здесь не в том, чтобы придумать замену стандартным контейнерам STL, а в том, чтобы сделать игру максимально быстрой на том железе что есть, и сделать это прозрачно для программиста.

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

Что отличает handle_container от других ассоциативных контейнеров, таких как std::map и std::unordered_map? Мы не указываем ключ при вставке данных, вот почему они называются (handle), а получаем некую управляющую структуру или идентификатор от контейнера после вставки.

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

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

┌───────────────────────────────────────────────┐
│           handle_map                          │
├───────────┬───────────┬───────────────────────┤
│   Handle  │   Idx     │  Object*              │
├───────────┼───────────┼───────────────────────┤
│     H1    │      h1   │  ─────────────────────┐
├───────────┼───────────┤                       │
│     H2    │      h2   │  ─────────┐           │  
├───────────┼───────────┤           │           │
│     H3    │      h3   │  ──┐      │           │
└───────────┴───────────┘    │      │           │
                             ▼      ▼           ▼
                        ┌───────┐┌───────┐┌───────┐
                        │ Объект││ Объект││ Объект│
                        │  O1   ││  O2   ││  O3   │
                        └───────┘└───────┘└───────┘

slot_container

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

Применяется для системы событий (у нас не может быть условно произвольных событий, все определено на этапе сборки): и событийная система использует slot_container для хранения подписчиков (обработчиков) событий. Каждый слот может быть использован для подписчика, и когда подписчик отписывается, слот освобождается. Новый подписчик либо становится в очередь, либо вытесняет старый из слота, такой подход часто используется в различных фреймворках (SDL, SFML, eventpp и другие.

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

Инициализация контейнера с 8 слотами оружия:
[ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 ]   <- Индексы слотов (оружие)
[ A | B | C | D | E | F | G | H ]   <- Объекты 

Удаление объекта "C" и "F":
[ 0 | 1 | X | 3 | 4 | X | 6 | 7 ]   <- Освобожденные слоты (кинули гранаты)
[ A | B |   | D | E |   | G | H ]   <- Объекты

Добавление нового объекта "I" в первый "свободный свой" слот:
[ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 ]   <- Индексы слотов 
[ A | B |   | D | E | I | G | H ]   <- Подобрали нож (I) добавлен в свой слот,
                                       гранат можем держать две, нож только один

Удаление "B" и перемещение "H" на его место (совпадают слоты):
[ 0 | X | 2 | 3 | 4 | 5 | 6 | 7 ]  
[ A | H |   | D | E | I | G |   ]   <- Поддерживается плотность данных, выкинули 
                                       винтовку и подобрали дробовик

Замещение "J" в первый доступный "свой" слот:
[ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 ]  
[ A | J |   | D | E | I | G |   ]  <- подобрали другой дробовик, 
                                      т.к. доступных слотов больше нет, то J замещает 

Удаление объекта "C" и "F":
[ 0 | 1 | X | 3 | 4 | X | 6 | 7 ]   <- Освобожденные слоты (подобрали гранату)
[ A | J | K | D | E | I | G |   ]   <- Объекты
                                      

Послесловие

Одной из ключевых характеристик создания софта является абстракция. Большая часть книг по программированию посвящена абстракциям, которые учат нас как можно ослабить связь между частями кода, чтобы их можно было легче изменять. Но слабые связи и хорошие абстракции подразумевают доступ к объектам через указатели, а обращение через указатель всегда означает работу с памятью, а это явные промахам кеша, алокации и освобождения. Вторая часть проблемы с абстракциями — это вызовы виртуальных методов. Проц сначала должен найти vtable объекта (опять указатель), а затем получить указатель на вызываемый метод (еще один указатель), снова приходится гоняться за указателями.

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

И тем больше все это приходит к линейным массивам, векторам и сырой памяти. Здесь нет универсального решения — только сложные компромиссы и опыт тех, кто уже прошел этой дорогой. Но именно это делает программирование игр таким увлекательным!

Надеюсь было интересно! Спасибо, что дочитали.

Источник