Commits

dirkbaechle committed 966524e Draft

- switched 'visited' list to set()

Rationale for the whole patch: While trying to analyze the source tree
of SCons (www.scons.org), I noticed that pylint took forever to finish
a single run. I tracked the problem down a little and finally ended my
search at the _get_cycles() function that gets called recursively.
They way it is implemented at the moment, you will get a very high number
of calls for medium to large graphs that are also very dense in nature
(have a high vertex degree).
In the case of SCons there are about 176 packages involved, which import
each other a lot. This results in 130869104 calls of _get_cycles()
and a runtime of 27minutes and 6.835seconds fo the whole pylint run.
With this patch you get 10156 calls, taking 30.893s for the complete
pylint call. Note, that the pruning of the search tree also reduces
the list of output results, since all manifolds that are simple rotated
versions of each other, get suppressed automatically.

Related to: "Better cyclic imports analysis algorithm", pylint,
http://www.logilab.org/ticket/2469 , (closes #2469)

  • Participants
  • Parent commits f3236bd

Comments (0)

Files changed (1)

     if vertices is None:
         vertices = graph_dict.keys()
     for vertice in vertices:
-        _get_cycles(graph_dict, vertice, [], [], result)
+        _get_cycles(graph_dict, vertice, [], set(), result)
     return result
 
 def _get_cycles(graph_dict, vertice=None, path=None, visited=None, result=None):
     try:
         for node in graph_dict[vertice]:
             if node not in visited:
+                if visited is None:
+                    visited = set()
                 _get_cycles(graph_dict, node, path, visited, result)
-                if visited is None:
-                    visited = []
-                visited.append(node)
+                visited.add(node)
     except KeyError:
         pass
     path.pop()