On Mon, Apr 16, 2007 at 10:02:08AM +0200, Loïc Minier <[EMAIL PROTECTED]> was heard to say:
[snip: changing BrokenScore makes things worse] OK, I knew there was a reason for its current value :). Probably when you drop BrokenScore to 0, aptitude wastes time trying all the permutations of "remove lib* and break the world". > On Thu, Apr 12, 2007, Daniel Burrows wrote: > > > > I'll see when I get a chance to look at the log more closely whether > > > > there's any clever way to cut down on the amount of work being done. > > > That would be nice! > > In the little bit of examination yesterday, I didn't see anything > > obvious. The general technique for speeding up a search like this is to > > share information between branches; for instance, if we can detect that > > "installing these two packages doesn't conflict immediately but will > > conflict eventually", lots of useless searches can often be curtailed > > (aptitude does a little of this, and it helps in some cases). > > Unfortunately, it looks to me like the different branches are > > more-or-less nonoverlapping. > > The one thing that would be interesting would be if we could somehow > > detect that two branches are "almost" the same and can be merged, at > > least for now. e.g., if I install libarts version X and that other > > branch there installed version Y, then there's no reason to split the > > computation unless and until this changes the list of broken deps and > > resolvers for those deps. That seems to be a general theme in the log, > > but I don't see a trivial way of fixing this (especially when there's > > more than one package involved, in which case we might need to merge > > branches that have diverged temporarily). > > You mentionned "depth first" versus "breadth first" searches and it > made me wonder whether aptitude should not use something inbetween: I > had pretty good results with starting with the default candidate > version and then trying every alternate version of build-deps which > were not high enough. IOW, trying to stick to the current target dist > / default candidate versions, and only diverging a minimal set of deps. > It seems valuable for end-users to be able to keep as many packages > as possible from sid when they want to use experimental, or to keep as > many as possible from stable when using backports etc. > But then this might as well be already implemented. :) What aptitude uses is sometimes called "best-first" search: it assigns a score to each search branch and explores branches that score more highly. StepScore controls how much the score of a branch increases (or decreases) with depth, so turning it up makes aptitude "want to" explore branches in a depth-first order (this is not a hard constraint, but turning it up sufficiently high will make it unlikely that aptitude ever behaves in a non-breadth-first way). The intended result is that aptitude spends its time looking at branches that (a) probably converge to a solution, and (b) have the sorts of characteristics that the user wants (not removing too many packages, for instance). The scores control how much these factors are weighted; StepScore drives the search forward, BrokenScore drives it towards a solution (hopefully :) ), and the other controls try to nudge it towards a "good" solution. I set StepScore fairly low to given the resolver some latitude to search around (so it would be willing to explore tradeoffs before comitting to a branch), but that risks this sort of thrashing. Setting StepScore to a higher value is a good short-term fix here, I think; I really like the idea of merging branches in the future, but I haven't had time to explore the math here. (the difficult part of the problem is equivalent to finding a minimal representation of a monotonic propositional equation -- this is NP-hard for nonomonotonic equations TTBOMK (IIRC, it's what makes circuit design tricky), and I don't know if there's a simplification for the monotonic case, or if there's an approximation algorithm. Slap me if I'm missing something!) > Thanks for your help; I intend to tune the aptitude flavor of > pbuilder-satisfydepends slightly more and I suppose more problematic > cases will pop up when it will be used by more people than me. Yeah, I'm interested in seeing what happens as the resolver is hammered on more. So far I haven't heard any complaints about the etch upgrade, which is encouraging. Daniel
