solver: optimize the encoding of the model#51612
Merged
alalazo merged 13 commits intospack:developfrom Nov 21, 2025
Merged
Conversation
Signed-off-by: Massimiliano Culpo <[email protected]>
Signed-off-by: Massimiliano Culpo <[email protected]>
If the node has a variant, it must have _at least_ one value Signed-off-by: Massimiliano Culpo <[email protected]>
Version selection based on "version_satisfies" only applies to virtual nodes. Signed-off-by: Massimiliano Culpo <[email protected]>
Signed-off-by: Massimiliano Culpo <[email protected]>
Unify two rules, and keep the error with a high weight. This reduces the size of the grounded problem. Signed-off-by: Massimiliano Culpo <[email protected]>
This makes the grounded size of the two rules increase like O(ndupes), instead of O(ndupes **2) Signed-off-by: Massimiliano Culpo <[email protected]>
Signed-off-by: Massimiliano Culpo <[email protected]>
Decoupling condition_nodes from TriggerID greatly reduces the grounded size of the problem, since we compute the nodes on which another node can act, without associating them with the rule that triggered the node lookup. Signed-off-by: Massimiliano Culpo <[email protected]>
Signed-off-by: Massimiliano Culpo <[email protected]>
Conflicts very often occur within the same package. Split the conflict rule to avoid an expensive "join" over unification sets most of the time. Signed-off-by: Massimiliano Culpo <[email protected]>
It turns out that "levels" are relative weights used by the heuristics to decide which atoms to guess first. Here we ask clingo to decide on DAG facts before guessing on facts representing internal states. Signed-off-by: Massimiliano Culpo <[email protected]>
alalazo
force-pushed
the
solver/improve-encoding-choice
branch
from
ce6d6e9 to
9f00eed
Compare
The improved encoding behaves much better with the default "oll" tactics. Signed-off-by: Massimiliano Culpo <[email protected]>
Member
Author
|
It seems the improved encoding performs better with the default |
1 task
haampie
approved these changes
Nov 21, 2025
Member
haampie
left a comment
haampie
left a comment
There was a problem hiding this comment.
LGTM! Nice to see also the variance go down 👍
1 task
psakievich
pushed a commit
to psakievich/spack
that referenced
this pull request
Dec 1, 2025
The optimizations here are mostly aimed at reducing the size of the grounded problem. In particular: * The `condition_nodes/3` facts have been decoupled from the `TriggerID` and turned into `condition_nodes/2`. This reduces the amount of grounded rules considerably. * The conflict rule has been split, to avoid in most cases an expensive join over unification sets Besides that, the heuristics has been reworked, and we started using "levels". This allow us to force a clear order over priorities of the guesses in the solver. Signed-off-by: Massimiliano Culpo <[email protected]>
harshula
pushed a commit
to ACCESS-NRI/spack
that referenced
this pull request
Dec 9, 2025
* Cherry-picked upstream commit 417913a The optimizations here are mostly aimed at reducing the size of the grounded problem. In particular: * The `condition_nodes/3` facts have been decoupled from the `TriggerID` and turned into `condition_nodes/2`. This reduces the amount of grounded rules considerably. * The conflict rule has been split, to avoid in most cases an expensive join over unification sets Besides that, the heuristics has been reworked, and we started using "levels". This allow us to force a clear order over priorities of the guesses in the solver. Signed-off-by: Massimiliano Culpo <[email protected]>
becker33
pushed a commit
that referenced
this pull request
Jan 11, 2026
The optimizations here are mostly aimed at reducing the size of the grounded problem. In particular: * The `condition_nodes/3` facts have been decoupled from the `TriggerID` and turned into `condition_nodes/2`. This reduces the amount of grounded rules considerably. * The conflict rule has been split, to avoid in most cases an expensive join over unification sets Besides that, the heuristics has been reworked, and we started using "levels". This allow us to force a clear order over priorities of the guesses in the solver. Signed-off-by: Massimiliano Culpo <[email protected]>
becker33
pushed a commit
that referenced
this pull request
Jan 11, 2026
The optimizations here are mostly aimed at reducing the size of the grounded problem. In particular: * The `condition_nodes/3` facts have been decoupled from the `TriggerID` and turned into `condition_nodes/2`. This reduces the amount of grounded rules considerably. * The conflict rule has been split, to avoid in most cases an expensive join over unification sets Besides that, the heuristics has been reworked, and we started using "levels". This allow us to force a clear order over priorities of the guesses in the solver. Signed-off-by: Massimiliano Culpo <[email protected]> Signed-off-by: Gregory Becker <[email protected]>
becker33
pushed a commit
that referenced
this pull request
Jan 12, 2026
The optimizations here are mostly aimed at reducing the size of the grounded problem. In particular: * The `condition_nodes/3` facts have been decoupled from the `TriggerID` and turned into `condition_nodes/2`. This reduces the amount of grounded rules considerably. * The conflict rule has been split, to avoid in most cases an expensive join over unification sets Besides that, the heuristics has been reworked, and we started using "levels". This allow us to force a clear order over priorities of the guesses in the solver. Signed-off-by: Massimiliano Culpo <[email protected]> Signed-off-by: Gregory Becker <[email protected]>
becker33
pushed a commit
that referenced
this pull request
Jan 15, 2026
The optimizations here are mostly aimed at reducing the size of the grounded problem. In particular: * The `condition_nodes/3` facts have been decoupled from the `TriggerID` and turned into `condition_nodes/2`. This reduces the amount of grounded rules considerably. * The conflict rule has been split, to avoid in most cases an expensive join over unification sets Besides that, the heuristics has been reworked, and we started using "levels". This allow us to force a clear order over priorities of the guesses in the solver. Signed-off-by: Massimiliano Culpo <[email protected]> Signed-off-by: Gregory Becker <[email protected]>
vjranagit
pushed a commit
to vjranagit/spack
that referenced
this pull request
Jan 18, 2026
The optimizations here are mostly aimed at reducing the size of the grounded problem. In particular: * The `condition_nodes/3` facts have been decoupled from the `TriggerID` and turned into `condition_nodes/2`. This reduces the amount of grounded rules considerably. * The conflict rule has been split, to avoid in most cases an expensive join over unification sets Besides that, the heuristics has been reworked, and we started using "levels". This allow us to force a clear order over priorities of the guesses in the solver. Signed-off-by: Massimiliano Culpo <[email protected]> Signed-off-by: Gregory Becker <[email protected]>
becker33
pushed a commit
that referenced
this pull request
Jan 22, 2026
The optimizations here are mostly aimed at reducing the size of the grounded problem. In particular: * The `condition_nodes/3` facts have been decoupled from the `TriggerID` and turned into `condition_nodes/2`. This reduces the amount of grounded rules considerably. * The conflict rule has been split, to avoid in most cases an expensive join over unification sets Besides that, the heuristics has been reworked, and we started using "levels". This allow us to force a clear order over priorities of the guesses in the solver. Signed-off-by: Massimiliano Culpo <[email protected]> Signed-off-by: Gregory Becker <[email protected]>
becker33
pushed a commit
that referenced
this pull request
Jan 26, 2026
The optimizations here are mostly aimed at reducing the size of the grounded problem. In particular: * The `condition_nodes/3` facts have been decoupled from the `TriggerID` and turned into `condition_nodes/2`. This reduces the amount of grounded rules considerably. * The conflict rule has been split, to avoid in most cases an expensive join over unification sets Besides that, the heuristics has been reworked, and we started using "levels". This allow us to force a clear order over priorities of the guesses in the solver. Signed-off-by: Massimiliano Culpo <[email protected]> Signed-off-by: Gregory Becker <[email protected]>
Member
|
This PR does not apply cleanly to releases/v1.0, and will be dropped from v1.0.3 |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This PR is part of an on-going effort to speed up the solver. The commits are all independent, so they may be rebased and merged, rather than squashed.
The optimizations here are mostly aimed at reducing the size of the grounded problem. In particular:
condition_nodes/3facts have been decoupled from theTriggerIDand turned intocondition_nodes/2. This reduces the amount of grounded rules considerably.Besides that, the heuristics has been reworked, and we started using "levels". This allow us to force a clear order over priorities of the guesses in the solver.
Results are the following:
radiuss.develop.csv
radiuss.pr.usc.csv
We can experiment further with heuristics in following PRs, but this seems a promising starting point.