Re: Documentation on debugging regexp performance

[Alan Mackenzie]

Hello, Clément.

On Thu, Jan 21, 2016 at 12:29:58AM -0500, Clément Pit--Claudel wrote:
> Hi emacs-devel,

> I'm running into a surprising regular expressions issue. I have
> attached a file (~50k) in which (re-search-forward "   +[^:=]+ +:=?")
> seems to be extremely slow. (I killed it after 30 seconds). Truncating
> the file to its first 20 lines reduces the time for re-search-forward
> to about a second, which is still extremely slow. 

> Are there good resources on how to rewrite regexps to make them
> Emacs-friendly? I didn't find such documentation, and I'm puzzled as to
> what could make the regexp above hard to re-search-forward for.

> Cheers,
> Clément.

"   +[^:=]+ +:=?" is an ill-formed regexp - if you get lots of spaces in
a non-match, the Emacs regexp engine will try all possible ways of
matching these spaces before giving up.  You have three concatenated
sub-expressions, all of which match any number of spaces, namely:

   " +[^:=]+ +"
    1122222233

I would suggest reformulating it thus:

   " +[^:= ][^:=]+ "
    112222223333334

Subexpression 1 matches ALL the leading spaces.  Subexp 2 is exactly one
character which can't be a space.  Subexp 3 matches almost anything,
including spaces, and subexp 4 matches a single space at the end (to make
sure there is at least one space there).

All the best with your regexp!

-- 
Alan Mackenzie (Nuremberg, Germany).