Native support for http method matching

[pi0]

Context: unjs/h3#461

I had been trying to implement a generic filter option for lookup but it adds too much overhead. If tree structure has a build-in method checker support, it could be much faster.

Acceptance criteria:

• lookup method to support an additional method option lookup(path, { method? }?
• addRoute to support an additional options object to set method criteria
• Introduce a new special tree node for route matcher and test it as "last step"
• For static fast-path, we need a method => Map<string, string> structure. other ideas welcome but it should be O(n + 1) maximum where as n is number of available methods and not affect performance when no method is specified

[aquapi]

https://github.com/aquapi/wint
@pi0 I make a faster router than Radix3 and it does support method matching.

Basically Radix3 is slower than @medley/router in dynamic path matching
(it is only faster when your pattern looks like /user/:id/sth - without any other url parameters and subpath).

Normally what you do to make routing fast is that you separate static routes and route patterns like URL parameters and wildcards.

For static path just use an object literal and for the dynamic path you can use @medley/router.

My approach is a bit different since I took the tree structure that @medley/router creates
and compile it all into a function ahead of time, so we can basically remove the recursive overhead and the JIT is able to optimize even more because I have more opportunities to inline things like string checking (This part is really complicated I cannot even explain to anyone).

Radix3 basically slices the URL into parts when matching URLs, and not all of the time all of the parts are needed to be checked because the previous parts do not match.

Also my router does support method matching but it is designed a bit different to reduce creating objects as much as possible.

But if you want to stick with Radix3 you can make an object literal with key is the method name and the value is the radix tree you want to match the URL.

[pi0]

Hi, dear @aquapi thanks for sharing your feedback and nice work on wint!

As a quick context, honestly I never put extra efforts into fine-tuning radix3 perf to compete with other routes (there were not many by the time too!) it was based on another work and really fast enough (25M+ matches in sec) that I guess really is not the performance bottleneck in any of real world scenarios user logic always will be main...

Saying all this, i am not against pushing performance even more on radix3 too and i guess there are improvements.

But if you want to stick with Radix3 you can make an object literal with key is the method name and the value is the radix tree you want to match the URL.

Thanks for this insight. I will certainly check in the benchmarks for cost of adding a new tree per method vs method as last segment matcher.

it is only faster when your pattern looks like /user/:id/sth - without any other url parameters and subpath)

Can you please elaborate more what do you mean by other URL parameters? Also have you made a benchmark suite by any chance? (would be happy to make one in radix3 ++ having you as collaborator here always!)

[aquapi]

@pi0 I will create a benchmark repo soon for Radix3 (H3), Memoirist (Elysia), Wint (Stric) and find-my-way (Fastify).
I don't add RegExpRouter (Hono) because it doesn't handle custom methods by default (it throws).

[aquapi]

@pi0 https://github.com/aquapi/routers
Here's the prototype.
I simply read from directories and feed all of the stuff to mitata and run it.

Seems like Radix3 is faster for path that has a lot of parameters because .split() is much faster than doing a lot of .substring() like what other routers do.

I can make a compiler for this matching strategy.

[aquapi]

Rebenchmark the whole thing again and Wint was faster in all tests.
I changed the Bun runtime flags so it optimizes the code as soon as possible.

BUN_JSC_jitPolicyScale=0.0 BUN_JSC_thresholdForOptimizeSoon=0 BUN_JSC_thresholdForJITSoon=0

[pi0]

Native route matching added in #107