Skip to content

find_path blows up exponentially #17339

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
Veykril opened this issue Jun 3, 2024 · 0 comments
Open

find_path blows up exponentially #17339

Veykril opened this issue Jun 3, 2024 · 0 comments
Labels
A-perf performance issues C-bug Category: bug

Comments

@Veykril
Copy link
Member

Veykril commented Jun 3, 2024

In the project that can't be shared publicly rust-analyzer started hanging up all worker threads within find_path_module / calculate_best_path. I assume that it is not actually hanging (as the recursion does look like having appropriate exit conditions everywhere) but instead running into a search tree so wide that with a max depth of 15 (

const MAX_PATH_LEN: usize = 15;
) we just run into too much work to do depending on the project setup. Lowering that to 5 seemed to somewhat fix the issue in the project somewhat confirming my assumption

@Veykril Veykril added A-perf performance issues C-bug Category: bug labels Jun 3, 2024
@Veykril Veykril self-assigned this Jun 3, 2024
bors added a commit that referenced this issue Jun 3, 2024
internal: Improve `find_path` performance

cc #17339, db80216 should fix a case where we don't reduce our search space appropriately. This also adds a fuel system which really shouldn't ever be hit, hence why it warns
lnicola pushed a commit to lnicola/rust that referenced this issue Jun 23, 2024
internal: Improve `find_path` performance

cc rust-lang/rust-analyzer#17339, db80216dac3d972612d8e2d12ade3c28a1826ac2 should fix a case where we don't reduce our search space appropriately. This also adds a fuel system which really shouldn't ever be hit, hence why it warns
@Veykril Veykril removed their assignment Aug 12, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-perf performance issues C-bug Category: bug
Projects
None yet
Development

No branches or pull requests

1 participant