<story><title>Node.js in Flame Graphs</title><url>http://techblog.netflix.com/2014/11/nodejs-in-flames.html</url></story><parent_chain><item><author>thedufer</author><text>&amp;gt; It’s unclear why Express.js chose not to use a constant time data structure like a map to store its handlers.&lt;p&gt;Its actually quite clear - most routes are defined by a regex rather than a string, so there is no built-in structure (if there&amp;#x27;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.&lt;p&gt;I can&amp;#x27;t explain away the recursion, though.  That seems wholly unnecessary.&lt;p&gt;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.</text></item></parent_chain><comment><author>quotemstr</author><text>Of course there&amp;#x27;s a faster way! Combine all the routes into a DFA, then run the DFA over the URL. It&amp;#x27;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.&lt;p&gt;You can use Ragel[1] to build your automaton.&lt;p&gt;[1] &lt;a href=&quot;http://www.colm.net/open-source/ragel/&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;www.colm.net&amp;#x2F;open-source&amp;#x2F;ragel&amp;#x2F;&lt;/a&gt;</text></comment>
<story><title>Node.js in Flame Graphs</title><url>http://techblog.netflix.com/2014/11/nodejs-in-flames.html</url></story><parent_chain><item><author>thedufer</author><text>&amp;gt; It’s unclear why Express.js chose not to use a constant time data structure like a map to store its handlers.&lt;p&gt;Its actually quite clear - most routes are defined by a regex rather than a string, so there is no built-in structure (if there&amp;#x27;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.&lt;p&gt;I can&amp;#x27;t explain away the recursion, though.  That seems wholly unnecessary.&lt;p&gt;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.</text></item></parent_chain><comment><author>andrewvc</author><text>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.&lt;p&gt;If I have the routes &amp;#x2F;foo&amp;#x2F;bar and &amp;#x2F;foo&amp;#x2F;bar&amp;#x2F;(\d+) I can generate the regexp ((^\&amp;#x2F;foo\&amp;#x2F;bar$)|(^\&amp;#x2F;foo\&amp;#x2F;bar\&amp;#x2F;\d+$))&lt;p&gt;I&amp;#x27;m not at all surprised, the quality of software in node is pretty low, I&amp;#x27;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 (&lt;a href=&quot;https://github.com/rails/journey&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;github.com&amp;#x2F;rails&amp;#x2F;journey&lt;/a&gt;)</text></comment>