make node search more efficient

Rather than search every node in the tree, comparing that node and all
of its parents every time, start at the root from both sides and work
our way down the tree

4 files changed, 43 insertions, 3 deletions

diff --git a/activerecord/lib/active_record/associations/join_dependency.rb b/activerecord/lib/active_record/associations/join_dependency.rb
index 871ca1c91d..fe0066bbe1 100644
--- a/activerecord/lib/active_record/associations/join_dependency.rb
+++ b/activerecord/lib/active_record/associations/join_dependency.rb
@@ -71,7 +71,7 @@ module ActiveRecord
         associations.reject { |association|
           join_assocs.detect { |a| node_cmp association, a }
         }.each { |association|
-          join_node = find_parent_node(association.parent) || @join_root
+          join_node = find_node(association.parent) || @join_root
           type      = association.join_type
           find_or_build_scalar association.reflection, join_node, type
         }
@@ -121,11 +121,28 @@ module ActiveRecord
 
       private
 
-      def find_parent_node(parent)
-        @join_root.find { |join_part| node_cmp parent, join_part }
+      def find_node(target_node)
+        stack = target_node.parents << target_node
+
+        left  = [@join_root]
+        right = stack.shift
+
+        loop {
+          match = left.find { |l| l.match? right }
+
+          if match
+            return match if stack.empty?
+
+            left  = match.children
+            right = stack.shift
+          else
+            return nil
+          end
+        }
       end
 
       def node_cmp(parent, join_part)
+        return true if parent == join_part
         return unless parent.class == join_part.class
 
         case parent
diff --git a/activerecord/lib/active_record/associations/join_dependency/join_association.rb b/activerecord/lib/active_record/associations/join_dependency/join_association.rb
index 3f9afa8992..6dd0e04d4d 100644
--- a/activerecord/lib/active_record/associations/join_dependency/join_association.rb
+++ b/activerecord/lib/active_record/associations/join_dependency/join_association.rb
@@ -33,6 +33,10 @@ module ActiveRecord
         def parent_table_name; parent.table_name; end
         alias :alias_suffix :parent_table_name
 
+        def match?(other)
+          super && reflection == other.reflection
+        end
+
         def join_constraints
           joins         = []
           tables        = @tables.dup
diff --git a/activerecord/lib/active_record/associations/join_dependency/join_base.rb b/activerecord/lib/active_record/associations/join_dependency/join_base.rb
index d3bc3dd1ad..48de12bcd5 100644
--- a/activerecord/lib/active_record/associations/join_dependency/join_base.rb
+++ b/activerecord/lib/active_record/associations/join_dependency/join_base.rb
@@ -8,6 +8,11 @@ module ActiveRecord
           super(klass, nil)
         end
 
+        def match?(other)
+          return true if self == other
+          super && base_klass == other.base_klass
+        end
+
         def aliased_prefix
           "t0"
         end
diff --git a/activerecord/lib/active_record/associations/join_dependency/join_part.rb b/activerecord/lib/active_record/associations/join_dependency/join_part.rb
index b8ce8ff46d..27304acceb 100644
--- a/activerecord/lib/active_record/associations/join_dependency/join_part.rb
+++ b/activerecord/lib/active_record/associations/join_dependency/join_part.rb
@@ -33,6 +33,20 @@ module ActiveRecord
           reflection.name
         end
 
+        def match?(other)
+          self.class == other.class
+        end
+
+        def parents
+          parents = []
+          node = parent
+          while node
+            parents.unshift node
+            node = node.parent
+          end
+          parents
+        end
+
         def each
           yield self
           iter = lambda { |list|