4 ms·

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

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

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