You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@felix.apache.org by "Richard S. Hall (JIRA)" <ji...@apache.org> on 2010/08/06 16:33:15 UTC
[jira] Created: (FELIX-2528) Potential performance issue in
resolver when uses constraint conflict is detected
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.
[jira] Updated: (FELIX-2528) Potential performance issue in
resolver when uses constraint conflict is detected
Posted by "Richard S. Hall (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/FELIX-2528?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Richard S. Hall updated FELIX-2528:
-----------------------------------
Description:
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 giving 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 determining 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 creates 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.
was:
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.
> 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.0, framework-3.0.1
> 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 giving 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 determining 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 creates 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.
[jira] Closed: (FELIX-2528) Potential performance issue in resolver
when uses constraint conflict is detected
Posted by "Richard S. Hall (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/FELIX-2528?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Richard S. Hall closed FELIX-2528.
----------------------------------
Resolution: Fixed
I have committed a fix for this issue. It is possible that it filters out certainly possibilities that it shouldn't, but the spec allows for that. In the end, it helped my scenario resolve quickly and doesn't appear to introduce regressions against the CT or our tests.
> 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.0, framework-3.0.1
> 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 giving 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 determining 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 creates 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.
[jira] Issue Comment Edited: (FELIX-2528) Potential performance
issue in resolver when uses constraint conflict is detected
Posted by "Richard S. Hall (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/FELIX-2528?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12896067#action_12896067 ]
Richard S. Hall edited comment on FELIX-2528 at 8/6/10 12:15 PM:
-----------------------------------------------------------------
I have committed a fix for this issue. It is possible that it filters out some potential solutions, but the spec allows for that. In the end, it helped my scenario resolve quickly and doesn't appear to introduce regressions against the CT or our tests.
was (Author: rickhall):
I have committed a fix for this issue. It is possible that it filters out certainly possibilities that it shouldn't, but the spec allows for that. In the end, it helped my scenario resolve quickly and doesn't appear to introduce regressions against the CT or our tests.
> 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.0, framework-3.0.1
> 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 giving 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 determining 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 creates 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.
[jira] Updated: (FELIX-2528) Potential performance issue in
resolver when uses constraint conflict is detected
Posted by "Karl Pauls (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/FELIX-2528?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Karl Pauls updated FELIX-2528:
------------------------------
Fix Version/s: framework-3.0.2
(was: framework-3.2.0)
> 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.0, framework-3.0.1
> Reporter: Richard S. Hall
> Assignee: Richard S. Hall
> Fix For: framework-3.0.2
>
>
> 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 giving 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 determining 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 creates 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.