Node.js in Flame Graphs

Re:Node.js in Flame Graphs by thedufer on Wednesday November 19, 2014 @12:30PM (#8631320)

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

[ Parent | on HN ]

Re:Node.js in Flame Graphs by colanderman on Wednesday November 19, 2014 @12:32PM (#8631338)

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

[ Parent | on HN ]

Re:Node.js in Flame Graphs by thedufer on Wednesday November 19, 2014 @12:34PM (#8631359)

Oh, right. My CS has gotten fuzzy - the tree gets enormous, but the runtime stays is O(n) on input length. Thanks for the explanation.

[ Parent | on HN ]

Re:Node.js in Flame Graphs by quotemstr on Wednesday November 19, 2014 @01:00PM (#8631513)

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

[ Parent | on HN ]

Re:Node.js in Flame Graphs by thedufer on Wednesday November 19, 2014 @01:33PM (#8631715)

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

[ Parent | on HN ]

Re:Node.js in Flame Graphs by jerf on Wednesday November 19, 2014 @01:54PM (#8631838)

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

[ Parent | on HN ]

Re:Node.js in Flame Graphs by ufo on Wednesday November 19, 2014 @02:07PM (#8631944)

The exponential blowup only occurs in the worst case. I don't have a proof at hand but I suspect that the final automaton shouldn't grow very large if your regexes are modeling web routes, since they are structured as a tree of paths with lots of "prefix-sharing" and no loops.

Other than that, if you are concerned about automaton size you can use a non-deterministc automaton instead of a deterministic one. You spend a bit more time (at each iteration you have to update a list of "active" states, while in the DFA case there is always a single active state) but on the other hand the automaton itself is much more compact.

[ Parent | on HN ]

Re:Node.js in Flame Graphs by danieldk on Wednesday November 19, 2014 @01:55PM (#8631849)

By that logic the app I work on would have a DFA with ~200,000 nodes. That sounds fairly large to me.

That's not very large, since you can store a DFA very compactly in a table (C array with structs). The table stores the transitions, which only have the character and the target state. Then you either keep an array with state offsets in the transition table, or you modify transition tables such that each transition points at the first transition of the target state.

[ Parent | on HN ]