Распределение памяти пула в очереди приоритетов

Question

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

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

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

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

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

Спасибо.

Answer 1

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

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

Answer 2

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

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);
}

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

Answer 3

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

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

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