ruby uriclassifier in place. 3x slower on MRI vs TST; 1.5x slower on JRuby vs same. surprisingly, for any realistic number of URIs the slowdown is basically linear

git-svn-id: svn+ssh://rubyforge.org/var/svn/mongrel/trunk@726 19e92222-5c0b-0410-8929-a290d50e31e9

2 files changed, 58 insertions, 45 deletions

diff --git a/lib/mongrel.rb b/lib/mongrel.rb
index edee39e..d4e0f56 100644
--- a/lib/mongrel.rb
+++ b/lib/mongrel.rb
@@ -4,7 +4,6 @@
 # Additional work donated by contributors.  See http://mongrel.rubyforge.org/attributions.html 
 # for more information.
 
-require 'rubygems'
 require 'socket'
 require 'http11'
 require 'tempfile'
@@ -18,10 +17,7 @@ ensure
   require 'thread'
 end
 
-begin
-  require 'cgi_multipart_eof_fix'
-rescue LoadError
-end
+require 'cgi_multipart_eof_fix'
 
 require 'stringio'
 require 'mongrel/cgi'
@@ -56,9 +52,11 @@ module Mongrel
 
     def initialize
       @routes = {}
-      @matcher = nil
+      @matcher = //
     end
     
+    # Register a handler object at a particular URI. The handler can be whatever 
+    # you want, including an array. It's up to you what to do with it.
     def register(uri, handler)
       raise RegistrationError, "#{uri.inspect} is already registered" if @routes[uri]
       raise RegistrationError, "URI is empty" if !uri or uri.empty?
@@ -67,6 +65,7 @@ module Mongrel
       rebuild
     end
     
+    # Unregister a particular URI and its handler.
     def unregister(uri)
       handler = @routes.delete(uri)
       raise RegistrationError, "#{uri.inspect} was not registered" unless handler
@@ -74,14 +73,15 @@ module Mongrel
       handler
     end
     
-    def resolve(request_uri)
-      raise UsageError, "No routes have been registered" unless @matcher
-      match = request_uri[@matcher, 0]
-      if match
-        path_info = request_uri[match.size..-1]
+    # Resolve a request URI by finding the best partial match in the registered 
+    # handler URIs.
+    def resolve(request_uri)      
+      if match = @matcher.match(request_uri)
+        uri = match.to_s
+        path_info = match.post_match
         # A root mounted ("/") handler must resolve such that path info matches the original URI.
-        path_info = "#{Const::SLASH}#{path_info}" if match == Const::SLASH
-        [match, path_info, @routes[match]]
+        path_info = "#{Const::SLASH}#{path_info}" if uri == Const::SLASH
+        [uri, path_info, @routes[uri]]
       else
         [nil, nil, nil]
       end
@@ -92,14 +92,10 @@ module Mongrel
     private
     
     def rebuild
-      routes = @routes.sort_by do |uri, handler|        
-        # Sort by name
-        uri
-      end.sort_by do |uri, handler|          
-        # Then by descending length
-        -uri.length 
+      routes = @routes.keys.sort.sort_by do |uri|
+        -uri.length
       end
-      @matcher = Regexp.new(routes.map do |uri, handler|
+      @matcher = Regexp.new(routes.map do |uri|
         Regexp.new('^' + Regexp.escape(uri))
       end.join('|'))
     end    
diff --git a/test/test_uriclassifier.rb b/test/test_uriclassifier.rb
index 973309a..d2099f8 100644
--- a/test/test_uriclassifier.rb
+++ b/test/test_uriclassifier.rb
@@ -185,37 +185,54 @@ class URIClassifierTest < Test::Unit::TestCase
     end
   end
   
-  def test_benchmark  
-    @fragments = %w(the benchmark module provides methods to measure and report the time used to execute ruby code)
-
-    @classifier = URIClassifier.new
-    @classifier.register("/", 1)
-
-    @requests = []
+  def xtest_benchmark    
+    # This benchmark should favor a TST, but it seems to be mostly irrelevant
+  
+    @uris = %w(
+      / 
+      /dag /dig /digbark /dog /dogbark /dog/bark /dug /dugbarking /puppy 
+      /c /cat /cat/tree /cat/tree/mulberry /cats /cot /cot/tree/mulberry /kitty /kittycat
+    )
     
-    @fragments.size.times do |n|
-      this_uri = "/" + @fragments[0..n].join("/")
-      @classifier.register(this_uri, 1)
-      @requests << this_uri
+    @requests = %w(
+      /
+      /dig
+      /digging
+      /dogging
+      /dogbarking/
+      /puppy/barking
+      /c
+      /cat
+      /cat/shrub
+      /cat/tree
+      /cat/tree/maple
+      /cat/tree/mulberry/tree
+      /cat/tree/oak
+      /cats/
+      /cats/tree
+      /cod
+      /zebra
+    )
+  
+    @classifier = URIClassifier.new
+    @uris.each do |uri|
+      @classifier.register(uri, 1)
     end
-    
-    @requests = @requests.map do |path|
-      (0..100).map do |n|      
-        path.size > n ? path[0..-n] : path
-      end
-    end.flatten * 10
-    
-    puts "#{@fragments.size} paths registered"
-    puts "#{@requests.size} requests queued"
-    
+
     Benchmark.bm do |x|
       x.report do
-        @requests.each do |request|
-          @classifier.resolve(request)
-        end
+#        require 'ruby-prof'
+#        profile = RubyProf.profile do
+          10000.times do
+            @requests.each do |request|
+              @classifier.resolve(request)
+            end
+          end
+#        end
+#        File.open("profile.html", 'w') { |file| RubyProf::GraphHtmlPrinter.new(profile).print(file, 0) }
       end
     end
-    
+        
   end
   
 end