Perf: non-leaf navigation in deeply-nested route trees re-matches every deeper sibling branch (super-linear, parabolic in depth)

[greydragon888]

Summary

When the route tree is deeply nested, navigating to a non-deepest route makes matchRoutes try (and fail) every route branch that is deeper than the target before it reaches the matching branch. Because those deeper branches all share the target's path prefix, each one independently re-runs the path matching/normalization for that prefix. The per-navigation cost is therefore ≈ (branches deeper than the target) × (cost of matching the target's prefix) — super-linear in depth, peaking at mid-depth and dropping to ~minimal only when the target is the deepest route.

This is a consequence of the (correct) deepest-first ranking + linear branch scan, not a correctness bug. Filing as a perf observation in case prefix-aware short-circuiting is of interest.

Version

• react-router 8.0.1 (Data mode, createBrowserRouter)
• Chromium / Node 24, production build

Reproduction

A layout-per-level chain with an index leaf at every level (≈ what you get from deeply nested layout routes):

function buildLevel(k: number, MAX: number): RouteObject {
  const children: RouteObject[] = [{ index: true, Component: () => <div data-n={k} /> }];
  if (k < MAX) children.push(buildLevel(k + 1, MAX));
  return { path: `l${k}`, Component: () => <Outlet />, children };
}
const MAX = 90;
const router = createBrowserRouter([
  { path: "/", children: [{ path: "deep", Component: () => <Outlet />, children: [buildLevel(1, MAX)] }] },
]);
// then client-navigate from "/" to "/deep/l1/l2/.../lD" for various D and measure main-thread script time

Observed — main-thread script (median) of one client navigation to depth D in a 90-level tree:

target depth D	3	30	45	60	75	90
script (ms)	1.41	4.37	5.91	6.05	4.23	1.70
deeper branches (90 − D)	87	60	45	30	15	0

A clear parabola: cost rises to a peak around depth 45–60 (~4× the shallowest navigation), then declines back to the baseline at depth 90 — i.e. it is cheapest to navigate to the deepest route and most expensive to navigate to a mid-depth one. (RME ≤ 3% per point, reproducible.)

Root cause

matchRoutesImpl scans the ranked branch list linearly until the first match:

let branches = precomputedBranches ?? flattenAndRankRoutes(routes);
for (let i = 0; matches == null && i < branches.length; ++i)
  matches = matchRouteBranch(branches[i], decoded, allowPartial);

rankRouteBranches / computeScore rank branches with more (static) segments first, so the deepest branches come first. To match /deep/l1/.../lD:

1. Every branch deeper than D (l{D+1}…l90) is tried first. In matchRouteBranch, each one successfully matches the shared prefix l1…lD (running matchPathImpl + joinPaths/removeDoubleSlashes/removeTrailingSlash/normalizePathname per segment) and only then fails at the next segment — so each does ~O(D) work before returning null.
2. Only after those (maxDepth − D) failures does it reach and match the depth-D branch.

So the redundant work is (maxDepth − D) branches each re-matching the same D-segment prefix → O((maxDepth − D) × D), which is exactly the measured parabola (zero redundancy when D = maxDepth, since the deepest branch is ranked first and matches immediately).

A CPU profile (CDP Profiler, unminified build, 6 navigations) of depth 60 vs 90 confirms where the time goes:

function	self-time @ depth 60	self-time @ depth 90
removeDoubleSlashes	8.80 ms	0.24 ms
removeTrailingSlash	5.12 ms	0.00 ms
joinPaths	4.43 ms	1.12 ms
matchPathImpl	3.32 ms	0.83 ms
normalizePathname	1.05 ms	0.03 ms
matchRouteBranch	0.98 ms	0.11 ms

The path-matching/normalization cost essentially vanishes at the deepest target — consistent with "zero deeper branches to try."

Impact

• Pronounced only at deep nesting (the repro uses 90 to make it legible); most apps nest far less, where the absolute cost is small.
• But the redundant work is structural: N branches sharing a path prefix each re-match that prefix independently. It also shows up, to a lesser degree, in wide trees where many ranked branches share a prefix and a low-ranked target is reached late in the scan.

Possible directions (non-prescriptive)

• Prefix-aware short-circuit: when matchRouteBranch fails at segment i, other branches sharing segments 0…i-1 will fail at the same point — they could be skipped.
• A prefix index / segment trie over the ranked branches would match each shared prefix once instead of per-branch.

Happy to share the full benchmark harness / profile traces if useful.

---

Environment

• react-router 8.0.1 · Data mode (createBrowserRouter)
• Node 24 · Chromium (Playwright + CDP) · Apple M3 Pro · production Vite build