On: Regular Expression Matching Can Be Simple And Fast

[blasdel]

But it's not a trivial speed increase -- for some cases PCREs are O(2^n) where Thomson's NFA is at worst O(n^2). The Thomson NFA quickly gets to be millions of times faster

Thomson's algorithm would let you could use regular expressions for cases where you would otherwise have never tried.

[haberman → blasdel]

> The Thomson NFA quickly gets to be millions of times faster

The O(2^n) worst case only comes from highly ambiguous patterns which are better written in other ways. So this isn't really accurate in practice.

[steveklabnik → blasdel]

Yes, a 1u to .1u increase is 10x, but it's still trivial. In most cases, everything else that you're doing is much slower than the match. Yes, in a degenerate case, the PCRE performs abysmally, but seriously, are you ever going to use "a?a?a?aaa"? I'd like to see some numbers on the average, not the absolute worst case.