It may be useful to see how the bundle resolution problem is proven to be NP-Complete through 3-SAT: http://stackoverflow.com/questions/2085106/is-the-resolution-problem-in-osgi-np-complete
On Fri, Nov 18, 2016 at 10:32 AM, Todor Boev <rinsv...@gmail.com> wrote: > My math is very rusty and my math background is in a different area. > Because of this I hoped to do the mostly programming exercise to integrate > the Resolver service in p2 rather than to extend the SAT mapping. I need to > look at the OSGi-to-SAT mapping paper in order to understand if this is > possible with the current design of the Resolver. > > Regards > > On Fri, Nov 18, 2016 at 5:17 AM, Pascal Rapicault <pas...@rapicault.net> > wrote: > >> On 11/17/2016 8:54 AM, Peter Kriens wrote: >> >> I remember trying to map uses constraints to a boolean expression but >> could not find any way that did not blow up the expression size. This >> seemed very unfortunate because I think they can actually be used to reduce >> the search space considerably. >> >> I'm really happy to see that there is at least 3 people if not more >> interested in the exercise of seeing how to encode uses constraints to SAT. >> How do you guys want to get moving on this? >> Peter, would you happen to still have what you had done? >> >> >> >> From an API level I do not think there is a big deal. The resolver could >> just fetch all resources at start. It can of course only return a single >> solution. This might be unfortunate but I find it hard to see why that is a >> limitation since any solution that satisfies all requirements should be ok. >> >> Kind regards, >> >> Peter Kriens >> >> >> >> On 17 nov. 2016, at 14:41, Thomas Watson <tjwat...@us.ibm.com> wrote: >> >> I will be interested to see if you can successfully map the OSGi uses >> concept into the SAT solver p2 uses. I briefly looked at that a long time >> ago when we were refactoring the Equinox framework (Luna) and were >> replacing the old Equinox resolver. It was far from obvious how you would >> achieve this. At that time I opt'ed to collaborate with a common resolver >> in Felix for the Equinox framework. But this is no magic implementation. >> There are still cases where the OSGi resolver algorithm will blow up. In >> Equinox we try to minimize that possibility by avoiding the resolution of >> all (10000) bundles at once. But as Pascal states, this does leave out >> some possible valid solutions that you will then not discover while >> resolving. >> >> If you do focus on how to map uses into the SAT solver in p2 I would be >> interested in collaborating to see if such a resolver would outperform the >> Felix resolver we use at runtime. My hope at the time I was looking into >> this was to map an OSGi Resolver service on top of the SAT solver >> implementation. But I cannot remember how the SAT solver is driven. I >> suspect the split between the OSGI Resovler and the OSGi ResolveContext >> will not fit well into the SAT implementation model. >> >> Tom >> >> >> >> >> >> From: Todor Boev <rinsv...@gmail.com> >> To: Equinox development mailing list <equinox-dev@eclipse.org> >> Date: 11/17/2016 02:22 AM >> Subject: Re: [equinox-dev] Convergence between p2 and the OSGi >> resolver+repository >> Sent by: equinox-dev-boun...@eclipse.org >> ------------------------------ >> >> >> >> - Regarding batch resolution: >> Ultimately I think the batch processing is about performance. At >> provisioning time where finding the best solution trumps speed the resolver >> can be executed against the entire set. But I have to try this. After than >> the equinox runtime should be able to re-create a correct (maybe not >> identical) resolution from the much smaller set of resources. I have tried >> the resolver against about 700 bundles and it did okay, but this is well >> short of 10,000. More research required....some day. >> >> - Regarding the additional p2 concepts: >> Can you point me to the documentation of how the resolution problem is >> converted to a SAT formula? >> >> Best regards >> >> On Thu, Nov 17, 2016 at 6:20 AM, Pascal Rapicault <*pas...@rapicault.net* >> <pas...@rapicault.net>> wrote: >> On 11/16/2016 10:49 AM, Todor Boev wrote: >> - Regarding resolver behavior: >> The goal is actually to replace the behavior of the objective function >> with the behavior of the resolver. This is the best way to guarantee that >> both p2 and the OSGi runtime agree on what is a consistent set of bundles. >> For example p2 does not take into account package uses constraints which >> leads to p2 selecting bundles that later fail to resolve at runtime. It >> does not matter which way to resolve is better, so long as they agree. >> Since the OSGi resolver is very unlikely to change it falls on p2 to match >> it's behavior. My current company (software ag) has had quite a number of >> issues where essentially p2 sets up the resolver to fail. >> >> - Regarding resolver scalability: >> The resolution is split between the resolver which processes the >> current set of resources and the resolver context which selects candidates >> when asked. If the goal is to support a very high number of candidates - a >> resolver context impl optimized for searches in a large candidate space can >> be provided. If the goal is to produce a solution that includes a very high >> number of resources - more research is required. Even if the initial set is >> 10,000 the resolver can be asked to process them not all at once, but >> incrementally in batches or even one by one. Which is in fact what equinox >> does today. >> The thing is that if you look at a subset of the available bundles, >> you may find a solution that is not the optimal one. p2 will consider all >> the possible candidates in one resolution invocation. >> >> >> I am trying to determine if it makes sense to invest effort in >> prototyping this given that subtle changes in behavior are in fact a goal, >> rather than an issue. >> Even though on the surface p2 resolver looks similar to what the OSGi >> resolver does, p2 has at least 2 additional concepts: >> 1) the expression of strict negation >> 2) the concept of patch >> >> I'm tempted to think that it is probably simpler to add support for the >> uses-clause in p2 (this has been a known issue for years, but I can't seem >> to find the bug tonight) than it is to replace the resolver completely and >> get all the tests to pass. The encoding of dependencies to a SAT formula is >> well documented and so are the optimization functions. >> >> >> On Wed, Nov 16, 2016 at 4:44 AM, Pascal Rapicault <*pas...@rapicault.net* >> <pas...@rapicault.net>> wrote: >> On 11/15/2016 12:52 PM, Todor Boev wrote: >> Hello, >> >> Are there any plans to bring together p2 and OSGi resolver+repository >> standards? >> There is no immediate plan for this. >> >> It should be beneficial to have similar (maybe identical?) dependency >> resolution at provisioning time and later at runtime. >> The install time and runtime resolvers resolve a slightly different >> problem because the install time resolver has to look for candidates in a >> large space, whereas the runtime one has to connect as many components >> together. >> I have not tried replacing the p2 resolver with the new OSGi resolver >> so I can't tell how it would perform. >> >> >> Specifically: >> - Is it possible to publish the bundle generic capabilities/requirements >> to the p2 repository? >> Yes this should be possible. The underlying p2 capability / >> requirement model is really extensible and the current limitation is only >> the serialized format. >> >> - Is it possible to use the equinox Resolver inside the p2 Planner? >> It is possible to get something going but I'm not sure if this will >> scale (p2 resolver is able to perform seamlessly on 10's of thousands of >> IUs), nor if you will be able to replicate the subtleties that result from >> having an objective function. >> >> - Even if the equinox Resolver can not be used is it possible for p2 to >> handle generic requirements/capabilities? >> Yes. This should not be too much work. >> >> >> >> Regards, >> Todor Boev >> >> >> _______________________________________________ >> equinox-dev mailing list >> *equinox-dev@eclipse.org* <equinox-dev@eclipse.org> >> To change your delivery options, retrieve your password, or unsubscribe >> from this list, visit >> *https://dev.eclipse.org/mailman/listinfo/equinox-dev* >> <https://dev.eclipse.org/mailman/listinfo/equinox-dev> >> _______________________________________________ equinox-dev mailing list >> *equinox-dev@eclipse.org* <equinox-dev@eclipse.org>To change your >> delivery options, retrieve your password, or unsubscribe from this list, >> visit *https://dev.eclipse.org/mailman/listinfo/equinox-dev* >> <https://dev.eclipse.org/mailman/listinfo/equinox-dev> >> _______________________________________________ >> equinox-dev mailing list >> *equinox-dev@eclipse.org* <equinox-dev@eclipse.org> >> To change your delivery options, retrieve your password, or unsubscribe >> from this list, visit >> *https://dev.eclipse.org/mailman/listinfo/equinox-dev* >> <https://dev.eclipse.org/mailman/listinfo/equinox-dev> >> >> _______________________________________________ >> equinox-dev mailing list >> *equinox-dev@eclipse.org* <equinox-dev@eclipse.org> >> To change your delivery options, retrieve your password, or unsubscribe >> from this list, visit >> *https://dev.eclipse.org/mailman/listinfo/equinox-dev* >> <https://dev.eclipse.org/mailman/listinfo/equinox-dev> >> _______________________________________________ >> equinox-dev mailing list >> equinox-dev@eclipse.org >> To change your delivery options, retrieve your password, or unsubscribe >> from this list, visit >> https://dev.eclipse.org/mailman/listinfo/equinox-dev >> >> >> _______________________________________________ >> equinox-dev mailing list >> equinox-dev@eclipse.org >> To change your delivery options, retrieve your password, or unsubscribe >> from this list, visit >> https://dev.eclipse.org/mailman/listinfo/equinox-dev >> >> >> >> >> _______________________________________________ >> equinox-dev mailing listequinox-...@eclipse.org >> To change your delivery options, retrieve your password, or unsubscribe from >> this list, visithttps://dev.eclipse.org/mailman/listinfo/equinox-dev >> >> >> >> _______________________________________________ >> equinox-dev mailing list >> equinox-dev@eclipse.org >> To change your delivery options, retrieve your password, or unsubscribe >> from this list, visit >> https://dev.eclipse.org/mailman/listinfo/equinox-dev >> > >
_______________________________________________ equinox-dev mailing list equinox-dev@eclipse.org To change your delivery options, retrieve your password, or unsubscribe from this list, visit https://dev.eclipse.org/mailman/listinfo/equinox-dev
