Fixing #2182 - SimpleGraph#walk is now iterative

It was previously recursive, and was causing
significant performance problems for large, wide
graphs.

Signed-off-by: Luke Kanies <luke@madstop.com>

1 files changed, 15 insertions, 4 deletions

diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb
index b1aaf6363..05420eab9 100644
--- a/lib/puppet/simple_graph.rb
+++ b/lib/puppet/simple_graph.rb
@@ -364,10 +364,21 @@ class Puppet::SimpleGraph
     end
 
     # Just walk the tree and pass each edge.
-    def walk(source, direction, &block)
-        adjacent(source, :direction => direction).each do |target|
-            yield source, target
-            walk(target, direction, &block)
+    def walk(source, direction)
+        # Use an iterative, breadth-first traversal of the graph. One could do
+        # this recursively, but Ruby's slow function calls and even slower
+        # recursion make the shorter, recursive algorithm cost-prohibitive.
+        stack = [source]
+        seen = Set.new
+        until stack.empty?
+            node = stack.shift
+            next if seen.member? node
+            connected = adjacent(node, :direction => direction)
+            connected.each do |target|
+                yield node, target
+            end
+            stack.concat(connected)
+            seen << node
         end
     end