aspnet/Mvc — pull request #848 by rynowak (2014-07-23 19:45:41+00:00)
Title: Optimize action selection 

Here's a PR for discussion of the general pattern.

We're still figuring out the best way to measure this because:
- We need to consider working set
- Our current perf test is too small to show any real delta
- We'd like to create (and run in the lab) a focused benchmark for this code

The idea is that we generate a tree of dictionaries, and make decisions at each node which patch to take based on a key-value-pair in route data. The ordering of decisions is based on the branchiest-first, and the tree is then reduced - you won't find any AD in two places in the tree.

We need to walk the entire tree to deal with the possibility of partial matches (which is supported by our action selection system). That's a case like:

```
Action1 = { controller = "Home", action = "Index" }
Action2 = { controller = "Home", action = "Index", foo = "bar" }

Values = { controller = "Home", action = "Index" }
```

In this case both of these match.

So while average time is closer to log-k(n), you can build parasitic cases that will be closer to log(n) where n is the number of nodes in the decision tree (sum of all values for all constraints).