Один из частых вопросов, которые я получаю от студентов или на наших внутренних студийных лекциях, — это какую стратегию выделения памяти лучше применять при разработке? Ответ: хотелось бы никакую, т.е. не использовать аллокации рантайм, но жизнь вносит свои коррективы.
Мы все знаем, что нельзя просто выделять память, когда вздумается, но откладываем решение этой проблемы до конца проекта. К тому времени дедлайны начинают давить, майлстоуны и некоторые части тела подгорать, и обычно уже слишком поздно, чтобы вносить серьезные изменения. Ну хотя бы есть пара недель перед релизом, чтобы поправить основные проблемы.
Динамическое выделение памяти — это как раз то, что относится к той категории вещей для большинства программистов, о которой все знают, но забивают пока не приходит OOM. Хотя немного продуманности и предварительного планирования могут помочь избежать большинства этих проблем, и даст небольшую надежду, что игра не вылетит по памяти в самый неподходящий момент.
Попробую убедить вас не использовать std::string/vector в функциях. При написании кода для пк, неважно - игры это или что-то другое, программа обычно разделяется на условно пять областей памяти.
Game++. Heap? Less <=== Вы тут
Текстовая область (.text): машинный код, условно неизменяемый во время выполнения.
Область данных (.rodata): глобальные и статические переменные, которые были инициализированы при компиляции.
Область BSS (.bss / block started by symbol): глобальные и статические переменные, которые не были инициализированы и по умолчанию устанавливаются в ноль.
Стек (stack): динамическая область памяти, которая используется для xранения локальных переменных, управления вызовами функций и передачи параметров между ними, сохранения состояния выполнения программы. Условно лежит с правого края нашего адресного пространства растет влево, конечно и имеет явно заданный размер, хоть и довольно большой, до нескольких мегабайт
Куча (heap): динамическая область памяти, которая позволяет выделять и освобождать память во время выполнения программы через вызовы malloc(), free(), new, delete. Дает нам более гибкое управление памятью по сравнению со стеком, но может приводить к фрагментации и требует явного освобождения памяти для предотвращения утечек. Условно лежит с левого края нашего адресного пространства и растет вправо, теоретически бесконечно.
Поскольку текстовая (text) и дата (.rodata) секции ведут себя одинаково, линковщик вполне может объединить их в одну секцию.
Stack
Стек - это основная форма памяти, используемая любой программой на C++. Он используется неявно, например, при объявлении переменных, и работает по принципу "первым пришел - последним ушел" (First-In-Last-Out). Это означает, что память, которая выделяется первой, освобождается последней. Стек используется для хранения переменных внутри функций (включая функцию main()). Каждый раз, когда функция объявляет новую переменную, она "проталкивается" в стек. Когда функция завершает выполнение, все переменные, связанные с этой функцией, удаляются из стека, и занимаемая ими память освобождается. Это обеспечивает "локальную" область видимости переменных функции. Переменные формально "удаляются", для сложных типов вызываются деструкторы, но данные, которые были на, стеке никуда не удаляются и не зануляются, стек просто откатывается на тот адрес, который был до вызова функции.
Стек является областью памяти, управляемой ОС и средой выполнения (runtime), в большинстве архитектур существует обещпринятый регистр указателя стека (ESP, EBP, EIP в x86/RSP, RBP, RIP x64/SP, FP в Aarch64), который используется для адресации стека. Физическое размещение стека в адресном пространстве процесса определяется ОС и может находиться в произвольной области памяти, выделенной для процесса.
С точки зрения кода, обращение к стеку эквивалентно доступу к любому другому адресу памяти. В плюсах существует понятие storage duration, и переменные с automatic storage duration обычно размещаются на стеке, но компилятор может разместить их в регистрах или полностью исключить их обработку в при оптимизациях. (Исправлено, спасибо @Dooez)
Обычно существует ограничение на размер стека, которое может варьироваться в зависимости от операционной системы. В большинстве современных языков программирования размер стека по умолчанию составляет около 1 МБ, если не установлен вручную. В OSX по умолчанию размер стека составляет 8 МБ, на консолях размер стека формально не ограничен, но выставление его размера больше 64Мб приводит к segfault внутри ядра ОС.
Переполнение стека
Если код пытается разместить слишком много информации в стеке, происходит переполнение стека (stack overflow), когда вся память в стеке была распределена, и дальнейшие выделения начинают залезать в другие разделы памяти.
Наиболее частой причиной переполнения будет чрезмерно глубокая или бесконечная рекурсия, когда функция вызывает сама себя много раз, что превышает доступное пространство стека. Например, такой функции на хватит где-то на 8 вызовов при мегабайтном стеке
int foo() {
char buffer_16kb[128 * 1024] = {0};
return foo();
}
Хозяйке на заметку
Стек управляется процессором, нет возможности его модифицировать (формально)
Переменные выделяются и освобождаются автоматически
Стек не безграничен – у большинства есть верхний предел
Стек растет и сжимается по мере создания и уничтожения переменных
Переменные стека существуют только пока существует функция, которая их создала
Стек и куча это один и тот же вид памяти
Heap
Куча является диаметральной противоположностью стека. Куча представляет собой большой пул памяти, который может использоваться динамически. Это память, которая не управляется автоматически — вы должны явно выделять и освобождать память. Если не освободить память, когда вы закончили с ней работу, это приведет к утечке памяти — памяти, которая все еще "используется" и недоступна другим процессам. В отличие от стека, обычно нет ограничений на размер кучи (или создаваемых в ней переменных), кроме физического размера памяти в машине. Переменные, созданные в куче, доступны в любом месте программы.
Хозяйке на заметку
Куча управляется руками, возможности по ее модификации практически безграничны
В языке C/C++ выделение и освобождение памяти в куче осуществляется с помощью функций malloc/new и free/delete
Куча имеет большой объем и обычно ограничена только физической памятью, доступной в системе
Для доступа к куче требуются указатели
Static
Статическая память используется для переменных, которые имеют тот же жизненный цикл, что и программа, например, глобальных переменных. Компилятор заранее знает, какой размер потребуется для этих переменных, и резервирует память во время компиляции.
struct yellow_sphere
{
const char * name;
char flour[1 * 1024];
yellow_sphere(const char *name) : name(name) {}
};
yellow_sphere * kolobok;
void the_kolobok_runaway()
{
kolobok = new yellow_sphere("from_babushka");
}
void meet_with_the_fox()
{
delete kolobok;
kolobok = nullptr;
}Три функции размещаются в области "инструкций", строковый литерал "from_babushka" помещается в область "данных или текста". Это происходит потому, что такие строки являются константами времени компиляции, но не могут быть изменены в рантайме (формально не могут). Указатель kolobok является глобальной переменной, поэтому он помещается в "статическую" область и зануляется при старте. Вызов new помещает kolobok в кучу, а delete удаляет его из кучи.
В коде выше мы не используем стек явно. А вот ниже уже будет использоваться стек.
void u_babushki()
{
yellow_sphere kolobok{"u_babushki"};
}При входе в функцию u_babushki() компилятор резервирует область в стеке для объекта kolobok. Размер выделенной памяти зависит от размера класса yellow_sphere, вся память выделяется в текущем фрейме стека функции.
Далее вызывается конструктор yellow_sphere с параметром "u_babushki", конструктор создает объект непосредственно в выделенной области стека, параметр передается по значению или по константной ссылке.
Объект существует только в рамках функции, при выходе из функции будет автоматически вызван деструктор, память стека освобождается без участия программиста. На стеке, в этом упрощенном случае будут:
+------------------------------+
| Параметры функции |
+------------------------------+
| Адрес возврата |
+------------------------------+
| Сохраненное состояние |
+------------------------------+
| Объект kolobok | <-- Место создания объекта
| - Внутренние данные |
| - Состояние |
+------------------------------+Поскольку объект создается полностью на стеке, компилятор может применять разные техники оптимизации: полная оптимизация объекта (RVO/NRVO), Inline-создание объекта, удаление ненужных копирований. В случае, если объект создается динамически, очень многое из оптимизаций компилятор применить просто не может.
RVO (Return Value Optimization) и NRVO (Named Return Value Optimization) — техники оптимизации компилятора , позволяющие избегать ненужного копирования объектов при возврате значений из функций. Основная идея в том, что возвращаемый объект создается сразу в памяти вызывающей функции, полностью избегая создания временных копий.
class Entity {
public:
Entity() { /* Сложный конструктор */ }
Entity(const Entity&) { /* Дорогое копирование */ }
};
Entity createEntity() {
// Компилятор может создать объект напрямую в месте вызова
return Entity();
}
int main() {
Entity obj = createObject(); // Прямое создание, без копирования
}сlang начал поддерживать RVO и NRVO с версии 3.9, выпущенной в 2016 году. Но полная реализация и включение этих оптимизаций в стандартные настройки компилятора произошли позже, ближе к 2019 году.
В студии поддержка NRVO появилась с версии, которая вышла в 2015 году, но она по факту не работала и по умолчанию была отключена, RVO фактически работал только в пределах видимости стека одной функции, если все имплементации объектов были видны в хедерах, ну т.е. очень редко. В VS 2022 NRVO стала включаться автоматически при настройках компилятора /Ox и был введен флаг /Zc:nrvo, позволяющий явно управлять этой оптимизацией для файлов, потому что может генерить некорректный код при определенных условиях. К тому же RVO отключается, если есть сложная логика копирования, класс содержит код с шаблонным стуктурами или функциями, которые участвуют в копировании. У кланга с этим поэффективнее будет.
Компромиссы
Игры существуют не в вакууме учебников по компьютерным наукам, поэтому нам приходится сталкиваться с реальными ограничениями, которые делают этот подход громоздким, неуклюжим и потенциально катастрофическим. Что может пойти не так при динамическом выделении памяти по требованию? Почти всё!
Использование кучи делает архитектуру программы проще: если нужно создать форматированную строку, выделение памяти в куче позволяет выбрать необходимый размер строки. Если у нас есть только стек, то нужно предварительно выделить строку с фиксированным размером во время компиляции. Это может привести к переполнению буфера, если его по каким-то причинам оказалось недостаточно, поскольку мы можем получить строку, которая превышает предварительно выделенную память. Однако использование кучи связано с некоторыми компромиссами, которые влияют на общую архитектуру по мере роста проекта.
Игры, как и любое другое программное обеспечение, работают на устройствах с ограниченным объемом памяти, на консолях или мобилках физически нет свопа, и ваш доступный объем памяти заканчивается примерно на половине того, что указано на коробке - есть еще операционная система, её сервисы, сторонние приложения и библиотеки и видеокарта, всем им тоже нужна оперативка.
Если разработчик точно знает этот лимит и тщательно отслеживает использование памяти, можно оставаться в его пределах. Однако в динамически выделяемых системах это сложно: игра запрашивает память всякий раз, когда это необходимо. И рано или поздно наступает момент, когда свободной памяти просто не остаётся. В такой ситуации вариантов немного. Можно попытаться освободить старые, неиспользуемые блоки памяти и выделить новый на их месте, но это требует сложного механизма управления памятью. Другой вариант — сделать игру устойчивой к нехватке памяти, но это ещё сложнее: системе нужно заранее уметь предугадывать возможные сбои и корректно на них реагировать, например, отключая часть функционала или снижая качество загружаемых ресурсов.
Даже установка фиксированных бюджетов памяти для различных игровых систем (графики, физики, звука, ИИ и т. д.) не гарантирует полного контроля. Например, разработчики могут предусмотреть лимит для системы частиц, но что, если во время боя на экране одновременно окажется слишком много взрывов и эффектов, и зааффектит уже физику или рендер?
Или если юниты создадут больше объектов для поиска пути, чем было заложено в бюджет этой системы? И такие проблемы могут проявляться только в ходе долгого тестирования или в сложных игровых сценариях, которые даже QA не предусмотрят. И даже если тесты пройдут успешно, нет никакой гарантии, что игра не выйдет за пределы памяти спустя какое-то время. Полностью предсказать все возможные комбинации работы игровых систем невозможно, удается лишь ограничить самые встречаемые кейсы, поэтому продуманное управление памятью и строгий контроль её использования должны быть заложены в архитектуру игры с самого начала.
Детерминизм
Поскольку стек используется только внутри функции и затем снова освобождается, текущее состояние памяти полностью определяется текущим стеком вызовов.
void bar() {}
void foo() { bar(); }
void foobar() { foo(); }
int main() {
foobar();'
return 0;
}Здесь каждая функция имеет свой собственный стековый фрейм (т.е. участок памяти в стеке). Всегда можно определить (и на это закладывается компилятор при выборе оптимизаций, что невозможно при работе с кучей), сколько памяти использует программа при вызове foobar, если известны размеры стековых фреймов foobar, foo и bar. Размер стекового фрейма зависит только от положения указателя стека при вызове foobar. Если избегать рекурсии, вся программа имеет максимальный размер памяти Х, который она никогда не превысит. Наша программа определена, детерминирована и использует декларированную область памяти, поскольку нам не нужно выполнять проверки на возможность выделения памяти.
Фрагментация
Фрагментация происходит, когда память часто выделяется и освобождается. Допустим, у нас есть 4 байта доступной памяти в куче – мы ожидаем, что следующий код будет работать:
cppCopyEditchar* x = new char; // 3 байта свободно
char* y = new char; // 2 байта свободно
delete x; // 3 байта свободно
char* z = new char[3]; /// boom
Однако программа не работает из-за фрагментации памяти. Хотя в куче есть 3 свободных байта, только два из них находятся рядом друг с другом. Наша куча стала «фрагментированной», поэтому мы не можем использовать всю доступную память. Можно визуально представить, почему z не удаётся выделить, если нарисовать использование памяти для каждой строки кода:
/** Используемая память: | 0x0 | 0x1 | 0x2 | 0x3 | */
// | | | | |
char* x = new char; //| x | | | |
char* y = new char; //| x | y | | |
delete x; //| | y | | |
char* z = new char[3]; //| | y | z | z | z ???? (ошибка)
В отличие от кучи, стек не может фрагментироваться: он всегда растёт и уменьшается целыми смежными блоками в одном направлении. Ещё одна проблема с детерминизмом заключается в том, что большинство реализаций кучи не имеют детерминированного верхнего предела времени выделения памяти. Это особенно критично для игр, которым приходится работать на устройствах только с доступным физическим объемом памяти. Тот же код, но без алокаций, только стек
/** Используемая память: | 0x0 | 0x1 | 0x2 | 0x3 | */
// | | | | |
char x; //| x | | | |
char y; //| x | y | | |
end function //| | | | |
char z[3] //| z | z | z | |Утечки
Ещё одной проблемой динамического выделения памяти являются ошибки в логике управления выделенными блоками. Если забыть освободить часть памяти, программа столкнётся с утечками, что со временем может привести к исчерпанию доступной памяти и даже краху игры. ОС не знает, что какие-то блоки стали зомби, для неё эта запрошенная память вся едина.
Обратная сторона утечек памяти — некорректный доступ к уже освобождённой памяти. Если программа освобождает блок, а затем пытается снова к нему обратиться, это может привести либо к исключению при доступе к памяти, либо, что ещё хуже, к незаметному повреждению данных, что со временем приведёт к трудноуловимым ошибкам в игре.
Некоторые техники, такие как подсчёт ссылок (reference counting) и сборка мусора (garbage collection), помогают автоматически отслеживать выделение и освобождение памяти. Однако они вводят дополнительные накладные расходы и сложности, такие как фрагментация памяти, внезапные паузы в работе игры или сложность реализации эффективного механизма очистки ненужных данных. Игры предпочитают ручное управление памятью, специализированные аллокаторы и контроль её использование на всех этапах разработки (бюджетирование).
Дополнительная логика и фреймворки
Использование кучи требует дополнительной логики в программе для управления предыдущими выделениями памяти, поиска свободных областей и невозможности компилятора предсказать когда это будет. Пусть от нас это и скрыто за вызовами new/delete они все равно есть, они дергают юзерспейс и кернел логику и в любом случае влияют негативно на общую производительности игры. Если вы используете кучу, это приводит к тому, что целый пласт глобальных оптимизаций компилятора выпадает и не выполняется. Ну а кроме прочего new/delete - это недетерминированные операции выделения памяти (т.е. происходят в относительно случайные моменты и занимают случайное время)
В консолях и мобилках, эти проблемы становятся ещё более критичными, поскольку такие системы могут иметь крайне малый объём памяти, как было сказано выше (относительно пк) или слабое железо, картофельные устройства сами по себе являются проблемой, потому что пользователи все равно ожидают нормальной работы и, когда игра не справляется, летит негативный отзыв, который читают все.
В большинстве случаев выгодно как можно больше отказаться от использования кучи, сократив как само количество вызовов, так и объемы. Меньше куча, меньше проблем!
Разработка на C++ без кучи — это просто «не использовать new и delete»?
К сожалению, всё не так просто. Наши любые плюсы выполняют значительное количество выделений памяти неявно, прозрачно для программиста, в тени STL и прячась от взгляда оптимизаторов и анализаторов. Например, если вам нужен динамический строковый объект, вы, скорее всего, используете std::string:
const char* name1 = "kolobok";
std::string name2 = "kolobok";
const char[] name3 = "kolobok";Какой из трех колобков испортил память? На первый взгляд new здесь нет, так в чём же проблема? Дело в том, что std::string сам выделяет динамическую память для хранения строки "kolobok". Это удобно, сильно упрощает синтаксис и позволяет сосредоточиться на логике программы вместо управления памятью. Но за удобства надо платить - удобная стандартная библиотека выполняет выделение памяти в очень многих местах.
Чтобы убедиться в этом надо лишь подключить один из множества существующих профайлеров Pix, Tracy, Razor (PS4/5) и немного пошаманив посмотреть из чего состоит кадр, я не буду сейчас сильно углубляться как интегрировать такой инструмент к себе в проект, но это на самом деле не сложно и решается хедером и расстановкой точек профилирования.
Статья про PIX (отслеживания аллокаций памяти) - практически бесплатно, для винды надо будет подключить пару библиотек и все должно заработать из коробки.
Статья про Tracy, это опенсорс инструмент, по функционалу не сильно уступает пиксу, а в чем-то даже и лучше.
А здесь пошаговая инструкция от разработчика LuxeEngine про интеграцию Tracy в движок.
Минимально хватает не более чем десятка макросов, чтобы подключить базовый функционал профайлера.
Скрытый текст
#pragma once
#ifndef TRACY_ENABLE
#define OZZY_PROFILER_BEGIN
#define OZZY_PROFILER_FRAME(x)
#define OZZY_PROFILER_SECTION(x)
#define OZZY_PROFILER_TAG(y, x)
#define OZZY_PROFILER_LOG(text, size)
#define OZZY_PROFILER_VALUE(text, value)
#else
#include "tracy/Tracy.hpp"
#define OZZY_PROFILER_BEGIN ZoneScoped
#define OZZY_PROFILER_FRAME(x) FrameMark
#define OZZY_PROFILER_SECTION(x) ZoneScopedN(x)
#define OZZY_PROFILER_TAG(y, x) ZoneText(x, strlen(x))
#define OZZY_PROFILER_LOG(text, size) TracyMessage(text, size)
#define OZZY_PROFILER_VALUE(text, value) TracyPlot(text, value)
#endifНо чтобы показать всю жесть алокаций и почему они так влияют на производительность, просто посмотрите на стек вызовов той строчки с std::string.
FFFFF80666211D05 ntoskrnl!KiSystemServiceCopyEnd+0x25
00007FFA3B6DB5D4 ntdll!RtlpAllocateHeapInternal+0xBB4
00007FFA38DBFDE6 ucrtbase!_malloc_base+0x36
00007FF7591011B7 DE_s!operator new+0x1F [D:\a\_work\1\s\src\vctools\crt\vcstartup\src\heap\new_scalar.cpp:35]
00007FF75498DBBE DE_s!std::basic_string<char,std::char_traits<char>,std::allocator<char> >::assign+0xDEНо на вызове malloc() приключения только начинаются, об этом была хорошая статья совсем недавно на хабре (https://habr.com/ru/companies/otus/articles/889020/) - выделяется блок памяти в куче, но фактический размер блока округляется до границ минимального блока (8, 16, 32, 64 байта, чем больше граница блока, тем меньше потерь на внешней фрагментации, но тем меньше реальной памяти для всех остальных) для оптимизации работы с памятью.
Если в куче есть подходящий свободный блок, он используется повторно. В противном случае malloc() запрашивает новую память у операционной системы с помощью системного вызова (и обычно они разные для больших и малых размеров). Выделенная память, помимо блока нужного размера содержит метаинфо о размере блока, указатели на соседние свободные блоки и флаги занятости, и что там еще придумают разработчики аллокатора. Это позволяет эффективно управлять памятью, но приводит к небольшим накладным расходам, поэтому выделять блоки по размеру меньше границы очень дорого, условно на 1 байт данных - будем получать 32-64 байта под метаинфо.
Но и функция free() тоже не бесплатная, в лучшем случае она помечает блок как свободный, чтобы его можно было повторно использовать в процессе. В худшем происходит возврат памяти ОС при определенных условиях, например когда процесс освобождает достаточно памяти, чтобы получались размеры, кратные размеру страницы ram.
И тут есть пара неприятных моментов, RtlpAllocateHeapInternal является низкоуровневой внутренней функцией в подсистеме памяти винды, частью Native API и используется для управления памятью в ядре Windows. И она если верить документации маек является блокирующей, т.е. приостанавливает выполнение потока до тех пор, пока операция выделения памяти не будет завершена (уважаемые хаброжители, поправьте меня, если я где-то ошибся). Т.е. где-то в другом потоке, сейчас стоит в очереди и громко плачет другая std::string, которая вдруг захотела немного пожить. Но и это еще не всё, там дальше идет вызов KiSystemServiceCopyEnd, а работает он так:
- Пользовательское приложение генерирует системный вызов
- Аргументы копируются в безопасную область
- KiSystemServiceCopyEnd завершает процесс копирования
- Происходит переключение в режим ядрат.е. я случайно (неслучайно конечно, а то было бы совсем просто) своим неудачным вызовом std::string наступил на нехватку буфера выделенной памяти для локального процесса и malloc переключил процесс в режим ядра, чтобы выделить еще памяти всему процессу. Не слишком ли дорого для того, чтобы просто поработать со строкой?
Локальные строки
Казалось бы выхода нет, не отказываться же от std::string и возвращаться к char[]? И да, и нет. Как показывает опыт больших проектов, полноценные std::string нужны очень редко, в одном случае из десяти, а то и меньше. В большинстве же случаев нам нужно поработать со строкой и вывести её на экран, в лог, сохранить в объекте и временная строка почти всегда будет объектом чьего-то владения.
Т.е. надо для этого сместить точку применения алгоритма, который работает с данными, ближе к самим данным. Умные люди придумали множество шаблонов для строк, я уже описывал примеры работы c ними в одной из статей цикла про плюсатый игрострой (https://habr.com/ru/articles/873016/), теперь давайте попробуем сделать строки которые будут решать задачу локальной компоновки, т.е. когда владельцем строки является сам стек и нам надо вывести сообщение в лог. У нас для этого есть как минимум две возможности: можем написать класс для работы со строкой, которая хранит буфер внутри себя (inplace string), это нормальное решение и многие игровые движки идут именно по такому пути. Например так, полный код можно посмотреть тут:
using pcstr = const char *;
using pstr = char *;
template <size_t _size>
class bstring {
using ref = bstring<_size>&;
using const_ref = const bstring<_size>&;
protected:
char _data[_size];
public:
enum {
capacity = _size,
};
public:
explicit inline bstring(int n) {
::snprintf(_data, _size, "%d", n);
}
inline pcstr c_str() const {
return _data;
}
inline char* data() {
return _data;
}Это полностью детерминированное решение, у вас всегда будет ограниченный буфер для работы. Хорошее упражнения для программиста, и написать свой класс строки надо хотя бы раз, как крестики-нолики, змейку или игру жизнь, чтобы понимать как оно устроено изнутри. Но и стандартная библиотека тоже предоставляет достаточно возможностей для реализации inplace строк.
// статический буфер фиксированного размера
alignas(std::max_align_t) char staticBuffer[1024];
// Создаем полиморфный ресурс памяти с использованием статического буфера
std::pmr::monotonic_buffer_resource pool{
std::data(staticBuffer),
std::size(staticBuffer)
};
// Создаем строки с использованием этого пула
std::pmr::string str1(&pool);
std::pmr::string str2(&pool);
str1 = "Первая строка";
str2 = "Вторая строка";
std::cout << "Статический пул: " << str1 << ", " << str2 << std::endl;В этом варианте строки будут создаваться на стеке, пока хватает локального буфера, и только после этого они будут размещаться в куче и вызывать динамические алокации.
Ad-hoc полиморфизм
Но что делать, если у нас есть несколько объектов разного типа, которые надо обрабатывать в зависимости от их типа. Разработчики Snowdrop движка (серия The Division) выкатили интересное, но порою спорное решение для ad-hoc полиморфизма на базе std::variant стандартной библиотеки. Это шаблонный класс, который содержит std::aligned_storage, достаточного размера для хранения памяти под любой из объектов но может содержать только один из возможных типов, такой себе union на максималках.
Типобезопасность отличает его от того же union, который хранит несколько типов в одной области памяти, но не предоставляет механизмов защиты от использования неверного типа. Именно поэтому использование union в C++ обычно не рекомендуется. Если же union всё-таки применяется, его следует использовать только для фундаментальных типов. Помимо типобезопасности, std::variant обладает рядом интересных свойств:
Хранимые типы не обязаны находиться в одном дереве наследования.
Память выделяется внутри объекта (не используется куча).
Память разделяется между всеми возможными типами (каждый тип использует одно и то же место в памяти).
RTTI не требуется.
Объявление std::variant выполняется с помощью параметризованного шаблона. Нужно просто перечислить все возможные типы, которые он может содержать либо объект babushka, либо колобка (kolobok).
//construct a babushka
std::variant<babushka, kolobok> who_runaway{babushka{"not_dedushka"}};
//destruct babushka and set it to a kolobok
who_runaway = kolobok{"yellow_face"};Присваивание значений std::variant может выполняться при инициализации (в конструкторе) или через оператор. Таким образом, std::variant позволяет безопасно хранить одно из нескольких типов, гарантируя корректное уничтожение предыдущего значения при изменении и все это без дополнительных аллокаций памяти, на детерминированном объеме.
Извлечение значения из std::variant не так интуитивно, как из std::optional. Мы можем получить значение из variant тремя способами.
std::get_if
Наиболее распространённый способ доступа к значению std::variant — это std::get. Однако эта функция выбрасывает исключение, если используется неверный тип, что делает её неудобной в некоторых случаях. Вместо этого можно использовать std::get_if, которая возвращает nullptr, если тип не совпадает, не выбрасывая исключений.
std::variant<babushka, kolobok> who_runaway{babushka{"not_dedushka"}};
const auto who = who_is_runaway();
if (std::holds_alternative<babushka>(who)) //who is a babushka
do_not_eat_humans(*std::get_if<babushka>(&who)); //use the appropriate measure
else if (std::holds_alternative<kolobok>(who)) //who contains a kolobok
eat_kolobok(*std::get_if<kolobok>(&who)); Синтаксис достаточно тяжелый и многословный, и много так не напрограммируешь. Но семнадцатые плюсы делают его более похожим на обычный код.
std::variant<babushka, kolobok> who_runaway{babushka{"not_dedushka"}};
const auto who = who_is_runaway();
if (const auto babka = std::get_if<babushka>(who); babka)
do_not_eat_humans(*babka);
else if (const auto kolob = std::get_if<kolobok>(who); kolob)
eat_kolobok(*kolob);std::visit
Другой способ получить содержимое std::variant — это использовать visitor. Он будет вызван с тем типом, который в данный момент хранится в variant.
std::variant<babushka, kolobok> who_runaway{babushka{"not_dedushka"}};
struct who_visitor
{
const char* operator()(babushka b) {return b.name;}
const char* operator()(kolobok k) {return k.name;}
};
const auto who = who_is_runaway();
who_visitor visitor;
//invokes name_visitor::operator()(babushka) if val contains an babushka
// or name_visitor::operator()(kolobok) if val is kolobok
const char* name = std::visit(visitor, who); std::variant::index
Третий способ — использовать индекс, который std::variant хранит для отслеживания текущего значения. Это позволяет применять variant в выражении switch-case. В сочетании с шаблоном variant_alternative_t мы также можем вывести правильный тип.
std::variant<babushka, kolobok> who_runaway{babushka{"not_dedushka"}};
const auto who = who_is_runaway();
switch (who.index())
{
case 0:
{
using t = std::variant_alternative_t<0, decltype(who))>; //babushka
const babushka& b = *std::get_if<t>(who);
}
break;
case 1:
{
using t = std::variant_alternative_t<1, decltype(who))>; //kolobok
const kolobok& k = *std::get_if<t>(who);
}
break;
}Основное применение std::variant (даже при использовании кучи) — это то, что можно назвать "ад-хок полиморфизмом". Вместо того чтобы искусственно создавать иерархию классов для несвязанных типов, мы можем использовать variant. Второй причиной для использования std::variant является то, что часть памяти будет повторно использована. Это особенно полезно при использовании в контекстах, где можно быть уверенным, что в любой момент времени требуется только одна версия.
Один из сценариев применения — это машина состояний. Текущее состояние — это единственное значение, которое может храниться в экземпляре variant, потому что машина состояний может находиться только в одном состоянии в любой момент времени. Давайте представим, что у нас есть машина состояний для монстра init - eat - sleep - chase player - runaway.
struct init {};
struct eat {int i;};
struct sleep {int i; int j;};
struct chase_player {double d;};
struct runaway {float f;};Мы можем определить транзишены (переходы) для такой машины состояний как свободные функции, члены класса машины состояний или члены структур состояний. Тогда весь код такой фсм будет условно состоять из одной функции. Это очень упрощенный пример, но он показывает возможности ad-hoc полиморфизма и области его применения, здесь нет никаких алокаций, но фсп полностью рабочая и использует минимально памяти.
eat transition(init b);
sleep transition(eat b);
chase_player transition(sleep b);
runaway transition(chase_player b);
eat transition(runaway b);
struct statemachine
{
std::variant<init, eat, sleep, chase_player, runaway> state;
void next()
{
std::visit(
//execute the edge
[this](auto ¤t_state)
{
//assign the result as the next state
state = transition(current_state);
}, state);
}
};Best practices
Основными контейнерами при оптимизации работы с кучей являются статические или гибридные варианты основных контейнеров стандартной библиотеки.
std::vector -> pmr::vector -> std::array (fixed_vector)
Простой код бенчмарка, на реальных проектах конечно же надо верить только профайлеру.
Бенчмарк
constexpr size_t MIN_SIZE = 2;
constexpr size_t MAX_SIZE = 1024;
// Стандартный std::vector
static void BM_StdVector(benchmark::State& state) {
for (auto _ : state) {
std::vector<int64_t> vec;
for (int64_t i = 0; i < state.range(0); ++i) {
vec.push_back(i);
}
benchmark::DoNotOptimize(vec);
}
}
BENCHMARK(BM_StdVector)->Range(MIN_SIZE, MAX_SIZE);
// Статический std::array
static void BM_StaticArray(benchmark::State& state) {
for (auto _ : state) {
std::array<int64_t, MAX_SIZE> arr{};
for (int64_t i = 0; i < state.range(0); ++i) {
arr[i] = i;
}
benchmark::DoNotOptimize(arr);
}
}
BENCHMARK(BM_StaticArray)->Range(MIN_SIZE, MAX_SIZE);
// pmr::vector с буфером фиксированного размера
static void BM_PMRVector(benchmark::State& state) {
std::array<std::byte, MAX_SIZE * sizeof(int64_t)> buffer;
std::pmr::monotonic_buffer_resource pool(buffer.data(), buffer.size());
for (auto _ : state) {
pool.release();
std::pmr::vector<int64_t> vec{&pool};
vec.reserve(state.range(0));
for (int64_t i = 0; i < state.range(0); ++i) {
vec.push_back(i);
}
benchmark::DoNotOptimize(vec);
}
}
BENCHMARK(BM_PMRVector)->Range(MIN_SIZE, MAX_SIZE);
array показывает наилучшую производительность на всех размерах
pmr::vector работает на уровне array, пока хватает локального буфера
разница в производительности увеличивается с ростом размера контейнера, размеры стека соответственно
Как это может быть реализовано в движке или игре. Допустим мы выявили проблему с аллокациями памяти при поиске пути для NPC. Стандартное решение, которое можно увидеть в большинстве случаев.
// имеем некоторый алгоритм, который генерит пути для NPC
std::vector<PathNode> GeneratePath() {
std::vector<PathNode> path;
path.reserve(128); // думаем что путь может быть длинный
....
PathNode node = pathfinding->node();
while (node) {
path.push_back(pathfinding->node())
node = node->next();
}
return path;
}
// надеемся, что компилятор умный и сможет в RVNO
std::vector<PathNode> path = GeneratePath(path);Как это работает по стандартной схеме: std::vector динамически выделяет память в куче, reserve(128) позволяет выделить пространство заранее, в расчете на то, что очень небольшая группа путей будет больше 128 хопов. Так мы снизим риск переалокаций на размерах 2, 4, 8, 16 и тд, и соответственно расходов на копирование. Из недостатков такого подхода получаем:
фрагментацию кучи
непредсказуемые задержки во время выполнения (allocation spikes)
каждый новый путь требует отдельной аллокации
неэффективно для многопоточных вычислений путей (все треды используют один и тот же аллокатор)
Вариант получше:
// имеем некоторый алгоритм, который генерит пути для NPC
bool GeneratePath(std::pmr::vector<PathNode>& path) {
....
PathNode node = pathfinding->node();
while (node) {
path.push_back(pathfinding->node())
node = node->next();
}
return true;
}
// не надеемся что компилятор умный, все алокации проходят под нашим контролем
std::array<std::byte, 128 * sizeof(PathNode)> buffer;
std::pmr::monotonic_buffer_resource pool(buffer.data(), buffer.size());
std::pmr::vector<PathNode> path{&pool};
// если будет очень длинный путь, пул вывалится в стандартный
// аллокатор и будет спайк в профайлере, оставим такие случаи на потом
path.reserve(128);
GeneratePath(path);Как это будет работать: buffer предварительно выделен на стеке и в него будут писаться данные без каких либ алокаций, пока его достаточно. Память выделяется из этого пула без обращения к системному аллокатору. Получаем значительное сокращение количества системных аллокаций если пути раздавались в цикле, уменьшаем фрагментацию кучи, исключаем блокировки между потоками благодаря тому, что все данные находятся на стеке, получаем предсказуемую производительность.
Еще лучше и без алокаций во время фрейма, но требует больших переделок:
// имеем некоторый алгоритм, который генерит пути для NPC
bool GeneratePath(std::array<PathNode, 128>& path) {
....
PathNode node = pathfinding->node();
int i = 0;
while (node && i < 128) {
path.push_back(pathfinding->node())
node = node->next();
++i;
}
return true;
}
// храним путь в NPC или в пуле таких объектов в виде фиксированного массива
// делаем контракт в игре, что пути не могут быть длиннее
struct NPC {
size_t pathLength;
std::array<PathNode, 128> path; // Фиксированный размер
};
npc.pathLength = GeneratePath(npc.path);Как это работает: std::array выделяется в пуле объектов или в самом NPC, и не требует отдельной аллокации. Размер известен на этапе компиляции, компилятор может применять к нему различные оптимизации. Получаем максимальную локальность данных в кэше, хорошую производительность и предсказуемость, отсутствие накладных расходов на управление памятью. Из недостатков получили ограниченный размер и необходимость обрабатывать дополнительные кейсы с длинными путями, например делать интерполяцию и перераспределять точки пути. Массивные объекты могут вызвать переполнение стека, поэтому 2-3мегабайтные стеки в играх это норма.
Попытка получить лучший перф привела к неочевидным решениям и возможно придется модифицировать не только GeneratePath(), но и зависимости. Пример, конечно, сильно упрощен и вычищен от ненужных данных, но взят на основе изменений реальной игры, и там это позволило снизить время расчета путей для каждых 100 юнитов (например случился десинк, который потребовал одномоментного обновления состояний всех нпс) на фрейме с 8 до 2мс, просто за счет грамотного избавления от аллокаций.
std::map(set) -> std::unordered_map -> f14::fast_map -> pmr::unordered_set
Код бенчмарк (insert, дорогая операция)
constexpr size_t MIN_SIZE = 2;
constexpr size_t MAX_SIZE = 1024;
static void BM_Map(benchmark::State& state) {
for (auto _ : state) {
std::map<int64_t, int64_t> map;
for (int64_t i = 0; i < state.range(0); ++i) {
map[i] = i;
}
benchmark::DoNotOptimize(map);
}
}
BENCHMARK(BM_Map)->Range(MIN_SIZE, MAX_SIZE);
static void BM_Umap(benchmark::State& state) {
for (auto _ : state) {
std::unordered_map<int64_t, int64_t> arr{};
for (int64_t i = 0; i < state.range(0); ++i) {
arr[i] = i;
}
benchmark::DoNotOptimize(arr);
}
}
BENCHMARK(BM_Umap)->Range(MIN_SIZE, MAX_SIZE);
static void BM_F14FastMap(benchmark::State& state) {
for (auto _ : state) {
folly::F14FastMap<int64_t, int64_t> map;
for (int64_t i = 0; i < state.range(0); ++i) {
map[i] = i;
}
benchmark::DoNotOptimize(map);
}
}
BENCHMARK(BM_F14FastMap)->Range(MIN_SIZE, MAX_SIZE);
static void BM_PMRSet(benchmark::State& state) {
std::array<std::byte, MAX_SIZE * sizeof(int64_t)> buffer;
std::pmr::monotonic_buffer_resource pool(buffer.data(), buffer.size());
for (auto _ : state) {
pool.release();
std::pmr::unordered_set<int64_t> map{&pool};
map.reserve(state.range(0));
for (int64_t i = 0; i < state.range(0); ++i) {
map.insert(i);
}
benchmark::DoNotOptimize(map);
}
}
BENCHMARK(BM_PMRSet)->Range(MIN_SIZE, MAX_SIZE);Другая частая проблема, которая встречается при разработке игр это ассоциативые контейнеры, хештаблицы и работа с ними. В играх std::map и std::set, и их варианты на основе векторов применяются для хранения и быстрого поиска данных, например, чтобы было удобно использовать хранение настроек, списки игровых ресурсов, объекты сцены и тд, где доступ по ключу должен быть быстрым и предсказуемым.
В AI-системах такие контейнеры применяются для кэширования путей, хранения состояний NPC. Set, в свою очередь, полезен там, где важно гарантировать уникальность элементов и быстро проверять их наличие, вроде активных эффектов персонажей, событий игрового мира, списка компонентов.
Из-за сравнительно высокой стоимости вставки и поиска, в std::map и std::set заменяют на более специализированные структуры данных, такие как хеш-таблицы std::unordered_map/set, а в особо сложных случаях на собственные реализации, оптимизированные под конкретные задачи, работающие на пулах, кастомных аллоакаторах, с явным резервированием памяти, или вообще на стеке.
Хеш-таблица предоставляет отображение ключа в соответствующее значение, преобразуя ключ в определённую "позицию" с помощью хеш-функции. Однако, даже если хеш-функция идеальна, конфликты неизбежны, так как бесконечное множество ключей отображается в ограниченное пространство памяти: разные ключи могут быть сопоставлены с одной и той же позицией. Для решения этой проблемы традиционные хеш-таблицы используют различные стратегии разрешения коллизий, наиболее распространённые из которых — метод цепочек (chaining) и линейное пробирование (linear probing).
Метод цепочек (chaining) является наиболее распространённым способом разрешения коллизий в хеш-таблицах. Если несколько ключей отображаются в одну и ту же позицию, их значения хранятся в связанном списке. При поиске сначала используется хеш-функция для определения позиции, затем связанный список в этой позиции последовательно просматривается для нахождения нужного ключа
Линейное пробирование (linear probing) — это ещё один стандартный метод разрешения коллизий в хеш-таблицах. В отличие от метода цепочек, при возникновении конфликта он последовательно проверяет следующие ячейки в массиве, начиная с позиции конфликта, пока не найдёт пустую ячейку или не вернётся к исходной позиции. Если свободное место не найдено, таблица увеличивается в размере, и все элементы перераспределяются с новым хешированием.
swisstable (f14) — это реализация хеш-таблицы, основанная на улучшенном методе линейного пробирования. Основная идея заключается в оптимизации производительности и использования памяти за счёт усложнения структуры таблицы, хранения метаданных в нодах и эффективного использования проца для увеличения пропускной способности операции поиска. За счет использования алгоритма линейного пробирования и определенной структуры ноды мы можем проверять несколько ключей за раз при одной итерации, подробнее тут.
Условный пример с определением области карты, которая известна конкретному юниту. Обновляется часто, потому что юниты ходят вокруг базы, могут иметь таски на эксплоринг карты, где видел врагов, получить обновления от союзных юнитов с которыми встретились и тд, используется еще чаще в совершенной разной логике. В конце фрейма бегаем по этим данным и проводим некоторый анализ, например куда пойти дальше, или какие ресурсы начать собирать, внутри фрейма могло быть до нескольких десятков апдейтов информации по тайлу. Оригинальный код был основан на использовании std::map написан давно и явно не был рассчитан на дамаг от стрел, которые завезли с одним из обновлений, что собственно и дало возможность провести дальнейшие оптимизации.
std::map<TileID, TileInfo> map_info;
map_info[tile.id] += TileInfo("wood");
map_info[tile.id] += TileInfo("enemy");Без особого ущерба коду и масштабных переделок можно перейти к использованию unordered_map несколько ускорив эту логику, но проблему кардинально не решили. Использование F14FastMap снизило время обработки почти в 2 раза, но все равно массовых баталиях была заметна просадка на старой логике.
folly::F14FastMap<TileID, TileInfo> map_info;
for (auto _ : events) {
map_info[tile.id] += TileInfo(event)
}В итоге сделали решение с временным pmr::unordered_set , который был аллоцирован на стеке, не дергал аллокацию и практически не ел перфа по сравнению со старшим братом, т.е. минимально влиял на время апдейта. А уже после этого выполнялось обновление основной map_info парой апдейтов, вместо десятков.
std::array<std::byte, MAX_SIZE * sizeof(TileInfo)> buffer;
std::pmr::monotonic_buffer_resource pool(buffer.data(), buffer.size());
std::pmr::unordered_set<TileInfo> frame_events{&pool};
frame_events.reserve(MAX_SIZE);
for (auto _ : events) {
frame_events[tile.id] += TileInfo(event);
}
// function end
std::copy(frame_events.begin(), frame_events.end(), std::inserter(map_info));std::string -> pmr::string -> static_string
Код бенчмарка
static void BM_std_string(benchmark::State& state) {
for (auto _ : state) {
std::string logMessage;
logMessage.resize(256);
logMessage = "Game Log: Player X has entered the level!";
benchmark::DoNotOptimize(logMessage);
}
}
BENCHMARK(BM_std_string);
// Benchmark для std::pmr::string
static void BM_pmr_string(benchmark::State& state) {
for (auto _ : state) {
char buffer[256];
std::pmr::monotonic_buffer_resource pool{buffer, sizeof(buffer)};
std::pmr::string logMessage(&pool);
logMessage = "Game Log: Player X has entered the level!";
benchmark::DoNotOptimize(logMessage);
}
}
BENCHMARK(BM_pmr_string);
// Benchmark для char buffer
static void BM_char_buffer(benchmark::State& state) {
for (auto _ : state) {
char buffer[256];
strcpy(buffer, "Game Log: Player X has entered the level!");
benchmark::DoNotOptimize(buffer);
}
}
BENCHMARK(BM_char_buffer);А тут будет история из жизни реального проекта, я скопировал это код "as is", что называется, из основной ветки, с разрешения компании конечно. Эта логику уже давно починили, но пример сам по себе показательный. Условно есть система логов, которая была кем-то и когда-то сделана и не менялась очень долгое время, пока не стала светиться в мемори профайлере.
// Это все прелюдия для системы логов, и OutputDebugStringA() вместо реальной записи
// файл.
enum Info
{
RNone = 0,
RError = 1,
};
void Log(Info, std::string a)
{
OutputDebugStringA(a.c_str());
}
void Log(Info severity, std::istream&& stream)
{
std::string message;
std::array<char, 64> buff{};
while (!stream.eof() && !stream.fail())
{
stream.read(buff.data(), buff.size());
message.append(buff.data(), static_cast<size_t>(stream.gcount()));
}
Log(severity, message);
}
// Наш основной цикл
int main() {
for (;;)
{
{
// метка профайлера
ProfileScopedEventStr("Game::TestMemory");
// Тут условно некоторая логика, которая выводит свои сообщения
// Это всё код из реальной игры
struct JsonParser
{
// тут возврат копии? или надеемся на RVO
std::vector<std::string> GetErrors()
{
return {{"no_pain"}};
}
} parser;
if (!parser.GetErrors().empty()) // обламываемся на RVO, потому что локальный
// объект
{
// непосредственно вывод ошибки в лог
Log(Info::RError,
std::stringstream()
<< std::string(" Invalid parameters ")
<< parser.GetErrors().front()); // второй раз обламываемся с RVO
// потому что std::string в stringsteam уходит копией
}
}
...
Game::step(dt);
}
}И видим очень интересную картинку в мемори профайлере PIXa. Этот код генерит 15 реальных алокаций просто чтобы вывести одну строку в лог. 2 аллокации я убрал, потому что это маркеры для OutputDebugStringA(), чтобы его можно было отфильтровать в поиске. И оно вот так работало всегда.
Увидев подобное безобразие пришлось чинить, а чинить такие вещи обычно сложно из-за кучи зависимостей, релейтед логики уже наверченной поверх всех этих систем. Но временные затраты и возвращаются сторицей в виде уменьшения расхода памяти, меньшей фрагментации и выросшим вдруг FPS (ненамного, всего +2 фпс после небольшой переделки системы логов). А поменяли то всего ничего, запретили и поправили код, который работал сo stringstreamи поменяли, там где было возможно вектора и строки на контейнеры с буферизацией.
void Log(Info, const char* a)
{
OutputDebugStringA(a);
}
template<typename ... Args>
void Log(Info severity, const char* fmt, const Args&...args)
{
std::array<char, 4096> buffer;
snprintf(buffer.data(), 4095, fmt, args...);
Log(severity, buffer.data());
}
// Наш основной цикл
int main() {
for (;;)
{
{
// метка профайлера
ProfileScopedEventStr("Game::TestMemory");
// Тут условно некоторая логика, которая выводит свои сообщения
struct JsonParser
{
const auto& GetErrors()
{
std::pmr::string error{&buffer};
errors.emplace_back(error);
return errors;
}
FixedMemoryResource<char, 4096> buffer;
std::pmr::vector<std::pmr::string> errors{&buffer};
} parser;
if (!parser.GetErrors().empty())
{
Log(Info::RError, " Invalid parameters %s",
parser.GetErrors().front().c_str());
}
}
...
Game::step(dt);
}
}Все данные которые использовал JsonParser выделяются локально, немного подрос размер стека, и стало немного старомодно, зато без аллокаций в MainThrd. На скриншоте нет аллокаций в основном треде, зато стало видно, что соседний тред тоже занимается фигней. Вот эти 68 байт аллокаций это короткие строки, от 20 до 60 символов, но это уже другая история.
Заключение
Проблемы с производительностью вызывают не только резкие выбросы аллокаций. Выделение множества небольших блоков памяти вдобавок приводит к плохой локальности кэша, особенно если игровой код обращается к этим данным последовательно, а строки это как раз та самая ахиллесова пята, которая постоянно наступает на эти грабли, и в большинстве случаев такие строки не больше 140 символов. Симптомы проблемы обычно проявляются в виде небольшого общего замедления, это "размазанный перф", который сложно точно определить с помощью профайлера.
Процесс оптимизации и убирания аллокаций относительно несложный, но затратный по времени и вносимым изменениям, да и к тому же "размазанный перф" убирается очень долго, кроме самых явных случаев. Нет какой-то критической точки, починив которую можно получить хороший прирост к перфу, даже в самых запущенных случаях вы получите +1%, но таких мест могут быть сотни. Само по себе время алокации достаточно маленькое, но оно комплексно влияет на весь стек вызова, порою давай буст не в самых очевидных местах. Поэтому при оптимизации работы с памятью лучше сравнивать с билдами недельной, а то и месячной давности при анализе прогресса.
16 мс на фрейм это слишком мало, чтобы разбрасываться этим временем и тратить его на алгоритмы аллокации памяти.
