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@gentoo.org>

1 files changed, 33 insertions, 3 deletions

diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
index e4305c18c96a..29eadba3d104 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