| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
Without this, bad stuff was happening, like spurious entries in the
structural-reasons list that triggered internal sanity checks.
|
|
This doesn't have a practical effect (those steps weren't being
processed anyway), but it does suppress spurious errors in the logs.
|
|
update it, not before.
|
|
|
|
parent step's tier, use the parent step's tier.
Previously, the code was decreasing the tier in the successor.
|
|
Some promotions are never being applied, for reasons that are not
currently clear. The sanity check ensures that promotions are always
applied, and also logs an error if it ever trips, to help track this
down.
|
|
If I need this again, I should probably just make it a separate logging
category -- hopefully I won't, though.
|
|
newly selected version, not just reverse dependencies.
|
|
|
|
The idea is that if there are only "a few" new promotions, it's quicker
to test them individually than to use the full promotion set. The exact
parameters of what "a few" means should probably be configurable at
runtime, not least so I can easily get some statistics on what the
effects of various settings are.
|
|
whenever a promotion is added, just retest tiers when steps are pulled off the queue.
This seems to be a win overall, probably because most of the computation
in the case where lots of promotions have been added is a waste (since
the steps won't be processed anyway, or another promotion will come
along and override the one that was applied). I would still like to
explore a hybrid model, where promotions are applied incrementally if
only "a few" have been added since a step was generated -- that should
vastly speed up scanning smallish subtrees.
|
|
These don't have any impact on performance that I can see one way or
the other -- which probably means they don't hurt much in smaller
cases, so it's a cheap way to avoid scalability surprises since the
hash tables should be better for large inputs.
|
|
promotion-finding routine.
|
|
Not just grammatically, but semantically.
|
|
|
|
This almost eliminates the time we were spending comparing dep solvers
(according to profiling, it's now down to 5% of the run time). There
are several parts to this commit:
(1) Making Boost a dependency of aptitude. This involved changing
the configure script, writing a README about it, and writing a
short shell script to verify that the configure script is up to
date.
(2) Redesigning the dep-solvers set so that all mutation goes through
a member function. The set needs to cache its hash value for the
sake of speed, and having mutation go through member functions
lets us invalidate the cache.
(3) Writing hash functions for the major resolver structures (that
is: the concrete package, version, dep, and tier objects in both
implementations, the choice object, and the solver_information
and dep_solvers objects in the search graph).
(4) Changing the std::set that we were using to collect identical
dep_solvers objects to a boost::unordered_set.
|
|
Really, this should use a hash table. I'm seriously tempted to just
lean on Boost here -- they have a very nice implementation of hashing.
|
|
According to profiling data, this was one of the main bottlenecks in
the new resolver. The new code uses a trick similar to the one used
by the promotion set (and hence is also not threadsafe :( ), storing
the counts in the step structures themselves (to avoid having to
allocate a tree structure); in this case we even use a "generation
counter" to avoid having to zero out the counts between runs. That
seems to have eliminated it as the main culprit and replaced it with
the dep-memoization code (which I knew would be a problem eventually;
now it is).
Note: if we ever want to support multiple threads in the resolver, the
solution would probably be to give each one its own side table
containing the counts of various steps (they could even use the
"generation" trick to avoid having to reset counts, like the main one
does now).
|
|
|
|
|
|
This saves a lot of memory, but needs to be optimized to save CPU time.
|
|
A solver should only get a validity condition if its tier has been
increased in a way that might be retracted (i.e., by a user constraint
or by a promotion derived from a user constraint).
|
|
promotion is retracted, recompute tiers for solvers that it might have "hit".
In this model, the tier_valid member of search_graph is no longer an
active expression that recomputes the solver's tier when it becomes
invalid. Instead, it's a pure expression that represents whether the
last promotion that was applied to the tier was valid. When any
promotion becomes invalid, the whole list of active steps is searched
for steps that it might have influenced (the same way we would search
for steps to apply it to) and the tier of each such step is recomputed.
The major reason for making this change is that maintaining all the
structures to track which solvers a promotion affected was expensive,
particularly in terms of memory usage. This information is only needed
rarely, so I don't want to overly burden the normal behavior of the
resolver with book-keeping to handle the corner case of retracted
promotions. The new code should be correct; it'll be a bit slow to
retract promotions and sometimes the wrong solvers will be recomputed,
but that's better than eating hundreds of megabytes of memory.
A secondary, but also important, reason is that this opens the door to
memoizing dependency solver sets. Previously, solver sets contained
backpointers to their own step; they had to, in order to maintain the
"zap this solver in this step" active expression. Now, solver sets
only contain pointers to structures that are common to all solvers for
their dependency, or to all solvers that were affected by a particular
promotion. This should mean that there are enough equivalent sets that
memoization of some sort will be a win. In particular, I hope that this
will tackle the last outstanding memory problem, where applying a
promotion takes a bunch of identical sets that share memory and creates
a bunch of identical sets that don't share memory, massively spiking
the program's memory usage in the process.
|
|
dependency information back in.
We need that information to correctly find choices in various internal
maps, but it's eliminated when we pass a choice through a choice-indexed
set.
|
|
information.
|
|
|
|
For some reason the code wasn't doing this, which led to a situation
where every step listed every choice that had ever been mentioned as
a solver. This may be part of why promotions were bogging everything
down -- most steps looked like they contained any given promotion!
|
|
|
|
Lots of empty promotions appear to get generated during the course of
the search, and the promotion set doesn't handle them properly. They
aren't very interesting (you hardly ever have any valuable knowledge
about the empty set), and they sit around eating memory.
|
|
|
|
Dependencies with no solvers should always cause the step that contains
them to be promoted to the conflict tier and thus ejected from the
graph.
|
|
the "is_last_child" member of the last step in the steps list.
This may be a symptom of the fact that the way steps are added is
rather error-prone. However, it should work now.
The problem was that we were always clearing the "is_last_child" member
of the last step in the global list of steps. We want to do this
whenever we add a child beyond the first, since otherwise each step
would have only one child. But we don't want to do it for the first
child, or only the very last step in the list would be marked as a last
child (meaning that every "child" list would contain all the steps
following its first entry).
|
|
|
|
first added.
The global index was getting ridiculously huge, and it doesn't need to
be. To find all the steps containing a choice, we can just start at
the first step where it was introduced as a solver, and trace out the
whole subtree below that, stopping whenever a step no longer contains
the choice in question.
With this commit, the time per step is much more reasonable (when
compiled without optimizations, it appears to be approximately as fast
as the old resolver was with optimizations). However, it also looks
like there are a few bugs left: it branches far too much and it got
stuck once in an infinite loop.
|
|
generated.
|
|
install_version choices.
get_has_dep() is only really meant to work for these choices; it will
throw an exception if called on a different type of choice.
|
|
dependency.
This situation will likely lead to a crash.
|
|
Some STL containers can move elements around when new entries are added.
I think the deque doesn't do this -- but performance isn't so important
that I want to implicitly depend on this level of detail regarding how
an STL container is implemented (whether or not the standard would
allow me to).
|
|
itself.
|
|
This just amounts to "if you only made one successor, jump to that
successor and repeat".
|
|
routine.
This will make it a bit cleaner to implement forced dependencies, I hope.
|
|
|
|
This means we return NoMoreSolutions whenever we're invoked after all
the solutions have been generated. Among other things, the unit tests
expect this.
|
|
than any choice from a solver.
This should be what we do anyway: the promotion's choice will always be
the most general one that covers all the solvers that hit it.
However, the fact that the previous code wasn't working exposes a bug in
contains(): although deps are no longer significant, it's claiming that
one choice with a dep doesn't contain another choice with a different
dep, even if neither is a from-dep-source choice and they install the
same version! That will be fixed momentarily.
|
|
|
|
from being discarded by promotions.
I'm not 100% sure this is what we want for the final behavior, but it
is one way of attacking the problem where the resolver would generate
a solution, then throw it away because it was already generated. Now
those solutions are never thrown away for any reason (although they can
still be affected by promotions that are discovered or by deferrals).
|
|
|
|
|
|
global set.
This ensures that we attempt to apply promotions to existing steps.
For instance, this should stop the resolver from returning new
"solutions" that contain old solutions as strict subsets.
|
|
|
