6 ms·

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 lengt

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/ http://www.colm.net/open-source/ragel/

thedufer 12y ago
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.
- colanderman 12y ago
  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.
  - thedufer 12y ago
    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.
    - quotemstr 12y ago
      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.
      - thedufer 12y ago
        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.
        jerf 12y ago
        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.
        danieldk 12y ago
        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.
        ufo 12y ago
        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.
badgersandjam 12y ago
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.
- rtkwe 12y ago
  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.
  - badgersandjam 12y ago
    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.
  - arcatek 12y ago
    I'm not sure I can think of a case where new routes should be added dynamically, is there ?
    - jonny_eh 12y ago
      That's the exact thing that caused Netflix's problem. Read the article.
  - 12y ago
ChuckMcM 12y ago
Oh that is very cool, I am definitely going to have to spend some time playing with that.
andrewstuart2 12y ago
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?
- nostrademons 12y ago
  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.
- 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 ago
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.
- yzzxy 12y ago
  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?

thedufer 12y ago

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.

colanderman 12y ago
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.
- thedufer 12y ago
  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.
  - quotemstr 12y ago
    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.
    - thedufer 12y ago
      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.
      - jerf 12y ago
        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.
      - danieldk 12y ago
        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.
      - ufo 12y ago
        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.

badgersandjam 12y ago

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.

rtkwe 12y ago
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.
- badgersandjam 12y ago
  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.
- arcatek 12y ago
  I'm not sure I can think of a case where new routes should be added dynamically, is there ?
  - jonny_eh 12y ago
    That's the exact thing that caused Netflix's problem. Read the article.
- 12y ago

ChuckMcM 12y ago

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

andrewstuart2 12y ago

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?

nostrademons 12y ago
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.
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 ago

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.

yzzxy 12y ago
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?