News for hackers. Stuff that matters.
Re:Fast request routing using regular expressions by sjtgraham on Thursday February 20, 2014 @06:53AM (#7270299)
Are regular expressions are good choice for routing? A trie seems like a better choice than a sequence of regexps. O(n) vs O(log n).
Re:Fast request routing using regular expressions by tcwc on Thursday February 20, 2014 @08:46AM (#7270666)
It depends on your regex engine. The author here is concatenating all of the paths into a single pattern, an automata based engine would ideally compile away the disjunction and offer performance linear with the input path length.
Re:Fast request routing using regular expressions by Gigablah on Thursday February 20, 2014 @07:02AM (#7270323)
It's funny that people are coming up with these libraries while comparing performance to the Symfony routing component, yet Symfony does exactly what you describe (dumping the routes to more or less a trie structure) if you activate caching, which is done in the standard framework distribution.

Not that I'm slagging off their efforts, in fact I plan to use FastRoute in one of my projects.

Re:Fast request routing using regular expressions by pjmlp on Thursday February 20, 2014 @08:41AM (#7270645)
Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems. -- Jamie Zawinski in 1997
Re:Fast request routing using regular expressions by skj on Thursday February 20, 2014 @07:37AM (#7270424)
Or, O(n^2) vs O(n log n).
Re:Fast request routing using regular expressions by skj on Thursday February 20, 2014 @07:40AM (#7270433)
Now that I read the article, seems like they're merging all the regexps into one, which really could be O(n). However, the trie will not be O(log n). You have to at least look at every character in the input, so there's a hard O(n) lower bound.
Re:Fast request routing using regular expressions by sjtgraham on Thursday February 20, 2014 @07:43AM (#7270450)
You're confusing n size of route set, with k length of the path to be matched. With a trie the worst case running time to match a route grows O(log n) with an array of regexps it's O(n). The length of a path string to be matched is independent of how many routes are in the route set.
Re:Fast request routing using regular expressions by amalcon on Thursday February 20, 2014 @08:15AM (#7270559)
In theory, the combined regex could be O(1) in the size of the route set.

Of course, in practice it's not. PCRE is backtracking-based rather than automaton-based, so increasing the complexity of the regex does have an effect on runtime.

Re:Fast request routing using regular expressions by jerf on Thursday February 20, 2014 @01:22PM (#7272572)
Which probably means we should be using a NFA-based engine for routing, rather than PCRE, because I don't think "don't backtrack" is a very serious restriction for routing. (Yes, of the hundreds of developers who may read this, one of them may have used backtracking in a routing expression. But in general I don't think it's that serious a restriction.)
Re:Fast request routing using regular expressions by sjtgraham on Thursday February 20, 2014 @07:44AM (#7270455)
No