[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Documentation on debugging regexp performance
From: |
Alan Mackenzie |
Subject: |
Re: Documentation on debugging regexp performance |
Date: |
Thu, 21 Jan 2016 17:16:07 +0000 |
User-agent: |
Mutt/1.5.24 (2015-08-30) |
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).