Управление памятью

После перерыва в 3 года решил всё таки вернуться к играм и начинаю с рефакторинга движка. Первая на очереди подсистема управления памятью.
Основные требования:
1) быстрая аллокация в критических местах;
2) контролируемая сборка мусора;
3) минимизация фрагментации памяти;
4) средства для отслеживания утечек.

Хочется чтобы всё работало следующим образом:
somePtr = RAM_ALLOC(size, HINT_FRAME)
Здесь хинт указывает на время жизни данных, варианты:
PERMANENT - живёт постоянно на протяжении всей работы программы;
LEVEL - живёт в течение одного уровня;
FRAME - живёт в течение одного кадра;
TEMP - живёт в течение одного использования (потом поясню).

Каждый вид аллокаций обрабатывается своим менеджером.
PERMANENT - можно использовать стандартный аллокатор, скорость работы тут не очень важна.
LEVEL и FRAME используют по два аллокатора Small Object Heap и Large Object Heap с разными стратегиями работы.
  SOH - имеет фиксированную кучу, аллокация осуществляется увеличением вершины кучи. При достижении конца кучи, делаем реалокацию  с увеличением объёма.
  После очистки кучи, размер будет новым. В кучу попадают все объекты размером менее 1 страницы (4К). Освобождения объектов нет.
  LOH - для объектов более 1 страницы. Выделение памяти идёт кратно размеру страницы. При исчерпании размера получаем исключение. Объекты можно освобождать.
Для LEVEL и FRAME используются кучи с разным размером. Для FRAME SOH и LOH соответственно значительно меньше. По окончанию времени жизни кучи она очищается.

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

В данной схеме утечки возможны только в PERMANENT куче. Для борьбы ничего кроме обычной привязки выделеного блока к месту выделения не придумал (file,line).

Хочу обсудить плюсы/минусы решения, а также ваши варианты.

ты это сам придумал? звучит интересно, я такого подхода не припомню.

можно пойти дальше и отвязать менеджер памяти от игровой специфики. сделать иерархию рангов - аналоги твоих level и frame. то есть при освобождении ранга N удаляются все выделенные объекты с рангом <= N. то есть чем меньше ранг, тем меньше живут объекты. то есть игровой цикл выглядит как-то так:

struct ObjectRanks
{
  enum
  {
    Frame, Level, Session, Permanent
  };
};
//....
while(running)
{
  if(changeLevel)
  {
    memManager->Release(ObjectRanks::Level);

    Object* levelTimeObject = memManager->Alloc<SomeObject>(ObjectRanks::Level);
    Object* otherLevelTimeObject = memManager->Alloc<SomeOtherObject>(ObjectRanks::Level);
  }
  //Render(), Input()....
  memManager->Release(ObjectRanks::Frame);
}
memManager->Release(ObjectRanks::Permanent);
exit(0);

Интересно, какие будут подводные камни? Пока мне только не нравится ситуация с тем, что если объект выделяет память для своих подобъектов, то убиты они будут в произвольном порядке.

Мизраэль
>Основные требования:
>1) быстрая аллокация в критических местах;
>2) контролируемая сборка мусора;
>3) минимизация фрагментации памяти;
>4) средства для отслеживания утечек.

берем : data driven + компонентная система (никаких INode, IRenderable и тд) + константные размеры пулов
получаем :
1) мы всегда при загрузке знаем сколько игре надо памяти на этом уровне, те знаем что игре надо 10 метров на компоненты, 5 метров на VBO, 10 текстур по 2048*2048, вот сидим и выделяем эту память за один раз
2) никаких динамических аллокаций в принципе
3) никакой сборки мусора
4) никакой фрагментации
5) никаких утечек
6) максимальная производительность
7) при правильно прямых руках - полная минимизация кеш мисов

ps. консольный подход

.::jimon::.
я тоже такое хотел предложить, так как в играх все очень предсказуемо и грех этим не воспользоваться

Suslik
> ты это сам придумал?
Не, ArenaAllocators

.::jimon::.
> data driven + компонентная система (никаких INode, IRenderable и тд)
А можно подробней о плюсах? Или сцылочкой... Просто я вижу только неудобства таких методов (смотрел пару презенташек и имел дело с одним творением подобного подхода).

DeadMeat
хым, по data-driven :
1) игра делается вне движка, игра делается в редакторе из компонент (привет юнити, udk, cryengine и тд), программеры делают скрипты, артовики делают контент и всё это собирается в редакторе
2) всё кроме редактора отвязано от контекста, те когда вы пишете скрипты то их одинаково можно прицепить на что угодно, скорее скрипты это тулзы которые помогают в редакторе решать разные проблемы :)
3) присутствует этап подготовки ресурсов, на нем все строковые идентификаторы заменяются на численные, всё что посчитать - считается, всё что можно упаковать (атласы, меши, звуки) - упаковывается и тд
4) игра на движке это просто плеер готовых данных, код становится максимально простым и максимально отвязанным от контекста, рендер становится числодробилкой, и задача "перезагрузить все ресурсы" уже не становится чем-то мрачным :)

компонентная-система :
1) максимальная лёгкость внедрения SoA структуры памяти
2) максимальная эффективность использования кеша (привет builtin preload и тд)
3) нет каких-то сложных структур контейнеров, везде можно обойтись простым массивом структур константного размера

в итоге код упрощается на порядок, количество строк кода можно уменьшить в 3-4 раза, баги ищутся куда проще, и всё работает значительно быстрее

.::jimon::.
Понятно... Пасиба.

.::jimon::.
> 1) мы всегда при загрузке знаем сколько игре надо памяти на этом уровне
Далеко не всегда. Зависит от типа игры. В каком-нить ГТА мы знаем что игре на этом уровне надо гигабайт 10.

StiX
> В каком-нить ГТА мы знаем что игре на этом уровне надо гигабайт 10.
на самом деле нет.
посмотри вокруг, там около 30 людей, 10 машин, пара-тройка вертолетов.
все это создается заранее, если нужно больше, то удаляется кто-то из <правило выбора объекта для удаления> и на его месте создается новый.
допустим для машин можно выбрать ту которая уехала дальше всех, либо за спиной и тд.
геймдизайнер в ходе разработки подбирает эти числа и смотрит на фпс.

заметь к стати, что в ГТА в определенных районах ездят определенные типы машин и в кадре никогда не увидишь всех типов машин сразу

Pushkoff
Я бы это уже назвал пулами под разные системы - пул для звуков, пул для текстур, пул для геймобджектов и т.д. + стриминг всего этого добра. На консолях только так и можно работать

StiX
смысл в том что каждый пул имеет четкий максимальный размер, вот мы его и выделяем сразу, как бы что за игра что упадет от нехватки памяти во время геймплея ? :) падать надо сразу

- а во время редактирования неизвестны точные размеры пулов и что тогда делать?

- какие структуры данных вы используете для хранения объектов?

в релизе это могут быть массивы фиксированного размера и free lists, но в редакторе всё должно легко меняться.

объекты могут "жить" только в "кластерах" и могут напрямую "указывать" только на объекты внутри этого кластера,
а на внешние ссылаться с помощью более глобальных идентификаторов (asset/resource GUIDs),
тогда становится легко реализовать сохранение и загрузку такого "блоба".
и, как правило, в таких "кластерах" объекты каждого типа хранятся в отдельных массивах.

- используется ли у вас подобие такого "кластера" или что-нибудь получше уже придумали?

например, в RenderWare был rwClump, где хранились меши, материалы, источники света и т.д., и clump можно было загрузить в один read.
(а в третьей ГТА вроде были захардкоденные пулы для пешеходов, машин, зданий, декалей и скриптовых объектов.)

PVSector
> - а во время редактирования неизвестны точные размеры пулов и что тогда делать?
известны. если они расчитываются из того что указал геймдиз

PVSector
> - используется ли у вас подобие такого "кластера" или что-нибудь получше уже
> придумали?
интовый идентификатор из которого за О(1) можно получить объект

Pushkoff
> интовый идентификатор из которого за О(1) можно получить объект

а можно поподробнее о реализации?

как у вас происходят операция добавления, удаления и прохода по "живым" объектам ?

если из середины массива будут удаляться объекты, то как у вас это разруливается?

при доступе к указателю на объект по хэндлу каждый раз делаете проверки типа if( mesh.IsValid() ) { mesh.ToPtr()->... ?

(я только знаю про простую look-up table, handles with 'real' object index (into the 'objects' array) and 'unique' counter.)