Potential performance issue in resolver when uses constraint conflict is
detected
---------------------------------------------------------------------------------
Key: FELIX-2528
URL: https://issues.apache.org/jira/browse/FELIX-2528
Project: Felix
Issue Type: Improvement
Components: Framework
Affects Versions: framework-3.0.1, framework-3.0.0
Reporter: Richard S. Hall
Assignee: Richard S. Hall
Fix For: framework-3.2.0
Whenever the resolver detects a uses constraint conflict, it tries to create
two permutations of its solution search space. Since a conflict effectively
arises between two parties (an existing package constraint and a package
constraint being added), the algorithm creates a potential solution permutation
removing the opposite party from each, since it doesn't know which one may
ultimately lead to a correct solution. The permutation removing the added
package constraint candidates is called a "uses" permutation (since it
permutates the package being used) while the permutation removing the existing
package constraint is called an "import" permutation (since it generally is
causing a backtrack on a previously selected imported package).
The algorithm is basically depth-first search, which ultimately results in it
given priority to the "uses" permutations. This means it won't backtrack on any
choices for imports until it determines that a previous choice was incorrect.
This appears to work fairly well in practice. The downside is that it is
possible that we keep detecting conflicts related to an incorrect import
decision before determine that the original import decision was incorrect. This
results in lots of import permutations being generated that are effectively
smaller and smaller subsets of each other. This can consume a lot of memory
which slows things down as well as creating lots of largely repetitive
permutations to process.
In short, we need to try to detect if we've already permutated an import and
not do it again.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
