boostorg / boostorg/graph

astar_search does unnecessary initialization of vertices

Open
#356 2 comments 1 reaction 0 assignees View on GitHub
performance
Dominant language
C++
Stars
392
Forks
239
Avg merge
1d 11m
Merged PRs (30d)
20

Description

From [Keith Bennet](https://github.com/boostorg/graph/wiki/Feedback-submissions-from-the-Boost-User-mailing-list#keith-bennett):
> astar_search() takes too much time to initialize all vertices (in a 2048x2048x40 matrix) even though we only need to initialize vertices when they are added to the open set. We ensure our data's initialization state is identical to a default-constructed object, then guarantee that the vertex initialization is done when the vertex is first added to the open set, and of course A* ensures that vertices aren't used until they're added to the open set (eg, when they're first discovered). To make resizing containers quicker, we ensure that our default-constructed objects are trivially-constructible so that resizing the underlying containers to match the matrix size does not require invoking expensive constructors which effectively reduces the initialization requirements to just resizing the containers correctly and setting the non-zero start-point state and end-point state.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.