Subject: Re: bug#6640: 23.2; Why is this regexp search taking so long? (and will it end?)

From: Noam Postavsky <[email-masked]>
Date: Fri, 10 Jun 2016 17:13:16 -0400

I haven't actually debugged the regexp engine, but I believe the
problem is that this regexp contains several repetitions of [^:]*[^:]*
(which becomes apparent if you expand the \{9\}). The regexp engine
isn't smart enough to coalesce them so when the match fails (due to
$), it has to go back and retry with all the possible different
matches to see if it will work that way. There are A^n possible
matches to try, where A is the length of non-colon string in the
buffer, and n is the number of [^:]*[^:]* sequences in the regexp
(which is 8 if \{9\} is used).

A regexp which should match the same thing is ^\([^:]*:\)\{9\}[^:]*
and ^\([^:]*:\)\{9\}[^:]*$ will fail to match anything much faster.