Performance regression on route matching for sites with 20+ routes

[KyleAMathews]

I'm working on upgrading my blog to the latest version of Gatsby which also means an upgrade under the hood from React-Router 0.13 to 2.0.

I noticed that upon doing so, clicking on some links on the front page has became very slow. As in 1.2 seconds as shown in this performance audit.

Looking at the bottom up chart. Almost all the time is spent in the matchPattern function.

My blog has roughly ~100 routes. Clicking around, some routes load near instantly and other take longer. When I added some console.logs, it turns out the matchPattern function is called for every route until there's a match. So if the route is near the top of the routes list, it's matched very quickly but if near the bottom, not so quickly. Surrounding the function with console.time, the function takes ~15ms of time each time it's called on my Macbook Pro ~2015 machine in Chrome.

Given 15ms execution per route, even with as little as 7 routes, users can start seeing delays of over 100ms which according to Google's RAIL Performance Model is the point at which users start noticing system delays.

Version

2.0.2

Steps to reproduce

1. Install Gatsby npm install -g gatsby
2. Run my blog locally — gatsby new perf-blog-test https://github.com/kyleamathews/blog; cd perf-blog; gatsby develop
3. Open localhost:8000 and compare latency clicking on different posts.
4. Compare this with http://bricolage.io which is still running react-router 0.13 where all path matching feels instant.

Expected Behavior

Path matching takes less than 100ms

Actual Behavior

Path matching can take longer than 1000ms.

[timdorr]

Can you spit out the route config? That would be helpful to see. I know Gatsby auto-generates it, so it may be creating something that's non-optimal. Not that we wouldn't want to make that config performant, but it would be helpful to attack from both sides.

[KyleAMathews]

Is there an easy way to print out the route config? Here's a screenshot of the routes object:

This is where the main bit where pages are added to the react-router config https://github.com/gatsbyjs/gatsby/blob/master/lib/isomorphic/create-routes.js#L152-L159

[taion]

I took a quick look. There's something wrong with our generated regexps. I don't see this problem against the experimental path-to-regexp branch: https://github.com/reactjs/react-router/tree/path-to-regexp.

[taion]

@KyleAMathews Can you run your test real quick against the path-to-regexp branch and let me know what the results look like?

[KyleAMathews]

Woah, the path-regexp branch drops execution time another order of magnitude. Now takes roughly ~10ms.

[KyleAMathews]

To put some UX meat on these raw execution time bones. Assuming a max route matching time of 1 second (at which point users start to lose focus on what they're doing) this is the maximum number of routes possible:

2.0.1: ~100
#3217: ~1300
path-to-regexp: ~9800

[taion]

FWIW, I'd suggest using a different strategy for your use case – something like a single route with a path like :slug and resolving the slug in getComponent (and, until we resolve #3098, returning the "not found" component from the getComponent function if the slug doesn't match).

#3217 is probably the right way to go, though using path-to-regexp is still up in the air, but properly supporting scalable routing for something like your case with a big basket of static routes would require special-casing child routes with fixed paths.

We can do this, but it'll be a bit farther away. Hmm, or maybe not.

[taion]

To elaborate on the above, the idea would be to special-case child routes that don't define any params, as those can be resolved with a simple hashmap lookup. For example, this is the logic in routington that handles this special case when matching: https://github.com/pillarjs/routington/blob/1.0.3/lib/match.js#L36-L47

cc @jonathanong, whose name has popped up on this issue tracker before, for any further thoughts here.

[KyleAMathews]

Great idea @taion! Gatsby is a special case for sure and since all routes are known ahead of time, it'd be easy + lightning fast to drop all our routes into an object and "match" using that. I'll try this in the next few days and report back.

[timdorr]

@taion I was thinking the same thing. Even better, you can short circuit all of the regex and just use some indexOf's to do it. Should be really fast for @KyleAMathews's case, since the routes are entirely static and simple.

[taion]

Better than indexOf – you just throw all the routes with static paths onto an object and just index into the object directly, so it'd be O(1) in the number of child routes.

We could actually do this right now, but I'd rather we not build further specific dependencies on our idiosyncratic pattern matching logic, given that we're still considering moving to path-to-regexp.

[jonathanong]

@taion not sure what input I can provide other than the hash map. I wouldn't use path to regexp for react router because it doesn't store routes as a tree (express and friends generally store routes as a simple list), which are how react routes are declared. Seems harder to integrate path to regexp than it is to make your own tree router with path to regexp semantics.

If you or anyone want to help maintain routington I can add you as a collaborator. The semantics are pretty similar to path to regexp. I don't even use it because trie routers are more difficult to code with when you take into account http methods, but it makes sense to me for react router.

[taion]

@jonathanong

We actually already have all the tree routing set up, and it is effectively a trie-based router. The route matching needs to be custom because we support lazily loading parts of the route tree from code-splitted chunks.

I was thinking about path-to-regexp in the context of replacing our existing code for generating those regexp semantics. It's similar enough that we can use it as a drop-in replacement for the function we currently use, though the feature set is slightly different.

In other words, use path-to-regexp purely for building the regexps for each node in the trie.

[ryanflorence]

Why'd we close this? Seems like a problem.

[taion]

#3217 mostly fixed the regression. There's further room for improvement/optimization, but this issue per se is now resolved.