astar_search does unnecessary initialization of vertices
Nobody has claimed this yet.
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 45/100
- Issue type
- Bug
- Clarity
- Mostly clear
- Activity status
- Stale
- Tech stack
- cpp
- Domain
- performance
Research direction
Start by locating the astar_search implementation in the Boost Graph code and trace how vertex state is initialized before and when vertices enter the open set. Compare the current initialization cost with the lazy-initialization behavior described in the issue, then verify that A* behavior remains correct while large vertex containers avoid unnecessary construction.
Written by the indexing model from the issue text.
Description
From Keith Bennet:
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.
- Dominant language
- C++
- Stars
- 395
- Forks
- 239
- Avg merge
- 18h 50m
- Merged PRs (30d)
- 20
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from boostorg/graph
-
beginner friendly
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
-
algorithm beginner friendly priority: high
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
Difficulty 5/5 Over a week Newbie friendliness 30/100
-
priority: high warning
-
algorithm
boostorg/graph#493 · 22 comments · 1 reaction · 2 assignees ·
Similar issues
-
enhancement
Difficulty 1/5 Under an hour Newbie friendliness 88/100
QuantStack/git2cpp#187 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 86/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
mlcommons/mobile_app_open#1182 ·
-
Needs-Triage
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
microsoft/winget-cli#6547 ·
-
Difficulty 1/5 Under an hour Newbie friendliness 90/100
AXERA-TECH/ax-llm#77 ·