GNU bug report logs - #6640
23.2; Why is this regexp search taking so long? (and will it end?)

Previous Next

Full log

View this message in rfc822 format

From: Noam Postavsky <npostavs <at> users.sourceforge.net>
To: 6640 <at> debbugs.gnu.org
Cc: Ryan Rix <ryan <at> whatthefuck.computer>, michael <at> cadilhac.name
Subject: bug#6640: 23.2; Why is this regexp search taking so long? (and will it end?)
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.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.