public inbox for gentoo-commits@lists.gentoo.org
 help / color / mirror / Atom feed
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",
                 ],


             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