Re: Documentation on debugging regexp performance

[Alan Mackenzie <acm@muc.de>]

Hello again Clément.

On Thu, Jan 21, 2016 at 11:37:48AM -0500, Clément Pit--Claudel wrote:
> On 01/21/2016 10:27 AM, Alan Mackenzie wrote:
> Hi Alan!

> > "   +[^:=]+ +:=?" 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

> I think this has different semantics: my original regexp requires at
> least three spaces. But I think prepending spaces to yours fixes that.

Sorry, yes, I'd extracted the interesting bit of your regexp, and forgot
that I'd done so.

> > 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).

> This is helpful, thanks! I realize however that maybe I
> oversimplified. The issue is that what I really want is something like
> this:

> "   +\\([^:=]+\\) +:=?"

> IOW, I want to capture that first group.

That is ambiguous.  But if we can assume that the first group always
begins with a non-space, and always ends with a non-space, then we can
reformulate the above as:

    "   +\\([^:= ]\\([^:=]+[^:= ]\\)?\\) +:=?"
                                    ^

(or something similar - I've not actually tested it).  The ? inside the
first expression is to cope with there just being 1 single character
matched by the group.

> > All the best with your regexp!

> Thanks. Your points about backtracking were helpful as well. Do you
> know if there are technical reasons why Emacs chooses a backtracking
> implementation for this regexp (instead of compiling it to a
> linear-time matcher)?

I'm afraid I don't know.  It might be that compiling a regexp for a
linear-time matcher would be slower.  Or, possibly, nobody has sat down
and hacked out a better regexp engine.

> Clément.

-- 
Alan Mackenzie (Nuremberg, Germany).