4 ms·
I unreasonably avoid frameworks that have O(n) routing. For some reason I just feel like the standard should be O(1) with the number of routes. There is a crate
by kevincox 6y ago
I unreasonably avoid frameworks that have O(n) routing. For some reason I just feel like the standard should be O(1) with the number of routes. There is a crate https://github.com/http-rs/route-recognizer https://github.com/http-rs/route-recognizer which does this but most frameworks roll their own which just loops over the registered routes and takes the first one.
It can be slightly less flexible, however in most cases if you are using this sort of flexibility your URL structure is too confusing anyways. Since you can group together an number of regular expressions and match them in O(n) with the length of the URL you clearly have a lot of flexibility available.
Of course I should probably check the real benchmarks because the NFA based approach almost certainly has more overhead.
- mwkaufma 6y agoIs the route count unbounded? O(n) = O(1) for constant-bounded n.
- kevincox 6y agoYes, this is why my discomfort is "unreasonable". However I feel bad knowing that every route I add is slowing down my app. And I have the impulse to sort my routes by popularity to improve performance. I wish I could just trust the framework to match "as fast as possible".
- staticassertion 6y agoIf it makes you feel better, it's honestly probably faster for a certain number of routes or fewer.
- skohan 6y agoHow many routes do you have? I feel like you would have to run a huge amount of endpoints for this to be an issue
- dochtman 6y agoOne of these days I'll write documentation for the toolkit I've been working on, which has a nice solution that satisfies this criterion.
- bikeshaving 6y agoThe benefit of doing “O(n) routing” is that you don’t have to do complicated things so that a certain route gets more precedence. Real websites often have legacy URLs or one-off URLs for marketing, and being able to give these routes higher precedence by placing them higher in the route list is just easier. It’s also easier to reason about the router testing each route in sequence rather than attempting to understand how it assigned priority based on some leaky heuristics. > if you are using this sort of flexibility your URL structure is too confusing anyways A lot of the time, we don’t have a say in URL structure, unless we’re happy to break old URLs all the time. Also, can we not use Big-O notation for quantities which never break 10,000, let alone 1,000. The cost of checking all the routes in order is going to be negligible.