3 ms·

I meant, you have a number of regular expressions, and each gets compiled (e.g. by calling re.compile in Python), so you have one DFA per regex. At least in Py

by quacker 13y ago

I meant, you have a number of regular expressions, and each gets compiled (e.g. by calling re.compile in Python), so you have one DFA per regex. At least in Python, there are also transient objects created whenever you match something with the regex (e.g. calling regex.match). >It's not like a bunch of heavy-wight regex objects have to be created for each input character. I'm not familiar with the Python or JavaScript implementations. Abstractly, if the DFA is just a graph (nodes and edges), then you would need to store something for every node and every edge. This could be an object per character (depending on the implementation and the regex, I suppose?). EDIT: I'm confusing myself. Each node represents a state. The characters would be on the edges. You would need to store a set of characters for every state. I just had this fuzzy notion that each regex requires a bit more state and a bit more logic than a handwritten version, so the hand-written version could very well be faster.

pjscott 13y ago
Aside from technical difficulty, there's really nothing stopping the V8 guys from spitting out native code to match their regular expressions. And, in fact, they seem to do this: http://blog.chromium.org/2009/02/irregexp-google-chromes-new-regexp.html http://blog.chromium.org/2009/02/irregexp-google-chromes-new... With a sufficiently smart regular expression engine and JIT, they should be able to do about as well as an equivalent hand-rolled thing.
- eliben 13y ago
  Yep, compiling the regex into some sort of "VM" is not a new technique, but eventually the algorithm this bytecode implements is what matters most. The article you linked to suggests that even after the rewrite, V8's regexes are backtracking rather than DFA (the re2 approach), which explains the results, in a way. This is really interesting. The most common point raised in the backtracking vs. DFA debates is pathological inputs that induce exponential behavior. But large alternations seem to be affected quite a bit as well, and are more common. Admittedly, there's no exponential behavior there - just an unfortunate constant factor.

by quacker 13y ago

pjscott 13y ago

Aside from technical difficulty, there's really nothing stopping the V8 guys from spitting out native code to match their regular expressions. And, in fact, they seem to do this: http://blog.chromium.org/2009/02/irregexp-google-chromes-new-regexp.html http://blog.chromium.org/2009/02/irregexp-google-chromes-new... With a sufficiently smart regular expression engine and JIT, they should be able to do about as well as an equivalent hand-rolled thing.

eliben 13y ago
Yep, compiling the regex into some sort of "VM" is not a new technique, but eventually the algorithm this bytecode implements is what matters most. The article you linked to suggests that even after the rewrite, V8's regexes are backtracking rather than DFA (the re2 approach), which explains the results, in a way. This is really interesting. The most common point raised in the backtracking vs. DFA debates is pathological inputs that induce exponential behavior. But large alternations seem to be affected quite a bit as well, and are more common. Admittedly, there's no exponential behavior there - just an unfortunate constant factor.