From unknown Wed Jun 18 23:04:54 2025 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailer: MIME-tools 5.509 (Entity 5.509) Content-Type: text/plain; charset=utf-8 From: bug#10651 <10651@debbugs.gnu.org> To: bug#10651 <10651@debbugs.gnu.org> Subject: Status: compiling pattern matching for (or ...) takes forever Reply-To: bug#10651 <10651@debbugs.gnu.org> Date: Thu, 19 Jun 2025 06:04:54 +0000 retitle 10651 compiling pattern matching for (or ...) takes forever reassign 10651 guile submitter 10651 rixed@happyleptic.org severity 10651 normal thanks From debbugs-submit-bounces@debbugs.gnu.org Mon Jan 30 05:11:18 2012 Received: (at submit) by debbugs.gnu.org; 30 Jan 2012 10:11:18 +0000 Received: from localhost ([127.0.0.1]:44609 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1RroCj-0004zk-Pr for submit@debbugs.gnu.org; Mon, 30 Jan 2012 05:11:18 -0500 Received: from eggs.gnu.org ([140.186.70.92]:49675) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1RroCh-0004zY-Tx for submit@debbugs.gnu.org; Mon, 30 Jan 2012 05:11:16 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1RroCS-0003xk-U0 for submit@debbugs.gnu.org; Mon, 30 Jan 2012 05:11:01 -0500 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,T_RP_MATCHES_RCVD autolearn=unavailable version=3.3.2 Received: from lists.gnu.org ([140.186.70.17]:58775) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RroCS-0003xg-SS for submit@debbugs.gnu.org; Mon, 30 Jan 2012 05:11:00 -0500 Received: from eggs.gnu.org ([140.186.70.92]:42358) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RroCN-00042E-2p for bug-guile@gnu.org; Mon, 30 Jan 2012 05:11:00 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1RroCG-0003xL-UB for bug-guile@gnu.org; Mon, 30 Jan 2012 05:10:54 -0500 Received: from eneide.happyleptic.org ([213.251.171.101]:36804) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RroCG-0003wj-MV for bug-guile@gnu.org; Mon, 30 Jan 2012 05:10:48 -0500 Received: from extranet.securactive.org ([82.234.213.170] helo=ccellier.rd.securactive.lan) by eneide.happyleptic.org with esmtp (Exim 4.72) (envelope-from ) id 1RroRA-0004OH-1r for bug-guile@gnu.org; Mon, 30 Jan 2012 11:26:12 +0100 Received: from rixed by ccellier.rd.securactive.lan with local (Exim 4.72) (envelope-from ) id 1RroC4-0005b7-KA for bug-guile@gnu.org; Mon, 30 Jan 2012 11:10:36 +0100 Date: Mon, 30 Jan 2012 11:10:36 +0100 From: rixed@happyleptic.org To: bug-guile@gnu.org Subject: compiling pattern matching for (or ...) takes forever Message-ID: <20120130101036.GA20941@ccellier.rd.securactive.lan> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-06-14) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 140.186.70.17 X-Spam-Score: -4.2 (----) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -4.2 (----) Not really a bug per se (although the manual states that "When Guile hangs or takes forever to complete a task, it is a bug."), but the time complexity behind the compilation of (or ...) patterns in (ice-9 match) module is so high that anything more than 8 sub-patterns takes forever for me. Here is a short demonstration of the problem: % time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b)) 'ab])" 0.06s user 0.00s system 102% cpu 0.054 total % time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b)) 'ab])" 0.13s user 0.01s system 99% cpu 0.136 total % time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b) ('a 'b)) 'ab])" 0.44s user 0.01s system 100% cpu 0.443 total % time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b)) 'ab])" 1.78s user 0.01s system 100% cpu 1.792 total % time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b)) 'ab])" 7.28s user 0.02s system 100% cpu 7.308 total % time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b)) 'ab])" 29.31s user 1.50s system 99% cpu 30.823 total % time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b)) 'ab])" 133.75s user 0.14s system 99% cpu 2:13.94 total % time guile -c "([@ (ice-9 match) match] '(a b) [(or ('a 'b) ('a 'b) % ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) ('a 'b) 'ab])" ? It's easy to work around by splitting the or in smaller chunks but it can take some time to understand why the compiler hangs. I believe such time complexity behavior should be advertised in the manual. From debbugs-submit-bounces@debbugs.gnu.org Mon May 21 16:52:15 2012 Received: (at 10651) by debbugs.gnu.org; 21 May 2012 20:52:15 +0000 Received: from localhost ([127.0.0.1]:37672 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1SWZaR-0000ui-0h for submit@debbugs.gnu.org; Mon, 21 May 2012 16:52:15 -0400 Received: from mail-yw0-f44.google.com ([209.85.213.44]:56883) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1SWZa6-0000tr-Jz for 10651@debbugs.gnu.org; Mon, 21 May 2012 16:52:13 -0400 Received: by yhq56 with SMTP id 56so4697204yhq.3 for <10651@debbugs.gnu.org>; Mon, 21 May 2012 13:51:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=ZaUNuysTTT72lS5EFZHQG3So1VwXrWIPvZofIagV00g=; b=0/hxrR9FwZHpSGfvW+8m/nltpeonLaZRuCn2s8Gp3nyhzm7OVgw7Ykw+PeETH1iwRk bQJnV3SBrK6T0Lfk58gNXGZKRVhKwJPDCcFfUUiKPkO0pjmLJKv6jkPEH5NZjtHprYSq c2yuf7129t8nreG951kYSrWP8wKfsEuMF6WlL2KDRr822L5lIJD3R6tl4FKSBmWuJSMG rkKF8rEsHl1oRHBxscdjFa1JC7F/Rfl23M4QaR4uRVHGj7ZdRwqqLKfpeMzCPUB00PMr ZhwKdNT0ol4iH2sYzbqoTKNB6bLNuARv3hbwSZ+yltoOD921IruSXroGUnO/4Or8gkBU 4fcA== MIME-Version: 1.0 Received: by 10.50.51.132 with SMTP id k4mr7787487igo.17.1337633469150; Mon, 21 May 2012 13:51:09 -0700 (PDT) Received: by 10.50.242.102 with HTTP; Mon, 21 May 2012 13:51:09 -0700 (PDT) Date: Mon, 21 May 2012 22:51:09 +0200 Message-ID: Subject: There should be a fix to this bug From: Stefan Israelsson Tampe To: 10651@debbugs.gnu.org, foof@synthcode.com Content-Type: multipart/alternative; boundary=14dae9340639c4b69604c0920f1b X-Spam-Score: -2.6 (--) X-Debbugs-Envelope-To: 10651 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -2.6 (--) --14dae9340639c4b69604c0920f1b Content-Type: text/plain; charset=ISO-8859-1 Hi, In the compilation of the or pattern the sk is made a lambda but not the fk hence the observed geometric explosion. I have a fix for this that works but intend to talk with foof about it to fix ithe upstream matcher. There is really no need to change the doc The fix is easy (I beleve). Actually a small diff for it shows shows, 482,483c482 < (let ((ffk (lambda () (match-gen-or-step v q g+s sk fk i)))) < (match-one v p g+s sk (ffk) i))) --- > (match-one v p g+s sk (match-gen-or-step v q g+s sk fk i) i)) /Stefan --14dae9340639c4b69604c0920f1b Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Hi,

In the compilation of the or pattern the sk is made a lambda but not the fk hence the observed geometric explosion. I have a fix
fo= r this that works but intend to talk with foof about it
to fix ithe upst= ream matcher. There is really no need to change the doc

The fix is easy (I beleve). Actually a small diff for it shows shows,
482,483c482
<=A0=A0=A0=A0=A0 (let ((ffk (lambda () (match-gen-o= r-step v q g+s sk fk i))))
<=A0=A0=A0=A0=A0=A0=A0 (match-one v p g+s = sk (ffk) i)))
---
>=A0=A0=A0=A0=A0 (match-one v p g+s sk (match-gen-or-step v q g+s sk fk = i) i))

/Stefan
--14dae9340639c4b69604c0920f1b-- From debbugs-submit-bounces@debbugs.gnu.org Fri Jun 08 06:47:39 2012 Received: (at 10651-done) by debbugs.gnu.org; 8 Jun 2012 10:47:39 +0000 Received: from localhost ([127.0.0.1]:34378 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1ScwjD-0004vA-Iz for submit@debbugs.gnu.org; Fri, 08 Jun 2012 06:47:39 -0400 Received: from xanadu.aquilenet.fr ([88.191.123.111]:50425) by debbugs.gnu.org with esmtp (Exim 4.72) (envelope-from ) id 1ScwjB-0004v3-5l for 10651-done@debbugs.gnu.org; Fri, 08 Jun 2012 06:47:38 -0400 Received: from localhost (localhost [127.0.0.1]) by xanadu.aquilenet.fr (Postfix) with ESMTP id F02AF72C1; Fri, 8 Jun 2012 12:45:16 +0200 (CEST) Received: from xanadu.aquilenet.fr ([127.0.0.1]) by localhost (xanadu.aquilenet.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 2tMioXr2Mdwm; Fri, 8 Jun 2012 12:45:16 +0200 (CEST) Received: from pluto (reverse-83.fdn.fr [80.67.176.83]) by xanadu.aquilenet.fr (Postfix) with ESMTPSA id 43A536F02; Fri, 8 Jun 2012 12:45:16 +0200 (CEST) From: ludo@gnu.org (Ludovic =?iso-8859-1?Q?Court=E8s?=) To: Stefan Israelsson Tampe Subject: Re: bug#10651: There should be a fix to this bug References: <20120130101036.GA20941@ccellier.rd.securactive.lan> Date: Fri, 08 Jun 2012 12:45:14 +0200 In-Reply-To: (Stefan Israelsson Tampe's message of "Mon, 21 May 2012 22:51:09 +0200") Message-ID: <87wr3i2ibp.fsf@gnu.org> User-Agent: Gnus/5.130005 (Ma Gnus v0.5) Emacs/24.0.93 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: -1.2 (-) X-Debbugs-Envelope-To: 10651-done Cc: foof@synthcode.com, 10651-done@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -1.2 (-) Hello! I updated (ice-9 match) from Chibi as recommended by Stefan, and it appears to fix the problem for me. Thanks! Ludo=E2=80=99. From unknown Wed Jun 18 23:04:54 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Fri, 06 Jul 2012 11:24:03 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator