Стоит ли использовать пулы частиц в управляемых языках?

10

Я собирался реализовать пул объектов для моей системы частиц в Java, затем я нашел это в Википедии. Перефразируя, он говорит, что пулы объектов не стоит использовать в управляемых языках, таких как Java и C #, потому что выделения занимают всего десятки операций по сравнению с сотнями в неуправляемых языках, таких как C ++.

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

Вопрос в следующем: стоит ли использовать управляемый пул объектов для частиц (в частности, тех, которые умирают и быстро восстанавливаются) на управляемом языке?

Густаво Масиэль
источник

Ответы:

14

Да, это так.

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

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

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


источник
+1 Но вы не затронули вопрос о том, стоит ли это использовать при использовании структур: в основном это не так (объединение типов значений ничего не дает) - вместо этого у вас должен быть один (или, возможно, набор) массив для управления ими.
Джонатан Дикинсон
2
Я не касался структуры, так как в OP упоминалось использование Java, и я не так хорошо знаком с тем, как типы / структуры значений работают в этом языке.
В Java нет структур, есть только классы (всегда в куче).
Брендан Лонг
1

Для Java не так полезно объединять объекты *, так как первый цикл GC для объектов, которые все еще находятся вокруг, будет переставлять их в памяти, перемещая их из пространства «Eden» и потенциально теряя пространственную локальность в процессе.

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

Java предлагает быстрое распределение пакетов, используя последовательный распределитель, когда вы быстро выделяете объекты в пространство Eden. Эта стратегия последовательного распределения является сверхбыстрой, более быстрой, чем mallocв C, поскольку она просто объединяет в пул память, уже распределенную прямым последовательным образом, но имеет недостаток, заключающийся в том, что вы не можете освободить отдельные части памяти. Это также полезный трюк в C, если вы просто хотите распределить вещи очень быстро, скажем, для структуры данных, где вам не нужно ничего удалять из нее, просто добавьте все, а затем используйте это и отбросьте все это позже.

Из-за этого недостатка неспособности освободить отдельные объекты, Java GC после первого цикла скопирует всю память, выделенную из пространства Eden, в новые области памяти, используя более медленный, более универсальный распределитель памяти, который позволяет памяти быть освобожденным в отдельных кусках в другой теме. Затем он может отбросить память, выделенную в пространстве Eden в целом, не заботясь об отдельных объектах, которые теперь скопированы и живут в других местах памяти. После этого первого цикла GC ваши объекты могут оказаться фрагментированными в памяти.

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

class Particle
{
    public float x;
    public float y;
    public boolean alive;
}

Сделать что-то вроде:

class Particles
{
    // X positions of all particles. Resize on demand using
    // 'java.util.Arrays.copyOf'. We do not use an ArrayList
    // since we want to work directly with contiguously arranged
    // primitive types for optimal memory access patterns instead 
    // of objects managed by GC.
    public float x[];

    // Y positions of all particles.
    public float y[];

    // Alive/dead status of all particles.
    public bool alive[];
}

Теперь, чтобы повторно использовать память для существующих частиц, вы можете сделать это:

class Particles
{
    // X positions of all particles.
    public float x[];

    // Y positions of all particles.
    public float y[];

    // Alive/dead status of all particles.
    public bool alive[];

    // Next free position of all particles.
    public int next_free[];

    // Index to first free particle available to reclaim
    // for insertion. A value of -1 means the list is empty.
    public int first_free;
}

Теперь, когда nthчастица умирает, чтобы ее можно было использовать повторно, поместите ее в свободный список следующим образом:

alive[n] = false;
next_free[n] = first_free;
first_free = n;

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

if (first_free != -1)
{
     int index = first_free;

     // Pop the particle from the free list.
     first_free = next_free[first_free];

     // Overwrite the particle data:
     x[index] = px;
     y[index] = py;
     alive[index] = true;
     next_free[index] = -1;
}
else
{
     // If there are no particles in the free list
     // to overwrite, add new particle data to the arrays,
     // resizing them if needed.
}

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

Чтобы облегчить работу с кодом, возможно, стоит написать собственные базовые контейнеры с изменяемым размером, в которых хранятся массивы с плавающей точкой, массивы целых чисел и массивы логических значений. Опять же, вы не можете использовать дженерики и ArrayListздесь (по крайней мере, с момента последней проверки), поскольку для этого требуются объекты, управляемые GC, а не непрерывные примитивные данные. Мы хотим использовать непрерывный массив int, например, не управляемых GC массивов, Integerкоторые не обязательно будут смежными после выхода из пространства Eden.

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


источник
1
Это хорошая статья по этому вопросу, и после 5 лет Java-кодирования я вижу это ясно; Java GC, конечно же, не тупой, и не был сделан для программирования игр (поскольку он не заботится о локальности данных и прочем), поэтому мы лучше играем, когда пожелаем: P
Gustavo Maciel