URL routing is O(m * n)

[chergert]

Not really a bug, just wanted to drop a note of some alternate dispatching possibilities. It's usually the first code I look at when perusing frameworks.

You might look at https://github.com/chergert/postal/blob/master/src/cut-n-paste/url-router.c for an example of alternate, faster url dispatching. And some usage examples: https://github.com/chergert/postal/blob/master/src/postal/postal-http.c#L1125

It is, however, tied to libsoup.

Cheers

[arteymix]

It's even O(n^2) when next is involved: https://github.com/valum-framework/valum/blob/master/src/valum-router.vala#L289, but that can easily be changed.

I know that routing strategy, it's based on a Trie-like data structure.

The complexity is inherent from using callbacks to match requests. It might be a good thing to make a compromise though. I'm am refactoring the Route code and better encapsulation (within Router) of how rule and regex are processed should make this possible.

Also, for relatively small application, the time spent on matching the Request object is negligible, so I'm not much concerned about this issue.

On the other hand, it's possible to reduce the complexity by building a tree of Router using subrouting.

var users = new Router ();

users.get ("users/me", (req, res) => {});

app.all ("users/<any:path>", users.handle);

The first thing I did was to untie the code so that it can support various backend.

EDIT: Just saying, thanks for the feedback!

[chergert]

I have a glib-based Trie if you need that as well. https://github.com/chergert/gnome-builder/blob/master/contrib/search/trie.h Cacheline optimized too.

[arteymix]

I doubt I can simply include GPL code, the project is distributed under the LGPL.

Otherwise, it can surely be useful to build a prefix index for static piece of rule and regex.

I think I could come up with a strategy that would select potentially « matching » Route candidates in the big routing queue and perform routing on a reduced queue. I could generalize it to other attribute (eg. method, http version, ...).

Just need to finish things first in #133 and I'll start working on this.

[chergert]

Feel free to use it under LGPL-2+

[arteymix]

I performed two related improvements:

• flags for HTTP methods (faster comparison)
• a GLib.Sequence to hold the routes

The idea is that we can eventually use exclusive criteria (like accepted HTTP method) to sort the sequence and find the candidates in logarithmic time.

Using flags for HTTP methods remove the need for Router.all and Router.methods and yields a nice syntax:

app.rule (Method.ALL, "", (req, res) => {
    // any standard HTTP method
});

app.rule (Method.GET | Method.POST, "", (req, res) => {
    // on GET or POST
});

app.rule (Method.ANY, "", (req, res) => {
   // any HTTP method (including custom)
});

All the Route stuff work with inheritance (RuleRoute, RegexRoute, etc...), which means that it will be much easier to perform targeted optimizations.

The trie would be specific to RuleRoute.

[arteymix]

Also, Route.then does not increase the queue size, which reduce considerably the number of Route objects to traverse.