After hacking on the resolver code for the last few months, I finally have my changes in a state where they appear to run and produce identical results (disclaimer: on one test case, albeit a fairly complicated one; YMMV) to the old code. The new code is also a bit more than twice as fast.
I plan to work on this for a few more weeks before putting it aside: profiling turns up a few hotspots that look like they should be very optimizable. The current top one on my list is the code that, whenever a new user constraint is added, updates all the solvers in all active steps to account for that constraint. According to the profiler, this is invoked some 800 times and it accounts for about 30-40% of the run-time. The reason seems to be that it spawns 100 instances of increase_solver_tier() each time it's invoked, and those add up fast. Presumably increase_solver_tier could be made faster; on the other hand, it's probably easier to just avoid actually invoking it until the last moment, like I do with promotion applications. It should be a win for the same reason. The question of why increase_solver_tier itself is slow is also interesting -- if it was a trivial operation, I'd expect that it would take a negligible amount of time on a modern processor, even invoked 800,000 times. It looks like it's spending a lot of time memoizing dependency solver lists, and that in turn spends most of its time comparing dependency solver lists -- 13% of the total runtime is spent just in dep_solvers::operator==. That isn't surprising; the implementation of operator== is hideously inefficient. Changing the representation of dep solver sets to something flat would help, and they're so small that it would probably be a flat-out win across the board. It was on my speculative TODO, and I think it just got bumped up in priority. (all those numbers are from gprof, so take them with a grain of salt, but it's usually ok at pointing out broad cost centers) Daniel _______________________________________________ Aptitude-devel mailing list [email protected] http://lists.alioth.debian.org/mailman/listinfo/aptitude-devel
