Fix inefficient SimpleGraph#matching_edge

This method has two issues:
 * it is inefficient when there are many events
 * it tries to match edges that shouldn't be matched

With recursive file resources, many change events can be generated.
The method used to find the good ones is pretty inefficient, allocating
arrays and/or appending to arrays which is a slow operation that can
consume lot of memory.

Still with recursife file resources, the current code tries to match the
events with edges pointing to generated sub-file-resources, which is not
necessary. In fact this all happens because we masquerade the sub-generated
resources with the topmost resource whic itself has auto-required links
to them. There is no reason to send back those events to where they were
generated.

This patch tries to minimize allocations or array appending, it also collect
event names (instead of events themselve) while matching since there are
great chances there are way less events names than events (and we're matchin
by name).

This patch also makes sure we select only edges that don't point back to
the event sources.

Results for matching 1100 events:
 * old code: 22s
 * new code:  0.02s

This patch also helps on the memory consumption side since the GC has
almost no work to perform.

Signed-off-by: Brice Figureau <brice-puppet@daysofwonder.com>

3 files changed, 61 insertions, 20 deletions

diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb
index 5e8f5cdb7..37a08e7f9 100644
--- a/lib/puppet/simple_graph.rb
+++ b/lib/puppet/simple_graph.rb
@@ -64,6 +64,14 @@ class Puppet::SimpleGraph
             end
         end
 
+        def each_out_edges
+            @adjacencies[:out].values.each do |edges|
+                edges.each do |edge|
+                    yield edge
+                end
+            end
+        end
+
         # The other vertex in the edge.
         def other_vertex(direction, edge)
             case direction
@@ -146,20 +154,37 @@ class Puppet::SimpleGraph
     # Collect all of the edges that the passed events match.  Returns
     # an array of edges.
     def matching_edges(events, base = nil)
-        events.collect do |event|
-            source = base || event.source
-
-            unless vertex?(source)
-                Puppet.warning "Got an event from invalid vertex %s" % source.ref
-                next
+        # collect edges out from sources
+        if base
+            # consider only edges which are not pointing to any event sources
+            # which is what a recursive file resources produces
+            event_sources = events.inject({}) { |hash, event| hash[event.source] = event.source ; hash}
+            edges = (adjacent(base, :direction => :out, :type => :edges) - event_sources.keys)
+        else
+            edges = events.inject([]) do |edges,event|
+                if wrapper = @vertices[event.source]
+                    wrapper.each_out_edges do |edge|
+                        edges << edge
+                    end
+                else
+                    Puppet.warning "Got an event from invalid #{event.source.ref}"
+                end
+                edges
             end
-            # Get all of the edges that this vertex should forward events
-            # to, which is the same thing as saying all edges directly below
-            # This vertex in the graph.
-            adjacent(source, :direction => :out, :type => :edges).find_all do |edge|
-                edge.match?(event.name)
+        end
+
+        # find all the different event names, we assume there won't be that many
+        # which should greatly shorten the next loop and reduce the cross-join
+        # between events x out-edges
+        event_names = events.inject({}) { |hash, event| hash[event.name] = event.name ; hash }
+
+        # match all our events to the edges
+        event_names.keys.inject([]) do |matching, event_name|
+            edges.each do |edge|
+                matching << edge if edge.match?(event_name)
             end
-        end.compact.flatten
+            matching
+        end
     end
 
     # Return a reversed version of this graph.
diff --git a/lib/puppet/transaction.rb b/lib/puppet/transaction.rb
index e132b7238..53b1c51f7 100644
--- a/lib/puppet/transaction.rb
+++ b/lib/puppet/transaction.rb
@@ -215,15 +215,17 @@ class Transaction
         # Collect the targets of any subscriptions to those events.  We pass
         # the parent resource in so it will override the source in the events,
         # since eval_generated children can't have direct relationships.
-        relationship_graph.matching_edges(events, resource).each do |orig_edge|
-            # We have to dup the label here, else we modify the original edge label,
-            # which affects whether a given event will match on the next run, which is,
-            # of course, bad.
-            edge = orig_edge.class.new(orig_edge.source, orig_edge.target, orig_edge.label)
-            edge.event = events.collect { |e| e.name }
-            set_trigger(edge)
+        Puppet::Util.benchmark(:debug, "Time for triggering #{events.size} events to edges") do
+            b = relationship_graph.matching_edges(events, resource)
+            b.each do |orig_edge|
+                # We have to dup the label here, else we modify the original edge label,
+                # which affects whether a given event will match on the next run, which is,
+                # of course, bad.
+                edge = orig_edge.class.new(orig_edge.source, orig_edge.target, orig_edge.label)
+                edge.event = events.collect { |e| e.name }
+                set_trigger(edge)
+            end
         end
-
         # And return the events for collection
         events
     end
diff --git a/spec/unit/simple_graph.rb b/spec/unit/simple_graph.rb
index 22d6ebe3d..7919d0c83 100755
--- a/spec/unit/simple_graph.rb
+++ b/spec/unit/simple_graph.rb
@@ -372,6 +372,20 @@ describe Puppet::SimpleGraph do
             edges.should be_include(@edges["a/b"])
             edges.should be_include(@edges["a/c"])
         end
+
+        describe "from generated resources" do
+            before :each do
+                @topsource = stub 'source'
+                @edges["a/topsource"] = Puppet::Relationship.new(@topsource, "a", {:event => :yay, :callback => :refresh})
+                @graph.add_edge(@edges["a/topsource"])
+            end
+
+            it "should not match with edges pointing back to events sources" do
+                @edges["a/b"].expects(:match?).never
+                @edges["a/topsource"].expects(:match?)
+                @graph.matching_edges([@event], @topsource)
+            end
+        end
     end
 
     describe "when determining dependencies" do