Пул объектов (Object Pool)

Задача

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

Мотивация

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

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

Проклятье фрагментации

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

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

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

6-3-1.1

Вот как будет фрагментирована наша куча и почему у нас будет ошибка выделения памяти, хотя теоретически памяти у нас достаточно.

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

Большинство консольных платформодержателей требуют, чтобы игры проходили "тест на протечку (soak test)", когда игра оставляется работающей на несколько дней в демо-режиме. Если игра падает - ей не разрешают выйти. Тест на протечку иногда проваливается и из-за какого-нибудь редкого бага, но чаще всего игру обрушивает утечка памяти, вызванная фрагментацией.

Лучшее из двух миров

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

Пул объектов дает нам лучшее из двух миров: с точки зрения менеджера памяти мы просто выделяем большой ломоть памяти и не освобождаем ее пока игра работает. Для пользователей пула мы можем создавать и удалять объекты сколько нашей душе будет угодно.

Шаблон

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

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

Когда использовать

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

• Вам нужно часто создавать и удалять объекты.

• Объекты одного размера.

• Выделение объектов из кучи работает медленно или может привести к фрагментации памяти.

• Каждый объект инкапсулирует ресурс типа базы данных или сетевого соединения, который сложно получать и можно использовать повторно.

Имейте в виду

Обычно вы можете положиться на сборщик мусора или операторы new и delete, которые сделают всю работу за вас. Когда вы используете пул объектов, вы как будто говорите "Я лучше знаю как обращаться с этими байтами". А еще это значит, что на вас ложится бремя ограничений шаблона.

Пул может тратить память на неиспользуемые объекты

Размер пула нужно настраивать соразмерно с нуждами игры. При настройке обычно проще всего понять когда пул недостаточного размера (уверен что падение игры наверняка привлечет ваше внимание). Но еще нужно следить и за тем чтобы пул не был слишком большим. Если уменьшить пул, освободившуюся память можно использовать для чего-либо более полезного.

В каждый момент времени может быть активно только определенное количество объектов

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

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

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

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

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

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

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

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

Размер памяти для каждого объекта фиксирован

Большинство реализаций пула хранят объекты в массиве объектов на месте (in-place). Если все ваши объекты одного типа - это нормально. Однако если вы захотите хранить в пуле объекты нескольких типов или экземпляры подклассов с дополнительными полями, вам нужно быть уверенными что каждый слот пула обладает достаточным размером чтобы вместить максимально возможный объект. В противном случае неожиданно большой объект вылезет за свои границы на соседний и разрушит память.

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

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

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

Повторно используемые объекты не очищаются автоматически

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

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

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

Я буду гордится если вы выберете для очистки магическое число 0x1deadb0b.

Неиспользуемые объекты остаются в памяти

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

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

Пример кода

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

Начнем с самой наипростейшей реализации. Для начала наш класс частиц:

class Particle
{
    public:
        Particle() : framesLeft_(0) {}
        
        void init(double x, double y,
            double xVel, double yVel, int lifetime)
            {
            x_ = x; y_ = y;
            xVel_ = xVel; yVel_ = yVel;
            framesLeft_ = lifetime;
        }
        
        void animate()
        {
            if (!inUse()) return;
            
            framesLeft_--;
            x_ += xVel_;
            y_ += yVel_;
        }
        
        bool inUse() const { return framesLeft_ > 0; }
    
    private:
        int framesLeft_;
        double x_, y_;
        double xVel_, yVel_;
};

Конструктор по умолчанию инициализирует частицу как "не используемую". Следующий вызов init() инициализирует частицу уже в живом состоянии.

Частицы анимируются с помощью функции с именем animate(), которая должна вызываться на каждом кадре.

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

Класс пула также предельно прост:

class ParticlePool
{
    public:
        void create(double x, double y,
            double xVel, double yVel, int lifetime);
        
        void animate()
        {
            for (int i = 0; i < POOL_SIZE; i++)
            {
                particles_[i].animate();
            }
        }
        
    private:
        static const int POOL_SIZE = 100;
        Particle particles_[POOL_SIZE];
};

Функция create() позволяет внешнему коду создавать новые частицы. Игра вызывает на каждом кадре animate(), анимируя тем самым все частицы в пуле.

Этот метод animate() представляет собой пример шаблона Метод обновления (Update Method).

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

Создание новой частицы предельно простое:

void ParticlePool::create(double x, double y,
    double xVel, double yVel,
    int lifetime)
{
    // Find an available particle.
    for (int i = 0; i < POOL_SIZE; i++)
    {
        if (!particles_[i].inUse())
        {
            particles_[i].init(x, y, xVel, yVel, lifetime);
            return;
        }
    }
}

Мы обходим пул и ищем первую доступную частицу. Когда мы ее находим, мы инициализируем ее и на этом все. Обратите внимание что в этой реализации, если у нас нет доступных частиц, мы вообще не создаем новую.

Это и есть вся простая система частиц за исключением рендеринга частиц конечно. Теперь мы можем создать пул и несколько частиц с его помощью. Частицы будут деактивировать сами себя автоматически когда закончится их время жизни.

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

Для тех из нас кто еще помнит теорию алгоритмов, создание частицы имеет сложность O(n).

Свободный список

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

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

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

Когда частица не используется, большая часть ее состояния не имеет никакого значения. Ее позиция и скорость не используются. Единственное состояние которое для нас важно - это мертва ли частица. В нашем примере это член класса _framesLeft. Все остальные биты можно использовать. Вот пересмотренный вариант:

class Particle
{
    public:
        // ...
        
        Particle* getNext() const { return state_.next; }
        void setNext(Particle* next) { state_.next = next; }
    
    private:
        int framesLeft_;
        
        union
        {
            // Состояние когда частица используется.
            struct
            {
                double x, y;
                double xVel, yVel;
            } live;
            
            // Состояние когда частица доступна.
            Particle* next;
        } state_;
};

Мы взяли все члены переменные за исключением framesLeft_ и переместили их в структуру live внутри объединения state_. Эта структура хранит состояние частицы когда она анимируется. Когда частица не используется, в дело вступает другая часть объединения - член next. Он хранит указатель на следующую доступную частицу за данной.

В наши дни объединения используются не слишком часто, так что даже их синтаксис может выглядеть для вас незнакомым. Если вы работаете в команде, у вас наверняка есть "гуру по памяти", который вам помогает в случаях, когда у вас появляются проблемы с бюджетом памяти. Спросите его об объединениях. Такие люди много о них знают, включая довольно забавные трюки с упаковкой битов.

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

Такая хитрая техника называется свободный список (free list). Чтобы она заработала, нам нужно удостовериться что указатели инициализируются корректно и поддерживать их когда частицы создаются и уничтожаются. И конечно нам нужно следить за головой списка:

class ParticlePool
{
        // ...
    private:
        Particle* firstAvailable_;
};

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

ParticlePool::ParticlePool()
{
    // Доступен первый.
    firstAvailable_ = &particles_[0];
    
    // Каждая частица указывает на следующую.
    for (int i = 0; i < POOL_SIZE - 1; i++)
    {
        particles_[i].setNext(&particles_[i + 1]);
    }
    
    // Последняя завершает список.
    particles_[POOL_SIZE - 1].setNext(NULL);
}

Теперь для создания новой частицы нам нужно перейти к первой доступной:

Сложность O(1), детка! Вот чего мы добились!

void ParticlePool::create(double x, double y,
    double xVel, double yVel,
    int lifetime)
{
    // Проверяем что пул не заполнен полностью.
    assert(firstAvailable_ != NULL);
    
    // Удаляем ее из списка доступных.
    Particle* newParticle = firstAvailable_;
    firstAvailable_ = newParticle->getNext();
    
    newParticle->init(x, y, xVel, yVel, lifetime);
}

Нам нужно знать когда частица умирает для того чтобы добавить ее в свободный список. Для этого мы сделаем так, чтобы animate() возвращала true, если предыдущая живая частица испустила дух в этом кадре:

bool Particle::animate()
{
    if (!inUse()) return false;
    
    framesLeft_--;
    x_ += xVel_;
    y_ += yVel_;
    
    return framesLeft_ == 0;
}

Когда это происходит, мы просто переносим ее обратно в список:

void ParticlePool::animate()
{
    for (int i = 0; i < POOL_SIZE; i++)
    {
        if (particles_[i].animate())
        {
            // Добавляем эту частицу в начало списка.
            particles_[i].setNext(firstAvailable_);
            firstAvailable_ = &particles_[i];
        }
    }
}

Вот и готово. Маленький и удобный пул объектов с константным временем создания и удаления.

Архитектурные решения

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

Привязаны ли объекты к пулу?

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

• Если объекты связаны с пулом:

  • Реализация будет проще. Вы можете просто добавить в объект пула флаг "используется" или функцию и на этом остановиться.

  • Вы можете быть уверены, что объекты создаются только в пуле. В C++ это легко сделать, объявив класс пула дружественным классом класса объекта и сделать его конструктор приватным.

  class Particle
  {
      friend class ParticlePool;
  
      private:
          Particle() : inUse_(false) {}
      
          bool inUse_;
  };
  
  class ParticlePool
  {
      Particle pool_[100];
  };

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

  • Вы можете избежать необходимости использовать флаг "используется". У многих объектов уже есть какое-то состояние, которое можно использовать для определения живой объект или нет. Например, частица может быть доступна для повторного использования, если ее координаты находятся за экраном. Если класс объекта знает, что его можно использовать в пуле, он может предоставлять метод inUse() для проверки этого состояния. Таким образом мы оберегаем пул от необходимости тратить лишнюю память для хранения флагов "используется".

• Если объекты не связаны с пулом:

  • Можно помещать в пул объекты любых типов. Это большое преимущество. Снижая связность объекта с пулом, вы имеете возможность реализовать обобщенный класс пула.

  • Состояние "используется" можно отслеживать извне объекта. Проще всего это сделать с помощью отдельного битового флага.

    template
    class GenericPool
    {
        private:
            static const int POOL_SIZE = 100;
    
            TObject pool_[POOL_SIZE];
            bool inUse_[POOL_SIZE];
    };

Кто отвечает за инициализацию повторно используемых объектов?

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

• Если пул повторно инициализируется внутри:

  • Пул может полностью инкапсулировать свои объекты. В зависимости от других возможностей, нужных вашим объектам, вы можете полностью хранить их внутри пула. В таком случае вы можете быть уверенными, что никакой другой код не будет хранить ссылку на объект пула и его можно будет свободно использовать повторно.

  • Пул отвечает за то как объект будет инициализирован. Объект пула может предлагать несколько функций для своей инициализации. Если инициализацией управляет пул, его интерфейсу нужно поддерживать их все и перенаправлять вызовы объекту.

    class Particle
    {
        // Несколько способов инициализации.
        void init(double x, double y);
        void init(double x, double y, double angle);
        void init(double x, double y, double xVel, double yVel);
    };
    
    class ParticlePool
    {
        public:
            void create(double x, double y)
            {
                // Переход к частице...
            }
            
            void create(double x, double y, double angle)
            {
                // Переход к частице...
            }
            
            void create(double x, double y, double xVel, double yVel)
            {
                // Переход к частице...
            }
    };

• Если объект инициализируется из внешнего кода:

  • Интерфейс пула может быть проще. Вместо предоставления нескольких функций для сокрытия всех возможных способов инициализации объекта, пул может просто возвращать ссылку на новый объект.

        class Particle
        {
        public:
        // Несколько способов инициализации.
        void init(double x, double y);
        void init(double x, double y, double angle);
        void init(double x, double y, double xVel, double yVel);
        };
    
        class ParticlePool
        {
        public:
        Particle* create()
        {
        // Возвращаем ссылку на доступную частицу...
        }
        private:
        Particle pool_[100];
        };

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

        ParticlePool pool;
    
        pool.create()->init(1, 2);
        pool.create()->init(1, 2, 0.3);
        pool.create()->init(1, 2, 3.3, 4.4);

  • Внешнему коду придется обрабатывать ошибку при создании нового объекта. Предыдущий пример предполагает что create() всегда будет успешно заканчиваться возвращением указателя на объект. Если пул переполнен, он может возвращать NULL. Чтобы делать это безопасно, вам нужно добавить проверку перед попыткой инициализации объекта.

    Particle* particle = pool.create();
    if (particle != NULL) particle->init(1, 2);

Смотрите также

• Довольно похоже на шаблон Приспособленец (Flyweight)GoF. Оба поддерживают коллекцию повторно используемых объектов. Разница в том что означает это "повторное использование". Объекты приспособленца используются повторно, разделяя один и тот же экземпляр между множеством обладателей одновременно. Таким образом мы избегаем дублирования использования памяти, используя один и тот же объект в нескольких контекстах.

  Объекты в пуле тоже можно использовать повторно, но только через некоторое время. "Повторное использование" в контексте пула объектов означает повторное использование памяти объекта после того как предыдущий владелец ее освободит. Когда мы используем пул объектов, мы не рассчитываем что объект будет разделяться между несколькими владельцами во время его жизни.

• Упаковка множества объектов одного типа вместе в памяти позволяет вам держать кэш процессора заполненным, пока игра обходит все его объекты. Шаблон Локальность данных (Data Locality) как раз об этом.