in reply to Re^2: Recursive sub-pattern spectacularly slow, what's wrong? (me, or just this use case, or a bug?)
in thread Recursive sub-pattern spectacularly slow, what's wrong? (me, or just this use case, or a bug?)

> Reason: Perl regex are highly pre-optimized by using heuristics.

Actually it's a post-optimization.

After the first full backtrack (from "a" to end/FAIL) the 2nd regex reports

and runs from "b" to FAIL.

After that the cached results are later used to see that no match is possible and backtracking is stopped. That's why the formula is n+(n-1)

So it's not that the 1st regex with the recursion is very bad¹, it's just that the second is very clever.

Hint: use re "debug" to see the details.

Cheers Rolf
(addicted to the Perl Programming Language :)
see Wikisyntax for the Monastery

¹) there still might be a memory leak somewhere, but who is using recursion to this extremes anyway?

  • Comment on Re^3: Recursive sub-pattern spectacularly slow, what's wrong? (me, or just this use case, or a bug?)
  • Select or Download Code

Replies are listed 'Best First'.
Re^4: Recursive sub-pattern spectacularly slow, what's wrong? (me, or just this use case, or a bug?)
by LanX (Saint) on Sep 28, 2025 at 17:11 UTC
    I was curious what a "detected a super-linear match" means and asked Duck-AI. Explanation below. (LLMs are good in condensing knowledge as long as you review the output like I did. see also https://stackoverflow.com/questions/12841970/how-can-i-recognize-an-evil-regex)

    Super-linear Match A super-linear match in the context of regular expressions refers to a situation where the time complexity of matching a pattern against a string exceeds linear time, often approaching quadratic or worse. This typically occurs due to certain patterns in the regular expression that can lead to excessive backtracking.

    Characteristics of Super-Linear Matches

    • Backtracking: When a regex engine encounters ambiguous patterns, it may try multiple paths to find a match. This can lead to exponential time complexity in the worst case, especially with nested quantifiers (e.g., .* followed by another .*).
    • Nested Quantifiers: Patterns like (a|b)*c can cause super-linear behavior when matched against strings that contain many as and bs, as the engine may explore all combinations of a and b before concluding that there is no match.
    • Long Input Strings: The longer the input string, the more pronounced the super-linear behavior can become, especially if the regex is poorly constructed.

    Example

    Consider the regex pattern ^(a|b)*c$ and the input string aaaaaaab. The regex engine may try to match the string by considering all possible combinations of a and b, leading to a significant increase in processing time.

    Conclusion

    To avoid super-linear matches, it's essential to design regular expressions carefully, minimizing the use of nested quantifiers and ambiguous patterns. This can help ensure that the matching process remains efficient and operates within linear time complexity.

    Basically its trying to detect that the complexity is more ("super") than linear and turns on caching.

    Since the situation from starting from "c" without prior match is the same like with a prior "b" or "ab" the cached result of a FAIL can be used to shortcut the search when starting from "c", "d" and so on.

    Of course you could also apply the same mechanism with recursive regexes, but as I said the use cases are rare.

    Cheers

    - LanX (LogIn timing out again)

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom