Skip to content

solver: use a new heuristic#46548

Merged
tgamblin merged 2 commits intospack:developfrom
alalazo:solver/new-heuristic
Sep 24, 2024
Merged

solver: use a new heuristic#46548
tgamblin merged 2 commits intospack:developfrom
alalazo:solver/new-heuristic

Conversation

@alalazo
Copy link
Copy Markdown
Member

@alalazo alalazo commented Sep 23, 2024

Extracted from #45189

This PR introduces a new heuristic for the solver, which behaves better when compilers are treated as nodes. Apparently, it performs better also on develop, where compilers are still node attributes.

The new heuristic:

  • Sets an initial priority for guessing a few attributes. The order is "nodes" (300), "dependencies" (150), "virtual dependencies" (60), "version" and "variants" (30), and "targets" and "compilers" (1). This initial priority decays over time during the solve, and falls back to the defaults.
  • By default it considers most guessed facts as "false". For instance, by default a node doesn't exist in the optimal answer set, or a version is not picked as a node version etc.
  • There are certain conditions that override the default heuristic using the priority of a rule, which previously we didn't use. For instance, by default we guess that a attr("variant", Node, Variant, Value) is false, but if we know that the node is already in the answer set, and the value is the default one, then we guess it is true.

Signed-off-by: Massimiliano Culpo <[email protected]>
Signed-off-by: Massimiliano Culpo <[email protected]>
@spackbot-app spackbot-app bot added the core PR affects Spack core functionality label Sep 23, 2024
@alalazo
Copy link
Copy Markdown
Member Author

alalazo commented Sep 23, 2024

Benchmarked on:

  • Spack: 0.23.0.dev0 (0f612d0)
  • Python: 3.11.5
  • Platform: linux-ubuntu20.04-icelake

radiuss.develop.csv
radiuss.pr.csv
radiuss.txt

radiuss

It seems to behave generally better also on develop.

Copy link
Copy Markdown
Member

@tgamblin tgamblin left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@alalazo LGTM. Can you please, in a follow-up, add the description from the PR to the comments in heuristic.lp? I think it'll help for long-term maintenance if these are documented in the code.

Merging now, based on the benchmark results, and leaving comment updates for future PR.s

@tgamblin tgamblin merged commit 679770b into spack:develop Sep 24, 2024
@alalazo alalazo deleted the solver/new-heuristic branch September 24, 2024 06:47
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

core PR affects Spack core functionality

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants