Выделение памяти пула в приоритетной очереди

Я пишу симулятор на основе событий, в котором каждое событие вызывает функцию обработки (узел), которая может генерировать новые события и так далее. С каждым событием связана временная метка, и их необходимо обрабатывать в порядке возрастания времени (но события не обязательно создаются в таком порядке). С этой целью я использую простой priority_queue<Event*>, где Event — это класс, содержащий указатель на узел обработки, который необходимо вызвать, и метку времени.

Итак, все работает нормально, но я получаю миллионы событий, выделяемых и освобождаемых в секунду, и это явно то, что ограничивает скорость моего симулятора (примерно 30% времени выполнения занимает выделение памяти и освобождение объектов Event).

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

Итак, мой вопрос: было бы практично/выгодно использовать пул объектов для моего priority_queue, и если да, то есть ли простой способ сделать это, возможно, с некоторым примером кода (или, по крайней мере, отправной точкой), желательно, не полагаясь сразу на Boost в первый раз?

На самом деле, некоторые ссылки, чтобы понять, как работает распределение пула, также будут приветствоваться!

Спасибо.


c++ event-driven priority-queue
person OlivierB    schedule 08.03.2011    source источник
comment
просто не забудьте предварительно выделить большой блок для вашего пула при инициализации, вам нужно будет выполнить некоторые измерения, чтобы узнать, какое наибольшее количество элементов требуется в любое время, чтобы полностью избежать динамического распределения.   -  person lurscher    schedule 11.03.2011

Ответы (3)


arrow_upward
0
arrow_downward

Быстрый и грязный пример пула объектов

EventPool.h

#include <stack>
class Event;

class EventPool
{
 public:
   explicit EventPool(const unsigned int initSize = 0);
   ~EventPool();
   Event* getEvent();
   void returnEvent(Event* e);
 private:
   std::stack<Event*> pool_;
};

EventPool.cxx

#include <Event.h>
#include <EventPool.h>

EventPool::EventPool(const unsigned int initSize)
{
   for(unsigned int i = 0; i < initSize; ++i)
   {
      pool_.push(new Event());
   }
}

EventPool::~EventPool()
{
   while(!pool_.empty())
   {
      delete pool_.top();
      pool_.pop();
   }
}

Event* EventPool::getEvent()
{
   if(pool_.empty())
   {
      return new Event();
   }
   Event* returnValue = pool_.top();
   pool_.pop();
   return returnValue;
}

void EventPool::returnEventToPool(Event* e)
{
   pool_.push(e);
}

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

person spbots    schedule 08.03.2011
comment
Мне нравится этот пример, он очень простой, адаптированный к тому, что я делаю, и дает мне прирост производительности от 5 до 10%. Теперь мне интересно, могу ли я по-прежнему ожидать еще большего улучшения, напрямую предоставляя настраиваемый распределитель контейнеру моей priority_queue, как это предлагается в других ответах? На __adjust_heap и __push_heap по-прежнему уходит около 25% времени выполнения, но я думаю, что это неизбежно! Я мог бы попробовать с бустом, если у меня есть время... - person OlivierB; 11.03.2011
comment
Рад помочь! Я добавил редактирование, чтобы показать инициализацию стека до заданного размера, включая инициализацию первой группы объектов. Это делает ваш бассейн немного громоздким (первоначальные затраты), но, надеюсь, позволит избежать дополнительного строительства в будущем. Вы должны выбрать оптимальное значение для initSize, поскольку очевидно, что больший размер начального пула означает больший объем памяти. - person spbots; 11.03.2011

arrow_upward
1
arrow_downward

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

В этом случае вы заранее знаете, что всегда выделяете событие. Это делает пул объектов отличным распределителем для ваших целей. Совершенно практично добавить настраиваемый распределитель, предназначенный для использования с объектами STL, в std::priority_queue очередь создается по шаблону во внутреннем контейнере с std::vector по умолчанию, и вы можете явно указать настраиваемый распределитель в std::vector. Результат должен быть довольно практичным и простым в использовании — настраиваемые распределители памяти, основанные на значениях, как и пулы объектов (насколько я знаю), довольно легко подключить.

person Puppy    schedule 08.03.2011

arrow_upward
0
arrow_downward

Я думаю, вы говорите о std::priority_queue. Да, можно предоставить собственную схему распределения.

Очередь приоритетов STL реализована в виде другого контейнера (по-моему, std::vector по умолчанию), который можно указать в качестве аргумента шаблона. Затем вы можете параметризовать этот другой контейнер с помощью своего распределителя (обычным способом STL).

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

person Leandro T. C. Melo    schedule 08.03.2011