Re^3: 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

"Detected a super-linear match, switching on caching..."

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) <Reveal this spoiler or all in this thread> 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]

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

https://stackoverflow.com/questions/12841970/how-can-i-recognize-an-evil-regex

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]