Using radix tree or dict for storing routes instead of list #2835
Replies: 2 comments 4 replies
-
|
Just curious, do you need more than 1k or at least ever create 100 url paths in a single deployment? Of course using No offense, but fast routing and such sounds like a gimmick to me. |
Beta Was this translation helpful? Give feedback.
-
|
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. |
Beta Was this translation helpful? Give feedback.
-
|
So you meant using radix tree can avoid using regex. In my previous post I focused on But still, if you replace regex with complex logic, you won't get the expected improvement. |
Beta Was this translation helpful? Give feedback.
-
|
Yeah, let's see what others think on this. |
Beta Was this translation helpful? Give feedback.
-
|
Maybe try https://github.com/adriangb/asgi-routing? |
Beta Was this translation helpful? Give feedback.
-
|
Thanks, I just saw your message. I will take a look into it with some dummy project. |
Beta Was this translation helpful? Give feedback.
-
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.
Beta Was this translation helpful? Give feedback.
All reactions