From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <gentoo-commits+bounces-1574069-garchives=archives.gentoo.org@lists.gentoo.org>
Received: from lists.gentoo.org (pigeon.gentoo.org [208.92.234.80])
(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)
key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256)
(No client certificate requested)
by finch.gentoo.org (Postfix) with ESMTPS id A83F5158099
for <garchives@archives.gentoo.org>; Tue, 28 Nov 2023 04:20:35 +0000 (UTC)
Received: from pigeon.gentoo.org (localhost [127.0.0.1])
by pigeon.gentoo.org (Postfix) with SMTP id 44B922BC014;
Tue, 28 Nov 2023 04:20:34 +0000 (UTC)
Received: from smtp.gentoo.org (dev.gentoo.org [IPv6:2001:470:ea4a:1:5054:ff:fec7:86e4])
(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)
key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256)
(No client certificate requested)
by pigeon.gentoo.org (Postfix) with ESMTPS id 2431A2BC014
for <gentoo-commits@lists.gentoo.org>; Tue, 28 Nov 2023 04:20:34 +0000 (UTC)
Received: from oystercatcher.gentoo.org (oystercatcher.gentoo.org [148.251.78.52])
(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)
key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256)
(No client certificate requested)
by smtp.gentoo.org (Postfix) with ESMTPS id 21D84342DF8
for <gentoo-commits@lists.gentoo.org>; Tue, 28 Nov 2023 04:20:33 +0000 (UTC)
Received: from localhost.localdomain (localhost [IPv6:::1])
by oystercatcher.gentoo.org (Postfix) with ESMTP id 7546113B9
for <gentoo-commits@lists.gentoo.org>; Tue, 28 Nov 2023 04:20:31 +0000 (UTC)
From: "Zac Medico" <zmedico@gentoo.org>
To: gentoo-commits@lists.gentoo.org
Content-Transfer-Encoding: 8bit
Content-type: text/plain; charset=UTF-8
Reply-To: gentoo-dev@lists.gentoo.org, "Zac Medico" <zmedico@gentoo.org>
Message-ID: <1701142937.49e01d041c74680a81860b819daff812d83df02f.zmedico@gentoo>
Subject: [gentoo-commits] proj/portage:master commit in: lib/_emerge/, lib/portage/tests/resolver/
X-VCS-Repository: proj/portage
X-VCS-Files: lib/_emerge/depgraph.py lib/portage/tests/resolver/test_rebuild_ghostscript.py lib/portage/tests/resolver/test_runtime_cycle_merge_order.py
X-VCS-Directories: lib/_emerge/ lib/portage/tests/resolver/
X-VCS-Committer: zmedico
X-VCS-Committer-Name: Zac Medico
X-VCS-Revision: 49e01d041c74680a81860b819daff812d83df02f
X-VCS-Branch: master
Date: Tue, 28 Nov 2023 04:20:31 +0000 (UTC)
Precedence: bulk
List-Post: <mailto:gentoo-commits@lists.gentoo.org>
List-Help: <mailto:gentoo-commits+help@lists.gentoo.org>
List-Unsubscribe: <mailto:gentoo-commits+unsubscribe@lists.gentoo.org>
List-Subscribe: <mailto:gentoo-commits+subscribe@lists.gentoo.org>
List-Id: Gentoo Linux mail <gentoo-commits.gentoo.org>
X-BeenThere: gentoo-commits@lists.gentoo.org
X-Auto-Response-Suppress: DR, RN, NRN, OOF, AutoReply
X-Archives-Salt: f0fbf973-70d4-4442-86b3-bb3e1ad256d4
X-Archives-Hash: 65bc6e030b41c480fc96272bedff752f
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",
],