ActionController::Routing::RouteSet

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!