aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2010-07-23 16:20:38 +0100
committerAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2010-07-23 16:20:38 +0100
commitee56c417f8f8b486f0de2aa3b09a1bf32a377764 (patch)
tree21df76e884b42dccd2c53e7e1e0bb77a9b672391
parent76ee405c9c9f91684e42bddb0ba527e29e1084a8 (diff)
downloadpaludis-ee56c417f8f8b486f0de2aa3b09a1bf32a377764.tar.gz
paludis-ee56c417f8f8b486f0de2aa3b09a1bf32a377764.tar.xz
Cleverer fetch ordering
Where fetches are simple, don't actually schedule a fetch when it becomes available. Instead, mark it as pending, and schedule it immediately before the associated install. Fixes: ticket:923
-rw-r--r--paludis/resolver/nag.cc32
-rw-r--r--paludis/resolver/resolver_TEST_continue_on_failure.cc10
2 files changed, 34 insertions, 8 deletions
diff --git a/paludis/resolver/nag.cc b/paludis/resolver/nag.cc
index a542aac..91a0607 100644
--- a/paludis/resolver/nag.cc
+++ b/paludis/resolver/nag.cc
@@ -300,7 +300,7 @@ NAG::sorted_strongly_connected_components(
throw InternalError(PALUDIS_HERE, "mismatch");
/* build edges between SCCs */
- PlainEdges scc_edges, scc_edges_backwards;
+ PlainEdges all_scc_edges, scc_edges, scc_edges_backwards;
for (Edges::const_iterator e(_imp->edges.begin()), e_end(_imp->edges.end()) ;
e != e_end ; ++e)
{
@@ -311,6 +311,7 @@ NAG::sorted_strongly_connected_components(
RepresentativeNodes::const_iterator to(representative_nodes.find(n->first));
if (! (to->second == from->second))
{
+ all_scc_edges.insert(std::make_pair(from->second, Nodes())).first->second.insert(to->second);
scc_edges.insert(std::make_pair(from->second, Nodes())).first->second.insert(to->second);
scc_edges_backwards.insert(std::make_pair(to->second, Nodes())).first->second.insert(from->second);
}
@@ -323,7 +324,7 @@ NAG::sorted_strongly_connected_components(
typedef std::set<std::pair<int, NAGIndex> > OrderableNow;
OrderableNow orderable_now;
- Nodes done;
+ Nodes done, pending_fetches;
for (StronglyConnectedComponentsByRepresentative::const_iterator c(sccs.begin()), c_end(sccs.end()) ;
c != c_end ; ++c)
@@ -333,7 +334,29 @@ NAG::sorted_strongly_connected_components(
while (! orderable_now.empty())
{
OrderableNow::iterator ordering_now(orderable_now.begin());
- result->push_back(sccs.find(ordering_now->second)->second);
+ StronglyConnectedComponentsByRepresentative::const_iterator ordering_now_scc(sccs.find(ordering_now->second));
+
+ if (ordering_now_scc->second.nodes()->size() == 1 && ordering_now_scc->second.nodes()->begin()->role() == nir_fetched)
+ pending_fetches.insert(ordering_now->second);
+ else
+ {
+ auto this_scc_edges(all_scc_edges.find(ordering_now->second));
+ if (this_scc_edges != all_scc_edges.end())
+ {
+ for (auto e(this_scc_edges->second.begin()), e_end(this_scc_edges->second.end()) ;
+ e != e_end ; ++e)
+ {
+ auto p(pending_fetches.find(*e));
+ if (p != pending_fetches.end())
+ {
+ result->push_back(sccs.find(*e)->second);
+ pending_fetches.erase(p);
+ }
+ }
+ }
+
+ result->push_back(ordering_now_scc->second);
+ }
done.insert(ordering_now->second);
PlainEdges::iterator ordering_now_edges(scc_edges_backwards.find(ordering_now->second));
@@ -353,6 +376,9 @@ NAG::sorted_strongly_connected_components(
orderable_now.erase(ordering_now);
}
+ if (! pending_fetches.empty())
+ throw InternalError(PALUDIS_HERE, "still have pending fetches");
+
if (done.size() != sccs.size())
throw InternalError(PALUDIS_HERE, "mismatch");
diff --git a/paludis/resolver/resolver_TEST_continue_on_failure.cc b/paludis/resolver/resolver_TEST_continue_on_failure.cc
index ec76f3f..0269b83 100644
--- a/paludis/resolver/resolver_TEST_continue_on_failure.cc
+++ b/paludis/resolver/resolver_TEST_continue_on_failure.cc
@@ -138,24 +138,24 @@ namespace test_cases
TEST_CHECK_EQUAL(resolved->job_lists()->execute_job_list()->length(), 6);
- const InstallJob * const direct_dep_job(simple_visitor_cast<const InstallJob>(**resolved->job_lists()->execute_job_list()->fetch(3)));
+ const InstallJob * const direct_dep_job(simple_visitor_cast<const InstallJob>(**resolved->job_lists()->execute_job_list()->fetch(1)));
TEST_CHECK(direct_dep_job);
TEST_CHECK_EQUAL(join(direct_dep_job->requirements()->begin(), direct_dep_job->requirements()->end(), ", ", stringify_req),
"0 satisfied independent always");
- const InstallJob * const indirect_dep_job(simple_visitor_cast<const InstallJob>(**resolved->job_lists()->execute_job_list()->fetch(4)));
+ const InstallJob * const indirect_dep_job(simple_visitor_cast<const InstallJob>(**resolved->job_lists()->execute_job_list()->fetch(3)));
TEST_CHECK(indirect_dep_job);
TEST_CHECK_EQUAL(join(indirect_dep_job->requirements()->begin(), indirect_dep_job->requirements()->end(), ", ", stringify_req),
- "1 satisfied independent always");
+ "2 satisfied independent always");
const InstallJob * const target_job(simple_visitor_cast<const InstallJob>(**resolved->job_lists()->execute_job_list()->fetch(5)));
TEST_CHECK(target_job);
if (direct_dep_installed)
TEST_CHECK_EQUAL(join(target_job->requirements()->begin(), target_job->requirements()->end(), ", ", stringify_req),
- "2 satisfied independent always, 4 independent, 3 independent");
+ "4 satisfied independent always, 3 independent, 1 independent");
else
TEST_CHECK_EQUAL(join(target_job->requirements()->begin(), target_job->requirements()->end(), ", ", stringify_req),
- "2 satisfied independent always, 3 satisfied, 4 independent, 3 independent");
+ "4 satisfied independent always, 1 satisfied, 3 independent, 1 independent");
}
} test_continue_on_failure_false(false), test_continue_on_failure_true(true);