--- Begin Message ---
|
Subject: |
compiling pattern matching for (or ...) takes forever |
|
Date: |
Mon, 30 Jan 2012 11:10:36 +0100 |
|
User-agent: |
Mutt/1.5.20 (2009-06-14) |
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.
--- End Message ---
--- Begin Message ---
|
Subject: |
Re: bug#10651: There should be a fix to this bug |
|
Date: |
Fri, 08 Jun 2012 12:45:14 +0200 |
|
User-agent: |
Gnus/5.130005 (Ma Gnus v0.5) Emacs/24.0.93 (gnu/linux) |
Hello!
I updated (ice-9 match) from Chibi as recommended by Stefan, and it
appears to fix the problem for me.
Thanks!
Ludo’.
--- End Message ---