From unknown Tue Jun 17 01:46:50 2025 X-Loop: help-debbugs@gnu.org Subject: bug#10651: compiling pattern matching for (or ...) takes forever Resent-From: rixed@happyleptic.org Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-guile@gnu.org Resent-Date: Mon, 30 Jan 2012 10:12:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 10651 X-GNU-PR-Package: guile X-GNU-PR-Keywords: To: 10651@debbugs.gnu.org X-Debbugs-Original-To: bug-guile@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.132791827819208 (code B ref -1); Mon, 30 Jan 2012 10:12:02 +0000 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 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-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 unknown Tue Jun 17 01:46:50 2025 X-Loop: help-debbugs@gnu.org Subject: bug#10651: There should be a fix to this bug References: <20120130101036.GA20941@ccellier.rd.securactive.lan> In-Reply-To: <20120130101036.GA20941@ccellier.rd.securactive.lan> Resent-From: Stefan Israelsson Tampe Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-CC: bug-guile@gnu.org Resent-Date: Mon, 21 May 2012 20:53:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 10651 X-GNU-PR-Package: guile X-GNU-PR-Keywords: To: 10651@debbugs.gnu.org, foof@synthcode.com Received: via spool by 10651-submit@debbugs.gnu.org id=B10651.13376335353519 (code B ref 10651); Mon, 21 May 2012 20:53:01 +0000 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: From: Stefan Israelsson Tampe Content-Type: multipart/alternative; boundary=14dae9340639c4b69604c0920f1b X-Spam-Score: -2.6 (--) 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 unknown Tue Jun 17 01:46:50 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.428 (Entity 5.428) X-Loop: help-debbugs@gnu.org From: help-debbugs@gnu.org (GNU bug Tracking System) To: rixed@happyleptic.org Subject: bug#10651: closed (Re: bug#10651: There should be a fix to this bug) Message-ID: References: <87wr3i2ibp.fsf@gnu.org> <20120130101036.GA20941@ccellier.rd.securactive.lan> X-Gnu-PR-Message: they-closed 10651 X-Gnu-PR-Package: guile Reply-To: 10651@debbugs.gnu.org Date: Fri, 08 Jun 2012 10:48:02 +0000 Content-Type: multipart/mixed; boundary="----------=_1339152482-18960-1" This is a multi-part message in MIME format... ------------=_1339152482-18960-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #10651: compiling pattern matching for (or ...) takes forever which was filed against the guile package, has been closed. The explanation is attached below, along with your original report. If you require more details, please reply to 10651@debbugs.gnu.org. --=20 10651: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D10651 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1339152482-18960-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit 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. ------------=_1339152482-18960-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit 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. ------------=_1339152482-18960-1--