CODEWITHSUNDEEP
c++performancealgorithmpriority-queue
hfhc2
hfhc2

Reputation: 4421

Time to pop element from a C++ priority_queue

I have the following problem: I am implementing an algorithm which essentially performs a sweep (https://en.wikipedia.org/wiki/Sweep_line_algorithm) through time to update data structures. For the relevant points in time I generate appropriate events which I store in a std::priority_queue: In each step I pop the event with smallest time value, process it and push some other events on the queue if necessary. Unfortunately my code runs very slowly. I used gprof to take a look and it seems like the algorithm spends about 60% of the execution time in std::priority_queue::pop. Is there any way to make the operation more efficient?

Edit: The loop essentially looks like this:

typedef std::priority_queue<Event, vector<Event>, greater<Event> > EventQueue;

while(!events.empty())
{
  Event e = events.top();
  events.pop();

  const DirectedEdge &edge = e.current_edge->get_edge();

  if(e.type == Event::LEAVING)
  {
    Event ee = e;

    ee.type = Event::ENTERING;

    ++ee.current_edge;

    if(!ee.current_edge)
    {
      ee.path->set_arrival_time(ee.time);
    }
    else
    {
      ee.current_edge->set_departure_time(ee.time);
      ee.time += get_delay(ee.current_edge->get_edge());

      events.push(ee);
    }
  }
  else
  { 
    Event ee = e;
    ee.type = Event::LEAVING;

    const FlowFloat time = queues[edge.get_index()].insert_traveler(e.time, e.path);

    ee.time = time;

    events.push(ee);
  }
}

Upvotes: 0

Views: 437

Answers (1)

Loghorn
Loghorn

Reputation: 2807

If you are using a C++11 compliant compiler, try to add a move constructor/operator to your Event class, because the priority_queue does a lot of operations on the elements and if it can move instead of copy it will be much faster. This of course depends on how Event is defined: if it is a POD type you don't gain anything; no gain also if the move operator doesn't do anything faster than copy.

Upvotes: 1

Related Questions