Performance: allocating new nodes

[pathway]

Profiling using the scale testing branch (including the priority queue): php xdebug and kcachegrind

A lot of time is spent constructing nodes, including __Constructor, and fromNode.

Would you consider an approach which did not require as much node construction. For example, if each nodeID need only be created once.

[jmgq]

From the top of my head I can think of two approaches to make this more efficient:

A) In Terrain\MyAStar.php a MyNode object is created from a Node object:

$myNode = MyNode::fromNode($node);

However, this is not necessary, as the $node object is actually a MyNode.

B) Use a cache of nodes. Before creating a new node, check if that node already exists in the cache. If so, return the existing one.

Both changes would happen at the Example level, rather than at the Algorithm level. When I created the examples, I focused more on making them easy to understand, rather than on efficiency, because the point of the examples is that a new user can understand how to use the algorithm. That's why I'm not inclined to sacrifice clarity for efficiency in the examples.

However, I think that option B can be used at the algorithm level after the changes in #9 have been developed, because in that case the user won't be creating a full node anymore, the nodes will be handled entirely by the algorithm, and I am more than happy to make the algorithm more efficient.

So, as a summary, this is what I expect from each part of the code:

• examples folder: easy to understand.
• src folder (actual algorithm): efficiency.

I think we should keep this issue open and try to implement a node cache after #9 has been developed.

And, of course, I'm open to discuss any suggestions you may have.

Thanks once again for your feedback, I really appreciate it.

[pathway]

That makes sense.

I was wondering about your intent with the code. An optimized version could be very ugly for learning.

[pathway]

Related to this, if you keep the nodes around, then you can store useful data in them.

That can have multiple benefits including reducing the need for new calls.

For example in this code, instead of keeping a Closed list, there is just a "closed" flag on each node: https://github.com/pathway/go-astar/blob/master/astar.go

[jmgq]

Thanks for the link, it's very interesting. I see that it also has a flag on every node to check if it belongs to the open list as well, it's a very clever implementation.

Once #9 has been implemented and the user has no access to the nodes, we can try to implement that. I think the highest priority right now should be to create the benchmark utility. Once that's done it will help us greatly to test the performance of new features against the current ones.

[pathway]

The flags on nodes are not uncommon so I dont feel you would be taking a unique design if you did that.

And I think your idea of benchmark reading/writing terrain files makes a lot more sense than my approach of pasting massive arrays into source code. It was just faster to get started so we could see numbers asap =D

[jmgq]

Don't worry, I understand why you did it like that, and it was very helpful :)

[jmgq]

Update after the v2.0.0 release:

At the moment, we create a new Node object per neighbour every time we make a call to AStar::generateAdjacentNodes, even when we have already created the same neighbour in previous calls to this function. As discussed in previous comments, a cache of nodes could help mitigate this.

The cache should implement the PSR-16 standard. We will need to add a new composer dependency: psr/simple-cache, as well as another dependency for its implementation.

One possible way to implement this would be to create a Score object (with the f, g and h properties). Each Node object will have two Score objects: the normal and tentative scores. When we call getAdjacentNodesWithTentativeScore, it will return the nodes that we have actually processed and stored in the cache (except for the ones we haven't created them yet, in which case we create the new ones and store them in the cache), and it will populate the tentative score, rather than the actual score. In fact, instead of calling getAdjacentNodesWithTentativeScore in the main loop, we can call two methods: one of them to get the successors (it will create new ones or return the existing ones from the cache), and then we call a new method: calculateTentativeScore.

The Node object could also have a new acceptTentativeScore(): void method that we will call before adding the node to the open list, and that will copy the values of the tentative score to its actual score.

The Node object won't need to expose the whole tentative score object, since we will only need to set and retrieve its G score. Perhaps this means that creating a new Score object could be overkill, an a simple float | int $tentativeG could be enough.