Re: Re (tilly) 1: Avoiding regex backtracking

This snippet shows very different behavior in 5.6.1 and 5.00503. In the earlier version I see the exponential execution time, but in 5.6.1 it seems to do *much* better. Do you know of any improvements in perl that might account for this?

-Blake

Comment on Re: Re (tilly) 1: Avoiding regex backtracking

Replies are listed 'Best First'.
Re (tilly) 3: Avoiding regex backtracking by tilly (Archbishop) on Mar 13, 2002 at 03:37 UTC
Yes. In 5.6 the engine keeps track of how long "complex RE's" are taking to match. If it is too long, then it redoes it while keeping a history of visited positions. This will reduce the worst case scenario from exponential to polynomial (unless, of course, you use backreferences). There is, however, an optimization that I know of which would turn this into straight linear behaviour. I gave a basic sketch of the idea at Re (tilly) 1: Research ideas, but to the best of my knowledge nobody has ever implemented it in any real RE engine...	[reply]

Replies are listed 'Best First'.

Re (tilly) 3: Avoiding regex backtracking
by tilly (Archbishop) on Mar 13, 2002 at 03:37 UTC

In 5.6 the engine keeps track of how long "complex RE's" are taking to match. If it is too long, then it redoes it while keeping a history of visited positions. This will reduce the worst case scenario from exponential to polynomial (unless, of course, you use backreferences).

There is, however, an optimization that I know of which would turn this into straight linear behaviour. I gave a basic sketch of the idea at Re (tilly) 1: Research ideas, but to the best of my knowledge nobody has ever implemented it in any real RE engine...

[reply]