Приветствую Хабравчане!

Прошлые уроки:

Пилим движок Arcanum. Урок 01. Начало
Пилим движок Arcanum. Урок 02. Работа с файлами игры, рисуем первый спрайт

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

Пояснение.

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

Синопсис.

Каждая программа, движок, специализированное ПО работает с памятью. Если отбросить все нюансы, то new в языке С++ почти всегда медленно. Поэтому для ускорения аллокаций используют разные подходы, техники и дополнительные библиотеки. Которые бы ускорили выделение памяти. Самый простой и очевидный, это использование библиотек по типу jemalloc, tcmalloc. Внутри себя данные библиотеки, создают арены памяти разного размера и при выделении памяти, они стараются минимизировать обращение к системным вызовам операционной системы. Если совсем упростить. То при запросе 4-ёх байт, вначале запрашивается кусок в несколько мегабайт и уже из него выделяется так нам нужные 4 байта. Преимущество таких библиотек заключается в их простой интеграции и не требует переписывания уже написанного кода. Подключили перегрузили глобальный new и delete и вперёд, множить количество UB:)

Почему данный подход совершенно не подходит к разрабатываемому движку?

Данный движок использует библиотеки SDL1 и SDL2. SDL1 развивается с конца 90-ых годов прошлого века, портирован под множество систем и архитектур. И я бы хотел максимально использовать данную возможность. В том числе и старые системы которые интересны энтузиастам. Так вот на таких системах проблематично завести распределители памяти, так как они написаны под современные системы. И на старых могут просто не собраться или требовать титанических усилий для портирования. Что совершенно не входит в мои планы.

Поэтому рассмотрим другой вариант, так как я использую стандарт С++ 98 (если меня читают js программисты, то это как использовать jQuery первых версий для разработки современных сайтах:)) Покопаемся в STL, чем он нам может помочь.

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

Если вам интересно узнать больше об аллокаторах, почему в С++ 98 они сделаны именно так, а не иначе. Рекомендую лекции Константина Владимирова.

Я тут придумал шутейку. Типа только импортозамещенные ссылки на видео. Я пытался их найти вне ютуба. Потратил минут 10. В VK нет, на rutube нет. Нашел только на яндекс видео.

Магистерский курс C++ (МФТИ, 2022-2023). Лекция 15. Аллокаторы

Магистерский курс C++ (МФТИ, 2022-2023). Лекция 16. Полиморфные аллокаторы

Очень советую потратить время и ознакомиться с данными лекциями.

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

Так как я пишу код используя стандарт языка С++ 98. Для лучшей портируемости, как на новые, так и на старые и очень старые системы. Возможно ли реализовать часть функционала полиморфных аллокаторов на С++ 98? Главное условие, что моя реализация должна быть совместима с новыми стандартами. При сборке на компиляторе с поддержкой начиная С++ 98 по С++ 14, использую мою кастомную реализацию. При использовании компилятора с поддержкой С++ 17 и выше, используем нативную реализацию.

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

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

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

В принципе на С++ 98 можно реализовать фичи не опирающиеся на новые конструкции языка. Конечно мы не сможем реализовать такие полезные вещи как:

1. Вывод типом с помощью auto

2. Циклы на foreach'ах

3. Семантика перемещения std::move

4. Списки инициализации std::initializer_list

5. Умные указатели

6. Спецификаторы

7. Разделители разрядов

8. И список можно долго продолжать...

   

Попытка портировать уже написанное.

Итог, боль, печаль и уныние.

Первым делом я решил, возьму нужный функционал, пару контейнеров, допилю напильником, да что может пойти не так? Как оказывается всё.

Первый вариант посмотреть реализацию STL от Microsoft и версию под gcc. Я не знаю, что за сверх люди пишут стандартную библиотеку. Но мне это очень сложно парсить. Подход чик, чик и в прод меня подвёл. А значит, так как мне нужен небольшой функционал, дорогу осилит идущий. Добавляем в закладки cppreference.com и начинаем грызть кактус гранит науки.

Реализация.

Весь урок лежит в ветке ArcanumTutorial_03_DrawingMapAndObjects. Клонируем переключаемся и поехали.

Сам движок использует не так много функционала стандартной библиотеки С++. А точнее:

1. Контейнеры vector, unordered_map, string

2. Пару алгоритмов из <algorithm>

3. Стандартные типы вроде size_t

4. И пару тройку заголовков из С.

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

Всю реализацию убрал в отдельный каталог в проекте. Заменил в исходниках, все инклюд файлы стандартной библиотеки на один #include <litecpp/litecpp.hpp>.

С помощью него разруливаем какую версию поддерживает компилятор и в зависимости от версии стандарта используем кастомную реализацию или нативную.

#ifndef litecpp_hpp
#define litecpp_hpp

#include <string>
#include <stdexcept>

#include <litecpp/defines.hpp>

#if ((defined(_MSVC_LANG) && _MSVC_LANG >= 201103L) || __cplusplus >= 201103L)
    #include <array>
#else
    #include <litecpp/array.hpp>
    #include <litecpp/string.hpp>
#endif

#if ((defined(_MSVC_LANG) && _MSVC_LANG >= 201703L) || __cplusplus >= 201703L)
    #include <memory_resource>
    #include <unordered_map>
#else
    #include <litecpp/memory_resource.hpp>
    #include <litecpp/monotonic_buffer_resource.hpp>
    #include <litecpp/vector.hpp>
    #include <litecpp/unordered_map.hpp>
    #include <litecpp/string.hpp>
#endif

#include <litecpp/test_func.hpp>

#endif 

Для начала требуется реализовать std::pmr::memory_resource. Это абстрактный класс от которого наследуются разные типы аллокаторов.

Реализация максимально простая. Главные методы это выделение и освобождение памяти.

#include <stddef.h>

namespace std
{
	namespace pmr
	{
		class memory_resource
		{
		public:
			virtual ~memory_resource() {};
			virtual void* allocate(size_t bytes) = 0;
			virtual void deallocate(void* p, size_t bytes) = 0;
			virtual void release() = 0;
		private:
		};
	}
}

Следом идёт уже первый распределитель памяти это std::pmr::monotonic_buffer_resource. Главная его цель, это получить ссылку на память и размер памяти. Работает как линейный аллокатор.

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

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

Главное преимущество распределителя это аллокация памяти за O(1)

void* monotonic_buffer_resource::allocate(size_t bytes)
{
	assert(bytes > 0);
	assert(_position + bytes <= _capacity);

	void* result = _content + _position;

	_position += bytes;

	return result;
}

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

void monotonic_buffer_resource::deallocate(void* p, size_t bytes)
{
	assert(p != nullptr);
	assert(bytes > 0);
}

Очистка памяти это простейшая операция. Внутрення позиция устанавливается в ноль.

void monotonic_buffer_resource::release()
{
	_position = 0;
}

Следом идёт, просто классика, своя полиморфная строка:)

Главное отличие от обычной строки это возможность передать в конструктор указатель на std::pmr::memory_resource.

Особо интересного там нет. Просто минимальная реализация строки. Но она так же ведет себя и как простая строка, это достигается за счёт проверки откуда брать память при аллокации, глобальный new или из memory_resource

			T* allocate(size_t count)
			{
				if (_resource)
				{
					void* ptr = _resource->allocate(count * sizeof(T));
				
					return new (ptr) T[count];
				}
				else
				{
					return new T[count];
				}
			}

В итоге строка выглядит так.

namespace std
{
	namespace pmr
	{
		typedef litecpp::base_string<char> string;
	}
}

Одно из интересных мест, это реализация std::pmr::unordered_map. Это закрытая хеш-таблица. В нее так же передается в конструктор распределитель. Я реализовал небольшой функционал. А именно вставку ключ-значение, поиск по ключу и в конструктор добавил возможность указать размер внутренней таблицы, в ячейках которых хранятся узлы пар, ключ, значение.

Хеш таблица стостоит из массива двухсвязных списков.

		template<typename K, typename T>
		class list
		{
		public:
			list() :
				head(nullptr),
				tail(nullptr)
			{
			}

			void append(list_node<K, T>* node)
			{
				node->next = nullptr;
				node->prev = tail;

				if (tail)
				{
					tail->next = node;
				}

				tail = node;

				if (head == nullptr) 
				{
					head = node;
				}
			}

			list_node<K, T>* head;
			list_node<K, T>* tail;
		};

Нода это узел списка с ключем и значением.

		template<typename K, typename T>
		class list_node
		{
		public:
			list_node(memory_resource* resource) :
				next(nullptr),
				prev(nullptr),
				first(resource)
			{
			}

			list_node*        next;
			list_node*        prev;
			std::pmr::string  first;
			T                 second;
		};

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

К примеру мне нужно добавить десятки тысяч ключей. На старте оригинальная таблица имеет размер 16. Пока она достигнет нужного размера в зависимости от количества записей. Она все время будет перестраиваться. Будет создан массив список в 32 элемента, но старые 16 элементов невозможно использовать, потом 64, 128 и т.д И предыдущая память будет недоступна для игры.

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

		unordered_map(size_t bucket_count, memory_resource* source) :
				_count(0),
				_bucket_count(bucket_count),
				_memory(source)
			{
				size_t list_size      = sizeof(list<K, T>);
				size_t allocated_size = list_size * _bucket_count;
				void* allocated_ptr   = _memory->allocate(allocated_size);

				_table = new (allocated_ptr) list<K, T>[_bucket_count];
			}

Я планирую всегда использовать для ключа std::pmr::string поэтому взял простую хеш функцию.

	size_t HashLy(const char* str)
			{
				unsigned int hash = 0;

				for (; *str; str++)
					hash = (hash * 1664525) + (unsigned char)(*str) + 1013904223;

				return hash;
			}

Поиск элементарен и поти один в один как в книжках.

			list_node<K, T>* find(const K& key)
			{
				size_t index = HashLy(key.c_str()) % _bucket_count;

				for (list_node<K, T>* i = _table[index].head; i != nullptr; i = i->next)
				{
					if (i->first == key.c_str())
					{
						return i;
					}
				}

				return nullptr;
			}

Для вставки данных я создал единственный метод emplace. В С++ 98 нет семантики перемещения. Но данный метод позволяет унифицировать вставку и не создавать ключ значение через std::pair. Который все равно делает аллокации при конструировании пары.

Можно сказать это лже Дмитрий emplace. Выглядит так:

			void emplace(const K& key, const T& value)
			{
				iterator i = find(key);

				if (i == end())
				{
					void* ptr = _resource->allocate(sizeof(list_node<K, T>));

					list_node<K, T>* node = new (ptr) list_node<K, T>(_resource);

					node->first = key.c_str();
					node->second = value;

					size_t index = HashLy(key.c_str()) % _bucket_count;

					_table[index].append(node);

					_count++;
				}
			}

Используя переданный в конструктор распределитель, создаем ноду в которую копируем ключ и значение. Ключ хранится в строке std::pmr::string которая берет память из этого же распределителя.

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

В моей реализации вектор не будет работать с контейнерами из стандартной библиотеки, пример.

std::pmr::vector<std::pmr::string> strs;

C++ 17 при конструировании вектора, проверяет условие если это полиморфный контейнер то всем контейнерам передается родительский распределитель. Для этого нужен как минимум enable_if_v или вариации. Нормальная реализация std::pmr::polymorphic_allocator.

Если учесть что может быть так:

std::pmr::vector<std::pmr::vector<std::pmr::string>> strs;

И без вариадических шаблонов не реально реализовать.

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

Для совместимости сделать макроc:

#define ALLOC_IF(x) (x, x)

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

В реализации std::pmr::vector нет ничего интересного, за исключением того. Что я создал базовый вектор и с помощью композиции реализовал std::pmr::vector и std::vector.

С реализацией мы разобрались. Да она не идеальна. Каждый урок я буду ее облагораживать и подкручивать. Это так сказать пре релиз:) Цель сохранить функционал и совместимость с оригиналом.

Теперь рассказ, как оно все работает в движке.

При инициализации движка я единожды аллоцирую память размером 16 мегабайт. Эту память я передаю глобальному распределителю _GlobalResource. А уже другие распределители берут память из него.

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

		std::vector<unsigned char>          _GlobalBuffer;
		std::pmr::monotonic_buffer_resource _GlobalResource;
		std::pmr::monotonic_buffer_resource _DatBufferResource;
		std::pmr::monotonic_buffer_resource _ResultBufferResource;
		std::pmr::monotonic_buffer_resource _SptiteBufferResource;
		std::pmr::monotonic_buffer_resource _DatListBufferResource;

Проблема с которой я боролся на старых системах. До старта игры, движку нужно прочитать все записи в архивах около 70 тысяч записей. До этого я использовал std::map и вставлял значения через insert.

namespace Arcanum
{
    class DatList
    {
    public:
        DatItem* Get(const std::string& file);
        void Add(const std::string& key, DatItem& file, const std::string& archive);
        size_t Count();
    private:
        typedef std::map<std::string, DatItem> container;
        container _Files;
    };
}

Вставка

void DatList::Add(const std::string& key, DatItem& file, const std::string& archive)
{
	DatItem* p = Get(key);

	if (p == NULL)
	{
		_Files.insert(std::make_pair(key, file));
	}
	else
	{
		strcpy(p->Archive, archive.c_str());
	}
}

Когда я делаю insert std::make_pair, происходит аллокация пары ключ-значение, потом при вставке идет аллокация пары в сам контейнер, старая пара уничтожается. Таких записей 70k, вы представляете сколько аллокаций и деалокаций? Поэтому я заранее выделил память для класса индексирующий файлы из архивов и теперь любая вставка записи это O(1). Что естественно ускорило загрузку и решилась проблема с фрагментацией памяти.

Теперь так выглядит код.

void DatList::Add(const std::string& key, DatItem& file, const std::string& archive)
{
	DatItem* p = Get(key);

	if (p == nullptr)
	{
		_Files.emplace(key.c_str(), file);
	}
	else
	{
		strcpy(p->Archive, archive.c_str());
	}
}

Просто заменил контейнер std::map на std::pmr::unordered_map. В следующем уроке я покажу как движок рисует карту и объекты на ней. Нам так же пригодятся распределители памяти для борьбы с фрагментацией при загруке карты с десятками тысяч тайлов, тысячами объектов на ней.

Что имеем по итогу:

1. У нас есть некоторые фичи из новых стандартов С++.

2. Теперь движок не фрагментирует память.

3. Я закрыл гештальт по написанию велосипедов:)

Не так уж и мало я вам скажу. Клево же! Рад буду советам, предложениям и критике.

Благодарности за предложения, вычитку статьи и советы. Спасибо ребят, что потратили на меня своё время, очень вам благодарен. Успехов на программерском пути!

Александру Новожилову и пользователю Setryyy.

Благодарю юзеров https://t.me/ProCxx за найденные ошибки.