Optimize Router matching with prefix Trie filter by kevmoo · Pull Request #509 · dart-lang/shelf

kevmoo · 2026-03-14T19:29:25Z

This commit replaces the (N)$ linear route iteration with a fast-path Trie filter.
Instead of checking every registered route's RegExp against the incoming request,
the Router now builds a prefix tree using the literal, non-variable segments of each route.

When a request is received, the Router walks the Trie to collect only routes
that exactly match the static prefix of the request path. It then evaluates
the original RegExp match only on those isolated candidates.

This provides (L)$ routing candidate filtration for massive APIs while maintaining
100% exact backward compatibility (preserving exact regex extraction, nested routers,
and exact positional priority).

Performance Metrics (10k routes across 100 controllers):

Metric	Before (Linear)	After (Trie)	Speedup
Worst-Case Match	902.19 μs	3.20 μs	~281x Faster
404 (Not Found)	734.12 μs	0.45 μs	~1,631x Faster

Also added more specific tests to validate behavior of soon-to-come trie perf improvement

This commit replaces the (N)$ linear route iteration with a fast-path Trie filter. Instead of checking every registered route's RegExp against the incoming request, the Router now builds a prefix tree using the literal, non-variable segments of each route. When a request is received, the Router walks the Trie to collect only routes that exactly match the static prefix of the request path. It then evaluates the original RegExp match only on those isolated candidates. This provides (L)$ routing candidate filtration for massive APIs while maintaining 100% exact backward compatibility (preserving exact regex extraction, nested routers, and exact positional priority). Performance Metrics (10k routes across 100 controllers): | Metric | Before (Linear) | After (Trie) | Speedup | | :--- | :--- | :--- | :--- | | Worst-Case Match | 902.19 μs | 3.20 μs | ~281x Faster | | 404 (Not Found) | 734.12 μs | 0.45 μs | ~1,631x Faster |

gemini-code-assist · 2026-03-14T19:29:39Z

Summary of Changes

Hello, I'm Gemini Code Assist¹! I'm currently reviewing this pull request and will post my feedback shortly. In the meantime, here's a summary to help you and other reviewers quickly get up to speed!

This pull request introduces a major performance optimization to the shelf_router package by integrating a Trie data structure for route matching. Instead of exhaustively checking every registered route, the router now uses a prefix tree to quickly filter down to a small set of potential candidates based on the static segments of the request path. This change drastically reduces the time required to find matching routes, especially in large API configurations, without altering the external behavior or priority of existing routes.

Highlights

Performance Optimization: Implemented a Trie-based filter for router matching, replacing the previous linear iteration approach.
Significant Speedup: Achieved substantial performance improvements, with route matching up to 281x faster and 404 (Not Found) handling up to 1631x faster in worst-case scenarios.
Backward Compatibility: Ensured 100% exact backward compatibility, preserving existing regex extraction, nested routers, and positional priority.

Changelog

pkgs/shelf_router/lib/src/router.dart
- Imported the new trie.dart file.
- Replaced the _routes list with an instance of the new Trie class.
- Modified the call method to leverage the Trie's getCandidates method for efficient route lookup.
pkgs/shelf_router/lib/src/router_entry.dart
- Imported package:meta/meta.dart.
- Marked RouterEntry as @internal and final class.
- Added a trieIndex field and initialized it in the constructor to preserve the original registration order for sorting candidates.
pkgs/shelf_router/lib/src/trie.dart
- Added a new file defining the _TrieNode and Trie classes.
- The Trie class manages a prefix tree, allowing routes to be added (add method) and efficiently retrieved as candidates (getCandidates method) based on static path segments.

Activity

No specific activity has been recorded for this pull request yet.

Using Gemini Code Assist

The full guide for Gemini Code Assist can be found on our documentation page, here are some quick tips.

Invoking Gemini

You can request assistance from Gemini at any point by creating a comment using either /gemini <command> or @gemini-code-assist <command>. Below is a summary of the supported commands on the current page.

Feature	Command	Description
Code Review	`/gemini review`	Performs a code review for the current pull request in its current state.
Pull Request Summary	`/gemini summary`	Provides a summary of the current pull request in its current state.
Comment	@gemini-code-assist	Responds in comments when explicitly tagged, both in pull request comments and review comments.
Help	`/gemini help`	Displays a list of available commands.

Customization

To customize Gemini Code Assist for GitHub experience, repository maintainers can create a configuration file and/or provide a custom code review style guide (such as PEP-8 for Python) by creating and adding files to a .gemini/ folder in the base of the repository. Detailed instructions can be found here.

Limitations & Feedback

Gemini Code Assist may make mistakes. Please leave feedback on any instances where its feedback is incorrect or counter productive. You can react with 👍 and 👎 on @gemini-code-assist comments. If you're interested in giving your feedback about your experience with Gemini Code Assist for GitHub and other Google products, sign up here.

You can also get AI-powered code generation, chat, as well as code reviews directly in the IDE at no cost with the Gemini Code Assist IDE Extension.

Review the Privacy Notices, Generative AI Prohibited Use Policy, Terms of Service, and learn how to configure Gemini Code Assist in GitHub here. Gemini can make mistakes, so double check it and use code with caution. ↩

gemini-code-assist

Code Review

This is an excellent optimization that significantly improves routing performance by using a Trie to filter route candidates. The implementation is well-done, maintaining backward compatibility with routing priorities and behavior. The new Trie data structure is implemented cleanly and the integration into the existing Router is seamless. I have one suggestion to improve the readability and simplify the logic in the Trie.add method.

Also added more specific tests to validate behavior of soon-to-come trie perf improvement

# Conflicts: # pkgs/shelf_router/benchmark/router_benchmark.dart # pkgs/shelf_router/pubspec.yaml

jonasfj

I think this is correct.

We could do better. But this is not bad.

jonasfj · 2026-03-14T20:49:43Z

-class RouterEntry {
+@internal
+final class RouterEntry {
+  static int _nextIndex = 0;


This is a bit dangerous.. because if a RouterEntry isn't immediately added to the trie, we risk having a problem with this index and ordering.

We could consider giving trie as an argument to the constructor.. so that creating an instance also always adds it to the trie.
And then we have a natural place to put a comment that explains why this is important.

I considered moving RouterEntry to trie.dart (or maybe the other way around) and making the ctor private so the Trie always manages lifetime.

Would you prefer that? It's just code motion, mostly.

kevmoo · 2026-03-16T21:30:33Z

/gemini review

gemini-code-assist

Code Review

This pull request introduces a significant performance optimization to the routing mechanism by replacing the linear scan of routes with a Trie-based filtering approach. The implementation correctly builds a prefix tree from the static parts of the routes and uses it to quickly select a small set of candidate routes for full regex matching. This drastically improves performance, especially for applications with many routes, as demonstrated by the provided metrics. The changes maintain backward compatibility by preserving the route registration order for matching priority. The new Trie implementation is well-structured and includes new tests to validate its behavior. Overall, this is an excellent improvement.

…ter entry - Add `.github/workflows/post_summaries.yaml` and `write-comments: false` in `publish.yaml` so `Health` and `Publish` workflow summaries are posted on PRs. - Configure `license_test_string` and `license` in `.github/workflows/health.yaml` to avoid false-positive warnings on 2-space copyright headers. - Add the missing `## 1.1.5-wip` entry in `pkgs/shelf_router/CHANGELOG.md` for #509 (`Optimize Router matching with prefix Trie filter`).

…5, and shelf_static 1.2.0 (#546) * chore: add health workflow and missing shelf_static changelog entry - Add `.github/workflows/health.yaml` calling `dart-lang/ecosystem/.github/workflows/health.yaml`. - Add the missing `CHANGELOG.md` entry under `## 1.2.0-wip` in `pkgs/shelf_static/CHANGELOG.md` for #507 (`feat(static): modernize directory listing UI`). * chore: add post_summaries.yaml, license config, and missing shelf_router entry - Add `.github/workflows/post_summaries.yaml` and `write-comments: false` in `publish.yaml` so `Health` and `Publish` workflow summaries are posted on PRs. - Configure `license_test_string` and `license` in `.github/workflows/health.yaml` to avoid false-positive warnings on 2-space copyright headers. - Add the missing `## 1.1.5-wip` entry in `pkgs/shelf_router/CHANGELOG.md` for #509 (`Optimize Router matching with prefix Trie filter`). * chore: prepare shelf 1.4.3, shelf_router 1.1.5, and shelf_static 1.2.0 releases - Document `toSecondResolution` microsecond truncation in `pkgs/shelf_static/CHANGELOG.md`. - Drop `-wip` suffix from `shelf` (`1.4.3`), `shelf_router` (`1.1.5`), and `shelf_static` (`1.2.0`). * chore(shelf): rename tools/ to tool/ to satisfy pub publish validation

…erEntry (#548) shelf_router 1.1.5 marks RouterEntry @internal (#509). The generator already imports it from src/ under an implementation_imports ignore; extend that ignore so analyze stays clean against the published shelf_router.

…erEntry shelf_router 1.1.5 marks RouterEntry @internal (#509). The generator already imports it from src/ under an implementation_imports ignore; extend that ignore so analyze stays clean against the published shelf_router.

kevmoo added 2 commits March 14, 2026 12:15

shelf_router: add benchmark

5e40a6a

Also added more specific tests to validate behavior of soon-to-come trie perf improvement

github-actions Bot added the package:shelf_router label Mar 14, 2026

kevmoo mentioned this pull request Mar 14, 2026

Enhance routing engine #504

Closed

4 tasks done

gemini-code-assist Bot reviewed Mar 14, 2026

View reviewed changes

Comment thread pkgs/shelf_router/lib/src/trie.dart Resolved

shelf_router: add benchmark

7aafc25

Also added more specific tests to validate behavior of soon-to-come trie perf improvement

kevmoo force-pushed the bench branch from 5e40a6a to 7aafc25 Compare March 14, 2026 19:32

kevmoo added 3 commits March 14, 2026 12:37

pr review

3cdc904

Merge branch 'bench' into better_router

10e0061

# Conflicts: # pkgs/shelf_router/benchmark/router_benchmark.dart # pkgs/shelf_router/pubspec.yaml

Address review feedback

26f0678

Base automatically changed from bench to master March 14, 2026 20:40

Merge remote-tracking branch 'origin/HEAD' into better_router

9549157

kevmoo requested a review from jonasfj March 14, 2026 20:57

jonasfj approved these changes Mar 14, 2026

View reviewed changes

kevmoo added 2 commits March 14, 2026 15:05

Merge remote-tracking branch 'origin/HEAD' into better_router

16fc85a

review bits

c0a8fdc

gemini-code-assist Bot reviewed Mar 16, 2026

View reviewed changes

kevmoo merged commit 4d99e49 into master Mar 16, 2026
28 checks passed

kevmoo deleted the better_router branch March 16, 2026 21:35

kevmoo mentioned this pull request Oct 11, 2026

chore: add health workflow and prepare shelf 1.4.3, shelf_router 1.1.5, and shelf_static 1.2.0 #546

Merged

kevmoo mentioned this pull request Oct 22, 2026

shelf_router_generator: fix analyze against shelf_router 1.1.5 #548

Merged

Navigation Menu

Repository navigation

Optimize Router matching with prefix Trie filter - #509

Optimize Router matching with prefix Trie filter#509
kevmoo merged 9 commits into
masterfrom
better_router

kevmoo commented Mar 14, 2026

Uh oh!

gemini-code-assist Bot commented Mar 14, 2026

Uh oh!

gemini-code-assist Bot left a comment

Uh oh!

Uh oh!

jonasfj left a comment

Uh oh!

jonasfj Mar 14, 2026

Uh oh!

kevmoo Mar 14, 2026

Uh oh!

kevmoo commented Mar 16, 2026

Uh oh!

gemini-code-assist Bot left a comment

Uh oh!

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Conversation

kevmoo commented Mar 14, 2026

Uh oh!

gemini-code-assist Bot commented Mar 14, 2026

Summary of Changes

Highlights

Footnotes

Uh oh!

gemini-code-assist Bot left a comment

Choose a reason for hiding this comment

Code Review

Uh oh!

Uh oh!

jonasfj left a comment

Choose a reason for hiding this comment

Uh oh!

jonasfj Mar 14, 2026

Choose a reason for hiding this comment

Uh oh!

kevmoo Mar 14, 2026

Choose a reason for hiding this comment

Uh oh!

kevmoo commented Mar 16, 2026

Uh oh!

gemini-code-assist Bot left a comment

Choose a reason for hiding this comment

Code Review

Uh oh!

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants