GNU bug report logs - #10651
compiling pattern matching for (or ...) takes forever

Previous Next

Package: guile;

Reported by: rixed <at> happyleptic.org

Date: Mon, 30 Jan 2012 10:12:02 UTC

Severity: normal

Done: ludo <at> gnu.org (Ludovic Courtès)

Bug is archived. No further changes may be made.

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 10651 in the body.
You can then email your comments to 10651 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

View this report as an mbox folder, status mbox, maintainer mbox


Report forwarded to bug-guile <at> gnu.org:
bug#10651; Package guile. (Mon, 30 Jan 2012 10:12:02 GMT) Full text and rfc822 format available.

Acknowledgement sent to rixed <at> happyleptic.org:
New bug report received and forwarded. Copy sent to bug-guile <at> gnu.org. (Mon, 30 Jan 2012 10:12:02 GMT) Full text and rfc822 format available.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: rixed <at> happyleptic.org
To: bug-guile <at> gnu.org
Subject: compiling pattern matching for (or ...) takes forever
Date: Mon, 30 Jan 2012 11:10:36 +0100
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.




Information forwarded to bug-guile <at> gnu.org:
bug#10651; Package guile. (Mon, 21 May 2012 20:53:01 GMT) Full text and rfc822 format available.

Message #8 received at 10651 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Israelsson Tampe <stefan.itampe <at> gmail.com>
To: 10651 <at> debbugs.gnu.org, foof <at> synthcode.com
Subject: There should be a fix to this bug
Date: Mon, 21 May 2012 22:51:09 +0200
[Message part 1 (text/plain, inline)]
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
[Message part 2 (text/html, inline)]

Reply sent to ludo <at> gnu.org (Ludovic Courtès):
You have taken responsibility. (Fri, 08 Jun 2012 10:48:02 GMT) Full text and rfc822 format available.

Notification sent to rixed <at> happyleptic.org:
bug acknowledged by developer. (Fri, 08 Jun 2012 10:48:02 GMT) Full text and rfc822 format available.

Message #13 received at 10651-done <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: Stefan Israelsson Tampe <stefan.itampe <at> gmail.com>
Cc: foof <at> synthcode.com, 10651-done <at> debbugs.gnu.org
Subject: Re: bug#10651: There should be a fix to this bug
Date: Fri, 08 Jun 2012 12:45:14 +0200
Hello!

I updated (ice-9 match) from Chibi as recommended by Stefan, and it
appears to fix the problem for me.

Thanks!

Ludo’.




bug archived. Request was from Debbugs Internal Request <help-debbugs <at> gnu.org> to internal_control <at> debbugs.gnu.org. (Fri, 06 Jul 2012 11:24:03 GMT) Full text and rfc822 format available.

This bug report was last modified 11 years and 268 days ago.

Previous Next


GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.