0

I am currently learning C++ and in doing so I am converting the A* path-finding algorithm that I previously wrote in Python to C++. I just decided to plunge in despite not knowing much about all the different kinds of data-types in the C++ libraries.

After finishing writing the program, the C++ version runs way slower than the Python version (the program uses std::map instead of Python dictionaries to store move costs). Regardless of whether or not you know path finding, would it be possible for someone to look at my code and tell why it is running so inefficiently?

I ran the visual studios profiler to examine what was so inefficient (I know that queues could be used to speed up searching but keep in mind that this runs x50 times faster in Python with the same code and no priority queue).. It appears that almost all the time is being used by std::map [] operators:

Function Name   Total CPU (%) -> 88.01 %
+ std::map<std::pair<int,int>,int,std::less<std::pair<int,int>>,
  std::allocator<std::pair<std::pair<int,int> const ,int> > >::
  operator[]

My code:

    void findPath(pair<int, int> startLocation, pair<int, int> endLocation){

    vector<pair<int, int>> openSet;
    vector<pair<int, int>> closedSet;
    openSet.push_back(startLocation);

    map<pair<int, int>, pair<int, int>> cameFrom;
    map<pair<int, int>, int> gCosts;
    map<pair<int, int>, int> fCosts;

    gCosts[startLocation] = 0;
    fCosts[startLocation] = heuristic(startLocation, endLocation);

    pair<int, int> currentNode;
    while (openSet.size() > 0){

        currentNode = openSet[0];

        for (std::vector<pair<int, int>>::iterator it = openSet.begin(); it != openSet.end(); ++it){
            pair<int, int> node = *it;
            if (fCosts[node] < fCosts[currentNode])
                currentNode = node;
        }

        if (DEBUG){
            cout << "Current Node: " << currentNode.first << " " << currentNode.second << endl;
        }

        if (currentNode == endLocation){
            break;
        }

        openSet.erase( remove(openSet.begin(), openSet.end(), currentNode), openSet.end() );
        closedSet.push_back(currentNode);

        vector<pair<int, int>> neighbors = getNeighbors(currentNode);

        for (std::vector<pair<int, int>>::iterator it = neighbors.begin(); it != neighbors.end(); ++it){
            pair<int, int> neighbor = *it;
            if (std::find(closedSet.begin(), closedSet.end(), neighbor) != closedSet.end()) {
                continue;
            }

            int possiblegCost = gCosts[currentNode] + heuristic(currentNode, neighbor);

            bool inOpenSet = find(openSet.begin(), openSet.end(), neighbor) != openSet.end();
            if (!inOpenSet || (possiblegCost < gCosts[neighbor])) {
                cameFrom[neighbor] = currentNode;
                gCosts[neighbor] = possiblegCost;
                fCosts[neighbor] = possiblegCost + heuristic(neighbor, endLocation);

                /*if (DEBUG){
                console() << "Modifying neighbor: " << neighbor.first << "," << neighbor.second << " Costs of: "
                << gCosts[neighbor] << " " << fCosts[neighbor] << endl;
                }*/

                if (!inOpenSet){
                    openSet.push_back(neighbor);
                }
            }

        }
    }

}
Marcel Champagne
  • 1
  • 3
    Try using `std::unordered_map` instead of plain old `std::map`, it uses hashing which might speed your program up sufficiently. – TartanLlama Jan 07 '15 at 10:05
  • 5
    Are you running an optimized build? – juanchopanza Jan 07 '15 at 10:06
  • @TartanLlama it might be worth mentioning that this will also require adding a specialisation for `std::pair` or specifying a hashing function as I describe [here](http://stackoverflow.com/a/26207312/2558027). – sjdowling Jan 07 '15 at 10:14
  • 1
    small micro-optimization however you can replace `while (openSet.size() > 0)` by `while (!myset.empty())` – Michiel uit het Broek Jan 07 '15 at 10:16
  • Furthermore, a while ago I did something similar for the Knapsack problem and I have used a queue instead of a set since I only took elements from one side and add elements to the otherside. In this case a queue might be faster. – Michiel uit het Broek Jan 07 '15 at 10:22
  • The `for` loop always compares item `0` with item `0` (which will always fail), you could start from `begin() + 1` – M.M Jan 07 '15 at 10:24
  • 1
    why do you always position yourself on `openSet[0]`? When you find a node with a lower cost, you `push_back`, so it's at the end of the vector. You're not really making proper use of C++. For example in the second `for` loop, you are always declaring the `neighbour`. In C++, this translates to: call `pair` constructor and it's `operator=`. So a micro-optimization would be to put that `pair` before the loop. – Hame Jan 07 '15 at 10:26
  • Your test run is a single call to `findPath` ? – M.M Jan 07 '15 at 10:26
  • Is it possible that the `operator[]` in question is elsewhere, e.g. in `getNeighbours`? It'd be good if you could narrow it down a bit to exactly which `operator[]` calls are being slow. An idea for this would be to use `insert()` or `find()` instead of `operator[]` in some cases. – M.M Jan 07 '15 at 10:30
  • agree at trying `unordered_map` -perhaps the combination of the data set and the order you're inserting things works out ends up with the `map` tree being very unbalanced – M.M Jan 07 '15 at 10:32
  • You're almost certainly running in Debug. Visual C++ has virtually different codebases for debug vs release STL containers. – Mahmoud Al-Qudsi Jan 07 '15 at 10:33
  • Do you use reference to pass the nodes into the functions? – Michiel uit het Broek Jan 07 '15 at 10:46
  • Thanks guys, I realized that I'm an idiot and was running in debug. Also the performance issue IS because I'm not using a priority queue, not sure why I was confused in the first place. This line is the line that uses 90% of the time: if (fCosts[node] < fCosts[currentNode] || (fCosts[node] == fCosts[currentNode] && gCosts[node] > gCosts[currentNode])) And that's the line that is doing all the comparisons that I could remove by using a priority queue. Thanks for the help regardless! – Marcel Champagne Jan 07 '15 at 11:41
  • Comparing int values should be basically free whereas accessing elements in the middle of node based containers is often not as you have already seen. I would still recommend trying out `std::unordered_map`. – sjdowling Jan 07 '15 at 13:29

1 Answers1

0

Using std::map::find and/or std::map::emplace/std::map::emplace_hint might be much faster than std::map operator[]

TNA
  • 2,595
  • 1
  • 14
  • 19
  • It seems to me that the time must be in reading and writing the existing entries; there'd be very little time spent on memory allocation. (so emplacing may help a teeny fraction but not much). – M.M Jan 07 '15 at 10:32
  • @Matt McNabb The Problem with `operator []` ist that it uses a combination of default construction, non-default contruction and assignment, although a single in-place construction would be enough in most cases but I agree that this probably won't help much with build-in datatypes like ints. – TNA Jan 07 '15 at 10:41