Low perfomance on multiple path traces with big grid (A*)

[devjolan]

Hi. Thank you for your library.

I am implementing path precalculation for given move map (black and white image) with size 1024*1024 and 11k edges on it and always after first iteration path finding takes ~300ms, but first path find is ~1ms.

I've found that this massive time loss was in pathfinding/core/grid.py in function cleanup:

def cleanup(self):
    for y_nodes in self.nodes:
        for node in y_nodes:
            node.cleanup()

In my case with this grid size every path find iteration cleaned 1024*1024 nodes what was very slow.

Maybe not best solution but i've modified library source to cache nodes that was used by path finding (only for A* and Grid just for my problem solving).

My solution:

pathfinding/core/grid.py

class Grid:
    def __init__(
        # ...
        self.dirty = False
        self._dirty_node_cache = {} # <-- added cache map

        self.passable_left_right_border = False
        # ...

    # ...
    def cleanup(self):
        for y_nodes in self.nodes:
            for node in y_nodes:
                node.cleanup()
    
    # --------------------------------------------
    # added two methods to cache and cleanup nodes
    # --------------------------------------------
    
    def cleanup_cache(self):
        for node_key in self._dirty_node_cache:
            self._dirty_node_cache[node_key].cleanup()
        
        self._dirty_node_cache = {}

    def add_node_to_cache(self, node):
        key = f"{node.x}_{node.y}"
        if key not in self._dirty_node_cache:
            self._dirty_node_cache[key] = node
    
    # ...

pathfinding/finder/finder.py

    def process_node(
            self, graph, node, parent, end, open_list, open_value=True):
        # ...
        ng = parent.g + graph.calc_cost(parent, node, self.weighted)

        if not node.opened or ng < node.g:
            graph.add_node_to_cache(node)   # <-- added node caching
        # ...

    def clean_grid(self, grid):
        """clean the map if needed."""
        if grid.dirty:
            grid.cleanup_cache()    # <-- replaced grid.cleanup() call
        grid.dirty = True

pathfinding/finder/a_star.py

    def check_neighbors(self, start, end, graph, open_list,
                        open_value=True, backtrace_by=None):
        
        # ...
        
        node = open_list.pop_node()
        node.closed = True
        graph.add_node_to_cache(node)   # <-- added node caching
        
        # ...

Some tests

Before modification

Path 1/11516. Steps: 15, runs: 27. Elapsed time: 0.000 ms
Path 2/11516. Steps: 11, runs: 29. Elapsed time: 295.001 ms
Path 3/11516. Steps: 10, runs: 10. Elapsed time: 289.000 ms
Path 4/11516. Steps: 14, runs: 21. Elapsed time: 290.000 ms
Path 5/11516. Steps: 11, runs: 37. Elapsed time: 315.001 ms
Path 6/11516. Steps: 22, runs: 136. Elapsed time: 285.998 ms
Path 7/11516. Steps: 12, runs: 12. Elapsed time: 324.999 ms
Path 8/11516. Steps: 9, runs: 21. Elapsed time: 288.032 ms
Path 9/11516. Steps: 14, runs: 21. Elapsed time: 284.969 ms
Path 10/11516. Steps: 19, runs: 91. Elapsed time: 346.003 ms
...

After modification

Path 1/11516. Steps: 15, runs: 27. Elapsed time: 1.031 ms
Path 2/11516. Steps: 11, runs: 29. Elapsed time: 0.000 ms
Path 3/11516. Steps: 10, runs: 10. Elapsed time: 0.000 ms
Path 4/11516. Steps: 14, runs: 21. Elapsed time: 0.996 ms
Path 5/11516. Steps: 11, runs: 37. Elapsed time: 0.000 ms
Path 6/11516. Steps: 22, runs: 136. Elapsed time: 2.000 ms
Path 7/11516. Steps: 12, runs: 12. Elapsed time: 0.971 ms
Path 8/11516. Steps: 9, runs: 21. Elapsed time: 0.000 ms
Path 9/11516. Steps: 14, runs: 21. Elapsed time: 0.000 ms
Path 10/11516. Steps: 19, runs: 91. Elapsed time: 1.000 ms
...

Minimal project for testing

TestPathFind.zip

[brean]

Hello @devjolan .

Thanks for pointing this out.

In the past we focused on CPU performance and made some great improvements but I also like to shine a light on memory consumption as well.
With your proposed cache might take a lot memory (especially if a path can not be found and we searched the whole map - in that case the cache references every cell).

As we always keep a reference to a parent node, I think there is some potential for using the edge nodes and use some back-tracking to clean up the map.

I am very busy right now, but as I will do the lecture slot on path finding as part of the robotics introduction for the computer science students at University Bremen I will discuss this and (possible) other solutions with the students mid of December.