8 ms·
> It’s unclear why Express.js chose not to use a constant time data structure like a map to store its handlers. Its actually quite clear - most routes are defi
by thedufer 12y ago
> It’s unclear why Express.js chose not to use a constant time data structure like a map to store its handlers.
Its actually quite clear - most routes are defined by a regex rather than a string, so there is no built-in structure (if there's a way at all) to do O(1) lookups in the routing table. A router that only allowed string route definitions would be faster but far less useful.
I can't explain away the recursion, though. That seems wholly unnecessary.
Edit: Actually, I figured that out, too. You can put middleware in a router so it only runs on certain URL patterns. The only difference between a normal route handler and a middleware function is that a middleware function uses the third argument (an optional callback) and calls it when done to allow the route matcher to continue through the routes array. This can be asynchronous (thus the callback), so the router has to recurse through the routes array instead of looping.
- cataphract 12y agoOn the other hand, without the recursion I don't see how the flame graph would have been helpful.
- msmillie 12y agoIn flame graphs heavy iteration tends to give "wider" structures. Recall the stacks aren't ordered on the X axis by time, but by contents.
- quotemstr 12y agoOf course there's a faster way! Combine all the routes into a DFA, then run the DFA over the URL. It's guaranteed to run in constant space and O(n) (n=URL length) time! The union of any set of regular languages is itself a regular language. You can use Ragel[1] to build your automaton. [1] http://www.colm.net/open-source/ragel/ http://www.colm.net/open-source/ragel/
- thedufer 12y agoYeah, but what's n there? Isn't that going to be something like the sum of each route's length? That doesn't buy us anything (well, probably a smaller constant). Unless you go the NFA route, but I'm pretty sure that costs non-constant space.
- colanderman 12y agoNo. n in the case of a DFA is the length of the input string. (i.e. the string being matched.) So, in terms of the GP's post, yes, this is an O(1) (with respect to number of routes) solution.
- thedufer 12y agoOh, right. My CS has gotten fuzzy - the tree gets enormous, but the runtime stays is O(n) on input length. Thanks for the explanation.
- quotemstr 12y agoThe automaton isn't even that big, really. The number of NFA states is roughly proportional to the total number of characters in the regular expressions involved, and NFA to DFA conversion usually expands the automaton only be a factor of two or three. Although the subset construction in theory worst-case exponential, that situation never occurs in practice.
- thedufer 12y agoBy that logic the app I work on would have a DFA with ~200,000 nodes. That sounds fairly large to me. I suspect this is a slight overestimate, but the point stands - non-trivial apps could quickly build very large state graphs.
- jerf 12y agoYes, but unless you're running on embedded, and to be honest to some extent even then unless you're way at the bottom of the power scale, you're running on a supercomputer that will laugh at 200,000 nodes in a DFA, and it's very easy for that DFA to run significantly faster than the presumably several tens of thousands of FAs you're running sequentially otherwise.
- badgersandjam 12y agoThis. I wrote something that did this a few years ago. It took n patterns (not regex, simpler) and turned them into one DFA state table with a function ptr stored for each final state. Then it had a tiny runtime. Never thought of using it for route tables however. Nice idea. Edit: I did consider rewriting the runtime as a forth style interpreter as well but the time never appeared.
- rtkwe 12y agoHow long does it take to build the DFA when a new route is added? That seems like the major time performance problem point if new routes are added often or regularly.
- badgersandjam 12y agoTo be honest I didn't time it and it wasn't thread safe and I don't have the source any more so I can't answer that. It doesn't do a lot so I imagine it would be relatively cheap. The function it performed to rebuild the DFA was to create an NFA for the new pattern stream (it worked on char *) and then walk both the existing master NFA and the merge them. Then it was converted from NFA to DFA via dragon book copy and paste algorithm (my discrete math isn't great). Both NFA and DFA were represented as a bunch of C structs tied together by pointers. Then a table generator walked the new DFA and generated a new state table. It was very naive but covered the common case where large parts of the byte stream to be matched were similar. I've got MacVim up and writing it again. May post it as a Show HN if I get the time to finish it.
- arcatek 12y agoI'm not sure I can think of a case where new routes should be added dynamically, is there ?
- jonny_eh 12y agoThat's the exact thing that caused Netflix's problem. Read the article.
- 12y ago
- ChuckMcM 12y agoOh that is very cool, I am definitely going to have to spend some time playing with that.
- andrewstuart2 12y agoThis approach will of course work, but you can't have a middleware stack with a defined order using that approach, unless I'm mistaken. Sure, you could use all routes that match, but is there a way to specify the order for all handlers, and whether or not you should continue after one handler is done?
- nostrademons 12y agoThe easiest way is to not conflate middleware handling with routing. Your routing infrastructure should take a dict mapping URL patterns to callables, and returns a callable (which uses this DFA-based approach to dispatch). Your middleware should be a callable that wraps another callable. If you want to apply middleware to just one path, wrap it before you register it with the routing table. If you want to apply middleware to all (or a subset of) paths, wrap the returned routing table, and optionally stick that in some other routing table.
- quotemstr 12y ago> You can't have a middleware stack with a defined order using that approach Sure you can. When you build your NFA, each accepting state is tagged with the route to which it corresponds. Converting to a DFA will merge states. Any accepting state in the DFA tagged with more than one route indicates a possible ambiguity. How you handle that ambiguity is up to you. One strategy is to just fail at route-building time. Another is to order the routes by priority (which priorities maybe coming from order in the source code) and eliminate from each accepting state all routes except the one with the highest priority. The latter approach gives you the "defined order" semantics you want.
- rtpg 12y agoThis is the reason we need more people in JS land taking compiler courses and the like. There's a lot of tech out there that are speed sensitive yet do not apply the "best" solution to a problem solved in the 70s.
- yzzxy 12y agoBut then you need to seduce the JS runtime into actually performing your optimizations. Maybe time for C/C++ extensions to become more prevalent a la Python?
- koenigdavidmj 12y agoThere is a library (I think it is Google's re2) that supports throwing a bunch of regular expressions into a single structure, matching an input string against all of them at once, and answering which patterns matched the input string. This gets you route lookup in time linear to the input string (or if not linear, still better than checking all the patterns one after another).
- f2f 12y agore2 is described here: http://swtch.com/~rsc/regexp/regexp3.html http://swtch.com/~rsc/regexp/regexp3.html
- rudolf0 12y agoI use RE2 and currently achieve this with regular string concatenation. Do you know if they provide an API for doing this without concatenation, and if it would be faster?
- koenigdavidmj 12y agoThe header file is available at https://code.google.com/p/re2/source/browse/re2/set.h https://code.google.com/p/re2/source/browse/re2/set.h , and if I recall correctly, it merges all the regexes into one DFA so that it's faster than just concatenating all your patterns into one string.
- deleted 12y ago[deleted]
- ksherlock 12y agoYou could compile all the regular expressions into a table. Lex has been doing that since, oh, 1975.
- andrewvc 12y agoA 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 agoRegexps with backtracks are not regular languages (IIRC, right?), does that matter here?
- stepstep 12y agoThat'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 agoJust 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 agoIt 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.)
- deleted 12y ago[deleted]
- andrewstuart2 12y agoThe other thing you can't properly get using a map is precedence. By building an array you can go through it in order so that middleware is run in the order it was defined in the code. That way, if you have any route definitions that match early on, especially if they allow execution to continue ( by calling next() ), they will run before any following code does. This allows your code to be very expressive and intuitive when reading it, as things have a defined order. I imagine the recursion is also done so that you can use a route object anywhere in that ordered stack and it will apply all its own handlers, in the order they were defined in the code.
- cdoxsey 12y agoMost routes are prefix matches, so a trie (or one of its variants) would work well.
- deleted 12y ago[deleted]