From: "Zac Medico" <zmedico@gentoo.org>
To: gentoo-commits@lists.gentoo.org
Subject: [gentoo-commits] proj/portage:master commit in: lib/_emerge/, lib/portage/tests/resolver/
Date: Tue, 28 Nov 2023 04:20:31 +0000 (UTC) [thread overview]
Message-ID: <1701142937.49e01d041c74680a81860b819daff812d83df02f.zmedico@gentoo> (raw)
commit: 49e01d041c74680a81860b819daff812d83df02f
Author: Zac Medico <zmedico <AT> gentoo <DOT> org>
AuthorDate: Tue Nov 28 03:42:17 2023 +0000
Commit: Zac Medico <zmedico <AT> gentoo <DOT> org>
CommitDate: Tue Nov 28 03:42:17 2023 +0000
URL: https://gitweb.gentoo.org/proj/portage.git/commit/?id=49e01d04
find_smallest_cycle: Optimize to traverse fewer nodes
If gather_deps is traversing a cycle that is greater than
or equal to the size of the current smallest_cycle, then
abort early. Also abort early if we traverse a node
encountered in a previous cycle for the same ignore_priority,
since that means the two cycles are identical.
On my laptop, this brings the emerge -pe @world time down
to 3m28.884s, compared to 10m44.268s with portage-3.0.55.
Bug: https://bugs.gentoo.org/918682
Signed-off-by: Zac Medico <zmedico <AT> gentoo.org>
lib/_emerge/depgraph.py | 36 ++++++++++++++++++++--
.../tests/resolver/test_rebuild_ghostscript.py | 2 +-
.../resolver/test_runtime_cycle_merge_order.py | 7 +++--
3 files changed, 39 insertions(+), 6 deletions(-)
diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
index e4305c18c9..29eadba3d1 100644
--- a/lib/_emerge/depgraph.py
+++ b/lib/_emerge/depgraph.py
@@ -9151,7 +9151,14 @@ class depgraph:
asap_nodes.extend(libc_pkgs)
- def gather_deps(ignore_priority, mergeable_nodes, selected_nodes, node):
+ def gather_deps(
+ ignore_priority,
+ mergeable_nodes,
+ selected_nodes,
+ node,
+ smallest_cycle=None,
+ traversed_nodes=None,
+ ):
"""
Recursively gather a group of nodes that RDEPEND on
eachother. This ensures that they are merged as a group
@@ -9171,10 +9178,24 @@ class depgraph:
# RDEPENDs installed first, but ignore uninstalls
# (these occur when new portage blocks an older package version).
return False
+ if traversed_nodes is not None:
+ if node in traversed_nodes:
+ # Identical to a previously traversed cycle.
+ return False
+ traversed_nodes.add(node)
selected_nodes.add(node)
+ if smallest_cycle is not None and len(selected_nodes) >= len(
+ smallest_cycle
+ ):
+ return False
for child in mygraph.child_nodes(node, ignore_priority=ignore_priority):
if not gather_deps(
- ignore_priority, mergeable_nodes, selected_nodes, child
+ ignore_priority,
+ mergeable_nodes,
+ selected_nodes,
+ child,
+ smallest_cycle=smallest_cycle,
+ traversed_nodes=traversed_nodes,
):
return False
return True
@@ -9332,12 +9353,21 @@ class depgraph:
local_priority_range.MEDIUM_SOFT + 1,
)
):
+ # Traversed nodes for current priority
+ traversed_nodes = set()
for node in nodes:
if not mygraph.parent_nodes(node):
continue
+ if node in traversed_nodes:
+ continue
selected_nodes = set()
if gather_deps(
- priority, mergeable_nodes, selected_nodes, node
+ priority,
+ mergeable_nodes,
+ selected_nodes,
+ node,
+ smallest_cycle=smallest_cycle,
+ traversed_nodes=traversed_nodes,
):
if smallest_cycle is None or len(selected_nodes) < len(
smallest_cycle
diff --git a/lib/portage/tests/resolver/test_rebuild_ghostscript.py b/lib/portage/tests/resolver/test_rebuild_ghostscript.py
index 8d7cbb1f92..88dc2b5fc3 100644
--- a/lib/portage/tests/resolver/test_rebuild_ghostscript.py
+++ b/lib/portage/tests/resolver/test_rebuild_ghostscript.py
@@ -137,9 +137,9 @@ class RebuildGhostscriptTestCase(TestCase):
mergelist=[
"sys-apps/dbus-1.15.6",
"x11-libs/gtk+-3.24.38",
+ "app-text/ghostscript-gpl-10.01.2",
"net-print/cups-2.4.6",
"net-dns/avahi-0.8-r7",
- "app-text/ghostscript-gpl-10.01.2",
"app-text/libspectre-0.2.12",
"x11-libs/goffice-0.10.55",
],
diff --git a/lib/portage/tests/resolver/test_runtime_cycle_merge_order.py b/lib/portage/tests/resolver/test_runtime_cycle_merge_order.py
index 305757ff47..a955ac3dc3 100644
--- a/lib/portage/tests/resolver/test_runtime_cycle_merge_order.py
+++ b/lib/portage/tests/resolver/test_runtime_cycle_merge_order.py
@@ -56,8 +56,11 @@ class RuntimeCycleMergeOrderTestCase(TestCase):
("app-misc/leaf-b-1", "app-misc/leaf-d-1", "app-misc/leaf-e-1"),
("app-misc/branch-d-1", "app-misc/branch-e-1"),
"app-misc/runtime-c-1",
- ("app-misc/runtime-cycle-c-1", "app-misc/branch-c-1"),
- "app-misc/branch-b-1",
+ (
+ "app-misc/branch-b-1",
+ "app-misc/runtime-cycle-c-1",
+ "app-misc/branch-c-1",
+ ),
("app-misc/runtime-cycle-b-1", "app-misc/plugin-b-1"),
"app-misc/plugins-consumer-1",
],
next reply other threads:[~2023-11-28 4:20 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-11-28 4:20 Zac Medico [this message]
-- strict thread matches above, loose matches on Subject: below --
2024-05-26 18:48 [gentoo-commits] proj/portage:master commit in: lib/_emerge/, lib/portage/tests/resolver/ Zac Medico
2023-12-24 19:30 Zac Medico
2023-12-06 20:29 Zac Medico
2023-11-28 22:42 Zac Medico
2023-11-28 22:26 Sam James
2023-11-19 17:56 Zac Medico
2023-06-16 3:34 Sam James
2023-06-16 3:34 Sam James
2020-11-22 6:13 Zac Medico
2020-09-21 5:39 Zac Medico
2020-02-15 0:05 Zac Medico
2019-09-12 1:51 Zac Medico
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1701142937.49e01d041c74680a81860b819daff812d83df02f.zmedico@gentoo \
--to=zmedico@gentoo.org \
--cc=gentoo-commits@lists.gentoo.org \
--cc=gentoo-dev@lists.gentoo.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox