Improve the performance of routing

[rynowak]

There's a number of known areas for performance improvement in Routing. It's also one of the few places in ASP.NET where the performance impact of the system scales up pretty dramatically for some users as they add more routes.

Some known issues/places for investigation:

Remove use of string.Split in routing

Routing does a string.split and the request path here: https://github.com/aspnet/Routing/blob/dev/src/Microsoft.AspNet.Routing/Template/TemplateMatcher.cs#L46

This happens for every route on every request. This is a known hotspot in all versions of routing, that starts to become a noticeable contributor to overall performance with about 20-30 routes. This could be replaced by using operations on string that take a start-index.

This is fixed now: 371d4e6

Optimize allocations in routing

In addition to the above - there's a number of allocations of data structures used in routing. Generally we're processing at most 3-4 parameters so most of these could be simplified (KeyValuePair<string, object>[] instead of dictionary, etc.

Optimize allocations in RouteData

We allocate a new RouteData and make a defensive copy of all of its data structures for each 'link' in routing. Generally there are 4 of these:

RouterMiddleware -> RouteCollection -> TemplateRoute -> MvcRouteHandler

The only one of these really doing any work here is TemplateRoute, but we'll allocate 8 dictionaries and 4 lists per request to support the contract of RouteData. We could consider making these copy -on-write, or changing the contract to allow more optimizations.

Optimize the design of attribute routing

Currently attribute routing is implemented as a list of individual routes that run in a fixed order. This isn't a good algorithm for how routing is used.

We should try to merge route entries into a tree, and process a segment at a time. This would have the most impact of all of these changes, and provide a serious performance advantage for using attribute routing.

[rynowak]

Update: removed use of string.Split 371d4e6

[rynowak]

I'd done some prototyping here, and handing this off to @ajaybhargavb to build the real deal 👍

[ajaybhargavb]

aspnet/Mvc@b8b222b
cef221f