From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Ralf Angeli Newsgroups: gmane.emacs.devel Subject: Progressively slow pattern match Date: Wed, 17 May 2006 21:33:18 +0200 Message-ID: <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 1147894454 30577 80.91.229.2 (17 May 2006 19:34:14 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Wed, 17 May 2006 19:34:14 +0000 (UTC) Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed May 17 21:34:12 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 1FgRmZ-0005jl-V6 for ged-emacs-devel@m.gmane.org; Wed, 17 May 2006 21:34:08 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1FgRmZ-0007Vz-Df for ged-emacs-devel@m.gmane.org; Wed, 17 May 2006 15:34:07 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1FgRm6-0007V6-ON for emacs-devel@gnu.org; Wed, 17 May 2006 15:33:38 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1FgRm5-0007Th-7V for emacs-devel@gnu.org; Wed, 17 May 2006 15:33:38 -0400 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1FgRm5-0007TV-0w for emacs-devel@gnu.org; Wed, 17 May 2006 15:33:37 -0400 Original-Received: from [212.227.126.177] (helo=moutng.kundenserver.de) by monty-python.gnu.org with esmtp (Exim 4.52) id 1FgRp0-0004Jd-6C for emacs-devel@gnu.org; Wed, 17 May 2006 15:36:38 -0400 Original-Received: from [212.144.211.96] (helo=neutrino.caeruleus.net) by mrelayeu.kundenserver.de (node=mrelayeu3) with ESMTP (Nemesis), id 0MKxQS-1FgRm226OQ-0006kJ; Wed, 17 May 2006 21:33:35 +0200 Original-To: emacs-devel@gnu.org X-Provags-ID: kundenserver.de abuse@kundenserver.de login:abf9ffac21f8345504ac40c53d3b40ba 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:54643 Archived-At: 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? -- Ralf