Performance: optimize route recognition. Large speedup for apps with many resource routes. Closes #10835.

git-svn-id: http://svn-commit.rubyonrails.org/rails/trunk@8674 5ecf4fe2-1ee6-0310-87b1-e25e094e27de

4 files changed, 165 insertions, 13 deletions

diff --git a/actionpack/CHANGELOG b/actionpack/CHANGELOG
index 2338c8a2f3..7fbac137c4 100644
--- a/actionpack/CHANGELOG
+++ b/actionpack/CHANGELOG
@@ -1,5 +1,7 @@
 *SVN*
 
+* Performance: optimize route recognition. Large speedup for apps with many resource routes.  #10835 [oleganza]
+
 * Introduce TemplateFinder to handle view paths and lookups.  #10800 [Pratik Naik]
 
 * Make render :partial recognise form builders and use the _form partial.  #10814 [djanowski]
diff --git a/actionpack/lib/action_controller/routing.rb b/actionpack/lib/action_controller/routing.rb
index ca04879810..d93dc5205f 100644
--- a/actionpack/lib/action_controller/routing.rb
+++ b/actionpack/lib/action_controller/routing.rb
@@ -7,6 +7,7 @@ require 'action_controller/routing/route'
 require 'action_controller/routing/segments'
 require 'action_controller/routing/builder'
 require 'action_controller/routing/route_set'
+require 'action_controller/routing/recognition_optimisation'
 
 module ActionController
   # == Routing
diff --git a/actionpack/lib/action_controller/routing/recognition_optimisation.rb b/actionpack/lib/action_controller/routing/recognition_optimisation.rb
new file mode 100644
index 0000000000..cf8f5232c1
--- /dev/null
+++ b/actionpack/lib/action_controller/routing/recognition_optimisation.rb
@@ -0,0 +1,158 @@
+module ActionController
+  module Routing
+    # BEFORE:   0.191446860631307 ms/url
+    # AFTER:    0.029847304022858 ms/url
+    # Speed up: 6.4 times
+    #
+    # Route recognition is slow due to one-by-one iterating over
+    # a whole routeset (each map.resources generates at least 14 routes)
+    # and matching weird regexps on each step.
+    #
+    # We optimize this by skipping all URI segments that 100% sure can't
+    # be matched, moving deeper in a tree of routes (where node == segment)
+    # until first possible match is accured. In such case, we start walking
+    # a flat list of routes, matching them with accurate matcher.
+    # So, first step: search a segment tree for the first relevant index.
+    # Second step: iterate routes starting with that index.
+    #
+    # How tree is walked? We can do a recursive tests, but it's smarter:
+    # We just create a tree of if-s and elsif-s matching segments.
+    #
+    # We have segments of 3 flavors:
+    # 1) nil (no segment, route finished)
+    # 2) const-dot-dynamic (like "/posts.:xml", "/preview.:size.jpg")
+    # 3) const (like "/posts", "/comments")
+    # 4) dynamic ("/:id", "file.:size.:extension")
+    #
+    # We split incoming string into segments and iterate over them.
+    # When segment is nil, we drop immediately, on a current node index.
+    # When segment is equal to some const, we step into branch.
+    # If none constants matched, we step into 'dynamic' branch (it's a last).
+    # If we can't match anything, we drop to last index on a level.
+    #
+    # Note: we maintain the original routes order, so we finish building
+    #       steps on a first dynamic segment.
+    #
+    #
+    # Example. Given the routes:
+    #   0 /posts/
+    #   1 /posts/:id
+    #   2 /posts/:id/comments
+    #   3 /posts/blah
+    #   4 /users/
+    #   5 /users/:id
+    #   6 /users/:id/profile
+    #
+    # request_uri = /users/123
+    #
+    # There will be only 4 iterations:
+    #  1) segm test for /posts prefix, skip all /posts/* routes
+    #  2) segm test for /users/
+    #  3) segm test for /users/:id
+    #     (jump to list index = 5)
+    #  4) full test for /users/:id => here we are!
+
+    class RouteSet
+      def recognize_path(path, environment={})
+        result = recognize_optimized(path, environment) and return result
+
+        # Route was not recognized. Try to find out why (maybe wrong verb).
+        allows = HTTP_METHODS.select { |verb| routes.find { |r| r.recognize(path, :method => verb) } }
+
+        if environment[:method] && !HTTP_METHODS.include?(environment[:method])
+          raise NotImplemented.new(*allows)
+        elsif !allows.empty?
+          raise MethodNotAllowed.new(*allows)
+        else
+          raise RoutingError, "No route matches #{path.inspect} with #{environment.inspect}"
+        end
+      end
+
+      def recognize_optimized(path, env)
+        write_recognize_optimized
+        recognize_optimized(path, env)
+      end
+
+      def write_recognize_optimized
+        tree = segment_tree(routes)
+        body = generate_code(tree)
+        instance_eval %{
+          def recognize_optimized(path, env)
+            segments = to_plain_segments(path)
+            index = #{body}
+            return nil unless index
+            while index < routes.size
+              result = routes[index].recognize(path, env) and return result
+              index += 1
+            end
+            nil
+          end
+        }, __FILE__, __LINE__
+      end
+
+      def segment_tree(routes)
+        tree = [0]
+
+        i = -1
+        routes.each do |route|
+          i += 1
+          # not fast, but runs only once
+          segments = to_plain_segments(route.segments.inject("") { |str,s| str << s.to_s })
+
+          node  = tree
+          segments.each do |seg|
+            seg = :dynamic if seg && seg[0] == ?:
+            node << [seg, [i]] if node.empty? || node[node.size - 1][0] != seg
+            node = node[node.size - 1][1]
+          end
+        end
+        tree
+      end
+
+      def generate_code(list, padding='  ', level = 0)
+        # a digit
+        return padding + "#{list[0]}\n" if list.size == 1 && !(Array === list[0])
+
+        body = padding + "(seg = segments[#{level}]; \n"
+
+        i = 0
+        was_nil = false
+        list.each do |item|
+          if Array === item
+            i += 1
+            start = (i == 1)
+            final = (i == list.size)
+            tag, sub = item
+            if tag == :dynamic
+              body += padding + "#{start ? 'if' : 'elsif'} true\n"
+              body += generate_code(sub, padding + "  ", level + 1)
+              break
+            elsif tag == nil && !was_nil
+              was_nil = true
+              body += padding + "#{start ? 'if' : 'elsif'} seg.nil?\n"
+              body += generate_code(sub, padding + "  ", level + 1)
+            else
+              body += padding + "#{start ? 'if' : 'elsif'} seg == '#{tag}'\n"
+              body += generate_code(sub, padding + "  ", level + 1)
+            end
+          end
+        end
+        body += padding + "else\n"
+        body += padding + "  #{list[0]}\n"
+        body += padding + "end)\n"
+        body
+      end
+
+      # this must be really fast
+      def to_plain_segments(str)
+        str = str.dup
+        str.sub!(/^\/+/,'')
+        str.sub!(/\/+$/,'')
+        segments = str.split(/\.[^\/]+\/+|\/+|\.[^\/]+\Z/) # cut off ".format" also
+        segments << nil
+        segments
+      end
+
+    end
+  end
+end
diff --git a/actionpack/lib/action_controller/routing/route_set.rb b/actionpack/lib/action_controller/routing/route_set.rb
index 83903aff85..30995297f3 100644
--- a/actionpack/lib/action_controller/routing/route_set.rb
+++ b/actionpack/lib/action_controller/routing/route_set.rb
@@ -208,6 +208,9 @@ module ActionController
         named_routes.clear
         @combined_regexp = nil
         @routes_by_controller = nil
+        # This will force routing/recognition_optimization.rb
+        # to refresh optimisations.
+        @compiled_recognize_optimized = nil
       end
 
       def install_helpers(destinations = [ActionController::Base, ActionView::Base], regenerate_code = false)
@@ -379,19 +382,7 @@ module ActionController
       end
 
       def recognize_path(path, environment={})
-        routes.each do |route|
-          result = route.recognize(path, environment) and return result
-        end
-
-        allows = HTTP_METHODS.select { |verb| routes.find { |r| r.recognize(path, :method => verb) } }
-
-        if environment[:method] && !HTTP_METHODS.include?(environment[:method])
-          raise NotImplemented.new(*allows)
-        elsif !allows.empty?
-          raise MethodNotAllowed.new(*allows)
-        else
-          raise RoutingError, "No route matches #{path.inspect} with #{environment.inspect}"
-        end
+        raise "Not optimized! Check that routing/recognition_optimisation overrides RouteSet#recognize_path."
       end
 
       def routes_by_controller