Progressively slow pattern match

Progressively slow pattern match

[Ralf Angeli]

In AUCTeX there is a regexp used with `looking-at' where pattern
matching seems to progressively get slower the longer a part of the
(possible) match gets.  I reduced the regexp to a bare minimum for
testing and the code now looks something like this:

(looking-at "\\(%+\\)*foo")

The problem occurs if this is used against a line with only %
characters in it.  The more of these characters there are the slower
it gets.  I checked the time one call of `looking-at' takes with
(abs (- (float-time) (progn (looking-at "\\(%+\\)*foo") (float-time))))
and got the following results (in seconds):

%%%%%%%%%%                 0.0006
%%%%%%%%%%%%%%%            0.0154
%%%%%%%%%%%%%%%%%%%%       0.5132
%%%%%%%%%%%%%%%%%%%%%%%%%  7.8058

The regexp is used with `looking-at' for checking if there are LaTeX
macros which have to be treated specially during paragraph movement.
As paragraph movement is used quite extensively when a region is to be
filled, users might get the notion that they are experiencing a hang
if they have such line for visually separating parts in the file.

Is this a deficiency in Emacs?  Is there a way matching can be sped up
with this or maybe another, equivalent regexp?

-- 
Ralf

Re: Progressively slow pattern match

[David Kastrup]

Ralf Angeli <angeli@caeruleus.net> writes:

> In AUCTeX there is a regexp used with `looking-at' where pattern
> matching seems to progressively get slower the longer a part of the
> (possible) match gets.  I reduced the regexp to a bare minimum for
> testing and the code now looks something like this:
>
> (looking-at "\\(%+\\)*foo")
>
> The problem occurs if this is used against a line with only %
> characters in it.  The more of these characters there are the slower
> it gets.  I checked the time one call of `looking-at' takes with
> (abs (- (float-time) (progn (looking-at "\\(%+\\)*foo") (float-time))))
> and got the following results (in seconds):
>
> %%%%%%%%%%                 0.0006
> %%%%%%%%%%%%%%%            0.0154
> %%%%%%%%%%%%%%%%%%%%       0.5132
> %%%%%%%%%%%%%%%%%%%%%%%%%  7.8058
>
> The regexp is used with `looking-at' for checking if there are LaTeX
> macros which have to be treated specially during paragraph movement.
> As paragraph movement is used quite extensively when a region is to be
> filled, users might get the notion that they are experiencing a hang
> if they have such line for visually separating parts in the file.
>
> Is this a deficiency in Emacs?  Is there a way matching can be sped up
> with this or maybe another, equivalent regexp?

Uh, "\\(%+\\)?foo" maybe?

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Progressively slow pattern match

[Kevin Rodgers]

David Kastrup wrote:
> Ralf Angeli <angeli@caeruleus.net> writes:
> 
>> In AUCTeX there is a regexp used with `looking-at' where pattern
>> matching seems to progressively get slower the longer a part of the
>> (possible) match gets.  I reduced the regexp to a bare minimum for
>> testing and the code now looks something like this:
>>
>> (looking-at "\\(%+\\)*foo")
>>
>> The problem occurs if this is used against a line with only %
>> characters in it.  The more of these characters there are the slower
>> it gets.  I checked the time one call of `looking-at' takes with
>> (abs (- (float-time) (progn (looking-at "\\(%+\\)*foo") (float-time))))
>> and got the following results (in seconds):
>>
>> %%%%%%%%%%                 0.0006
>> %%%%%%%%%%%%%%%            0.0154
>> %%%%%%%%%%%%%%%%%%%%       0.5132
>> %%%%%%%%%%%%%%%%%%%%%%%%%  7.8058
>>
>> The regexp is used with `looking-at' for checking if there are LaTeX
>> macros which have to be treated specially during paragraph movement.
>> As paragraph movement is used quite extensively when a region is to be
>> filled, users might get the notion that they are experiencing a hang
>> if they have such line for visually separating parts in the file.
>>
>> Is this a deficiency in Emacs?  Is there a way matching can be sped up
>> with this or maybe another, equivalent regexp?
> 
> Uh, "\\(%+\\)?foo" maybe?

Or even just "\\(%*\\)foo".

-- 
Kevin

Re: Progressively slow pattern match

[Ralf Angeli]

* David Kastrup (2006-05-17) writes:

> Ralf Angeli <angeli@caeruleus.net> writes:
>
>> (looking-at "\\(%+\\)*foo")
[...]
>> Is this a deficiency in Emacs?  Is there a way matching can be sped up
>> with this or maybe another, equivalent regexp?
>
> Uh, "\\(%+\\)?foo" maybe?

The original regexp looks something like
"\\(%+[ \t]*\\)*foo"
in order to match stuff like
%% %% %% foo

-- 
Ralf

Re: Progressively slow pattern match

[Alan Mackenzie]

'n Abend, Ralf!

On Wed, 17 May 2006, Ralf Angeli wrote:

>In AUCTeX there is a regexp used with `looking-at' where pattern
>matching seems to progressively get slower the longer a part of the
>(possible) match gets.  I reduced the regexp to a bare minimum for
>testing and the code now looks something like this:

>(looking-at "\\(%+\\)*foo")

>The problem occurs if this is used against a line with only %
>characters in it.  The more of these characters there are the slower
>it gets.  I checked the time one call of `looking-at' takes with
>(abs (- (float-time) (progn (looking-at "\\(%+\\)*foo") (float-time))))
>and got the following results (in seconds):

>%%%%%%%%%%                 0.0006
>%%%%%%%%%%%%%%%            0.0154
>%%%%%%%%%%%%%%%%%%%%       0.5132
>%%%%%%%%%%%%%%%%%%%%%%%%%  7.8058

>The regexp is used with `looking-at' for checking if there are LaTeX
>macros which have to be treated specially during paragraph movement.
>As paragraph movement is used quite extensively when a region is to be
>filled, users might get the notion that they are experiencing a hang
>if they have such line for visually separating parts in the file.

>Is this a deficiency in Emacs?  Is there a way matching can be sped up
>with this or maybe another, equivalent regexp?

It's a bad regexp.  It's got a sort of ambiguity, in that you've got both
a "+" and a "*" on the "%" you want to match.  The number of ways %+* can
divide a row of n %s is the number of ordered partions of n[*].  The
Emacs regexp engine tries out ALL of these, I think.  Each time it comes
to the non-% at the end, it goes back to try a different subdivision, to
see if that gives a longer match.  Evidently, each % you add doubles the
time the regexp engine takes, approximately (though I suspect that for
your last timining, the jump was only 4%, not 5%).

And yes, I've done this too.  :-(  The solution is to write either %+ or
%*, but not both together.

[*] As in, 4 = 3 + 1
             = 2 + 1 + 1
             = 1 + 2 + 1
             = 1 + 3
             = 2 + 2 
             = 1 + 1 + 2
             = 1 + 1 + 1 + 1



>Ralf

-- 
Alan.

Re: Progressively slow pattern match

[Alan Mackenzie]

On Wed, 17 May 2006, Ralf Angeli wrote:

>* David Kastrup (2006-05-17) writes:

>> Ralf Angeli <angeli@caeruleus.net> writes:

>>> (looking-at "\\(%+\\)*foo")
>[...]
>>> Is this a deficiency in Emacs?  Is there a way matching can be sped up
>>> with this or maybe another, equivalent regexp?

>> Uh, "\\(%+\\)?foo" maybe?

>The original regexp looks something like
>"\\(%+[ \t]*\\)*foo"
>in order to match stuff like
>%% %% %% foo

Use "\\(%+[ \t]+\\)%*foo"
               ^
instead

>Ralf

-- 
Alan.

Re: Progressively slow pattern match

[David Kastrup]

Ralf Angeli <angeli@caeruleus.net> writes:

> * David Kastrup (2006-05-17) writes:
>
>> Ralf Angeli <angeli@caeruleus.net> writes:
>>
>>> (looking-at "\\(%+\\)*foo")
> [...]
>>> Is this a deficiency in Emacs?  Is there a way matching can be sped up
>>> with this or maybe another, equivalent regexp?
>>
>> Uh, "\\(%+\\)?foo" maybe?
>
> The original regexp looks something like
> "\\(%+[ \t]*\\)*foo"
> in order to match stuff like
> %% %% %% foo

"\\(%[% \t]*\\)foo"

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Progressively slow pattern match

[Stuart D. Herring]

> The original regexp looks something like
> "\\(%+[ \t]*\\)*foo"
> in order to match stuff like
> %% %% %% foo

Try "\\(%+\\(?:[ \t]+%+\\)*\\)"?  I think that should avoid invoking the
backtracker for long strings of %.

Davis

-- 
This product is sold by volume, not by mass.  If it appears too dense or
too sparse, it is because mass-energy conversion has occurred during
shipping.

Re: Progressively slow pattern match

[Ralf Angeli]

* Alan Mackenzie (2006-05-17) writes:

> On Wed, 17 May 2006, Ralf Angeli wrote:
>
>>The original regexp looks something like
>>"\\(%+[ \t]*\\)*foo"
>>in order to match stuff like
>>%% %% %% foo
>
> Use "\\(%+[ \t]+\\)%*foo"

Thanks for all the explanations and suggestions, also from Kevin,
David and Stuart.  So it really was a badly written regexp. \c:

I think I'll settle with
"\\(%[% \t]*\\)?foo"
That means David's suggestion with an added "?" in order for it to
match a bare "foo" without preceding comment characters as well.  For
me it looks like the one easiest to understand.

-- 
Ralf

Re: Progressively slow pattern match

[Richard Stallman]

This problem is documented under the definition of * in regexps in the
Lisp manual.  I made the text a little clearer and a little louder, in case
that helps.