3 ms·
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 reg
by 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 agoWell 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).