Аллокаторы памяти
Предисловие
Для начала, хотелось бы сразу отметить, что если кто-то впервые слышит термины «аллокатор», «алгоритмы распределения памяти» и не понимает, для чего это все нужно, то тогда, прежде чем читать данную статью, я рекомендую ознакомиться с данным источником. В данной статье достаточно хорошо рассказывается, какие существуют проблемы в стандартных аллокаторах памяти, и для каких целей стоит использовать другие способы распределения памяти, помимо стандартных. Здесь же я буду рассказывать только о самих алгоритмах распределения, ну и, конечно же, в конце приведу реализацию одного из аллокаторов, которая может быть без проблем использована в стандартных контейнерах С++.
Основы
Концептуально выделяется пять основных операции, которые можно осуществить над аллокатором (хочется отметить, что не все аллокаторы могут явно соответствовать этому интерфейсу):
Linear Allocator
Linear Allocator, он же «линейный» — это самый простой вид аллокаторов. Идея состоит в том, чтобы сохранить указатель на начало блока памяти выделенному аллокатору, а также использовать другой указатель или числовое представление, которое необходимо будет перемещать каждый раз, когда выделение из аллокатора завершено. В этом аллокаторе внутренняя фрагментация сведена к минимуму, потому что все элементы вставляются последовательно (пространственная локальность), и единственная фрагментация между ними — выравнивание.
Дальше предлагаю рассмотреть несколько примеров, в которых будет наглядно показано в деталях, как работает данный аллокатор. Возьмем некоторый блок памяти равный 14 байтам и отдадим его в управление аллокатору. Как видно из картинки ниже, мы сохраняем указатель на начало памяти (start), а также храним два указателя, либо два числовых представления, которые содержат информацию об общем (end) и используемом (used) размерах памяти.
Представим, что в аллокатор поступил запрос на выделение 4 байт памяти. Действия аллокатора на исполнения этого запроса будут следующие:
Дальше, например, приходит запрос на выделение 8 байт и, соответственно, действия аллокатора будут точно такими же вне зависимости от размера выделяемого блока памяти.
А вот здесь уже будет немного интереснее, например, если приходит запрос на выделение только 1 байта, и если мы не хотим выравнивать блоки в памяти (например адреса кратные 2, 4, …), то действия аллокатора останутся точно такими же.
Но, если нам нужно выделять блоки памяти с определенным выравниванием (например выравнивание адресов кратных 2), то здесь действие аллокатора немного меняется. Меняется оно не в плане реализации, а в том, что помимо самих данных равных объему одного байта, мы еще забираем и один дополнительный байт из памяти аллокатора для выравнивания, который не несет никакой смысловой нагрузки. Как раз-таки это и есть та самая возможная минимальная фрагментация памяти внутри линейного аллокатора.
Отлично, теперь самое время поговорить об освобождении памяти. Как уже отмечалось ранее, данный вид аллокоторов не поддерживает выборочное освобождение определенных блоков памяти. То есть, если провести тонкую аналогию с malloc/free, имея указатель, скажем, на 0xFFAA00, мы могли бы освободить этот блок памяти, но вот линейный аллокатор нам этого позволить не может.
Все, что мы можем сделать, это освободить всю занятую память целиком внутри аллокатора и продолжить работать с ним, как с совершенно пустым.
Pool Allocator
Идея блочного аллокатора заключается в том, что он разделяет некоторый большой участок памяти на более мелкие участки одинакового размера. По своей сути он также является очень простым аллокатором, так как, когда запрашивается выделение, он просто возвращает один из свободных участков памяти фиксированного размера, а когда запрашивается освобождение то, он просто сохраняет этот участок памяти для дальнейшего использования. Таким образом, распределение работает очень быстро, а фрагментация все еще очень мала.
Дальше, также, как и с линейным аллокатором, предлагаю рассмотреть все на примере, чтобы детальнее понять, как он работает, поэтому возьмем некоторый блок памяти равный 12 байт и отдадим его в управление аллокатору. Как видно из картинки ниже, мы сохраняем указатель на начало (start) и конец (end) памяти, которой управляет аллокатор, а также список (freeblocks) из адресов свободных блоков в аллокаторе. В качестве средства для хранения данных о том, что блок занят или свободен, можно использовать много средств, например массив из булевых значений, но я именно решил остановиться на выборе односвязного списка, так как он наиболее просто и наглядно характеризует данную концепцию (кстати, сами звенья списка можно хранить в свободных блоках памяти, тем самым убрав дополнительные расходы с памятью).
Если приходит запрос на выделение одного блока памяти, то действия аллокатора очень примитивные. Сначала он проверяет, есть ли звенья в списке свободных блоков, если их там нет, то не трудно догадаться, что память в аллокаторе уже закончилась. Если же там есть хотя бы одно звено, то он просто достает корневое или хвостовое (в данной реализации отдаются хвостовые звенья) звено списка и отдает его адрес пользователю.
Если приходит запрос на выделение нескольких блоков памяти, то аллокатор точно так же по очереди проделывает те же действия, описанные на предыдущем шаге.
Что касается освобождения блока, если приходит запрос на освобождение, то тогда аллокатор просто добавляет этот адрес в один из концов односвязного списка. Стоит отметить такой момент, что в качестве адреса блока для освобождения может прийти, например адрес, несоответствующий адресу памяти аллокатора, например 0xEFAB12, и тогда будет возможна такая ситуация, что мы в дальнейшем отдадим пользователю тот участок памяти, который нам не принадлежит (конечно же, это приведет к undefined behavior или если очень сильно повезет, то просто к краху программы). Для избегания этой возможной проблемы как раз-таки и используются begin и end, которые позволяют проверить, не ошибся ли пользователь адресом во время запроса на операцию освобождения.
Помимо выхода за пределы памяти, которой не управляет аллокатор, есть еще одна возможная проблема. Пользователь может прийти с запросом освободить совершенно любой адрес, находящийся в области памяти аллокатора, но не равный адресу начала какого-либо из блоков, допустим блока с адресом 0xFFAA07. Эта операция, конечно же, приведет к undefined behavior. Если есть необходимость дополнительно проверять, все ли правильно делает пользователь, то есть возможность это отслеживать. Для отслеживания этого существует множество решений, например хранить также адреса и занятых блоков или вообще проверять адрес на кратность размеру блоков в аллокаторе (все зависит от фантазии и от конкертной ситуации, в которой используется аллокатор).
Stack Allocator
На самом деле, это умная эволюция линейного распределителя, которая позволяет управлять памятью, как стеком. Все так же, как и раньше, мы сохраняем указатель вместе с «header» блоком (в дальнейшем будет употребляться, как заголовок) на текущий адрес памяти и перемещаем его вперед для каждого выделения. В отличие от линейного аллокатора, мы также можем переместить его назад, то есть выполнить операцию deallocate, которая линейным аллокатором не поддерживается. Как и прежде, сохраняется принцип пространственной локальности, а фрагментация все еще минимальная.
Предлагаю рассмотреть несколько примеров все с тем же блоком памяти в 14 байт. Как и с линейным аллокатором, мы точно также сохраняем указатели на начало памяти (start) и конец (end), а также указатель на конец используемой памяти (used).
Когда приходит запрос на выделение памяти, помимо выделения некоего ее объема памяти, запрашиваемого пользователем, мы еще дополнительно выделяем заголовок (пользователь с ним никак не будет взаимодействовать), в котором храним сведения о том, сколько было выделено байт (в данном примере размер заголовка составляет 2 байта). Например, если пришел запрос на выделение 2 байт, то состояние аллокатора будет точно таким же, как на рисунке ниже. Важно отметить то, что пользователю будет отдан указатель не на заголовок, а на блок, следующий сразу за заголовком, то есть в данном примере это блок с адресом 0xFFAA02.
Аналогичная ситуация будет и, например с выделением 6 байт.
А вот с освобождением все немного поинтереснее (как уже обсуждалось ранее, выделять и освобождать память мы можем только с использованием алгоритма LIFO). Для начала от указателя, который пользователь просит освободить, нужно отнять размер заголовка, после чего разыменовать значение и уже только после этого сдвинуть указатель used на размер заголовка вместе с размером блока, полученного из заголовка. Здесь так же, как и с блочным аллокатором, возможна ситуация освобождения «рандомных» блоков памяти, которая также приведет к undefined behavior. Дополнять аллокаторы дополнительными проверками или нет – дело каждого. Самое главное — не забывать об этом моменте.
Теперь, разобравшись в основах, самое время освоить что-то более серьезное.
«Примитивный стандартный аллокатор»
Дальше будет представлена реализация аллокатора, который можно будет без проблем использовать с STL. Алгоритм распределения памяти в этом аллокаторе будет схож с алгоритмом, который используется стандартным аллокатором. Хочу сразу отметить, что не претендую на полноту реализации malloc, мною были взяты лишь основные концепции из него c добавлением в некоторых местах своей логики. Все его тонкости и нюансы, конечно же, не были учтены в этой реализации…
В основе алгоритма лежит взаимодействие с «chunks» (дальше будет употреблено, как участок, в данной реализации их размер статичен и должен быть кратен четырем, а также все выделения памяти из памяти аллоктора выравниваются на размер, кратный четырем), о которых дальше и пойдет речь. В качестве примера возьмем участок c размером 16 байт. Внутри себя он будет содержать указатели на начало (start) и конец (end) памяти, указатель на максимальный блок памяти (maxblock) и множество (freeblocks), в котором будут храниться заголовки свободных блоков. Размер заголовка в данной реализации занимает 4 байта, но он может без проблем варьироваться в размере для нужных вам целей. Например, если вы точно знаете, что размер выделяемых блоков памяти будет не больше, чем максимальное числовое значение, которое можно представить в одно или двухбайтной переменной, то можно будет использовать заголовок в размере 1 или 2 байт.
При операции выделения памяти из участка, прежде всего нужно проверить, достаточно ли памяти (в данной реализации, это константная операция, мы просто сравниваем с maxblock заголовком и, если размер аллоцируемой памяти меньше, чем максимальный блок, то значит у нас достаточно памяти для этого выделения). Если памяти достаточно, то мы просто отдаем адрес памяти, следующий за заголовком, как и в стековом аллокаторе, а также удаляем прошлый заголовок из множества свободных блоков и уже только после этого добавляем туда новый заголовок, только что выделенного блока памяти. Важно отметить, что если мы аллоцировали память из максимального блока, то нам нужно будет обновить значение максимального блока.
При последующих выделениях все происходит точно также, как и на предыдущем шаге.
Но вот как только память в участке закончилась, аллокатор берет и просто создает еще один участок того же или большего размера (в данной реализации все участки одинакового размера). Стоит также следить за тем, чтобы размер возможного блока для выделения не превышал размер участка с вычетом размера заголовка.
Дальше уже в новом участке можно без проблем выделять нужные блоки памяти. Выделение памяти будет происходить по точно такому же сценарию, как и в предыдущем участке.
Теперь немного о том, почему именно в данной реализации размер участка должен быть кратен четырем. Ответ очень просто – это делается для простоты реализации и восприятия алгоритма. Так как возможна такая ситуация, что в конце участка может остаться некоторая область памяти, в которой просто на просто не поместится заголовок (пример этого продемонстрирован на следующем рисунке). Чтобы решить эту проблему, можно будет заполнять эту память дополнительным выравниваем, либо делать размер заголовка меньшим или же использовать дополнительные средства для отслеживания этой возможной проблемы, иначе эта память будет потеряна и самая главное, что в дальнейшем потерянная память сможет накапливаться!
Прежде, чем освободить память, нужно определить, в каком участке находится блок (в текущей реализации эта операция с линейной сложностью относительно общего количества участков, если подразумевается, что будет большое количество участков, то ее можно будет сделать константной, добавив в заголовок индекс участка, в котором была выделена память). В последующем операция освобождения идентична со стековым аллокатором, за исключением того, что нужно будет добавить адрес заголовка освобожденного блока во множество свободных блоков, а также обновить maxblock, если размер только что освобожденного блока больше, чем maxblock.
Важно отметить, что в данной реализации, при каждом последующем освобождении памяти происходит попытка дефрагментации в том участке из которого была освобождена память. Дефрагментация нужна для того, чтобы объединять свободные блоки в большие по размеру. Например, в данной ситуации, как на рисунке ниже, мы не сможем выделить 6 байт, пусть даже размер свободной памяти нам и позволяет это сделать, но зато фрагментация говорит нам твердое и решительное «нет»!
Операция дефрагментации очень примитивная. Суть ее заключается в том, что после операции освобождения памяти идет проверка, не свободны ли два соседних блока слева и справа от освобожденного. Если два соседствующих блока свободны, то они объединяются в один единый.
Еще хотелось бы отметить, что данная реализация будет катастрофически ужасно работать с выделением маленьких блоков памяти, например равных 1 байту. В такой ситуации мы получаем +7 лишних байт на выделение всего лишь одно байта памяти из-за того, что размер заголовка равен 4 байтам и еще плюс 3 байта для вырывания адресов, которые должны быть кратны четырем. Этим я хочу сказать, что не стоит слепо использовать какой-либо алгоритм распределения памяти, так как вместо долгожданной оптимизации иногда можно получить только лишь дополнительные затраты.
Думаю, теории будет достаточно и поэтому, как сказал Линус Торвальдс: «Болтовня ничего не стоит. Покажите мне код». Ну что ж, приступаем…
Реализация
Требования к аллокаторам приведены в стадарте С++ в главе «Allocator requirements [allocator.requirements]«. Исходя из тех требований самый примитивный интерфейс аллокатора, который может использоваться в STL, должен выглядеть примерно вот так:
Предполагается, что STL контейнеры обращаются к аллокатору не напрямую, а через шаблон std::allocator_traits, который предоставляет значения, такие как:
Отлично, с требованиями разобрались, теперь наконец приступаем к написанию аллокатора. Для начала напишем некоторый интерфейс или адаптер, на самом деле это трудно назвать и тем, и другим, поэтому пусть это будет некая «прослойка», в которой при помощи стратегий мы сможем без проблем менять алгоритм аллоцирования памяти для определенных целей:
Благодаря стратегии для распределения памяти, мы сможем делать примерно вот так:
То есть мы можем гибко менять алгоритмы распределения для необходимых целей в той или иной ситуации. Единственное требование к AllocationStrategy — у них должны быть операции allocate и deallocate.
Здесь и дальше используются стандартные контейнеры. Согласен, что будет очень много выделений из кучи. Думаю, что для тех, кто будет писать свои аллокаторы, это будет неприемлемо. В качестве альтернативы, конечно же, можно писать свои контейнеры или использовать чужие, заточенные под определенные нужды, но в данной реализации я старался как можно проще преподнести материал, поэтому мой выбор лег именно на стандартные контейнеры.
Теперь немного о том, как можно украсить использование аллокаторов вместе со стандартными контейнерами:
Можно также использовать аллокаторы и с умными указателями, но для этого придется написать небольшую прослойку:
Ну и теперь, наконец, пример использования всего этого:
Хотелось бы заострить внимание на том, что данная реализация является самой примитивной, но она может быть без проблем расширена в ту сторону, которая вам необходима, поэтому все в ваших руках!
Заключение
Спасибо за внимание, очень надеюсь, что данная статья оказалась кому-то полезной. Также желаю всем успехов в тесном взаимодействии с памятью, и самое главное, не забывать очень важные слова Дональда Кнута: «Преждевременная оптимизация — корень всех зол».
Ссылка на репозиторий с полной реализацией аллокатора.
Привет, Хабр! В этой статье я попытаюсь рассказать, что из себя представляет менеджмент памяти в программах/приложениях с точки зрения прикладного программиста. Это не исчерпывающее руководство или мануал, а просто обзор существующих проблем и некоторых подходов к их решению.
Зачем это необходимо? Программа — это последовательность команд по обработке данных (в самом общем случае). Эти данные необходимо некоторым образом хранить, загружать, передавать и т.д. Все эти операции не происходят мгновенно, следовательно, они непосредственно влияют на скорость работы вашего конечного приложения. Умение оптимально управлять данными в процессе работы позволит вам создавать весьма нетривиальные и очень требовательные к ресурсам программы.
Замечание: основная часть материала излагается с примерами из игр/игровых движков (т.к. эта тема более интересная лично для меня), однако большую часть материала можно применить и к написанию серверов, пользовательских приложений, пакетов графики и т.д.
Невозможно все держать в памяти. Но если не успел подгрузить, то получишь мыло
С места в карьер
Да, в проектах типа «Minecraft» работа GC может быть и незаметна, т.к. они в целом не требовательны к ресурсам вычислителя, однако такие игры, как «Red Dead Redemption 2», «God of War», «Last of Us», работают «едва ли» не на пике производительности системы и поэтому нуждаются не только в большом количестве ресурсов, но и в грамотном их распределении.
Кроме этого, работая в среде с автоматическим выделением памяти и сборкой мусора, вы можете столкнуться с нехваткой гибкости в управлении ресурсами. Не секрет, что Java скрывает под капотом все детали реализации и аспекты своей работы, поэтому на выходе вы имеете только установленный интерфейс взаимодействия с ресурсами системы, но его может не хватить при решении некоторых задач. Например, запуск в каждом кадре алгоритма с неконстантным количеством аллокаций памяти (это может быть поиск путей для AI, проверка видимости, анимации, и т.д.) неизбежно ведет к катастрофическому падению производительности.
Как выглядят аллокации в коде
Прежде чем продолжить изложение, я бы хотел показать, как непосредственно происходит работа с памятью в C/C++ на паре примеров. В общем случае, стандартный и самый простой интерфейс для распределения памяти процесса представляется следующими операциями:
Здесь можно добавить про дополнительные функции, которые позволяют выделить выровненный участок памяти:
Обратите внимание на то, что на различных платформах могут поддерживаться различные стандарты функций, доступные, например на macOS, и недоступные на win.
Забегая вперед, выровненные особым образом участки памяти могут вам понадобиться как для попадания в кэш-линии процессора, так и для вычислений с помощью расширенного набора регистров (SSE, MMX, AVX, и т.д).
Пример «игрушечной» программы, которая выделяет память и печатает значения буфера, интерпретируя их как целые числа со знаком:
На macOS 10.14 данную программу можно собрать и запустить следующим набором команд:
Замечание: здесь и далее я не очень хочу освещать такие операции C++ как new/delete, так как они скорее относятся к конструированию/уничтожению непосредственно объектов, но под собой используют обычные операции по работе с памятью наподобие malloc/free.
Проблемы с памятью
Существует несколько проблем, возникающих при работе с ОЗУ компьютера. Все они, так или иначе, вызваны не только особенностями ОС и ПО, но и архитектурой железа, на котором все это добро работает.
1. Количество памяти
К сожалению, память ограничена физически. На PlayStation 4 это 8 GiB GDDR5, 3.5 GiB из которых операционная система резервирует для своих нужд. Виртуальная память и подкачка страниц особо не помогут, так как swapping страниц на диск — операция весьма медленная (в рамках фиксированных N кадров в секунду, если говорить об играх).
Также стоит отметить и ограниченный «бюджет» — некоторое искусственное ограничение на объем используемой памяти, созданное с целью запуска приложения на нескольких платформах. Если вы создаете игру для мобильной платформы и хотите поддержать не одно, а целую линейку устройств, вам придется ограничить свои аппетиты в угоду обеспечения более широкого рынка сбыта. Это может быть достигнуто как просто ограничением расхода ОЗУ, так и возможностью конфигурировать это ограничение в зависимости от гаджета, на котором игра, собственно, запускается.
2. Фрагментация
Неприятный эффект, который появляется в процессе множественных аллокаций кусочков памяти различного размера. В результате вы получаете раздробленное на множество отдельных частей адресное пространство. Объединить эти части в единые блоки бОльшего размера не выйдет, так как часть памяти занята, и свободно перемещать ее мы не можем.
Фрагментация на примере последовательных аллокаций и освобождений блоков памяти
В итоге: имеем может и достаточно свободной памяти количественно, но не качественно. И очередной запрос, скажем, «выделить место под аудио дорожку» аллокатор удовлетворить не сможет, т.к единого куска памяти такого размера просто нет.
3. Кэш процессора
Иерархия памяти компьютера
Кэш современного процессора — это некоторое промежуточное звено, которое связывает главную память (ОЗУ) и непосредственно регистры процессора. Так получилось, что доступ к памяти на чтение/запись — это весьма медленные операции (если говорить о кол-ве тактов CPU, необходимых для выполнения). Поэтому существует некоторая иерархия кэша (L1, L2, L3, и тд), которая позволяет как бы «по некоторому предсказанию» подгружать данные из ОЗУ, или неспешно их вытеснять в более медленную память.
Размещение однотипных объектов подряд в памяти позволяет «значительно» ускорить процесс их обработки (если обработка происходит последовательно), так как в этом случае проще предсказать, какие данные понадобятся дальше. И под «значительно» понимается прирост производительности в разы. Об этом неоднократно говорили разработчики движка Unity в своих докладах на GDC.
4. Multi-Threading
Обеспечение безопасного доступа к разделяемой памяти в многопоточной среде является одной из основных проблем, которую вам придется решать при создании собственного игрового движка/игры/любого другого приложения, которое использует несколько потоков для достижения бОльшей производительности. Современные вычислители устроены весьма нетривиальным образом. У нас имеется и сложная структура кэша, и несколько ядер вычислителя. Все это при неправильном использовании может привести к ситуациям, когда разделяемые данные вашего процесса будут повреждены в результате работы нескольких потоков (если они одновременно попытаются работать с этими данными без контроля доступа). В самом простом случае, это будет выглядеть следующим образом:
Я не хочу углубляться в тему многопоточного программирования, так как множество его аспектов выходит очень сильно за рамки изложения статьи или даже целой книги.
5. Malloc/free
Операции по выделению/освобождению не происходят мгновенно. На современных ОС, если мы говорим про Windows/Linux/MacOS они реализованы хорошо и работают в большинстве ситуаций быстро. Но потенциально это весьма трудоемкие операции. Мало того, что это является системным вызовом, так еще в зависимости от реализации это может потребовать время для поиска подходящего куска памяти (First Fit, Best fit, и тд.) или поиска места для вставки и/или мерджа освобожденного участка.
Кроме того, свеже-выделенная память может быть в действительности не отображена на реальные физические страницы, что при первом обращении также может потребовать некоторое время.
Это детали реализации, а что с применимостью? Malloc/new не имеют представления о том, в каком месте, как и для чего вы их вызвали. Они выделяют память (в худшем случае) размером 1 KiB и 100 MiB одинаково… одинаково плохо. Непосредственно стратегия использования отдается на откуп либо программисту, либо тому, кто реализовал среду исполнения вашей программы.
6. Memory corruption
Как говорит вики, это одна из самых непредсказуемых ошибок, проявляется только в ходе работы программы, и чаще всего вызвана непосредственно ошибками в написании этой программы. Но что эта проблема из себя представляет? К счастью (или сожалению), она не связана с коррумпированностью вашего компьютера. Скорее она отображает ситуацию, когда вы пытаетесь работать с памятью, которая вам не принадлежит. Сейчас поясню:
В С/С++, где есть арифметика указателей, с этим вы столкнетесь на раз-два. Однако в Java Runtime придется изрядно попотеть, чтобы получить подобного рода ошибку (сам не пробовал, но думаю, что такое возможно, иначе жизнь была бы слишком простой).
7. Утечки памяти
Является частным случаем более общей проблемы, встречающейся во многих языках программирования. Стандартная библиотека C/C++ предоставляет доступ к ресурсам ОС. Это могут быть файлы, сокеты, память и т.д. После использования ресурс должен быть корректно закрыт и
занятую им память следует освободить. И если говорить конкретно об освобождении памяти — накапливающиеся утечки в результате работы программы могут привести к «out of memory» ошибке, когда ОС будет не способна удовлетворить очередной запрос на аллокацию. Часто разработчик просто забывает освободить использованную память по тем или иным причинам.
Здесь же стоит добавить про корректное закрытие и освобождение ресурсов на GPU, т.к ранние драйверы не позволяли возобновить работу с видеокартой если предыдущий сеанс был завершен неверно. Только перезагрузка системы могла решить эту проблему, что является весьма сомнительным — заставлять юзера перезагружать систему после работы вашего приложения.
8. Dangling pointer
Висячий указатель — некоторый жаргон, описывает ситуацию, когда указатель ссылается на недопустимое значение. Подобная ситуация может запросто возникнуть при использовании классических C-style указателей в C/C++ программе. Предположим, вы выделили память, сохранили адрес на нее в указателе p, а потом освободили память (см. пример кода):
Указатель хранит некоторое значение, которое мы можем интерпретировать как адрес блока памяти. Так получилось, что мы не можем утверждать, является ли этот блок памяти валидным, или нет. Только программист, основываясь на тех или иных соглашениях, может оперировать указателем. Начиная с C++11 в стандартную библиотеку были введены ряд дополнительных указателей «smart pointers», которые позволяют в некотором плане ослабить контроль ресурсов со стороны программиста за счет использования дополнительной мета-информации внутри себя (об этом позже).
Как частичное решение можно использовать специальное значение указателя, которое будет сигнализировать нам о том, что по этому адресу ничего нет. В C в кастве этого значения используется макрос NULL, а в C++ ключевое слово языка nullptr. Решение это частичное, так как:
Пример кода с null:
Можно в некоторой степени автоматизировать этот процесс:
9. Тип памяти
RAM — обычная оперативная память общего назначения, доступ к которой через центральную шину имеют все ядра вашего процессора и устройства периферии. Ее объем варьируется, но чаще всего речь идет о N гигабайтах, где N равняется 1,2,4,8,16 и тд. Вызовы malloc/free стремятся разместить желаемый вами блок памяти как раз в RAM компьютера.
VRAM (video memory) — видео память, поставляется вместе с видеокартой/видео-ускорителем вашего ПК. Она, как правило, меньшего объема чем RAM (порядка 1,2,4 GiB), однако обладает большим быстродействием. Распределением этого типа памяти занимается драйвер видеокарты, и чаще всего прямого доступа к ней вы не имеете.
На PlayStation 4 такого разделения нет, и вся оперативная память представлена едиными 8 гигабайтами на GDDR5. Поэтому все данные, как для процессора, так и для видео-ускорителя лежат рядом.
Хороший менеджмент ресурсов в игровом движке включает в себя грамотное распределение памяти как в Main RAM, так и на стороне VRAM. Здесь можно столкнуться с дублированием, когда одни и те же данные будут находятся там и там, или с избыточным трансфером данных с RAM на VRAM и обратно.
В качестве иллюстрации ко всем озвученным проблемам: можно посмотреть на аспекты устройства компьютеров на примере архитектуры PlayStation 4 (рис.). Здесь представлен центральный процессор, 8 ядер, кэши уровня L1 и L2, шины данных, оперативная память, графический ускоритель и т.д. С полным и подробным описанием можно ознакомиться в книге Джейсона Грегори «Game Engine Architecture».
Архитектура PlayStation 4
Общие подходы к решению
Универсального решения нет. Но есть набор некоторых моментов, на которых следует акцентировать внимание, если вы собираетесь реализовывать мануально аллокацию и управление памятью в вашем приложении. Сюда можно отнести и контейнеры, и специализированные аллокаторы, стратегии выделения памяти, дизайн системы/игры, менеджеры ресурсов и другое.
Типы аллокаторов
Использование специальных аллокаторов памяти основывается на следующей идее: вы знаете, какого размера, в какой моменты работы и в каком месте вам понадобятся участки памяти. Следовательно, вы можете выделить необходимую память, как-то ее структурировать и использовать / переиспользовать. В этом состоит общая идея/концепция использования специальных аллокаторов. Какие они бывают (разумеется не все) можно посмотреть далее:
Linear allocator
Представляет буфер непрерывного адресного пространства. В ходе работы позволяет выделять участки памяти произвольного размера (такие, что они умещаются в буфер). Но освободить всю выделенную память можно только за 1 раз. Т.е произвольный участок памяти не может быть освобожден — он будет оставаться как бы занятым до тех пор, пока весь буфер не будет помечен как чистый. Такая конструкция обеспечивает выделение и освобождение за O(1), что дает гарантию скорости при любых условиях.
Типичный use-case: в процессе обновления состояния процесса (каждый кадр в игре) вы можете использовать LinearAllocator для выделения tmp буферов для каких-либо технических нужд: обработка ввода, работа со строками, парсинг команд ConsoleManager в режиме отладки и т.д.
Stack allocator
Модификация линейного аллокатора. Позволяет освобождать память в порядке, обратном порядку выделения, иными словами, ведет себя как обычный стек по принципу LIFO. Может быть весьма полезен для проведения нагруженных математических вычислений (иерархия трансформаций), для реализации работы скриптовой подсистемы, для любых вычислений, где наперед известен указанный порядок освобождения памяти.
Простота конструкции обеспечивает O(1) скорость выделения и освобождения памяти.
Pool allocator
Позволяет выделять блоки памяти одинакового размера. Может быть реализован как буфер непрерывного адресного пространства, разбитый на блоки заранее установленного размера. Эти блоки могут образовывать связный список. И мы всегда знаем, какой блок отдать при аллокации следующим. Эту мета информацию можно сохранить в самих блоках, что накладывает ограничение на минимальный размер блока (sizeof(void*)). В реальности это не критично.
Поскольку все блоки имеют единый размер, нам не принципиально, какой блок возвращать, а следовательно все операции по выделению/освобождению могут быть выполнены за O(1).
Frame allocator
Линейный аллокатор но только с привязкой к текущему кадру — позволяет делать tmp выделения памяти и затем при смене кадра автоматически все освобождать. Его стоит выделить отдельно, так как это некоторая глобальная и уникальная сущность в рамках runtime игры, а поэтому его можно сделать весьма внушительного размера, скажем пара десятков MiB, что будет весьма кстати при загрузке ресурсов и их обработке.
Double frame allocator
Представляет собой двойной frame allocator, но с некоторой особенностью. Он позволяет выделять память в ткущем кадре, и использовать ее как в текущем, так и в следующем кадрах. Т.е память, которую вы выделили в кадре N, будет освобождена только после N+1 кадра. Реализуется это переключением активного frame для выделения в конце каждого кадра.
Но этот тип аллокатора как и предыдущий накладывает ряд ограничений на время жизни объектов, созданных в выделенной им памяти. Поэтому вы должны отдавать себе отчет о том, что по завершении кадра данные просто станут невалидными, и повторное к ним обращение может повлечь за собой серьезные проблемы.
Static allocator
Аллокатор такого типа распределяет память из буфера, полученного, например, на этапе запуска программы, либо захваченного на стеке в фрейме функции. По типу это может быть совершенно любой аллокатор: linear, pool, stack. Почему он называется статический? Размер захватываемого буфера памяти должен быть известен на этапе компиляции программы. Это накладывает существенное ограничение: объем доступной этому аллокатору памяти не можем изменяться во время работы. Но каковы преимущества? Используемый буфер будет автоматически захвачен и потом освобожден (либо по завершении работы, либо при выходе из функции). Это не нагружает кучу, избавляет вас от фрагментации, позволяет быстро выделить память по месту.
Можно посмотреть на примере кода использование этого аллокатора, если вам необходимо разбить строку на подстроки и что-то с ними сделать:
Также можно отметить, что использование памяти из стека в теории значительно эффективнее, т.к. стек фрейм текущей функции с большой вероятностью уже будет в кэше процессора.
Все эти аллокаторы так или иначе решают проблемы с фрагментацией, с нехваткой памяти, со скоростью получения и освобождения блоков необходимого размера, с временем жизни объектов и занимаемой ими памятью.
Следует так же отметить, что правильный подход к дизайну интерфейсов позволит вам создавать своего рода иерархии аллокаторов, когда, например: pool выделит память из frame alloc, а frame alloc в свою очередь выделит память из linear alloc. Подобную структуру можно продолжить и дальше, адаптируя под свои задачи и нужды.
Подобный интерфейс для создания иерархий мне видится следующим образом:
В него вы можете обернуть стандартные для вышей платформы malloc/free операций, что также даст дополнительную гибкость. Более того, подобные классы дают вам больше возможностей для профилирования, вы с легкостью сможете добавить подсчет необходимой статистики внутри реализации этих методов. В этот интерфейс можно было бы добавить синтаксический сахар по созданию/удалению объектов с использованием шаблонов, но лучше оставить это для следующего раза.
Умные указатели
Smart pointer — это некоторая разновидность указателей в стандартной библиотеке C++ начиная с С++11 (не говорите про boost, разговор только о стандарте). Представляет собой класс-обертку, который хранит собственно сам указатель, осуществляет операции над ним и содержит дополнительную мета-информацию о том, как и когда освободить память и удалить объект. В этом месте мы немного отходим от непосредственно выделения памяти к скорее отслеживанию времени жизни объекта.
Так что же позволяют делать умные указатели? В самом простом случае это:
Следующие виды умных указателей являются основными и самыми распространенными:
Unique pointer
Позволяет иметь в программе только 1 указатель на объект (уникальность доступа).
Как только unique pointer удаляется, сразу же удаляется используемый объект и освобождается занятая им память. Хорошо подходит для создания указателей на файловые дескрипторы, т.к. чаще всего только 1 участник может читать/писать файл.
Если вы передаете указатель на объект из uniquePtr1 в uniquePtr2, то значение в uniquePtr1 инвалидируется, т.к допускается только 1 владелец объекта.
Shared pointer
Указатели раздельного доступа с автоматическим подсчетом ссылок (reference counting). Позволяют нескольким участникам ссылаться на один объект, не беспокоясь о том, кто в итоге должен удалить его. Поскольку подсчет ссылок автоматический, то, как только последний ссылающийся указатель удален, объект также будет удален.
Однако такой вид указателя не лишен недостатков. Во-первых, он не способен бороться с циклическими ссылками, когда объекты ссылаются друг на друга. В таком случае вы гарантированно получите утечку памяти. Во-вторых, в много-поточной среде работа с указателями раздельного доступа накладывает свои ограничения на консистентность памяти и раздельность доступа потоками.
Weak pointer
Слабая ссылка на объект. Позволяет хранить указатель на объект раздельного доступа, но не удерживать его. Что это значит? Вы можете создать объект и сохранить указатель на него в shared pointer. До тех пор, пока последний shared pointer не удален, объект будет оставаться в памяти. Однако, вы можете создать из shared pointer weak pointer. Таким образом, если сильные (shared) указатели остались на объект, то из weak pointer вы можете получить shared pointer. А если нет — то weak pointer инвалидируется, и вы узнаете о том, что объект, на который вы хранили указатель уже удален.
Недостатком как shared, так и weak pointer является необходимость хранить дополнительно meta-data для каждого объекта. Здесь храниться и кол-во ссылок на объект, способ его удаления и т.д. В общем случае, это O(N) overhead по памяти, где N — кол-во создаваемых объектов. Однако такую жертву можно считать допустимой, т.к в проекте на тысячи строк кода вам будет тяжело договориться с другим программистом о том, кто ответственен за удаление того или иного объекта. В противном случае висячие ссылки и утечки памяти гарантированы.
Финальная мысль в этой части: использовать умные указатели необходимо с также некоторой долей осторожности. Например, используя shared pointer, вы неявно соглашаетесь с тем, что ваш объект (на который вы ссылаетесь через этот указатель) будет где-то когда-то кем-то удален. И это может быть не самый удачный момент работы вашей программы. Кроме это вы должны отдавать себе отчет о расходуемой памяти на meta-info и о том, как данные, на которые вы ссылаетесь через умный указатель будут попадать в кэш. Пример:
Пример достаточно вымученный. Однако во многих ситуация мы можем отказаться от использования тяжеловесных умных указателей. Об этом далее.
Unique id
Никто не заставляет нас использовать указатели, чтобы обращаться к объектам. Мы можем использовать идентефикаторы (id/identificator), выраженные целым числом, строкой, или еще как-то. Каковы преимущества данного подхода:
Очевидным недостатками такого подхода являются: необходимость контролировать уникальность id, ограничивать количество объектов, которые могут быть адресованы через id, жертвовать контролем и использовать посредника для доступа к объекту.
Подобные id повсеместно используют в современных приложения, библиотеках (Vulkan, OpenGL), игровых движках (Godot, CryEngine). Об EntityID можно почитать в документации к упомянутому уже CryEngine.
Рассмотрим простой пример, когда id представлен двумя числами: индекс и поколение. Индекс говорит нам о том, где конкретно лежит объект (в какой ячейке массива), а поколение указывает на но, был ли объект удален или нет.
Теперь по ID обработчик будет в состоянии найти объект или определить, что объекта с таким ID нет. Это можно сделать следующим образом:
При удалении объекта по его id мы просто должны увеличить счетчик generation на 1 у соответствующего id из массива ids.
Контейнеры
В стандартной библиотеке языка C++ есть множество классов, которые облегчают работу с тем или иным видом объектов. И здесь это не реклама std, вы можете самостоятельно реализовать единожды необходимые вам контейнеры, а затем переиспользовать их неограниченное число раз. В первую очередь обратите внимание на следующие классы:
Почему я их упоминаю в статье про менеджмент памяти? Потому что они контролируют доступ к объектам внутри себя и исключают возможность memory corruption. Вызывая необходимые методы вы с легкостью сможете добавлять/удалять объекты, получать на них ссылки, итерироваться по ним, не задумываясь о том, где и как они лежат.
Общие идеи
Здесь мне бы хотелось уйти от конкретики к более абстрактным вещам, которые касаются не столько кода, сколько архитектуры и дизайна системы в целом. Ряд наблюдений, мыслей, которые мне удавалось увидеть/прочесть в том или ином источнике литературы за долгое время.
Под конкретные задачи
При создании системы, разработчик как никто иной должен знать, какие данные и как он будет обрабатывать. На основе этого он сможет выбрать ту стратегию выделения памяти и работы с ней, которая наилучшим (в рамках задачи) образом подходит ему. Как было сказано ранее, библиотечные функции malloc/free не знают, как и для чего вы их вызвали, поэтому полагаться на их производительность при решении весьма специфических задач не стоит.
Что требуется брать в расчет? Вы можете определить, сколько памяти вам потребуется (нижняя/верхняя граница), в какие моменты работы программы, какие задачи потребуют множество аллокаций, а какие нет. Можно порассуждать о том, можно ли часть аллокаций убрать, разместить данные на стеке, перенести запросы на выделение из нагруженных частей программы в менее нагруженные.
СryEngine Sandbox: как пример среды для разработки игр
Крупные игровые движки, такие как Unreal, Unity, CryEngine и т.д, ничего не знают о том, какую игру вы делаете. Да, они могут быть заточены под определенные механики, жанры, но в общем случае — только вы сможете настроить систему таким образом, что она будет в состоянии удовлетворить ваши запросы на размещение тех или иных ресурсов в памяти компьютера.
Pre-allocating
Заранее получить всю необходимую память для работы программы, разместить в ней необходимые объекты и/или распределять эту память под свои нужды уже в процессе работы.
Преимущество такого подхода очевидно: никаких запросов malloc/free на выделение памяти в течение работы. Отсюда вытекает и тот факт, что ОС не скажет вам «run out of memory», т.к все необходимое вы получили заранее и не более. Теперь вы сможете работать с памятью в том стиле, который требуется для решения ваших задач (выравнивание, попадание в кэш, упаковка данных подряд и т.д).
Но такой подход очень сложен в реализации. Он требует ручного распределения памяти среди всех объектов вашей системы. Более того, вы неизбежно можете столкнуться с перерасходом и большим кол-вом неиспользуемой памяти. Если ваша система будет делать множество динамических аллокаций в процессе работы, то такой подход неизбежно приведет ко всем тем проблемам с malloc/free, которые были озвучены ранее: фрагментация, долгие вызовы, нехватка памяти.
Не надо бояться динамической памяти
В наше время многие системы требуют динамического выделения памяти в процессе работы. И это нормально: вы не можете знать заранее, какого размера вам на вход попал файл, текстура, меш и т.д. Современные вычислители смогут позволить себе пару тысяч динамических аллокаций без потерь в производительности.
Однако не стоит увлекаться: если вы знаете, как и какая подсистема использует ресурсы, то лучше двигаться в сторону специализированных аллокаторов, адаптированных под конкретные цели. Большинство open-source движков, исходный код которых мне удавалось посмотреть, по такому принципу и работают. Где они могут, там оптимизируют, где нет — отдают все на откуп malloc/free.
Дизайн из ограничений
На GDC компания CD Project Red представила интересный доклад, в котором дизайнер уровней рассказал, как они создавали архитектуру игровых локаций «The Witcher: Blood and Wine» в условиях четких (количественных) ограничений на расход памяти и время подгрузки локаций. Им приходилось выверять количество геометрии, которая будет загружена в памяти, выстраивать здания таким образом, что движок будет способен подгрузить все необходимые данные налету, пока игрок идет из точки А в точку Б.
В одной из статей дизайнер локаций из Naughty Dog также упомянул, что им приходилось при разработке «Uncharted 4: A Thief’s End» оптимизировать мир игры таким образом, что в любой момент времени вся обозримая часть (то, что находиться в кадре) локации могла быть успешно обработана движком игры. 
Заключение
В конце хотелось бы отметить, что управление памятью программы, как и управление други ресурсами, выходит далеко за рамки простых менеджеров памяти и структур данных. В рамках игровых движков существует множество аспектов, которые так или иначе связаны с темой этой статьи. Это может быть и загрузка/хранение ресурсов, отслеживание времени жизни игровых объектов, обеспечение безопасности много-поточного доступа и т.д. Со всеми моментами можно и необходимо познакомиться, прочитав специальную литературу по каждой из тем (конечно, если вам это интересно).