| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
7c43f786ebba
|
|
There is a cost in memory to this change. But the win in terms of
speed is *huge*. How huge? Well, when compiled without optimization,
the new code is now 4-5 times faster than the previous code *with*
optimization and something like 20-30 times faster than 0.5.2.
|
|
choice, and to find choices that contain a particular choice.
|
|
|
|
A 3-way comparison is the traditional "return <0, =0, or >0" protocol.
The implementation supports compile-time polymorphism to select the most
appropriate comparison, defaulting to operator<.
This yields a huge improvement in the program run-time, probably because
the program compares lots of complex objects, especially things like
imm::set objects that build their comparison from sub-comparisons.
It would still be good to overload compare3<> on the types used in the
aptitude resolver universe -- although the core types are simple enough
that the compiler will probably be able to optimize the extra
comparisons away (I hope, anyway).
|
|
contains which is itself contained in the input choice.
The choice is unique if it exists because of the structure of
choice_set. Overlapping choices that are not identical must install
versions of the same package, and there can only be one choice that
installs a version of any given package.
|
|
choices are added to a set, log at ERROR level and try to continue.
|
|
This is in preparation for backpropagating conflict/promotion
information, and in fact much of the code for that is already
implemented in this commit (just not activated yet). I decided to
use integer references into a deque to keep things a little more
compact instead of having a huge number of structures on the heap: the
resolver is already memory-hungry enough, no need to make things even
worse.
|
|
choice_sets, rather than manually storing the different types of choices in the solution object.
This has two beneficial effects. First, it should make it a bit easier
to add a new choice type, although many parts of the program will still
have to be touched. Perhaps more importantly, this provides a cleaner
conceptual model of what the resolver does: it finds "choice points"
(that is to say, dependencies that need to be solved) and makes choices
at them.
This commit sneaks in a few optimizations that I came across in the
process of rewiring all the resolver logic. The big one is that testing
whether a solution violates a user constraint now requires steps
proportional to the size of the solution, not to the number of user
constraints. (each step is logarithmic in the number of constraints,
but that's still a big improvement)
|
|
|
|
This will make it a lot easier to port the frontend code to use choice
sets, should I decide to move the backend solution to using choice
sets. for_each() is efficient, but also a pain to use; when I'm only
going to iterate over one small set, it's a lot simpler to have an
iterator interface available.
|
|
|
|
solutions an imm::sets.
|
|
Needed to use this in the solution object.
|
|
|
|
This matters because choice sets are used to store the information that
a set of actions has a joint consequence. This means that we only want
to store the *narrowest* action added to a set, because to be part of
both a more general action and a more specific action, you must be
part of the more specific one. (technically, when building the sets
that we are looking for joint consequences in (that is, search nodes /
solutions), we should take the widest action that's added to them -- but
in practice, we never add overlapping actions to one of these sets
anyway due to the monotonicity rule (actions only overlap if they touch
the same package).
|
|
|
|
|
|
eliminating overlaps, and write a test case for it.
|
