[Pkg-puppet-devel] [SCM] Puppet packaging for Debian branch, upstream, updated. 0.25.4-89-gcbbd363

[James Turnbull]

The following commit has been merged in the upstream branch:
commit 56b575393bb9db99b25182d7d167a2768b561e6e
Author: Brice Figureau <brice-puppet at daysofwonder.com>
Date:   Sat Mar 20 14:13:31 2010 +0100

    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 at daysofwonder.com>

diff --git a/lib/puppet/simple_graph.rb b/lib/puppet/simple_graph.rb
index 5e8f5cd..37a08e7 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 e132b72..53b1c51 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 22d6ebe..7919d0c 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

-- 
Puppet packaging for Debian