Using radix tree or dict for storing routes instead of list

[acidbotmaker]

I was reviewing the httprouter documentation and noticed it uses a radix tree to store routes instead of a list, aiming for quicker route fetching.

From my understanding, Starlette's current approach involves the Router class iterating through all route objects to match the given path and parameters. If a match (partial or full) is found, the loop stops, and the corresponding endpoint is called. This approach results in a worst-case time complexity of O(N), where N is the number of routes.

To experiment, I created a quick-and-dirty patch where routes are stored in a dictionary (routes_hash[path] -> route_obj). I tested this with 10,000 routes but didn’t observe a significant improvement in speed. My reasoning is that if a dictionary-based approach doesn’t yield noticeable speedups, using a radix tree likely wouldn’t either.

Would switching to a radix tree (or another data structure) make a meaningful difference in performance, or am I overthinking the potential benefits here?

PS: I found this previous discussion but since author wasn't clear I decided to create new one.

[nggit]

Just curious, do you need more than 1k or at least ever create 100 url paths in a single deployment?
Let's say even if the routing is poorly written, it's still unlikely to be a major performance issue.

Of course using dict stuff can be better, but it depends on how it is implemented, whether it will add complexity to the point that it is not worth doing.

No offense, but fast routing and such sounds like a gimmick to me.
But let's wait to see what Starlette developers say.

[acidbotmaker]

I have yet to see a project with 1000+ paths but I have seen projects with nested paths (100+) and looping through all with regex matching for query seems so inefficient.

[nggit]

So you meant using radix tree can avoid using regex. In my previous post I focused on dict vs list because you mentioned about O(n). And n < 1000 is nothing to worry about.

But still, if you replace regex with complex logic, you won't get the expected improvement.

[acidbotmaker]

Yeah, let's see what others think on this.

[adriangb]

Maybe try https://github.com/adriangb/asgi-routing?

[acidbotmaker]

Thanks, I just saw your message. I will take a look into it with some dummy project.