5 ms·

I'm not surprised the hand-written version is faster. You need to store an object for each regex. If these objects are DFAs, for example, then there is a consid

by quacker 13y ago

I'm not surprised the hand-written version is faster. You need to store an object for each regex. If these objects are DFAs, for example, then there is a considerable amount of overhead storing the graph to represent the DFA. The hand-written version has comparatively little state, and no generalized logic which would further slow it down. Error-reporting is another good reason for hand-written lexers (and parsers). It's harder to get readable and accurate error messages when the logic is embedded in the regex or some library/framework. EDIT: The link posted in the comments of the article is great. From Rob Pike: A regular expression library is a big thing. Using one to parse identifiers is like using a Ferrari to go to the store for milk. http://commandcenter.blogspot.com/2011/08/regular-expressions-in-lexing-and.html http://commandcenter.blogspot.com/2011/08/regular-expression...

eliben 13y ago
> I'm not surprised the hand-written version is faster. You need to store an object for each regex. If these objects are DFAs, for example, then there is a considerable amount of overhead storing the graph to represent the DFA. I'm not sure what this means specifically. Presumably, the DFA is created once and then only some sort of small state has to be maintained (i.e. which state we're in, perhaps a little more). It's not like a bunch of heavy-wight regex objects have to be created for each input character.
- 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.
kkowalczyk 13y ago
The reason you should be surprised is this: regular expressions are implemented in C. In some implementation they are even jit'ed. It's a testament to how good V8 is that char-by-char loop is faster in JavaScript than optimized C code but if you were to benchmark pre-V8 JavaScript interpreters or current implementations of Python or Ruby, regex matching would smoke char-by-char loop written in the language simply by virtue of being C code.
- deleted 13y ago
  [deleted]
- jlarocco 13y ago
  No. This isn't too surprising to anybody who knows how regular expressions work under the hood. The hand rolled parser is asymptotically faster than using regex. It wouldn't surprise me at all if the hand rolled parser were still faster for a complicated enough language and a large enough input file. It's analogous to a hand optimized assembly language implementation of bubble sort being slower than quicksort in a slow, high level language. At some point the bubble sort will lose, simply because it's asymptotically worse.
  - pjscott 13y ago
    Well hold on; that "asymptotically faster" part needs a bit more detail so people don't get wrong ideas. In a DFA-based regexp implementation (which, admittedly, V8 doesn't use) matching is guaranteed O(n), where n is the number of characters you look at before finding a match or deciding that the match has failed. There are DFA-based lexer generators, like GNU flex, which take regular expressions for your tokens, turn it into a big DFA, and spit out a linear-time lexer. This is the same asymptotic time as the hand-rolled parser. The regexp-based version linked to in the article, on the other hand, has a list of regular expressions which are sequentially tried against the input to grab each token. For this particular lexer, a failed match will fail on the first character, i.e. in constant time. So this is asymptotically O(n*k) where n is the input length and k is the (small, constant) number of tokens. Finally, most regular expression engines are not DFA-based; they use a backtracking algorithm which is, theoretically, exponential-time. However, with the particular regular expressions used here, successful matching will be O(n) for each one, and failed matching O(1).

by quacker 13y ago

eliben 13y ago

> I'm not surprised the hand-written version is faster. You need to store an object for each regex. If these objects are DFAs, for example, then there is a considerable amount of overhead storing the graph to represent the DFA. I'm not sure what this means specifically. Presumably, the DFA is created once and then only some sort of small state has to be maintained (i.e. which state we're in, perhaps a little more). It's not like a bunch of heavy-wight regex objects have to be created for each input character.

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.

kkowalczyk 13y ago

The reason you should be surprised is this: regular expressions are implemented in C. In some implementation they are even jit'ed. It's a testament to how good V8 is that char-by-char loop is faster in JavaScript than optimized C code but if you were to benchmark pre-V8 JavaScript interpreters or current implementations of Python or Ruby, regex matching would smoke char-by-char loop written in the language simply by virtue of being C code.

deleted 13y ago
[deleted]
jlarocco 13y ago
No. This isn't too surprising to anybody who knows how regular expressions work under the hood. The hand rolled parser is asymptotically faster than using regex. It wouldn't surprise me at all if the hand rolled parser were still faster for a complicated enough language and a large enough input file. It's analogous to a hand optimized assembly language implementation of bubble sort being slower than quicksort in a slow, high level language. At some point the bubble sort will lose, simply because it's asymptotically worse.
- pjscott 13y ago
  Well hold on; that "asymptotically faster" part needs a bit more detail so people don't get wrong ideas. In a DFA-based regexp implementation (which, admittedly, V8 doesn't use) matching is guaranteed O(n), where n is the number of characters you look at before finding a match or deciding that the match has failed. There are DFA-based lexer generators, like GNU flex, which take regular expressions for your tokens, turn it into a big DFA, and spit out a linear-time lexer. This is the same asymptotic time as the hand-rolled parser. The regexp-based version linked to in the article, on the other hand, has a list of regular expressions which are sequentially tried against the input to grab each token. For this particular lexer, a failed match will fail on the first character, i.e. in constant time. So this is asymptotically O(n*k) where n is the input length and k is the (small, constant) number of tokens. Finally, most regular expression engines are not DFA-based; they use a backtracking algorithm which is, theoretically, exponential-time. However, with the particular regular expressions used here, successful matching will be O(n) for each one, and failed matching O(1).