priority_queue becomes extremely slow in debug mode

Question

I am currently writing an A* pathfinding algorithm for a game and came across a very strange performance problem regarding priority_queue's.

I am using a typical 'open nodes list', where I store found, but yet unprocessed nodes. This is implemented as an STL priority_queue (openList) of pointers to PathNodeRecord objects, which store information about a visited node. They are sorted by the estimated cost to get there (estimatedTotalCost).

Now I noticed that whenever the pathfinding method is called, the respective AI thread gets completely stuck and takes several (~5) seconds to process the algorithm and calculate the path. Subsequently I used the VS2013 profiler to see, why and where it was taking so long.

As it turns out, the pushing to and popping from the open list (the priority_queue) takes up a very large amount of time. I am no expert in STL containers, but I never had problems with their efficiency before and this is just weird to me.

The strange thing is that this only occurs while using VS's 'Debug' build configuration. The 'Release' conf. works fine for me and the times are back to normal.

Am I doing something fundamentally wrong here or why is the priority_queue performing so badly for me? The current situation is unacceptable to me, so if I cannot resolve it soon, I will need to fall back to using a simpler container and inserting it to the right place manually.

Any pointers to why this might be occuring would be very helpful!

.

---

Here is a snippet of what the profiler shows me:

http://i.stack.imgur.com/gEyD3.jpg

.

Code parts:

---

Here is the relevant part of the pathfinding algorithm, where it loops the open list until there are no open nodes:

// set up arrays and other variables
PathNodeRecord** records = new PathNodeRecord*[graph->getNodeAmount()]; // holds records for all nodes
std::priority_queue<PathNodeRecord*> openList; // holds records of open nodes, sorted by estimated rest cost (most promising node first)


// null all record pointers
memset(records, NULL, sizeof(PathNodeRecord*) * graph->getNodeAmount());


// set up record for start node and put into open list
PathNodeRecord* startNodeRecord = new PathNodeRecord();
startNodeRecord->node = startNode;
startNodeRecord->connection = NULL;
startNodeRecord->closed = false;
startNodeRecord->costToHere = 0.f;
startNodeRecord->estimatedTotalCost = heuristic->estimate(startNode, goalNode);

records[startNode] = startNodeRecord;
openList.push(startNodeRecord);



// ### pathfind algorithm ###

// declare current node variable
PathNodeRecord* currentNode = NULL;

// loop-process open nodes
while (openList.size() > 0) // while there are open nodes to process
{
    // retrieve most promising node and immediately remove from open list
    currentNode = openList.top();
    openList.pop(); // ### THIS IS, WHERE IT GETS STUCK


    // if current node is the goal node, end the search here
    if (currentNode->node == goalNode)
        break;


    // look at connections outgoing from this node
    for (auto connection : graph->getConnections(currentNode->node))
    {
        // get end node
        PathNodeRecord* toNodeRecord = records[connection->toNode];

        if (toNodeRecord == NULL) // UNVISITED -> path record needs to be created and put into open list
        {
            // set up path node record
            toNodeRecord = new PathNodeRecord();
            toNodeRecord->node = connection->toNode;
            toNodeRecord->connection = connection;
            toNodeRecord->closed = false;
            toNodeRecord->costToHere = currentNode->costToHere + connection->cost;
            toNodeRecord->estimatedTotalCost = toNodeRecord->costToHere + heuristic->estimate(connection->toNode, goalNode);

            // store in record array
            records[connection->toNode] = toNodeRecord;

            // put into open list for future processing
            openList.push(toNodeRecord);
        }
        else if (!toNodeRecord->closed) // OPEN -> evaluate new cost to here and, if better, update open list entry; otherwise skip
        {
            float newCostToHere = currentNode->costToHere + connection->cost;

            if (newCostToHere < toNodeRecord->costToHere)
            {
                // update record
                toNodeRecord->connection = connection;
                toNodeRecord->estimatedTotalCost = newCostToHere + (toNodeRecord->estimatedTotalCost - toNodeRecord->costToHere);
                toNodeRecord->costToHere = newCostToHere;
            }
        }
        else // CLOSED -> evaluate new cost to here and, if better, put back on open list and reset closed status; otherwise skip
        {
            float newCostToHere = currentNode->costToHere + connection->cost;

            if (newCostToHere < toNodeRecord->costToHere)
            {
                // update record
                toNodeRecord->connection = connection;
                toNodeRecord->estimatedTotalCost = newCostToHere + (toNodeRecord->estimatedTotalCost - toNodeRecord->costToHere);
                toNodeRecord->costToHere = newCostToHere;

                // reset node to open and push into open list
                toNodeRecord->closed = false;
                openList.push(toNodeRecord); // ### THIS IS, WHERE IT GETS STUCK
            }
        }
    }


    // set node to closed
    currentNode->closed = true;
}

---

Here is my PathNodeRecord with the 'less' operator overloading to enable sorting in priority_queue:

namespace AI
{
    struct PathNodeRecord
    {
        Node node;
        NodeConnection* connection;

        float costToHere;
        float estimatedTotalCost;

        bool closed;



        // overload less operator comparing estimated total cost; used by priority queue
        // nodes with a higher estimated total cost are considered "less"
        bool operator < (const PathNodeRecord &otherRecord)
        {
            return this->estimatedTotalCost > otherRecord.estimatedTotalCost;
        }
    };
}

Answer 1

std::priority_queue<PathNodeRecord*> openList

I think the reason is that you have a priority_queue of pointers to PathNodeRecord. and there is no ordering defined for the pointers.

try changing it to std::priority_queue<PathNodeRecord> first, if it makes a difference then all you need is passing on your own comparator that knows how to compare pointers to PathNodeRecord, it will just dereference the pointers first and then do the comparison.

EDIT: taking a wild guess about why did you get an extremely slow execution time, I think the pointers were compared based on their address. and the addresses were allocated starting from one point in memory and going up. and so that resulted in the extreme case of your heap (the heap as in data structure not the memory part), so your heap was actually a list, (a tree where each node had one children node and so on). and so you operation took a linear time, again just a guess.

Answer 2

You cannot expect a debug build to be as fast as a release optimized one, but you seems to do a lot of dynamic allocation that may interact badly with the debug runtime.

I suggest you to add _NO_DEBUG_HEAP=1 in the environment setting of the debug property page of your project.