Hacker News Reader

Comment by quotemstr | Hacker News Reader

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/

View on HN

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

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

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

I'm not sure I can think of a case where new routes should be added dynamically, is there ?

That's the exact thing that caused Netflix's problem. Read the article.

Worst case is absurd, yes. But most (all?) added routes that exhibit that behavior are routes that would exhibit that behavior when run as a regex (and hence converted into a DFA) on their own. (I.e. generally if you would shoot yourself in the foot with this method you've already shot yourself in the foot.)

Your worst case is O(nd + O(constructing the new route's DFA)), where "n" is the number of nodes in the previous DFA and "d" is the number of nodes in the DFA of the new route.

Note that constructing r's DFA can be done beforehand, and hence the actual time the router will be offline is only O(nd).

(Assuming a simple 2 DFA -> 1 NFA -> DFA merge. Your worst case is that every possible pair from the two, and singleton of the two is present in the final DFA, i.e. ({node from old, node from new} -> nd + {node from old} -> n + {node from new} -> d) -> O(nd + n + d) -> O(n*d). Note that this isn't the classic O(2^n) behavior, because we know that, due to the old DFA and new route DFA being DFAs, only one node in n and one node in d can be present at a time in the final stateset.

A better bet may be to use the classic "lazily-constructed DFA" approach. In other words, keep it as an NFA while only converting (sets of) nodes to DFA nodes when necessary. If you are worried about memory, you can even do this only for "hot" sections of the NFA, or only for those sections of the NFA that have the most performance gain for the number of nodes added.

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

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

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?

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

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

Oh that is very cool, I am definitely going to have to spend some time playing with that.

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.

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.

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.

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.

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.

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.

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.

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.

Reply on news.ycombinator.com