mje113/newark — pull request #5 by jackxxu (2014-08-27 15:13:15+00:00)
Title: use multiplex regex to implement routing

# multiplexing newark routing

The objectives of this PR are to make routing in Newark framework flexible and fast.

## the advantages
1. use multiplex routes (combining all the route regex to create a jumbo regex) and match one time instead of match individually. the following benchmark shows that in that particular example, routing times drops to almost 10% of the current approach (of course, your milage may vary). see below for benchmark results.

2. more readable routes: currently, in order to to match something like `/people/1.xml` and enforce the xml extension, we will need to use a nerdy regex like `get \/people\/(?\S*).xml$/ {...}`. this change allows a much readable syntax such as `get '/people/:id.xml/ {...}`. It even allows syntax like `get '/people/:id.:format/ {...}` (see the 2 new tests `test/test_router.rb`)

N.B. the code can obviously be refactored, but I'd leave it for a future update.

## Survey of routing algorithm in ruby web frameworks

many approaches are used in

1. our current approach that loop through all route's regex and match. some of the gems that use it include:
* journey gem (https://github.com/rails/journey), and thus Rails.
* sinatra gem (https://github.com/sinatra/sinatra)

the disadvantage of this approach is its O(n) complexity, especially a large amount of routes are matched.

2. multiplexing approach. this approach takes advantage of the ruby regular expression's `union` and `named capture` functionality to create a multiplex route and match only once. It additionally benefits from the better performance of `===` over `match` method. it has O(1) complexity.
* rack-multiplexer gem (https://github.com/r7kamura/rack-multiplexer)

## Benchmark results
with mri ruby 2.1.1, on MacPro,
```
iterations = 100000

Benchmark.bmbm do |x|
x.report('linear approach') do
iterations.times do
request_paths.each do |path|
routes_regex.find {|regex| regex.match(path) }
end
end
end

x.report('multiplex approach') do
iterations.times do
request_paths.each do |path|
jregex === path
end
end
end
end

__END__

Rehearsal ------------------------------------------------------
linear approach 10.410000 0.010000 10.420000 ( 10.418204)
multiplex approach 1.480000 0.000000 1.480000 ( 1.479806)
-------------------------------------------- total: 11.900000sec

user system total real
linear approach 10.290000 0.010000 10.300000 ( 10.303956)
multiplex approach 1.500000 0.000000 1.500000 ( 1.497642)
``