priority_queue efficiency

[helios]

I'm implementing a path finding algorithm and I'm having a hard time understanding the performance pattern I'm seeing.
Currently, I have Dijkstra's using an deque and A* using priority_queue+deque. For some reason, the A* version is orders of magnitude slower. Can anyone see anything that might be causing this?

std::shared_ptr<std::vector<StarSystem *>> StarSystem::find_fastest_route(StarSystem *dst, double max_distance){
	if (dst->id == this->id)
		return std::make_shared<std::vector<StarSystem *>>();
	std::deque<std::pair<size_t, StarSystem *>> queue;
	std::unordered_set<uintptr_t> visited;
	std::vector<std::pair<size_t, StarSystem *>> came_from;
	came_from.push_back({0, this});
	queue.push_back({0, this});
	visited.insert((uintptr_t)this);

	while (queue.size()){
		auto top = queue.front();
		queue.pop_front();
		auto n = top.second->nearby_systems.size();
		for (size_t i = 0; i < n; i++){
			auto distance = top.second->nearby_systems[i].second;
			if (max_distance >= 0 && distance > max_distance)
				continue;
			auto nearby_system = top.second->nearby_systems[i].first;
			if (visited.find((uintptr_t)nearby_system) != visited.end())
				continue;
			came_from.push_back({top.first, nearby_system});
			if (nearby_system->id == dst->id)
				return rebuild_list(came_from);
			queue.push_back({came_from.size() - 1, nearby_system});
			visited.insert((uintptr_t)nearby_system);
		}
	}
	return std::shared_ptr<std::vector<StarSystem *>>();
}

struct AStarQueueElement{
	double distance;
	size_t came_from;
	StarSystem *system;
	bool operator<(const AStarQueueElement &b) const{
		return this->distance < b.distance;
	}
};

std::shared_ptr<std::vector<StarSystem *>> StarSystem::find_fastest_route_Astar(StarSystem *dst, double max_distance){
	if (dst->id == this->id)
		return std::make_shared<std::vector<StarSystem*>>();
	std::priority_queue<AStarQueueElement, std::deque<AStarQueueElement>> queue;
	std::unordered_set<uintptr_t> visited;
	std::vector<std::pair<size_t, StarSystem *>> came_from;
	came_from.push_back({0, this});
	queue.push(AStarQueueElement{dst->distance_sqr(this), 0, this});
	visited.insert((uintptr_t)this);

	while (queue.size()){
		auto top = queue.top();
		queue.pop();
		auto top_distance = top.distance;
		auto top_came_from = top.came_from;
		auto top_system = top.system;
		auto n = top_system->nearby_systems.size();
		for (size_t i = 0; i < n; i++){
			auto distance = top_system->nearby_systems[i].second;
			if (max_distance >= 0 && distance > max_distance)
				continue;
			auto nearby_system = top_system->nearby_systems[i].first;
			if (visited.find((uintptr_t)nearby_system) != visited.end())
				continue;
			came_from.push_back({top_came_from, nearby_system});
			if (nearby_system->id == dst->id)
				return rebuild_list(came_from);
			queue.push(AStarQueueElement{dst->distance_sqr(nearby_system), came_from.size() - 1, nearby_system});
			visited.insert((uintptr_t)nearby_system);
		}
	}
	return std::shared_ptr<std::vector<StarSystem *>>();
}

[Smac89]

This is probably because priority_queue takes order O(logn) time to add an item whereas deque is order O(1)

If you are just finding a path i.e. not concerned about shortest path, then something like dfs might work. You can use an actual stack if you don't want to incur the recursive overhead

[helios]

I don't believe a logarithmic complexity is enough to explain the slowdown I'm seeing. The A* implementation has to be at least 1000 times slower. I'm pretty sure the queue doesn't grow to be over 1 nonillion elements long.

[cire]

Your heuristic for choosing a node to process in the A* algorithm should include both the estimated distance to the destination, and the accurate distance to from the departure point. You only seem to take into account the estimated distance to the destination.

Also, if the other "distance" values you're using here are not also "distance squared", then your distance-to-dst estimate is likely a (possibly severe) over-estimate which isn't optimal for the algorithm.

[Smac89]

You should test this. Replace the priority_queue with the deque and see what happens

[helios]

cire: I don't think so. I'm searching for the "fastest" path, not the shortest path. Here, "fastest" being defined as "passing through the fewest nodes".

Smac89: Not a bad idea.

[cire]

cire: I don't think so. I'm searching for the "fastest" path, not the shortest path. Here, "fastest" being defined as "passing through the fewest nodes".

Then your "distance" variables hold the number of edges between nodes?

[helios]

Ah. You're right, that's wrong. I should fix the termination condition.

I just tested replacing the priority_queue with a deque and std::sorting right at the end of the outer loop and now the performance is on par with the Dijkstra's implementation. Something must be seriously wrong with the priority_queue implementation in VC++ 2013.

[a10e29]

Maybe the cost of the vector is adding up? pop_front removes the first element would that cause all remaining elements to undergo std::move (hence the orders of magnitude slower)?

[helios]

My priority_queue was using deque, though. I tested both vector and deque and found no difference in performance.