-
Notifications
You must be signed in to change notification settings - Fork 1
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Literals optimization #2
Comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.
The text was updated successfully, but these errors were encountered: