From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Noam Postavsky Newsgroups: gmane.emacs.bugs 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 Message-ID: References: NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: ger.gmane.org 1465593263 7047 80.91.229.3 (10 Jun 2016 21:14:23 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 10 Jun 2016 21:14:23 +0000 (UTC) Cc: Ryan Rix , michael@cadilhac.name To: 6640@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Fri Jun 10 23:14:14 2016 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1bBTks-00075H-Be for geb-bug-gnu-emacs@m.gmane.org; Fri, 10 Jun 2016 23:14:14 +0200 Original-Received: from localhost ([::1]:44461 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bBTko-00059A-1R for geb-bug-gnu-emacs@m.gmane.org; Fri, 10 Jun 2016 17:14:10 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:47043) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bBTkj-000593-5M for bug-gnu-emacs@gnu.org; Fri, 10 Jun 2016 17:14:06 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bBTkf-0007NQ-Vd for bug-gnu-emacs@gnu.org; Fri, 10 Jun 2016 17:14:05 -0400 Original-Received: from debbugs.gnu.org ([208.118.235.43]:52186) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bBTkf-0007NM-Qz for bug-gnu-emacs@gnu.org; Fri, 10 Jun 2016 17:14:01 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1bBTkf-0006hp-PH for bug-gnu-emacs@gnu.org; Fri, 10 Jun 2016 17:14:01 -0400 X-Loop: help-debbugs@gnu.org In-Reply-To: Resent-From: Noam Postavsky Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 10 Jun 2016 21:14:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 6640 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: Original-Received: via spool by 6640-submit@debbugs.gnu.org id=B6640.146559320425715 (code B ref 6640); Fri, 10 Jun 2016 21:14:01 +0000 Original-Received: (at 6640) by debbugs.gnu.org; 10 Jun 2016 21:13:24 +0000 Original-Received: from localhost ([127.0.0.1]:36290 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bBTk3-0006gh-VA for submit@debbugs.gnu.org; Fri, 10 Jun 2016 17:13:24 -0400 Original-Received: from mail-oi0-f49.google.com ([209.85.218.49]:34791) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bBTk1-0006gV-T3 for 6640@debbugs.gnu.org; Fri, 10 Jun 2016 17:13:22 -0400 Original-Received: by mail-oi0-f49.google.com with SMTP id d132so27283890oig.1 for <6640@debbugs.gnu.org>; Fri, 10 Jun 2016 14:13:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:from:date:message-id:subject:to:cc; bh=W+GrdbD2e90RdSCIBbZGbvnXKCapNmJ2kyGxjBSjYYA=; b=EMfGVnRxjAZSpwKP1ZHZQ3EB+TArcfpsNNyy+UsxyvMjuICRFUckPHSgPHP7e9qPUc Hud3QjsVxnvj7+/8Q232XN0K2bcjJLMjAjp8Ke9IyWzA31OtIBbZvvvd4M5NyFqvYuu3 cvSgHy5GIBdFDde+5y25lWvc7MlSqfqj5KsWNoVCwilmpOHOQmCIPpk8PVE+k1IhLod9 dicaRSu8vj7jQT/dvJBynQ+plmzz+GKouVLHXgu9cVn8ps+H5ov6GHkdO3VC6XYjRew1 VGSIVd7e642tGKfwH6JVn5Jma/YkIr9V60Qxs6MAKVsFpBYY3Mj793pRlkLzApIUfqfK idgg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:sender:from:date:message-id:subject :to:cc; bh=W+GrdbD2e90RdSCIBbZGbvnXKCapNmJ2kyGxjBSjYYA=; b=C1QlJsRtvGPO/hNWGb8GkSeHZK1QBSLTPgNpWcfpejhok60ARi18ZgzmISi9OZxMI3 SGkK1v5hzAADwFIy72JdlebFIAhxRBmXy0mgZYZNGpxa38hhMcz4U5D6zK2OX1Hr5sbZ yI8iWUPRzhzszB7dMq7hbRu4+cOcM1cgUYz1QVnOw2BxbZccDdxB1FKuvKYEg1e2pxaX hSXSc4qYSJAG1YMRxVjA+Mb67o043vxUsjZeL7m7lioZTTURFoYToshycuCB2dcfiX1m NEETwZaFMFio4nDmB2fWJY0heM/89gAKfFskHmSczm0dL+kJM0SIZl8F8g+eEqb/o3KL 7pIg== X-Gm-Message-State: ALyK8tLPrduFPvXq/1c6+/Fu8FMqWYBNgiC9GaAt1HEj8/SWm1w3M2aLq95otvYr7UfHEDDRcOiw1YSj1hKuBw== X-Received: by 10.157.29.10 with SMTP id m10mr2512978otm.196.1465593196488; Fri, 10 Jun 2016 14:13:16 -0700 (PDT) Original-Received: by 10.157.5.168 with HTTP; Fri, 10 Jun 2016 14:13:16 -0700 (PDT) X-Google-Sender-Auth: a6e1tL5ZRTu39r-DUDzwksHkTtY X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 208.118.235.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.org gmane.emacs.bugs:119398 Archived-At: 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.