5 ms·

A lot of people here are right, the right way is with an NFA. I just want to add that the solution is not even hard, you can do it with string concatenation and

A lot of people here are right, the right way is with an NFA. I just want to add that the solution is not even hard, you can do it with string concatenation and capture groups using regexps. Regexps are NFAs, and are highly optimized C code in just about every JS engine. If I have the routes /foo/bar and /foo/bar/(\d+) I can generate the regexp ((^\/foo\/bar$)|(^\/foo\/bar\/\d+$)) I'm not at all surprised, the quality of software in node is pretty low, I've seen numerous issues in node libs being just as boneheaded. I swear, the fact that the express devs overlooked a key optimization is crazy. Rails, by way of example, uses the Journey engine to solve this problem (https://github.com/rails/journey https://github.com/rails/journey)

llimllib 12y ago
Regexps with backtracks are not regular languages (IIRC, right?), does that matter here?
- stepstep 12y ago
  That's right. Typical routing regexes will not use backreferences, so that's not really an issue here. However, most routes do have parameters implemented as capture groups (which, I believe, is also not technically a feature of regular expressions). One simple solution would be to use a big regex (the union of all the routes) to determine which route it is (in O(n) time), and then once you know the route, use another regex to parse the parameters in the URL. So each route lookup requires 2 regex matches rather than N.
  - stepstep 12y ago
    Just re-read this and realized it's unclear: when I said O(n) time, I meant linear in the length of the URL to be parsed. The point is that with this technique, it doesn't matter how many routes there are.
mjs 12y ago
It looks like routes are either strings (exact match) or regular expression objects. I don't think there's a way to combine regular expressions in JavaScript. I don't think this was an unreasonable implementation. Sure, it could be optimized, but no-one needed it enough to do the work. (Even Netflix didn't need a faster matcher, they needed a matcher that didn't slow down between the 1st match and the nth.)
- andrewvc 12y ago
  What I'm saying is that the pipe (or) "|" is a cheap way to combine regexps. It has its limitations, but its better than an O(n) search through an array. The regexp parser can create an NFA that is far more optimized.
  - spion 12y ago
    In JS, "far more" isn't quite that dramatically far as in other dynamic language runtimes. See http://jsperf.com/regex-list-vs-full http://jsperf.com/regex-list-vs-full
thedufer 12y ago
> I can generate the regexp ((^\/foo\/bar$)|(^\/foo\/bar\/\d+$)) And how would you know which one got matched? The regex match isn't going to tell you that. Also, it needs to recognize if multiple were matched, which is definitely not going to be done by the built-in regex matcher. It's certainly possible, but pretending it's trivial isn't helping, either.
- andrewvc 12y ago
  First off, you don't need to handle the 'multiple' case, since the "|" has precedence rules applied to it. The leftmost match is the match. Second, you know which one matched based on the index of the capture groups, which is deterministic. See this example: http://rubular.com/r/HiW6gjnURe http://rubular.com/r/HiW6gjnURe You could write a simple router based on this in < 50 lines of JS. I'd do it now, but I have work to do.
  - thedufer 12y ago
    > First off, you don't need to handle the 'multiple' case, since the "|" has precedence rules applied to it. Read my top-level post again - multiple routes can be called on the same request, so express has to be able to find all of the matches, not just the first one. This is a mistake in the original article, as the author doesn't appear to understand the power of express routers. > Second, you know which one matched based on the index of the capture groups, which is deterministic. Deterministic, yes. But now you're also writing your own regex parser, because you have to know how many capture groups each sub-regex contains in order to figure out the indexing.
    - deleted 12y ago
      [deleted]
    - andrewvc 12y ago
      Ah, I did miss that, but it does still work. Run the following code below, you'll see multiple groups match. "/foo/bar/3".match(/((^\/foo\/bar\/.*)|(^\/foo\/bar\/(\d+)$)|(^\/baz))/) => Additionally, parsing out the number of capture groups in a regexp is simple, just looked for unescaped paren groups. You can do it once at route definition.
plorkyeran 12y ago
Given that combined regex, how do you determine which of the routes that went in to it was the one that matched?
- baudehlo 12y ago
  If it matched the first, match[2] is set. If it matched the second, match[3] is set. Or you use a better regexp library than the default JS one and use named captures.
spion 12y ago
This indicates it probably wont be much faster in JS http://jsperf.com/regex-list-vs-full http://jsperf.com/regex-list-vs-full Most of the time in the single-regex case is likely spent on allocating the matches array (which for a router with 300 routes would have over 300 undefined elements on every execution) V8 is not quite the typical dynamic language runtime. Code that would be dead slow in others is optimized really well by the amazing JIT.
- andrewvc 12y ago
  Interesting, I'm looking at it right now, and it's saying that the multiple regexes are ~ 50% slower in both chrome and firefox. Am I missing something? It looks like the single regex actually is a significant win. It is interesting how much allocation changes things though, very cool that you made this.
  - spion 12y ago
    Yeah multiple regexes are slower, but the performance gain isn't too gigantic. If we had `regex.execIterable(string)` we could avoid allocating massive arrays and maybe get a really significant difference
LunaSea 12y ago
Oh yes, I forgot about the legendary Ruby On Rails code quality: http://puppetlabs.com/security/cve/cve-2013-0277 http://puppetlabs.com/security/cve/cve-2013-0277

llimllib 12y ago

Regexps with backtracks are not regular languages (IIRC, right?), does that matter here?

stepstep 12y ago
That's right. Typical routing regexes will not use backreferences, so that's not really an issue here. However, most routes do have parameters implemented as capture groups (which, I believe, is also not technically a feature of regular expressions). One simple solution would be to use a big regex (the union of all the routes) to determine which route it is (in O(n) time), and then once you know the route, use another regex to parse the parameters in the URL. So each route lookup requires 2 regex matches rather than N.
- stepstep 12y ago
  Just re-read this and realized it's unclear: when I said O(n) time, I meant linear in the length of the URL to be parsed. The point is that with this technique, it doesn't matter how many routes there are.

mjs 12y ago

It looks like routes are either strings (exact match) or regular expression objects. I don't think there's a way to combine regular expressions in JavaScript. I don't think this was an unreasonable implementation. Sure, it could be optimized, but no-one needed it enough to do the work. (Even Netflix didn't need a faster matcher, they needed a matcher that didn't slow down between the 1st match and the nth.)

andrewvc 12y ago
What I'm saying is that the pipe (or) "|" is a cheap way to combine regexps. It has its limitations, but its better than an O(n) search through an array. The regexp parser can create an NFA that is far more optimized.
- spion 12y ago
  In JS, "far more" isn't quite that dramatically far as in other dynamic language runtimes. See http://jsperf.com/regex-list-vs-full http://jsperf.com/regex-list-vs-full

thedufer 12y ago

> I can generate the regexp ((^\/foo\/bar$)|(^\/foo\/bar\/\d+$)) And how would you know which one got matched? The regex match isn't going to tell you that. Also, it needs to recognize if multiple were matched, which is definitely not going to be done by the built-in regex matcher. It's certainly possible, but pretending it's trivial isn't helping, either.

andrewvc 12y ago
First off, you don't need to handle the 'multiple' case, since the "|" has precedence rules applied to it. The leftmost match is the match. Second, you know which one matched based on the index of the capture groups, which is deterministic. See this example: http://rubular.com/r/HiW6gjnURe http://rubular.com/r/HiW6gjnURe You could write a simple router based on this in < 50 lines of JS. I'd do it now, but I have work to do.
- thedufer 12y ago
  > First off, you don't need to handle the 'multiple' case, since the "|" has precedence rules applied to it. Read my top-level post again - multiple routes can be called on the same request, so express has to be able to find all of the matches, not just the first one. This is a mistake in the original article, as the author doesn't appear to understand the power of express routers. > Second, you know which one matched based on the index of the capture groups, which is deterministic. Deterministic, yes. But now you're also writing your own regex parser, because you have to know how many capture groups each sub-regex contains in order to figure out the indexing.
  - deleted 12y ago
    [deleted]
  - andrewvc 12y ago
    Ah, I did miss that, but it does still work. Run the following code below, you'll see multiple groups match. "/foo/bar/3".match(/((^\/foo\/bar\/.*)|(^\/foo\/bar\/(\d+)$)|(^\/baz))/) => Additionally, parsing out the number of capture groups in a regexp is simple, just looked for unescaped paren groups. You can do it once at route definition.

plorkyeran 12y ago

Given that combined regex, how do you determine which of the routes that went in to it was the one that matched?

baudehlo 12y ago
If it matched the first, match[2] is set. If it matched the second, match[3] is set. Or you use a better regexp library than the default JS one and use named captures.

spion 12y ago

This indicates it probably wont be much faster in JS http://jsperf.com/regex-list-vs-full http://jsperf.com/regex-list-vs-full Most of the time in the single-regex case is likely spent on allocating the matches array (which for a router with 300 routes would have over 300 undefined elements on every execution) V8 is not quite the typical dynamic language runtime. Code that would be dead slow in others is optimized really well by the amazing JIT.

andrewvc 12y ago
Interesting, I'm looking at it right now, and it's saying that the multiple regexes are ~ 50% slower in both chrome and firefox. Am I missing something? It looks like the single regex actually is a significant win. It is interesting how much allocation changes things though, very cool that you made this.
- spion 12y ago
  Yeah multiple regexes are slower, but the performance gain isn't too gigantic. If we had `regex.execIterable(string)` we could avoid allocating massive arrays and maybe get a really significant difference

LunaSea 12y ago

Oh yes, I forgot about the legendary Ruby On Rails code quality: http://puppetlabs.com/security/cve/cve-2013-0277 http://puppetlabs.com/security/cve/cve-2013-0277