rails/rails — pull request #14555 by stevegraham (2014-04-01 16:49:06+00:00)
Title: A new trie based router

**Warning! This is a massive change. Opening a PR to bring this work to wider attention and open discussion, not necessarily to propose a merge at this point in time**

### A new router for Rails

**TL;DR I propose a new router for Rails that is drastically smaller in size while retaining full compatibility with the existing routing API**

#### Why?

Recently I had a need to add some functionality to the Rails router. Unfortunately I had great difficulty in understanding how Journey worked. All of Journey is :nodoc: and the author was unresponsive to basic questions such as would the API be stable for the foreseeable future, i.e. is it safe to write code that extends the router and not have it break when a new version of Rails is released.

Not being able to get basic questions answered, the difficulty in understanding it, and lack of documentation led me to consider writing a compatible router with less code. My reasoning was if it was simpler it would weigh in as less code making it:

- Easier to maintain
- More welcoming to others wanting to contribute to Rails maintenance and development
- (Hopefully) have significantly improved performance characteristics, although definitely not worse performance.

Journey has been in Rails since 3.2, and that doesn't appear to have been touched more than superficially since then suggests it is daunting to approach for the uninitiated. Especially when I was able to remove circa 2150 loc with a first stab at an alternative router.

#### How it works

As I thought about an appropriate data structure I decided a trie would be a natural fit and it has O(log n) runtime and space characteristics. Instead if tokenising on each character as one might normally do with a trie, I thought tokenising on each path segment would be clearer, e.g. when one is in the debugger and inspecting the routing tree.

Consider the following canonical path pattern `/:controller(/:action(/:id))(.:format)` The new router will tokenise at the segment boundaries and annotate each segment with if it is optional or not. e.g. `:controller` is required and the remaining are not. The trie will then find or instantiate a node for `:controller`, look for a child node for `:action` or initialise one and append to the collection. This will be repeated until the path is exhausted.

Each node in the trie can point to a route object. Any route object can pointed at by multiple nodes. This is because a route object can be reachable by more than one path e.g. in the above example when optional segments are not present, or in the case of separate matching path, e.g a glob route.

#### Results

2150 LOC removed from Rails
Full compatibility with existing API. Tests are green.
ActionPack test suite execution time from ~35 seconds to ~29 seconds on my machine.

#### Benchmarks

I prepared the following benchmark and ran it against master and my branch. It takes 336 distinct paths and creates GET routes for them mapped to a simple Rack app. The router is asked to match each route 1000 times. This process is then repeated 5 times and an average time is taken.

```ruby
require 'bundler/setup'

Bundler.setup

require 'benchmark'
require './lib/action_dispatch'

# puts 'LOL'

arr = ["foo", "bar", "baz", "qux", "quux", "corge", "grault", "garply"]
paths = arr.permutation(3).map { |a| "/#{a.join '/'}" }
set = ActionDispatch::Routing::RouteSet.new(ActionDispatch::TestRequest)

class HelloWorld
def initialize(response)
@response = response
end

def call(env)
[ 200, { 'Content-Type' => 'text/plain' }, [@response] ]
end
end

set.draw do
paths.each do |path|
get path, to: HelloWorld.new(path)
end
end

times = 5.times.map do |i|
Benchmark.measure {
1000.times do |i|
paths.each do |path|
request = ActionDispatch::TestRequest.new
request.path = paths.first

set.call request.env
end
end
}
end

puts times.reduce(0) { |memo, obj| memo + obj.real } / 5

```

- My branch = 39.96 seconds
- Rails master = 32.61 seconds

As you can see, so far my router is faster. Anyway the point is, it is not slower AND it amounts to significantly less lines of code. So I would like to kick off a serious discussion about replacing the existing router with this one. Maybe I can start by making it into a Rails plugin?

Cheers

S