felix-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Richard S. Hall (JIRA)" <j...@apache.org>
Subject [jira] Created: (FELIX-2528) Potential performance issue in resolver when uses constraint conflict is detected
Date Fri, 06 Aug 2010 14:33:15 GMT
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.

View raw message