Literals optimization #2
Description
nim-regex implements a literals optimization that puts it on par with PCRE performance. This is only because the nim-regex NFA engine is pretty slow, as it's is 35x times faster than PCRE in one of the benchmarks where the NFA is not hit much. I think, nregex would be consistently faster than PCRE once the optimization is in place.
However, both find/findAll APIs have quadratic time worst case complexity (linear time best case, though). Granted, PCRE has the same issue in the same situations (and many more). A linear time version would require to track all possible matching states in parallel (NFA style), and it would be slower. Another way may be to transform the expression into re".*regex" where "regex" is the expression, and "dot" matches new lines, that way the regex can start anywhere in the string.
That said, nregex is just a PoC to play around DFAs, so I doubt I'll ever implement this.