Re: Progressively slow pattern match

[Kevin Rodgers <ihs_4664@yahoo.com>]

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