Question on RE2::Match latency for patterns containing a large number of match groups about re2 HOT 4 CLOSED

IMO, this is an egregious misuse of regular expressions. Between that and the ~6yo version of RE2, it wouldn't be reasonable for me to spend time (either professionally or personally) digging into why the linear-time constant seems to be larger for the single pattern. There are better (i.e. more readable, more maintainable, more efficient) ways of parsing data in such a format. (The data would be in a better format, ideally, but that may or may not be within your control.)

from re2.

Thank you for the quick response. Unfortunately, we don’t have much control over both the data and the pattern (parse query) as they come from our customers. We agree that such a pattern is not ideal. To us, it appears that the latency grows exponentially with the increase in the number of match groups in the pattern. If you can confirm that RE2::Match always maintains linear performance in the latest version of RE2, even for the edge case we encountered, it would greatly help us to determine whether an upgrade to RE2 is a viable solution.

from re2.

If you have a test case you should be able to try the latest RE2 yourself.

from re2.

Also, it seems unsound to draw conclusions about asymptotic complexity from two (2) data points. For now, my guess is that the DFA and NFA execution engines incur overhead (i.e. increase the linear-time constant) due to the large number of (.*?) subexpressions. (Specifically, combining so much ambiguity with so many capturing groups would amplify cost significantly.) Updating the version of RE2 could be a mitigation, but considering it a solution would be a categorical mistake.

from re2.