From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Kevin Rodgers Newsgroups: gmane.emacs.devel Subject: Re: Progressively slow pattern match Date: Wed, 17 May 2006 13:50:16 -0600 Organization: IHS Message-ID: References: <87ejysbg5d.fsf@neutrino.caeruleus.net> <851wusphnd.fsf@lola.goethe.zz> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: sea.gmane.org 1147895541 1982 80.91.229.2 (17 May 2006 19:52:21 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Wed, 17 May 2006 19:52:21 +0000 (UTC) Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed May 17 21:52:21 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 1FgS3o-0000qp-FD for ged-emacs-devel@m.gmane.org; Wed, 17 May 2006 21:51:57 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1FgS3o-00083S-0m for ged-emacs-devel@m.gmane.org; Wed, 17 May 2006 15:51:56 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1FgS3Q-0007vp-5l for emacs-devel@gnu.org; Wed, 17 May 2006 15:51:32 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1FgS3O-0007v3-Gw for emacs-devel@gnu.org; Wed, 17 May 2006 15:51:31 -0400 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1FgS3O-0007uy-CH for emacs-devel@gnu.org; Wed, 17 May 2006 15:51:30 -0400 Original-Received: from [80.91.229.2] (helo=ciao.gmane.org) by monty-python.gnu.org with esmtps (TLS-1.0:RSA_AES_256_CBC_SHA:32) (Exim 4.52) id 1FgS6J-0006LC-T4 for emacs-devel@gnu.org; Wed, 17 May 2006 15:54:32 -0400 Original-Received: from list by ciao.gmane.org with local (Exim 4.43) id 1FgS2z-0000hv-IW for emacs-devel@gnu.org; Wed, 17 May 2006 21:51:05 +0200 Original-Received: from 207.167.42.206 ([207.167.42.206]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Wed, 17 May 2006 21:51:05 +0200 Original-Received: from ihs_4664 by 207.167.42.206 with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Wed, 17 May 2006 21:51:05 +0200 X-Injected-Via-Gmane: http://gmane.org/ Original-To: emacs-devel@gnu.org Original-Lines: 36 Original-X-Complaints-To: usenet@sea.gmane.org X-Gmane-NNTP-Posting-Host: 207.167.42.206 User-Agent: Thunderbird 1.5.0.2 (Windows/20060308) In-Reply-To: <851wusphnd.fsf@lola.goethe.zz> 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:54646 Archived-At: David Kastrup wrote: > 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? Or even just "\\(%*\\)foo". -- Kevin