GNU bug report logs -
#10651
compiling pattern matching for (or ...) takes forever
Previous Next
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.
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):
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):
[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):
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.