Searching for a performance bug in a C++20 pathfinding algorithm (NBA*) - follow up

Question

I have followed some advice in the previous iteration, yet even the current version is too slow compared to the Java implementation of the same algorithm. (C++ version with g++ -O3 runs in around 200 milliseconds; the Java version around in 10 milliseconds; both in graphs of the same size and topology properties.)

Pathfinders.NBAstar.hpp

#ifndef COM_GITHUB_CODERODDE_GRAPH_PATHFINDERS_NBA_STAR_HPP
#define COM_GITHUB_CODERODDE_GRAPH_PATHFINDERS_NBA_STAR_HPP
#include "DirectedGraph.hpp"
#include "Pathfinders.SharedUtils.hpp"
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <optional>
#include <sstream>
#include <stdexcept>
#include <unordered_map>
#include <unordered_set>
#include <vector>
namespace com::github::coderodde::pathfinders {
 using namespace com::github::coderodde::directed_graph;
 using namespace com::github::coderodde::pathfinders::util;
 template<typename Node = int, typename Weight = double>
 void stabilizeForward(
 DirectedGraph<Node>& graph,
 DirectedGraphWeightFunction<Node, Weight>& weight_function,
 HeuristicFunction<Node, Weight>& heuristic_function,
 std::priority_queue<HeapNode<Node, Weight>>& open_forward,
 std::unordered_map<Node, Info<Node, Weight>>& info,
 Node const& current_node,
 Node const& target_node,
 Weight& best_cost,
 const Node** touch_node_ptr) {
 std::unordered_set<Node>* children =
 graph.getChildNodesOf(current_node);
 for (Node const& child_node : *children) {
 if (info[child_node].closed) {
 continue;
 }
 Weight tentative_distance =
 info[current_node].distance_forward.value() +
 weight_function.getWeight(current_node, child_node);
 if (!info[child_node].distance_forward.has_value()
 ||
 info[child_node].distance_forward > tentative_distance) {
 HeapNode<Node, Weight>
 node{ child_node,
 tentative_distance +
 heuristic_function.estimate(child_node, target_node) };
 open_forward.emplace(node);
 info[child_node].distance_forward = tentative_distance;
 info[child_node].parent_forward = current_node;
 if (info[child_node].distance_backward.has_value()) {
 Weight path_length = tentative_distance +
 info[child_node].distance_backward.value();
 if (best_cost > path_length) {
 best_cost = path_length;
 *touch_node_ptr = &child_node;
 }
 }
 }
 }
 }
 template<typename Node = int, typename Weight = double>
 void stabilizeBackward(
 DirectedGraph<Node>& graph,
 DirectedGraphWeightFunction<Node, Weight>& weight_function,
 HeuristicFunction<Node, Weight>& heuristic_function,
 std::priority_queue<HeapNode<Node, Weight>>& open_backward,
 std::unordered_map<Node, Info<Node, Weight>>& info,
 Node const& current_node,
 Node const& source_node,
 Weight& best_cost,
 const Node** touch_node_ptr) {
 std::unordered_set<Node>* parents =
 graph.getParentNodesOf(current_node);
 for (Node const& parent_node : *parents) {
 if (info[parent_node].closed) {
 continue;
 }
 Weight tentative_distance =
 info[current_node].distance_backward.value() +
 weight_function.getWeight(parent_node, current_node);
 if (!info[parent_node].distance_backward.has_value()
 || info[parent_node].distance_backward > tentative_distance) {
 HeapNode<Node, Weight>
 node{ parent_node,
 tentative_distance +
 heuristic_function.estimate(parent_node, source_node) };
 open_backward.emplace(node);
 info[parent_node].distance_backward = tentative_distance;
 info[parent_node].parent_backward = current_node;
 if (info[parent_node].distance_forward.has_value()) {
 Weight path_length = 
 tentative_distance + 
 info[parent_node].distance_forward.value();
 if (best_cost > path_length) {
 best_cost = path_length;
 *touch_node_ptr = &parent_node;
 }
 }
 }
 }
 }
 template<typename Node = int, typename Weight = double>
 Path<Node, Weight>
 runBidirectionalAstarAlgorithm(
 DirectedGraph<Node>& graph,
 DirectedGraphWeightFunction<Node, Weight>& weight_function,
 HeuristicFunction<Node, Weight>* heuristic_function,
 Node& source_node,
 Node& target_node) {
 checkTerminalNodes(graph, source_node, target_node);
 std::priority_queue<HeapNode<Node, Weight>> open_forward;
 std::priority_queue<HeapNode<Node, Weight>> open_backward;
 std::unordered_map<Node, Info<Node, Weight>> info;
 open_forward .emplace(source_node, Weight{});
 open_backward.emplace(target_node, Weight{});
 info[source_node].distance_forward = Weight{};
 info[target_node].distance_backward = Weight{};
 info[source_node].parent_forward = std::nullopt;
 info[target_node].parent_backward = std::nullopt;
 const Node* touch_node = nullptr;
 Weight best_cost = std::numeric_limits<Weight>::max();
 Weight total_distance =
 heuristic_function
 ->estimate(
 source_node,
 target_node);
 Weight f_cost_forward = total_distance;
 Weight f_cost_backward = total_distance;
 while (!open_forward.empty() && !open_backward.empty()) {
 if (open_forward.size() < open_backward.size()) {
 Node current_node = open_forward.top().getElement();
 open_forward.pop();
 if (info[current_node].closed) {
 continue;
 }
 info[current_node].closed = true;
 if (info[current_node].distance_forward.value() +
 heuristic_function->
 estimate(current_node, target_node) >= best_cost
 ||
 info[current_node].distance_forward.value() +
 f_cost_backward -
 heuristic_function->
 estimate(current_node, source_node)
 >= best_cost) {
 // Reject the 'current_node'.
 } else {
 // Stabilize the 'current_node':
 stabilizeForward<Node, Weight>(
 graph,
 weight_function,
 *heuristic_function,
 open_forward,
 info,
 current_node,
 target_node,
 best_cost,
 &touch_node);
 }
 if (!open_forward.empty()) {
 f_cost_forward = open_forward.top().getDistance();
 }
 } else {
 Node current_node = open_backward.top().getElement();
 open_backward.pop();
 if (info[current_node].closed) {
 continue;
 }
 info[current_node].closed = true;
 if (info[current_node].distance_backward.value() +
 heuristic_function 
 ->estimate(current_node, source_node)
 >= best_cost 
 ||
 info[current_node].distance_backward.value() +
 f_cost_forward -
 heuristic_function->estimate(current_node, target_node) >=
 best_cost) {
 // Reject the 'current_node'!
 } else {
 // Stabilize the 'current_node':
 stabilizeBackward<Node, Weight>(
 graph,
 weight_function,
 *heuristic_function,
 open_backward,
 info,
 current_node,
 source_node,
 best_cost,
 &touch_node);
 }
 if (!open_backward.empty()) {
 f_cost_backward = open_backward.top().getDistance();
 }
 }
 }
 if (touch_node == nullptr) {
 throw PathDoesNotExistException{
 buildPathNotExistsErrorMessage(source_node, target_node)
 };
 }
 Path<Node, Weight> path =
 tracebackPath(
 *touch_node,
 info,
 weight_function);
 return path;
 }
} // End of namespace 'com::github::coderodde::pathfinders'.
#endif // COM_GITHUB_CODERODDE_GRAPH_PATHFINDERS_NBA_STAR_HPP

My wildest guess is that I do copying instead of movement behind the scene. I really need your advice, since I plan to make my library efficient.

The entire (Visual Studio 2022) project lives here.

• Deduplicator: Why do you have all that virtual dispatch and polymorphism all over the place? What a waste.
• coderodde: @Deduplicator Maybe that’s because I am a beginner (duh)?
• Incomputable: @coderodde, I would like to do a full review, but I need your help in order to understand the algorithm. Do you have time for a discord call or something similar? My email is in my profile.

Answer 1

Your main issue appears to be in checkTerminalNodes, which copies the entire graph. It should be passed by const& instead of by value. Note that if we make this change, the compiler will give us an error, because the hasNode function also needs to be marked const.

const-correctness

In C++, all non-static member functions that do not change the class member data should be marked const. There are a few other places in the codebase with this problem.

The DirectedGraphWeightFunction::getWeight function is one of the more interesting ones: Note that std::unordered_map::operator[] is a non-const function. That's because if you ask for an item in the map that doesn't exist, it will insert a new one for you! We don't want that here.

The correct thing to do here is not to work around the compiler error by avoiding marking getWeight() as const - we should instead use a different function to find the node, such as find() or at().

As a side-note: using contains(), followed by a call to operator[] means we are actually searching the map twice for the same item! Using find() will avoid this.

Const-correctness issues like this tend to cascade. Because some member functions that should be marked const aren't, there are a few other places that have to pass objects by non-const &, rather than const&. While this may not affect performance, it does make the code a lot less easy to reason about. Passing arguments by non-const & in C++ explicitly means: "I will change this data".

• coderodde: Looks promising! I will give it a try soon.
• coderodde: Fixing checkTerminalNodes to a reference improved the running time by the factor of 2,5, yet it's still very slow compared to the Java version.