[GH-ISSUE #444] perf: replace O(n) linear route matching with radix trie #100

New issue

Closed

opened 2026-05-06 12:37:13 +02:00 by BreizhHardware · 0 comments

BreizhHardware commented

2026-05-06 12:37:13 +02:00

Owner

Originally created by @Divkix on GitHub (Mar 11, 2026).
Original GitHub issue: https://github.com/cloudflare/vinext/issues/444

Problem

Every incoming request triggers 3-6 linear scans over the full route list, calling matchPattern(urlParts, route.patternParts) for every route until a match. For apps with 500 routes this means 1,500-3,000 pattern comparisons per request.

The matching logic is duplicated in 4 codebases:

pages-router.ts (scanner module, dev time)
app-router.ts (scanner module, dev time)
app-rsc-entry.ts (generated entry, runtime)
pages-server-entry.ts (generated entry, runtime)

Solution

Replace the linear scan with a radix trie that provides O(depth) lookup instead of O(n). The trie enforces correct precedence via traversal order at each node (static > dynamic > catch-all > optional catch-all) with recursive DFS backtracking for dead-end branches.

Implementation

PR: #442

Originally created by @Divkix on GitHub (Mar 11, 2026). Original GitHub issue: https://github.com/cloudflare/vinext/issues/444 ## Problem Every incoming request triggers 3-6 linear scans over the full route list, calling `matchPattern(urlParts, route.patternParts)` for every route until a match. For apps with 500 routes this means 1,500-3,000 pattern comparisons per request. The matching logic is duplicated in 4 codebases: - `pages-router.ts` (scanner module, dev time) - `app-router.ts` (scanner module, dev time) - `app-rsc-entry.ts` (generated entry, runtime) - `pages-server-entry.ts` (generated entry, runtime) ## Solution Replace the linear scan with a radix trie that provides O(depth) lookup instead of O(n). The trie enforces correct precedence via traversal order at each node (static > dynamic > catch-all > optional catch-all) with recursive DFS backtracking for dead-end branches. ## Implementation - PR: #442