O(pages * visible links) performance in prefetch code.

[phulin]

Description

When loading a page with a large number of visible links on a site with a large number of pages, gatsby checks every page against every link on the page when finding the @reach/router routes to prefetch.

I'm building a site to navigate a large, highly-connected dataset which preferably should have large numbers of cross-references. My current deployment—on only a partial dataset—has 9,000 pages, several of which have 500 or more links on them. If a user scrolls quickly down the page, the prefetching code can easily trigger to find routes for several hundred of the links, causing comparison of each link with each potential route. This can cause a UI freeze for 2-3 seconds on my laptop (or more on slower machines).

Inside @reach/router, each comparison triggers several instances of the path-normalization code, which executes a regex to trim leading/trailing slashes and splits the path on slashes. In Chrome, the vast majority of the UI freeze (80%+) is spent inside this normalization function

As far as a solution, I'm happy to write a PR when I get a chance, but I'd like to confirm the right approach first. As far as I can tell, gatsby should never use the wildcard features of @reach/router, meaning we should be able to just use a big map like the existing cache to get to O(log(pages) * links) asymptotic performance. But I may have missed some complication here.

Steps to reproduce

Example page where the problem occurs: https://uscode.io/title-26/

Environment

System:
OS: macOS High Sierra 10.13.6
CPU: (4) x64 Intel(R) Core(TM) i7-4558U CPU @ 2.80GHz
Shell: 3.2.57 - /bin/bash
Binaries:
Node: 11.10.0 - /usr/local/bin/node
npm: 6.9.0 - /usr/local/bin/npm
Languages:
Python: 2.7.16 - /usr/local/bin/python
Browsers:
Chrome: 74.0.3729.131
Firefox: 52.0.2
Safari: 12.1
npmPackages:
gatsby: ^2.4.3 => 2.4.3
gatsby-image: ^2.0.41 => 2.0.41
gatsby-plugin-emotion: ^4.0.6 => 4.0.6
gatsby-plugin-manifest: ^2.1.1 => 2.1.1
gatsby-plugin-netlify: ^2.0.16 => 2.0.16
gatsby-plugin-offline: ^2.1.0 => 2.1.0
gatsby-plugin-react-helmet: ^3.0.12 => 3.0.12
gatsby-plugin-robots-txt: ^1.4.0 => 1.4.0
gatsby-plugin-sharp: ^2.0.37 => 2.0.37
gatsby-plugin-sitemap: ^2.1.0 => 2.1.0
gatsby-source-filesystem: ^2.0.33 => 2.0.33
gatsby-transformer-sharp: ^2.1.19 => 2.1.19
npmGlobalPackages:
gatsby-cli: 2.5.13

[phulin]

After more research I realize that client-side pages mean that gatsby does use wildcard routes with reach/router, and so a big map won't work. Maybe this change would need to be pushed into router somehow, but since gatsby doesn't appear to tell reach/router about non-prefetched pages, I'm not sure how this would work.

[me4502]

A colleague and I looked into this, and we proposed (and implemented on a branch) using a Trie to solve this issue.

This has been put on the backburner as @Moocar is currently making major changes to greatly improve how this currently works.

[me4502]

Relevant PRs:

Moocar's changes: #13004
The trie: #12711

Either can be applied as a patch for a temporary solution. We've been running the Trie change as a patch with patch-package for months now.

[phulin]

@me4502, great, thanks so much! I'll keep track of Moocar's PR and run the trie version for now.