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.

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".