Динамическое распределение памяти и управление памятью

17

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

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

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

Используемый язык: C ++; В настоящее время разрабатывается под Windows, но планируется портировать позже.

Bunkai.Satori
источник
Какой язык?
Kylotan
@Kylotan: используемый язык: C ++ в настоящее время разрабатывается под Windows, но планируется к переносу позже.
Bunkai.Satori

Ответы:

23

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

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

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

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

Профиль и посмотри. Например, в C ++ динамическое выделение в куче обычно является «медленной» операцией (в том смысле, что она требует обхода кучи в поисках блока соответствующего размера). В C # это обычно очень быстрая операция, потому что она включает чуть больше, чем приращение. Разные языковые реализации имеют разные характеристики производительности в отношении выделения памяти, фрагментации при выпуске и так далее.

Внедрение системы пула памяти, безусловно, может привести к повышению производительности - и поскольку мобильные системы обычно недостаточно мощны по сравнению с настольными системами, вы можете увидеть больше выигрыша на конкретной мобильной платформе, чем на настольном компьютере. Но опять же, вам придется профилировать и посмотреть - если в настоящее время ваша игра работает медленно, но распределение / освобождение памяти не отображается на профилировщике как горячая точка, реализуя инфраструктуру для оптимизации распределения памяти и, вероятно, выиграл доступ ' Я не получу много денег.

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

Опять профиль и посмотрим. Теперь ваша игра работает нормально? Тогда вам не нужно беспокоиться.

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

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

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

Например, если вы считаете, что менеджер памяти - это то, что просто перехватывает вызовы new / delete / free / malloc / что угодно и обеспечивает диагностику того, сколько памяти вы выделяете, что у вас течет и так далее - тогда это может быть полезным инструмент для игры, находящийся в стадии разработки, который поможет вам отлаживать утечки, настраивать оптимальный размер пула памяти и т. д.


источник
Согласовано. Код таким образом, что позволяет вам изменить вещи позже. В случае сомнений, тест или профиль.
axel22
@ Джош: +1 за отличный ответ. Вероятно, мне понадобится сочетание динамического выделения, статического выделения и пулов памяти. Тем не менее, производительность игры поможет мне в правильном сочетании этих трех. Это явный кандидат на принятый ответ на мой вопрос. Тем не менее, я хотел бы оставить вопрос открытым некоторое время, чтобы посмотреть, что другие внесут.
Bunkai.Satori
+1. Отличная проработка. Ответ почти на каждый вопрос о производительности всегда "профиль и посмотреть". В наши дни аппаратное обеспечение слишком сложно, чтобы рассуждать о производительности из первых принципов. Вам нужны данные.
Великолепно
@ Великолепно: спасибо за ваш комментарий. Таким образом, цель состоит в том, чтобы сделать игру работоспособной и стабильной. Во время разработки не нужно слишком беспокоиться о производительности. Все это можно и будет исправлено после завершения игры.
Bunkai.Satori
Я думаю, что это несправедливое представление времени выделения C # - например, каждое выделение C # также включает в себя блок синхронизации, выделение Object и т. Д. Кроме того, куча в C ++ требует модификации только при распределении и освобождении, тогда как C # требует коллекции ,
DeadMG
7

Мне нечего добавить к отличному ответу Джоша, но я прокомментирую это:

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

Между пулами памяти и обращением newк каждому выделению есть середина . Например, вы можете выделить определенное количество объектов в массиве, а затем установить флаг для них, чтобы «уничтожить» их позже. Когда вам нужно выделить больше, вы можете перезаписать их с установленным флагом уничтожения. Подобные вещи немного сложнее в использовании, чем new / delete (так как для этого у вас есть 2 новые функции), но их легко написать и они могут принести вам большой выигрыш.

Kylotan
источник
+1 за приятное дополнение. Да, вы правы, это хороший способ управления более простыми элементами игры, такими как: пули, частицы, эффекты. Специально для них не было бы необходимости выделять память динамически.
Bunkai.Satori
3

Совершенно правильно ли выделять память для всех объектов, включая выстрелы (пули), динамически с помощью функции new () по умолчанию?

Нет, конечно нет. Нет распределения памяти является правильным для всех объектов. Оператор new () предназначен для динамического размещения, то есть он подходит, только если вам нужно, чтобы распределение было динамическим, либо потому, что время жизни объекта является динамическим, либо потому, что тип объекта является динамическим. Если тип и время жизни объекта известны статически, вы должны назначить его статически.

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

DeadMG
источник
+1 за хороший ответ. Таким образом, в целом, правильный подход будет следующим: в начале разработки планировать, какие объекты могут быть распределены статически. Во время разработки динамически размещать только те объекты, которые абсолютно необходимо размещать динамически. В конце выполните профилирование и настройку возможных проблем с производительностью выделения памяти.
Bunkai.Satori
0

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

Вот простой пример того, как вы можете избежать Foosмногократного выделения и освобождения, используя массив с отверстиями с элементами, связанными вместе (решая это на уровне «контейнера» вместо уровня «распределителя»):

struct FooNode
{
    explicit FooNode(const Foo& ielement): element(ielement), next(-1) {}

    // Stores a 'Foo'.
    Foo element;

    // Points to the next foo available; either the
    // next used foo or the next deleted foo. Can
    // use SoA and hoist this out if Foo doesn't 
    // have 32-bit alignment.
    int next;
};

struct Foos
{
    // Stores all the Foo nodes.
    vector<FooNode> nodes;

    // Points to the first used node.
    int first_node;

    // Points to the first free node.
    int free_node;

    Foos(): first_node(-1), free_node(-1)
    {
    }

    const FooNode& operator[](int n) const
    {
         return data[n];
    }

    void insert(const Foo& element)
    {
         int index = free_node;
         if (index != -1)
         {
              // If there's a free node available,
              // pop it from the free list, overwrite it,
              // and push it to the used list.
              free_node = data[index].next;
              data[index].next = first_node;
              data[index].element = element;
              first_node = index;
         }
         else
         {
              // If there's no free node available, add a 
              // new node and push it to the used list.
              FooNode new_node(element);
              new_node.next = first_node;
              first_node = data.size() - 1;
              data.push_back(new_node);
         }
    }

    void erase(int n)
    {
         // If the node being removed is the first used
         // node, pop it from the used list.
         if (first_node == n)
              first_node = data[n].next;

         // Push the node to the free list.
         data[n].next = free_node;
         free_node = n;
    }
};

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

for (int index = foos.first_node; index != -1; index = foos[index].next)
    // do something with foos[index]

введите описание изображения здесь

И вы можете обобщить структуру данных «связанного массива дырок» вышеупомянутого типа, используя шаблоны, размещая новые и вызывая dtor вручную, чтобы избежать требования для назначения копирования, заставить его вызывать деструкторы при удалении элементов, предоставлять прямой итератор и т. Д. предпочел сохранить пример в стиле C, чтобы более четко проиллюстрировать концепцию, а также потому, что я очень ленив.

Тем не менее, эта структура имеет тенденцию ухудшаться в пространственной локализации после того, как вы удалите и вставите объекты в середину или из нее. В этот момент nextссылки могут заставить вас идти вперед и назад по вектору, перезагружая данные, ранее удаленные из строки кэша, в рамках одного и того же последовательного обхода (это неизбежно при любой структуре данных или распределителе, которая позволяет удалять данные в постоянном времени без перетасовки элементов при возврате пробелы от середины с постоянной вставкой и без использования чего-либо вроде параллельного набора битов или removedфлага). Чтобы восстановить дружественность кешу, вы можете реализовать метод копирования ctor и swap следующим образом:

Foos(const Foos& other)
{
    for (int index = other.first_node; index != -1; index = other[index].next)
        insert(foos[index].element);
}

void Foos::swap(Foos& other)
{
     nodes.swap(other.nodes):
     std::swap(first_node, other.first_node);
     std::swap(free_node, other.free_node);
}

// ... then just copy and swap:
Foos(foos).swap(foos);

Теперь новая версия снова доступна для кеша. Другой способ - сохранить отдельный список индексов в структуре и периодически сортировать их. Другой - использовать набор битов, чтобы указать, какие индексы используются. Это всегда заставит вас пересматривать набор битов в последовательном порядке (чтобы сделать это эффективно, проверяйте 64-битные за раз, например, используя FFS / FFZ). Битовый набор является наиболее эффективным и ненавязчивым, для которого требуется только параллельный бит на элемент, чтобы указать, какие из них используются, а какие удалены, вместо того, чтобы требовать 32-битных nextиндексов, но он требует больше времени для правильной записи (он не будет будьте быстры для обхода, если вы проверяете по одному биту за раз - вам нужно FFS / FFZ, чтобы сразу найти установленный или неустановленный бит среди 32+ битов за раз, чтобы быстро определить диапазоны занятых индексов).

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

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

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

Что касается того, что Джош упомянул о GC, я не изучал реализацию GC в C # так же близко, как Java, но распределители GC часто имеют начальное распределениеэто очень быстро, потому что используется последовательный распределитель, который не может освободить память из середины (почти как стек, вы не можете удалять вещи из середины). Затем он оплачивает дорогостоящие затраты, чтобы фактически разрешить удаление отдельных объектов в отдельном потоке путем копирования памяти и очистки ранее выделенной памяти в целом (например, уничтожение всего стека за один раз при копировании данных во что-то более похожее на связанную структуру), но поскольку это делается в отдельном потоке, это не обязательно останавливает потоки вашего приложения. Однако это несет в себе очень значительную скрытую стоимость дополнительного уровня косвенности и общей потери LOR после начального цикла GC. Это еще одна стратегия ускорения выделения ресурсов - сделать его дешевле в вызывающем потоке, а затем выполнить дорогостоящую работу в другом. Для этого вам нужно два уровня косвенности, чтобы ссылаться на ваши объекты, а не один, так как они будут в конечном итоге перетасовываться в памяти между временем, которое вы изначально выделяли, и после первого цикла.

Еще одна стратегия в том же духе, которую немного проще применить в C ++, - просто не пытайтесь освободить ваши объекты в основных потоках. Просто добавление и добавление и добавление в конец структуры данных, которая не позволяет удалять объекты из середины. Однако отметьте те вещи, которые нужно удалить. Затем отдельный поток мог бы позаботиться о дорогостоящей работе по созданию новой структуры данных без удаленных элементов, а затем атомарно заменить новую на старую, например, большая часть затрат как на выделение, так и на освобождение элементов может быть передана на отдельный поток, если вы можете сделать предположение, что запрос на удаление элемента не должен выполняться немедленно. Это не только делает освобождение более дешевым, насколько это касается ваших потоков, но и делает распределение более дешевым, поскольку вы можете использовать гораздо более простую и тупую структуру данных, которая никогда не должна обрабатывать случаи удаления из середины. Это как контейнер, который нуждается только вpush_backфункция для вставки, clearфункция для удаления всех элементов и swapобмена содержимым с новым компактным контейнером, исключая удаленные элементы; это все, что касается мутаций.


источник