New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

URL routing is O(m * n) #144

Open
chergert opened this Issue Jan 4, 2016 · 6 comments

Comments

Projects
None yet
2 participants
@chergert

chergert commented Jan 4, 2016

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

This comment has been minimized.

Show comment
Hide comment
@arteymix

arteymix Jan 5, 2016

Member

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!

Member

arteymix commented Jan 5, 2016

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

This comment has been minimized.

Show comment
Hide comment
@chergert

chergert Jan 5, 2016

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.

chergert commented Jan 5, 2016

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 added a commit that referenced this issue Jan 5, 2016

Reduce routing complexity for the 'next' callback
Improve the complexity as of #144.

Traverse the linked list nodes and use the current node directly (rather
than traversing it again) to describe how the routing should continue
when 'next' is called.
@arteymix

This comment has been minimized.

Show comment
Hide comment
@arteymix

arteymix Jan 5, 2016

Member

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.

Member

arteymix commented Jan 5, 2016

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

This comment has been minimized.

Show comment
Hide comment
@chergert

chergert Jan 5, 2016

Feel free to use it under LGPL-2+

chergert commented Jan 5, 2016

Feel free to use it under LGPL-2+

arteymix added a commit that referenced this issue Jan 10, 2016

Reduce routing complexity for the 'next' callback
Improve the complexity as of #144.

Traverse the linked list nodes and use the current node directly (rather
than traversing it again) to describe how the routing should continue
when 'next' is called.
@arteymix

This comment has been minimized.

Show comment
Hide comment
@arteymix

arteymix Jan 31, 2016

Member

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.

Member

arteymix commented Jan 31, 2016

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

This comment has been minimized.

Show comment
Hide comment
@arteymix

arteymix Jan 31, 2016

Member

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

Member

arteymix commented Jan 31, 2016

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

@arteymix arteymix added this to the 0.3.0 milestone Feb 6, 2016

@arteymix arteymix added the enhancement label Feb 6, 2016

@arteymix arteymix modified the milestone: 0.3.0 Oct 23, 2016

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment