Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Node.js in Flame Graphs

techblog.netflix.com

Post reply on HN
Print view View original

251–259 of 259 posts

Re: Node.js in Flame Graphs

#251

Post by quotemstr »

andrewstuart2 wrote: post #178
quotemstr wrote: post #22

Earlier quoted context omitted.

Of 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/

This 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?

> 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.

Re: Node.js in Flame Graphs

#252

Post by dang »

jaytaylor wrote: post #221

I am upset that the title has been changed from "Node.js in Flames". Which is not only the real title of the article, but also a reasonable description of what they've been facing with Node. #moderationfail

I can see why you would feel that way, but the title, while clever and (I'll take your word for it) fitting, was arguably misleading and unarguably baity. The HN guidelines call for changing such titles, so the moderators were just doing their job. There likely would have been more complaints about the title if we hadn't changed it.

Re: Node.js in Flame Graphs

#253

Post by augustl »

kyllo wrote: post #164
augustl wrote: post #70

A surprising amount of path recognizers are O(n). Paths/routes are a great fit for radix trees, since there's typically repetitions, like /projects, /projects/1, and /projects/1/todos. The performance is O(log n). I built one for Java: https://github.com/augustl/path-travel-agent

How does your radix trie implementation handle variables in the URL paths, in a nutshell?

This is one of the reasons for why I call it a "bastardized radix tree" in the README :)

The routes are stored as "nodes". There's a root node. It has a hash map of child nodes, by name. It also has a list of "parameterized" nodes. When a node gets a path segment, it will first look in its hash map. If nothing is there, it'll call the parameterized nodes in sequence. Typically there's just one parameterized node.

For the following paths:

  /projects
  /projects/new
  /projects/special
  /projects/:project-id
The root node will have a single item in its hash map, "projects". No items in the parameterized node.

The node for "projects" will have to items in its hash map, "new" and "special". It will have a single item in it's parameterized node, for :project-id.

I updated the README just now with a slightly more detailed explanation :)

Re: Node.js in Flame Graphs

#254

Post by boblauer »

thedufer wrote: post #68
andrewvc wrote: post #36

Earlier quoted context omitted.

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 qualit…

> 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.

You can get the index of the match via the .exec function. It returns an array. The first element is the match, and then an element for each capturing group. You'd need to keep track of how many sub-capturing groups each individual top-level capturing group has, but that's not terribly difficult.

As far as multiple matches, after you found a match, you would then test against a new regex that is everything to the right of the previous regex's captured group.

((a)|(b)|(c)|(d)) -> if b matches, you then test against ((c)|(d)), and so on.

Re: Node.js in Flame Graphs

#255

Post by boblauer »

thedufer wrote: post #137
andrewvc wrote: post #103

Earlier quoted context omitted.

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.

> just looked for unescaped paren groups Don't forget non-matching groups! Which brings up my point yet again - everyone is pretending this is a dead-simple problem to solve, but all of the proposed solutions are buggy. Not really an option for such a widely-used library. I'm not claiming it's impossible. I'm claiming it's more difficult than anyone is willing to admit.

Counting capturing groups is a solved problem - http://stackoverflow.com/questions/16046620/regex-to-count-t...

Re: Node.js in Flame Graphs

#256

Post by kyllo »

augustl wrote: post #253
kyllo wrote: post #164

Earlier quoted context omitted.

How does your radix trie implementation handle variables in the URL paths, in a nutshell?

This is one of the reasons for why I call it a "bastardized radix tree" in the README :) The routes are stored as "nodes". There's a root node. It has a hash map of child nodes, by name. It also has a list of "parameterized" nodes. When a node gets a path segment, it will first look in its hash map. If nothing is there, it'll call the parameterized nodes in sequence. Typically there's just one parameterized node. For…

Very cool, thanks for taking the time to explain! I recently learned how tries work so it was cool to see a real-world implementation like yours.

Re: Node.js in Flame Graphs

#257

Post by runT1ME »

nostrademons wrote: post #202
runT1ME wrote: post #197

Earlier quoted context omitted.

>When you have a number of interdependent modules, then every change request and new feature has to go through that module's owner. If it's not their top priority (and it won't be), then getting your work done suddenly has a hard dependency on a team who is...generally pretty unresponsive, at least from your POV. Is that true? Again, I've never done development on that scale, so I could totally be wrong, but I'm seei…

Imagine what happens at scale if everyone forks the repo when a critical feature they need isn't being worked on by the core team. Suddenly you have dozens of forks. Now imagine that the core team eventually gets around to publishing that bugfix you really do want. All of these incompatible forks need to down-integrate the change and work around the little tweaks they've added. You have a mess. Open source works beca…

I appreciate the response, but I don't follow the argument.

>All of these incompatible forks need to down-integrate the change and work around the little tweaks they've added. You have a mess.

Is that really better than having a mess without any demarcation of the software? Either way people are going to make a change. Your way involves no disincentive to making quick fix that just your team needs. Modularized codebases means that before submitting that PR or forking, you're forced to consider how this will affect everyone who uses the library.

I understand your point about modularizing codebases causing more friction between teams. That's quite insightful and I haven't considered that. However, I think that gets down to a cultural issue of what do you value more, clean code that is easier to comprehend, or fostering geniality between teams.

Re: Node.js in Flame Graphs

#258

Post by jaytaylor »

dang wrote: post #252
jaytaylor wrote: post #221

I am upset that the title has been changed from "Node.js in Flames". Which is not only the real title of the article, but also a reasonable description of what they've been facing with Node. #moderationfail

I can see why you would feel that way, but the title, while clever and (I'll take your word for it) fitting, was arguably misleading and unarguably baity. The HN guidelines call for changing such titles, so the moderators were just doing their job. There likely would have been more complaints about the title if we hadn't changed it.

Understood. And thank you for following up, I really do appreciate it.

Re: Node.js in Flame Graphs

#259

Post by JDiculous »

gasping wrote: post #239
JDiculous wrote: post #236

Earlier quoted context omitted.

One more advantage of Node.js over Java is that development is much faster with Node.js.

No, just please no. Any moderately competent programmer can be productive in either Java or Javascript (+ Node.js). Javascript may help incompetent programmers feel productive because Javascript has fewer compile-time constraints but in the long run the cost of maintaining code written by an incompetent more than counteracts any perceived benefit that Javascript offers.

Well obviously the work of an incompetent programmer is going to increase the long run cost of maintaining code. That has nothing to do with the fact that Javascript is faster to develop in.
Post reply on HN