From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.emacs.devel Subject: Re: Progressively slow pattern match Date: Wed, 17 May 2006 21:37:10 +0200 Message-ID: <851wusphnd.fsf@lola.goethe.zz> References: <87ejysbg5d.fsf@neutrino.caeruleus.net> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: sea.gmane.org 1147894673 31254 80.91.229.2 (17 May 2006 19:37:53 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Wed, 17 May 2006 19:37:53 +0000 (UTC) Cc: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed May 17 21:37:52 2006 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by ciao.gmane.org with esmtp (Exim 4.43) id 1FgRqA-0006TM-U9 for ged-emacs-devel@m.gmane.org; Wed, 17 May 2006 21:37:51 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1FgRqA-0002lH-Dk for ged-emacs-devel@m.gmane.org; Wed, 17 May 2006 15:37:50 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1FgRpw-0002kP-Rh for emacs-devel@gnu.org; Wed, 17 May 2006 15:37:37 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1FgRpu-0002i6-N8 for emacs-devel@gnu.org; Wed, 17 May 2006 15:37:35 -0400 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1FgRpu-0002hd-Eg for emacs-devel@gnu.org; Wed, 17 May 2006 15:37:34 -0400 Original-Received: from [199.232.76.164] (helo=fencepost.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.52) id 1FgRsp-00051m-MS for emacs-devel@gnu.org; Wed, 17 May 2006 15:40:36 -0400 Original-Received: from localhost ([127.0.0.1] helo=lola.goethe.zz) by fencepost.gnu.org with esmtp (Exim 4.34) id 1FgRpt-0005KD-En; Wed, 17 May 2006 15:37:33 -0400 Original-Received: by lola.goethe.zz (Postfix, from userid 1002) id 4DA871C40B51; Wed, 17 May 2006 21:37:11 +0200 (CEST) Original-To: Ralf Angeli In-Reply-To: <87ejysbg5d.fsf@neutrino.caeruleus.net> (Ralf Angeli's message of "Wed, 17 May 2006 21:33:18 +0200") User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.0.50 (gnu/linux) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:54644 Archived-At: Ralf Angeli writes: > In AUCTeX there is a regexp used with `looking-at' where pattern > matching seems to progressively get slower the longer a part of the > (possible) match gets. I reduced the regexp to a bare minimum for > testing and the code now looks something like this: > > (looking-at "\\(%+\\)*foo") > > The problem occurs if this is used against a line with only % > characters in it. The more of these characters there are the slower > it gets. I checked the time one call of `looking-at' takes with > (abs (- (float-time) (progn (looking-at "\\(%+\\)*foo") (float-time)))) > and got the following results (in seconds): > > %%%%%%%%%% 0.0006 > %%%%%%%%%%%%%%% 0.0154 > %%%%%%%%%%%%%%%%%%%% 0.5132 > %%%%%%%%%%%%%%%%%%%%%%%%% 7.8058 > > The regexp is used with `looking-at' for checking if there are LaTeX > macros which have to be treated specially during paragraph movement. > As paragraph movement is used quite extensively when a region is to be > filled, users might get the notion that they are experiencing a hang > if they have such line for visually separating parts in the file. > > Is this a deficiency in Emacs? Is there a way matching can be sped up > with this or maybe another, equivalent regexp? Uh, "\\(%+\\)?foo" maybe? -- David Kastrup, Kriemhildstr. 15, 44793 Bochum