From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: rixed@happyleptic.org Newsgroups: gmane.lisp.guile.bugs Subject: bug#10651: compiling pattern matching for (or ...) takes forever Date: Mon, 30 Jan 2012 11:10:36 +0100 Message-ID: <20120130101036.GA20941@ccellier.rd.securactive.lan> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1327918328 20203 80.91.229.3 (30 Jan 2012 10:12:08 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Mon, 30 Jan 2012 10:12:08 +0000 (UTC) To: 10651@debbugs.gnu.org Original-X-From: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Mon Jan 30 11:12:07 2012 Return-path: Envelope-to: guile-bugs@m.gmane.org Original-Received: from lists.gnu.org ([140.186.70.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1RroDW-0008TZ-Sq for guile-bugs@m.gmane.org; Mon, 30 Jan 2012 11:12:07 +0100 Original-Received: from localhost ([::1]:38373 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RroDU-00048k-4f for guile-bugs@m.gmane.org; Mon, 30 Jan 2012 05:12:04 -0500 Original-Received: from eggs.gnu.org ([140.186.70.92]:42445) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RroDM-00048f-KU for bug-guile@gnu.org; Mon, 30 Jan 2012 05:12:02 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1RroDK-00040P-8a for bug-guile@gnu.org; Mon, 30 Jan 2012 05:11:56 -0500 Original-Received: from debbugs.gnu.org ([140.186.70.43]:40986) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RroDK-00040F-72 for bug-guile@gnu.org; Mon, 30 Jan 2012 05:11:54 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.72) (envelope-from ) id 1RroDS-00050l-QU for bug-guile@gnu.org; Mon, 30 Jan 2012 05:12:02 -0500 X-Loop: help-debbugs@gnu.org 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: X-Debbugs-Original-To: bug-guile@gnu.org Original-Received: via spool by submit@debbugs.gnu.org id=B.132791827819208 (code B ref -1); Mon, 30 Jan 2012 10:12:02 +0000 Original-Received: (at submit) by debbugs.gnu.org; 30 Jan 2012 10:11:18 +0000 Original-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 Original-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 Original-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 Original-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 Original-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 Original-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 Original-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 Original-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 Original-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 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-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.13 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 2) X-Received-From: 140.186.70.43 X-BeenThere: bug-guile@gnu.org List-Id: "Bug reports for GUILE, GNU's Ubiquitous Extension Language" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Original-Sender: bug-guile-bounces+guile-bugs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.bugs:6112 Archived-At: 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.